Khóa luận Giải pháp sắp xếp chuỗi gen sử dụng cây hậu tố

Position Second Position Third Position T C A G T Phe Ser Tyr Cys T Phe Ser Tyr Cys C Leu Ser Stop Stop A Leu Ser Stop Trp G C Leu Pro His Arg T Leu Pro His Arg C Leu Pro Gln Arg A Leu Pro Gln Arg G A Ile Thr Asn Ser T Ile Thr Asn Ser C Ile Thr Lys Arg A Met Thr Lys Arg G G Val Ala Asp Gly T Val Ala Asp Gly C Val Ala Glu Gly A Val Ala Glu Gly G Mỗi amino axid bao gồm một nguyên tử Cacbon trung tâm (Cα), một nhóm amino (NH2), một nguyên tử Hidro, một nhóm COOH và một gốc Ri liên kết trực tiếp với nguyên tử Cα. Gốc Ri là đặc trưng cho từng loại amino axid khác nhau. Hình 7: Liên kết peptit giữa các amino axid[13] Protein bao gồm bốn mức độ tổ chức: Cấu trúc bậc 1 là trình tự sắp xếp các axit amin trong chuỗi polypeptid, cấu trúc bậc 2 phát sinh từ sự uốn các thành phần của chuỗi polypeptid thành những cấu trúc đều đặn trong không gian( dạng xoắn α(alpha helix) hay lớp mỏng β(Beta sheets)). Cấu trúc bậc 3 quy định sự kết hợp các chuỗi xoắn hay lớp mỏng đó thành hình dạng ba chiều trong không gian. Cấu trúc bậc 4 là sự tổ chức nhiều chuỗi polypeptid thành một phân tử protein. DNA, RNA và quá trình tổng hợp protein Tổng hợp protein là quá trình tạo ra proteins dựa trên thông tin được mã hóa trong gen( là các đoạn mã đặc biệt của DNA có chức năng điều khiển cấu trúc và hoạt động của tế bào, là đơn vị chức năng của sự di truyền) gồm ba giai đoạn chính: (1) Transcription (phiên mã) (2) Splicing (ghép mã) (3) Translation (dịch mã)[1] có thể được mô tả như hình dưới Hình 8: Quá trình tổng hợp protein[1] Chương 2: Sắp xếp hai chuỗi sinh học Các chuỗi sinh học có thể được hiểu là dạng biểu diễn tuyến tính của các đại phân tử sinh học như axid nucleic (DNA, RNA) hay protein…Trong một chuỗi sinh học, các đơn phân của đại phân tử sinh học được ký hiệu bởi các chữ cái đại diện tương ứng. Như vậy, một chuỗi sinh học sẽ bao gồm một tập các chữ cái đại diện cho các phần tử đơn phân tương ứng. Chẳng hạn, đối với chuỗi sinh học của axid nucleic sẽ là một dãy các kí tự A,T,G,C xen kẽ lẫn nhau, đối với chuỗi sinh học của protein sẽ bao gồm 20 kí tự tương ứng với 20 loại axid amin khác nhau. Do DNA hay Protein đều có cấu trúc đa phân được cấu thành từ một số lượng rất lớn đơn phân, chính vì vậy các chuỗi sinh học cũng có kích thước rất lớn, thông thường cỡ hàng triệu phần tử. Đây chính là nguồn gốc của sự bùng nổ dữ liệu trong Tin Sinh Học. Hầu hết mọi người tin rằng sở dĩ các sinh vật có cùng tổ tiên trở nên khác nhau là do trải qua 1 quá trình tiến hóa. Tiến hóa là một quá trình mà kết quả của nó là sự thay đổi các đặc tính được thừa kế qua nhiều thế hệ. Bởi các thay đổi có khả năng được thừa kế nên các nhà khoa học tổng kết rằng phải có một vài thay đổi trong gen của các sinh vật này tương ứng với mỗi sự thay đổi tiến hóa. Trong thực nghiệm các nhà sinh học đã so sánh gen của hai sinh vật để hiểu rõ hơn về mối quan hệ di truyền và liên kết tiến hóa giữa 2 sinh vật. Điều này cho thấy rằng hai loài càng gần nhau càng có nhiều cặp gen chung. Ví dụ dưới đây về loài người và chuột sẽ cho ta một vài hình dung về điều này Bảng 5: Số cặp gen chung giữa người và chuột[22] Bởi lý do trên chúng ta phải tìm ra phương pháp so sánh bộ gen của hai loài và rút ra tất cả các cặp gen chung được bảo tồn của chúng. Để giải quyết vấn đề này chúng ta sẽ làm quen với việc so sánh 2 chuỗi sinh học. Giới thiệu về so sánh 2 chuỗi sinh học Việc nghiên cứu dựa trên phân tích các chuỗi sinh học đơn lẻ có nhiều hạn chế trong việc đưa ra các kết quả theo ý muốn đặc biệt không thể đánh giá mối tương quan giữa các chuỗi sinh học hay chính là mối quan hệ di truyền giữa loài này với loài khác. Chính vì vậy người ta đã đi đến phân tích trên hai hay nhiều chuối sinh học khác nhau. Có nhiều lý giải cho việc so sánh chuỗi này. Trước hết, thuyết tiến hoá cho rằng các chuỗi gen có thể đều xuất phát từ các chuỗi di truyền ban đầu. Do đó việc theo dõi lịch sử tiến hoá của những đột biến và các biến đổi tiến hoá khác là một công việc hết sức thú vị. Sự so sánh về các chuỗi sinh học trong trường hợp này được hiểu là sự so sánh dựa vào tiêu chí tiến hoá. Ví dụ, số lượng đột biến, chèn và xoá các thành phần cần thiết để biến đổi một chuỗi DNA thành 1 chuỗi khác là sự tính toán phản ánh mối quan hệ tiến hoá.  Nói cách khác, 1 phép so sánh có thể thực tế hơn khi mà người ta không nhằm vào 1 sự tái lập cụ thể quá trình tiến hoá của các sự kiện mà tập trung vào các đoạn xác định của nguồn gốc chung có thể lần lượt trùng hợp với các đoạn cấu trúc hoặc chức năng tương tự. Theo quan điểm này, các đặc tính vật lý của axit amin đóng vai trò quan trọng hơn trong nghiên cứu về tiến hoá. Biểu đồ điểm Biểu đồ điểm là phương pháp lâu đời nhất để so sánh các chuỗi (do Maizel và Lenk đưa ra). Một biểu đồ điểm là sự biểu thị các điểm tương đồng giữa 2 chuỗi sinh học. Biểu đồ gồm 2 trục, mỗi trục biểu thị một trong 2 chuỗi được so sánh. Một cửa sổ có độ dài cố định, theo một tiêu chí, là khi cho 2 chuỗi trượt trên các trục tương ứng, tại mỗi vị trí của chúng, các điểm(đường chéo ngắn) được tạo ra khi có sự giống nhau giữa các cặp phần tử trong 2 chuỗi tại vị trí đó. Vì vậy, nếu hai chuỗi giống nhau trên toàn bộ chiều dài, thì một đường chéo chính sẽ được tạo ra gồm tập hợp các điểm. Ngược lại, nếu 2 chuỗi chỉ tương tự nhau ở các đoạn bộ phận, thì một đường chéo kéo dài sẽ được tạo ra trên biểu đồ. Hình 10 đưa ra một ví dụ về biểu đồ điểm. Ở đây, chuỗi alpha Hemoglobin được so sánh với chuỗi beta hemoglobin ở người. Ở đây độ dài của ô được đặt là 31, các điểm tương xứng và không tương xứng được gán các giá trị tương ứng +5 đến -4. Các giá trị màu xám của biểu đồ sắp xếp theo sự tương đồng của 2 ô. Chúng ta có thể dễ dàng nhận thấy một đường chéo chính ở giữa được thể hiện rõ nét và các đường chéo mờ ở 2 bên, điều này cho thấy 2 chuỗi được so sánh là tương tự nhau trên toàn bộ chiều dài. Hình 10: Biểu đồ điểm của 2 chuỗi DNA: chuỗi alpha của hemoglobin ở người được quy định là trục hoành, còn trục tung là chuỗi beta . Hình được vẽ bởi công cụ dotter.[23]  Biểu đồ điểm là một phương pháp hữu hiệu để so sánh 2 chuỗi. Tuy nhiên đó không phải là phương pháp phân tích hiệu quả nhất. Dựa vào biểu đồ điểm chúng ta có thể đánh giá ngay 2 chuỗi được so sánh là tương tự trên toàn bộ chiều dài hay chỉ tương tự trên một đoạn đoạn cục bộ. Sự tương tự cục bộ có thể hiểu là sự tồn tại của các vùng trên hai chuỗi có sự tương tự nhau. Biểu đồ điểm sẽ chỉ ra tất cả các tương tự cục bổ tương ứng với những đường chéo nhỏ song song nhau ở hai bên đường chéo chính. Phương pháp này thể hiện một cách rất trực quan và dễ hiểu, thích hợp với những đánh giá mang tính chất định tính. Sắp xếp 2 chuỗi sinh học Sắp xếp chuỗi là sự sắp xếp một chuỗi ở trên một chuỗi khác nơi các phần tử nằm tại một vị trí được coi là có cùng nguồn gốc tiến hoá. Nếu các phần tử giống nhau cùng xuất hiện ở cả 2 chuỗi thì vị trí này được bảo tồn trong tiến hoá. Nếu các phần tử đó khác nhau, người ta cho rằng 2 chuỗi đó xuất phát từ cùng 1 phần tử ban đầu. Các chuỗi tương đồng có thể khác nhau về độ dài được giải thích bằng các thao tác chèn hay xoá trong các chuỗi sinh học. Thay vì đánh giá 2 chuỗi tương tự nhau một cách định tính như trong biểu đồ điểm chỉ ra, chúng ta có đánh giá một cách định lượng sự tương tự đó. Nói cách khác là chúng ta sẽ lượng tử hóa sự giống nhau giữa hai chuỗi nhằm đưa ra một kết quả đánh giá chính xác nhất. Để làm được việc này biểu đồ điểm rõ ràng không thể là một giải pháp thích hợp, thay vào đó chúng ta phải tính được giá trị biểu diễn độ giống nhau giữa 2 chuỗi đó dựa trên giá trị điểm số của từng cặp phần tử tương ứng nhau trong sắp xếp. Đối với sắp xếp các chuỗi DNA, chúng ta phải gán một giá trị điểm số cho tất cả các cặp có thể {A,A}, {T,T}, {A,G}, {C,G}… Còn trong trường hợp các chuỗi axid amin, có tới 20 loại axid amin khác nhau, chính vì vậy người ta thường biểu diễn điểm số của tất cả các cặp dưới dạng một ma trận điểm số. Đây là một ma trận 2 chiều trong đó mỗi một phần tử biểu diễn điểm số của một cặp 2 phần tử axid admin tương ứng. Giá trị điểm số có thể nhận các giá trị được qui định dựa trên những kinh nghiệm trong sinh học. Một điều dĩ nhiên là các cặp giống nhau {A,A},{M,M} sẽ có điểm số cao hơn so với các cặp không giống nhau {A,M},{K,V}…Có một số ma trận loại này đã được lập sẵn ra để sử dụng chung, có thể kể đến như: DayHoff, hay bộ ma trận trọng số BLOSUM… Dựa vào đây ta có thể tính điểm số cho sự giống nhau trên toàn chuỗi sinh học, đó là nền tảng cho các phương pháp so sánh chuỗi về sau này. Một trong những phương pháp đó gọi là sắp xếp chuỗi sinh học. Sắp xếp chuỗi sử dụng các phương pháp đối sánh 2 chuối sinh học với nhau để thể hiện sự tương đồng giữa chúng. Bằng cách gán thêm các khoảng trống(được biểu diễn bởi dấu ‘-‘) vào các vị trí nhất định trên mỗi chuỗi để tạo ra hai chuỗi được sắp xếp có sự tương ứng các cặp phần tử khác với ban đầu mà vẫn giữ được thứ tự các phần tử trên từng chuỗi. Chẳng hạn với hai chuỗi ban đầu BANANA và ANANAS ta có thể đưa ra một sắp xếp như sau: BANANA- -ANANAS Ký hiệu “-” dùng để biểu thị thao tác chèn hoặc xoá bởi vì chèn trong chuỗi này tương đương một sự bỏ trống trong một chuỗi khác, hiện tượng này gọi là “indel”, viết tắt của ‘insert’ và ‘delete’. Ta xét một ví dụ khác về sắp xếp chuỗi như dưới đây: B--KETBALL BASKE-BAL- Trong sắp xếp trên chúng ta cũng chỉ có thể đánh giá một cách định tính về sự tương đồng giữa 2 chuỗi, để có thể đưa ra đánh giá chính xác người ta đã sử dụng. phương pháp gán giá trị (điểm số) cho các cặp chữ được đối chiếu. Chẳng hạn đối với cặp chữ giống nhau sẽ gán cho một điểm số là một số dương (tùy theo từng cặp chữ cái), với các cặp không khớp nhau sẽ được gán điểm số âm, còn lại các cặp có một vế bị thiếu (indel) sẽ được cho một giá trị điểm số thấp. Sau đó tính tổng điểm số trên các cặp chữ cái sẽ cho ta điểm số của phương pháp trên. Việc tìm ra cách sắp để có thể đạt được điểm số tối đa sẽ là phương án sắp xếp tối ưu nhất. Như vậy, có thể thấy rằng chúng ta đã đưa bài toán trong sinh học về một bài toán có thể biểu diễn trong tin học. Bằng việc xây dựng các hàm tính điểm số, hàm trừ điểm số cho các vị trí trống và sử dụng các thuật toán trong tin học ta có thể giải quyết được bài toán trên. Một phương pháp cơ bản, dễ thấy là quét hết các khả năng để tìm trường hợp cho kết quả tốt nhất. Cách này chỉ dùng được khi kích thước các chuỗi là nhỏ. Phương pháp qui hoạch động sẽ cho kết quả khả quan hơn về thời gian tính toán và đã được áp dụng trong hầu hết trong các bài toán sắp xếp chuỗi sinh học. Tuy nhiên, một vấn đề rất đáng cân nhắc là việc xây dựng các hàm khoảng cách, hàm khoảng trống như thế nào là phù hợp nhất. Hàm khoảng cách sẽ xác định các giá trị âm của các chữ cặp khác nhau hoặc chỗ trống, sau đó cực tiểu hóa khoảng cách này. Hàm tương tự sẽ gán giá trị cao cho các cặp giống nhau và giá trị thấp của cho chỗ trống, sau đó cực tiểu hóa điểm. Việc này hoàn toàn là do cân nhắc dựa trên sự hiểu biết tổng quát về thế giới sinh học phân tử cũng như trên cơ sở toán học. Năm 1981, Smith và Waterman lần đầu tiên đã áp dụng thuật toán trên toàn chiều dài của chuỗi sinh học và đã thu được kết quả rất khả quan. Về sau này, phương pháp trên không ngừng được cải tiến về nội dung và cách thức thực hiện. Về vấn đề cân nhắc cho điểm số đối với các cặp chữ khớp nhau hay các cặp chữ không khớp nhau, chúng ta có thể dễ dàng thấy được sự khác biệt ngay trong bản thân chúng. Chẳng hạn, nếu một cặp Tryptophanes (T) giống nhau sẽ được đánh giá là quan trọng hơn so với cặp Analines (A). Đối với các axid amin, một ma trận điểm đối xứng sẽ được tạo ra để gán giá trị điểm số cho từng cặp tương ứng. Một trong những ma trận rất nổi tiếng là ma trận DayHoff ra đời năm 1978 mang tên người xây dựng nên nó. Một số ma trận khác được xây dựng gần đây hơn như các ma trận BLOSUM hay ma trận của Gonnet. Vấn đề còn lại lúc này là phải tìm ra một hàm đánh điểm số phù hợp cho các khoảng trống trên chuỗi. Trong thuật toán của Smith và Waterman đã không có một yêu cầu nào cụ thể trên các dãy khoảng trống có chiều dài khác nhau, nghĩa là nó coi một dãy các khoảng trống liên tiếp như là tổng của các khoảng trống đơn lẻ. Điều này có thể gây ra sự không chính xác trong cấu trúc tổng thể bởi người ta quan niệm rằng sự xuất hiện khoảng trống đầu tiên sẽ khác với các khoảng trống liền sau nó. Quan điểm này phù hợp với các qui luật tự nhiên và sinh học và đã được các nhà nghiên cứu xây dựng thành công thức dạng g(k) = a+b(k). Trong đó g là hàm khoảng trống, k là số khoảng trống kế tiếp, a và b là các hằng số. Việc xây dựng được các hàm khoảng trống và ma trận cặp điểm cùng với phương pháp qui hoạch động đã làm nền tảng để giải quyết bài toán sắp xếp chuỗi. Có rất nhiều thuật toán cài đặt cụ thể, ta sẽ làm quen với thuật toán sắp xếp loại I. Thuật toán sắp xếp 2 chuỗi sinh học Giới thiệu về thuật toán sắp xếp loại I Chúng ta sẽ làm quen với thuật toán dùng để so sánh 2 chuỗi, dựa vào quy hoạch động. Ngoài ra, còn đề cập tới các hàm trống, hàm tính điểm và khoảng cách. Đó là cách tiếp cận đối với sắp xếp 2 chuỗi sinh học bằng phương pháp sắp xếp loại 1, phương pháp này áp dụng kỹ thuật qui hoạch động một khá cách hiệu quả. Xét ví dụ sắp xếp 2 chuỗi sau: "RDISLVKNAGI" và "RNILVSDAKNVGI" R D I S L V - - - K N A G I  R N I - L V S D A K N V G I Các dấu “-” biểu thị khoảng trống trong chuỗi (phần chèn hay xoá ). Trật tự xuất hiện chữ cái trong sắp xếp giống nhau ở các chuỗi tương tự. Hai chữ cái in trong cùng cột gọi là cặp tương ứng. Một loại sắp xếp khác có thể thay thế cho 3 cặp đầu có thể là . Sắp xếp loại I không cho phép các chỗ trống liền kề trong chuỗi đối diện. Sắp xếp loại I có thể được biểu thị như 1 chuỗi các cặp chữ cái liên tục không ảnh hưởng đến trật tự của các chữ cái trong chuỗi. Ít nhất một trong số các chuỗi, không có chữ cái nào bị bỏ sót khi chuyển sang cặp tiếp theo. Ví dụ trên đây được coi là sắp xếp loại I được biểu thị bằng việc liệt kê các cặp số liệu đối với các cặp chữ cái. ( (1,1), (2,2), (3,3), (5,4), (6,5), (7,9), (8,10), (9,11), (10,12), (11,13)) . Trong ví dụ (5,4) có nghĩa là chữ cái thứ 5 của chuỗi đầu tiên tương ứng với chữ cái thứ 4 của chuỗi thứ 2. Cách trình bày này sẽ được chọn để xác định sắp xếp I. Trong 20 axit amin, các cặp chữ cái giống nhau không xảy ra thường xuyên như ở DNA. Vì vậy, sắp xếp trọng số đã được phát triển dựa trên thuộc tính giá trị của mỗi cặp axit amin phù hợp với nhau. Sắp xếp này do M. Dayhoff đưa ra dựa trên tần suất trao đổi giữa các axit amin. Ma trận thuộc tính 20 x 20 này xuất phát từ các giá trị dương khác nhau (sắp xếp từ +2 đến +17) với các giá trị từ -8 đến +7 cho các cặp chữ cái khác nhau. Điểm của một sắp xếp được tạo nên bởi trọng số của các cặp tương ứng trong sắp xếp trừ đi điểm phạt đối với mọi chỗ trống. Nói chung, điểm phạt chỗ trống sẽ là một hàm về chiều dài của chỗ trống. Ví dụ trên đây về số điểm bằng ma trận Dayhoff sẽ là:  Ý nghĩa đằng sau công thức tính điểm này là cách sắp xếp tối ưu hoá, điểm này có thể là cách biểu thị tốt nhất sự tương đồng về sinh học giữa hai chuỗi. Tìm ra cách sắp xếp tối ưu như vậy là nhiệm vụ chính của việc so sánh chuỗi. Thuật toán sắp xếp loại I dựa trên việc coi quá trình tìm sắp xếp tối ưu như là bài toán tìm đường đi trong một ma trận đồ thị mà trục tung và trục hoành sẽ biểu diễn 2 chuỗi theo thứ tự ban đầu của chúng. Tại mỗi điểm là giao nhau của 2 chữ cái trên 2 chuỗi thể hiện một cặp được ghép với nhau. Khi đó, mỗi một sắp xếp sẽ được biểu diễn như một đường đi trong ma trận đồ thị nói trên. Ta có thể hình dung một cách trực quan về thuật toán sắp xếp loại I dưới đây: Hình 11: Sắp xếp loại I[23] Sắp xếp loại I Cho là bảng các chữ cái giới hạn và s=(si) với i=1…|s| (|s| : số phần tử, hay lực lượng của s) và t = (ti) i=1…|t| là các phần tử xác định bởi các chữ cái trong . Định nghĩa 1 [23]: Một tập có thứ tự của các cặp (xi,yi)i=1…N,(xi,yi) {1,...,|s|}x{1,…,|t|} với x1=1Vy1=1 và xN=|s|VyN=|t| là sắp xếp loại 1 nếu: min(xi+1-xi,yi+1-yi) =1, i=1,…N-1 (1) Định nghĩa 2 [23]: Cho , là hàm khoảng trống, và là một hàm trọng số trên một cặp chữ cái trong 2 chuỗi sinh học cần so sánh, điểm số s của sắp xếp loại 1 được định nghĩa là: (2) với: (3) Nếu trong một trường hợp sắp xếp mà không bắt đầu với cặp (1,1) và không kết thúc với cặp (|s|,|t|) thì sẽ có các khoảng trống bên trái, hoặc phải của sắp xếp, chúng được gọi chung là các khoảng trống đầu cuối. Trong sắp xếp thông thường người ta không tính đến việc trừ điểm số đối với các khoảng trống đầu cuối và coi một trong 2 chuỗi như là được so sánh tương ứng với một phần của chuỗi còn lại. Nếu ta xét đến việc trừ điểm số đối với các khoảng trống đầu cuối thì hàm điểm số sẽ có dạng như sau: (4) Một hàm phạt đối với khoảng trống sẽ có dạng g(n)=a+b*(n-2) với a>b. Còn hàm trọng số thông thường đối chiếu với giá trị cho trong một ma trận trọng số, điển hình là ma trận trọng số DayHoff. Bài toán sắp xếp 2 chuỗi sinh học có thể chuyển về tìm một sắp xếp mà cho ta điểm số tối đa trong tất cả các cách sắp xếp. Thuật toán sắp xếp loại I được mô tả như một đường đi trong đồ thị định hướng loại 1 trong đó các điểm của đồ thị là tích hữu hướng {1,…,|s|} x {1,…,|t|} U {(0,0), (|s|+1,||t|+1)}. Hai điểm sau được coi là nguồn xuất phát và đích cần phải đến. Từ điểm (0,0) có thể đi tới bất kì điểm (i,j) nào thỏa mãn i=1 V j=1 và từ bất kì điểm nào có dạng (|s|,j) hay (i,|t|) đều có thể đi đến (|s|+1,|t| + 1). Nói chung mọi đường đi trong đồ thị phải thoả mãn điều kiện là số bước đi ở một trong hai hướng phải =1 hay là từ điểm (i,j) chỉ có thể đi đến được (i+1,j+k) hoặc (i+k,j+1) với k>1 và i+k < |s|+1, j+k < |t|+1. Trừ trường hợp các đường đi từ nguồn hay đến đích, tất cả các đường đi còn lại trong đồ thị e((xi,yi),(xj,yj)) sẽ được gán một trọng số như sau: (5) Trọng số cho các đường đi từ điểm nguồn hay đến điểm đích tùy thuộc vào việc ta có xét đến trừ điểm số đối với các khoảng trống bắt đầu và kết thúc hay không. Nếu có xét đến, một đường đi từ (0,0) đến (i,j) sẽ được gán trọng số là w(i,j) - G((0,0),(i,j)) và mọi đường đi đến (|s+1|,|t+1|) sẽ được gán một trọng số là –G((i,j),(|s+1|,|t+1|)). Theo nguyên tắc trên sẽ có một sự tương ứng 1-1 giữa sắp xếp loại I và đường đi trong đồ thị định hướng loại 1. Một đường đi trong đồ thị định hướng được tạo thành bởi các điểm tương ứng với một cặp chữ trên hai chuỗi sinh học. Điểm số của đồ đường đi trong đồ thị chính là điểm số của trường hợp sắp xếp trên. Bời vậy, một thuật toán chuẩn để tìm một đường đi tối ưu trong đồ thị định hướng không đối xứng với trọng số được gắn vào các cạnh khi áp dụng vào đồ thị loại 1 cũng cho ta một sắp xếp loại I tối ưu. Chúng ta sẽ xét thuật toán để tìm đường đi tối ưu này trong trường hợp không xét đến trừ điểm số đối với các khoảng trống đầu cuối. Thuật toán A-I: Trọng số của sắp xếp loại I giữa chuỗi s và t có thể được tính bằng cách lấp đầy một mảng hai chiều , L(1,j) = w(1,j) và L(i,1) = w(i,1) theo công thức: (6) Ban đầu ta sẽ lấp đầy các dòng đầu dựa và các dữ liệu có sẵn, sau đó đến dòng thứ hai dựa vào dữ liệu đã có ở dòng 1….Điểm có trọng số lớn nhất ở dòng cuối và cột cuối chính là điểm số của sắp xếp. Cách sắp xếp tương ứng với điểm số đó có thể được chỉ ra một cách chi tiết bằng phương pháp quay lui từ điểm này tới điểm mà từ đó tới nó sẽ cho giá trị lớn nhất, làm như vậy cho đến khi trở về điểm đích đầu tiên.  Chứng minh: Đỉnh vi của đồ thị được đánh số sao cho mỗi cạnh luôn trỏ tới đỉnh có chỉ số cao hơn. Độ dài lij dùng để chỉ cạnh từ vi tới vj. Và l(vi) là độ dài đường đi tối ưu từ v1 tới vi. Và: l(vi) = max (l(vj) + lij), (7) Áp dụng cách tính dựa vào bước trước với đỉnh vj. Cho các đỉnh theo thứ tự (1,1), (1,2), ..., (1, |t|), (2,1),..., (|s|, |t|). Các đỉnh trước của (i,j) là (i-k,j-1), (i-1,j-1) và (i-1,j-k). Cho đỉnh (i,j) với i=1 v j=1 đặt l(i,j) = w(sxi,tyj) và i>1^j>1 l(i - k, j - 1) + e((i - k,j - 1),(i, j)), với 2 ≤ k ≤ i – 1 l(i, j) = max l(i - 1, j - 1) + e((i - 1,j - 1),(i, j)) l(i - 1, j - k) + e((i - 1,j - k),(i, j)), với 2 ≤ k ≤ j – 1 l(i - k, j - 1) + w(si, sj) - g(k-1), với 2 ≤ k ≤ i – 1 = max l(i - 1, j - 1) + w(si, sj) l(i - 1, j - k) + w(si, sj) - g(k-1), với 2 ≤ k ≤ j – 1 l(i - k, j - 1) - g(k-1), với 2 ≤ k ≤ i – 1 = w(si, sj) + max l(i - 1, j - 1) l(i - 1, j - k) - g(k-1), với 2 ≤ k ≤ j – 1 Thuật toán trên sử dụng phương pháp qui hoạch động để lấp đầy mảng biểu diễn đồ thị. Tại mỗi điểm sau khi được lấp đầy sẽ chứa giá trị tối ưu mà từ điểm xuất phát đến nó. Như vậy, điểm cuối cùng sẽ lưu điểm số đường đi tối ưu, bằng cách áp dụng kỹ thuật quay lui ta sẽ tim được lần lượt các đỉnh mà đồ thị đi qua. Thuật toán này tương tự với thuật toán mà Needleman và Wunsch (Needleman, S.B and Wunsch, C.D J.Mol.Biol, 1970) đã đưa ra trước đó như là những người đầu tiên áp dụng phương pháp qui hoạch động vào bài toán sắp xếp chuỗi. Tại mỗi bước tiến, chương trình sẽ duyệt qua mỗi đỉnh một lần. Tại mỗi bước này, có xấp xỉ i+j giá trị được kiểm tra, trong đó i+j < |s|+|t|. Bởi vậy, khi n là số nguyên biểu diễn chiều dài của chuỗi lớn hơn trong hai chuỗi sinh học, các phép toán sẽ được thực hiện với độ phức tạp O(n3). Quá trình quay lui sẽ có độ phức tạp |s|+|t|. Chương 3: Phương pháp sắp xếp 2 chuỗi sinh học dùng Maximal unique match(MUM) Giới thiệu về MUM Mặc dù cặp gen được bảo tồn hiếm khi cùng chứa toàn bộ một chuỗi, chúng thường có chung nhiều xâu con ngắn và một số trong đó là duy nhất trong cặp gen. Xét ví dụ dưới đây, Cho 2 chuỗi S và T: S = at ga ctc a gctac t ggtcagctatt acttaccgc # T = at gt ctc t gctac ggtcagctatt c acttaccgc $ Dễ thấy 2 chuỗi S và T có chung khá nhiều xâu con: at, ctc, gctac, ggtcagctatt và acttaccgc. Trong 5 xâu con chung đó chỉ có ac không phải là duy nhất. Nó xuất hiện hơn một làn ở cả hai chuỗi. Bạn có thể chỉ ra rằng a, c, t và g cũng là xâu con chung của S và T. Tuy nhiên chúng không phải là lớn nhất vì chúng có trong ít nhất một xâu con chung dài hơn. Chúng ta chỉ xét tới những xâu con chung có độ dài lớn nhất Nhiệm vụ của chúng ta là tìm ra tất cả các xâu con chung duy nhất và có độ dài lớn nhất của hai cặp gen A và B cho trước. Mỗi xâu con chung này còn được gọi là MUM. Với hầu hết các cặp gen được bảo tồn tồn tại ít nhất một MUMs duy nhất. Vì vậy MUM có hai đặc tính: Nó xuất hiện duy nhất một lần trong cả hai cặp gen Nó không nằm trong bất kì một MUMs dài hơn (hay nó có chiều dài tối đa). Chúng ta có định nghĩa về MUM như sau: Định nghĩa 2 [22]: MUM là một xâu con chung giữa 2 gen có độ dài lớn hơn một độ dài d xác định và nó có độ dài lớn nhất, nghĩa là không thể mở rộng nó bằng cách thêm vào bất kí kí tự nào và cuối cùng MUM là duy nhất trong cả hai xâu. Với ví dụ trên giả sử d = 3, Chuỗi S và T có 4 MUMs: ctc, gctac, ggtcagctatt, acttaccgc. Xâu con ac không phải là MUM vì có độ dài bé hơn d và nó không phải là duy nhất trong cả hai chuỗi. Ta xét một ví dụ khác S = a cg a t # T = cg t a $ Cho d = 1, chúng ta sẽ có 2 MUMs: cg và t. a không phải là MUM bởi vì nó xuất hiện 2 lần ở xâu S. Một số phương pháp tìm MUM Phương pháp Brute-force: Ý tưởng của phương pháp này là trước tiên ta sẽ tìm tất cả các xâu con chung của hai chuỗi, sau đó với mỗi xâu con sẽ so sánh độ dài của nó với độ dài d cho trước và cuối cùng là xem chúng có phải là duy nhất trong cả hai chuỗi không, thuật toán được trình bày dưới đây[22]: Input: cho hai chuỗi gen S[1…m1] và T[1…m2] for every position i in S for every position i in S Find the longest common prefix P of S[i…m1] and T[j…m2] If |P| >= d and P is unique in both genomes P is MUM Output: Các MUM của hai chuỗi gen Phương pháp này có độ phức tạp về thời gian là O(m1m2), khá chậm. Phương pháp k-mers: Một phương pháp khác để tìm MUM giữa hai chuỗi x và y là tìm ra k-mers chung, k-mer đơn giản là một xâu con với độ dài k. Dưới đây là thuật toán[22]: Kí hiệu một k-mer của x là (w; 0; i) với w = xi…xi+k-1 Kí hiệu một k-mer của y là (z; 1; j) với z = yj…yj+k-1 Sắp xếp chúng theo thứ tự từ điển Đưa ra tất cả các MUM có độ dài k giữa x và y Xét cặp x, y dưới đây với k=3: x = cabbc y = bbcab 3-mers của x: (cab, 0, 1), (abb, 0, 2), (bbc, 0, 3) 3-mers của y: (bbc, 1, 1), (bca, 1, 2), (cab, 1, 3) Xắp xếp chúng: (abb, 0, 2), (bbc, 0, 3), (bbc, 1, 1), (bca, 1, 2), (cab, 0, 1), (cab, 1, 3) Đưa ra các MUM: (bbc, 0, 3), (bbc, 1, 1) và (cab, 0, 1), (cab, 1, 3) Với L là số matches. Trong trường hợp xấu nhất thời gian chạy thuật toán có độ phức tạp là O(mn) khi ta có O(m) k-mers của x và O(n) k-mers của y. Điểm yếu của thuật toán này là các MUM tìm được chưa hẳn đã là tối đa, vì thế ta lại phải tốn thêm thời gian O(L) để chọn lọc các MUM thực sự. Một giải pháp được đặt ra là tăng k và giảm L và vì thế thời gian chạy được giảm đi, tuy nhiên ta lại bỏ sót một số MUM (bé hơn k nhưng vẫn có ý nghĩa). Bởi vậy, khi đặt một giá trị cho k, chúng ta đang tạo ra một sự phù hợp giữa c