LUẬN VĂN:SẮP HÀNG ĐA CHUỖI

Chia sẻ: Lan Lan | Ngày: | Loại File: PDF | Số trang:38

Thêm vào BST

Báo xấu

82
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mỗi một thuật toán, một chương trình sắp hàng đa chuỗi đều có những ưu điểm và nhược điểm riêng của mình. Vì thế cần tìm cách tối ưu từng ưu điểm của từng phương pháp, và hạn chế nhược điểm của chúng.Khóa luận sẽ trình bày về các phương pháp sắp hàng đa chuỗi được ứng dụng rộng rãi hiện nay đồng thời phân tích và đưa ra một giải pháp nhằm phát huy tối đa ưu điểm cũng như hạn chế tối thiểu nhược điểm của từng phương pháp....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: LUẬN VĂN:SẮP HÀNG ĐA CHUỖI

TRƯỜNG …………………. KHOA………………………. ----- ----- Báo cáo tốt nghiệp Đề tài: SẮP HÀNG ĐA CHUỖI
Lời cảm ơn Tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới Tiến sỹ Lê Sỹ Vinh. Thầy là người trực tiếp giao đề tài và tận tình hướng dẫn cũng như giúp đỡ tôi trong quá trình thực hiện luận văn này. Đồng thời tôi xin chân thành cảm ơn thầy Từ Minh Phương, hiện đang công tác tại SUlab công ty FPT. Thầy đã tạo điều kiện và đưa ra những lời khuyên bổ ích cho tôi trong thời gian cuối thực hiện khóa luận. Hà Nội tháng 05 năm 2010 Sinh viên Nguyễn Hà Anh Tuấn
Tóm tắt nội dung Sắp hàng đa chuỗi là một bài toán tin sinh học phổ biến trên thế giới hiện nay, mặc dù đã có rất nhiều phương pháp tiếp cận cũng như thuật toán được đưa ra để giải quyết bài toán này tuy nhiên chưa thuật toán nào cho kết quả tới khả năng tối ưu. Trong nội dung của khóa luận, tôi xin được khái quát tổng quan bài toán sắp hàng đa chuỗi cũng như một số thuật toán tiêu biểu trên thế giới hiện nay. Đồng thời tôi cũng xin đưa ra một số ý kiến của mình cũng như giải pháp nhằm tăng tính ổn định và tin cậy của các thuật toán này.
Mục lục Chương 1: Giới thiệu chung..............................................................................................1 Chương 2: Các phương pháp phổ biến hiện nay...............................................................6 1.MUSCLE ...................................................................................................................6 2.MAFFT ......................................................................................................................8 3. ProbCons .................................................................................................................10 Chương 3: EM-Coffee (Extended M-Coffee).................................................................12 1.Đặt trọng số khi kết hợp các thuật toán....................................................................12 2.MUMSA...................................................................................................................13 3.T-Coffee, M-Coffee .................................................................................................14 3.1. T-Coffee ...........................................................................................................14 3.2. M-Coffee ..........................................................................................................20 4.EM-Coffee ...............................................................................................................21 Chương 4: Kết quả thực nghiệm .....................................................................................23 1. Bộ dữ liệu BAliBASE.............................................................................................23 Chương 5: Kết luận .........................................................................................................31 Tài liệu tham khảo...........................................................................................................32
Chương 1: Giới thiệu chung Phần giới thiệu về sắp hàng đa chuỗi( multiple sequence alignment) dưới đây được viết một phần dựa trên luận văn tiến sĩ của thầy Lê Sỹ Vinh[31] và quyển sách Inferring Phylogenies của giáo sư Joseph Felsenstein[30]. Theo học thuyết tiến hóa của Darwin[1], tất cả các sinh vật trên trái đất đều có cùng một tổ tiên chung. Theo thời gian và quá trình tiến hóa của các sinh vật, các ADN của chúng dần đổi khác biệt với tổ tiên. Các ADN biến đổi từ cùng một nguồn gốc được gọi chung là các ADN tương đồng(homology). Và tổng quát hơn nữa, một chuỗi ADN tiến hóa từ cùng một tổ tiên là chuỗi tương đồng. Những sự biến đổi của các chuỗi ADN có thể nhiều hay ít, có thể xảy ra đồng thời hay phân tán tuy nhiên chúng vẫn giữ lại một số thông tin có trong chuỗi ADN của tổ tiên. Theo nhận định của các nhà khoa học, việc biến đổi ADN của các sinh vật đều thông qua 3 phép biến đổi sau: − Phép chèn, đưa thêm một ADN vào chuỗi. − Phép xóa, xóa đi 1 ADN trong chuỗi. − Phép thay thế, thay thế ADN này bằng một ADN khác. Trong khi các phép thay thế chỉ làm thay đổi những vị trí nhất định của một chuỗi ADN chứ không làm thay đổi độ dài của chuỗi ADN đó, một phép chèn hay một phép xóa lại làm cho số lượng ADN của chuỗi nhiều hơn một ADN hoặc ít đi một ADN. Tuy nhiên, chúng ta không thể xác định được sự khác biệt giữa phép chèn và phép xóa nên 2 phép này được gộp lại thành một phép biến đổi và gọi tên chung cho chúng là phép chèn/xóa. Bảng 1 là ví dụ về các phép biến đổi giữa 2 chuỗi ADN s1 và s2. Trong ví dụ này ta có thể thấy tại vị trí thứ 2 và vị trí thứ 3 có thực hiện phép biến đổi thay thế ( C – A và A – G) đồng thời tại vị trí thứ 7 xác định được một phép chèn/xóa. Tại các vị trí còn lại ta có thể thấy sự tương đồng giữa 2 chuỗi s1 và s2, chẳng hạn tại vị trí 1 cả 2 chuỗi s1 và s2 đều là A hay tại vị trí 4 là G. Page | 1
Bảng 1: Ví dụ về các phép biến đổi 1 2 3 4 5 6 7 8 9 s1 A G C T G T C A G s2 A G C T - G T A G Thông thường đặc điểm của sinh vật dựa vào cấu chúc chuỗi ADN của chúng, như vậy khi xuất hiện một phép biến đổi bên trong chuỗi ADN thì đặc điểm của sinh vật sẽ bị biến đổi. Sự thay đổi này có thể là những dấu hiệu bên ngoài giúp chúng ta có thể xác định điểm khác biệt hoặc chỉ là sự biến đổi bên trong sinh vật và cần tập trung nghiên cứu mới nhận ra sự biến đổi này. Khi sự biến đổi là quá lớn, rất có thể một loài sinh vật hoàn toàn mới sẽ xuất hiện. Chính vì vậy sự xuất hiện của các chương trình sắp hàng đa chuỗi hay bắt cặp đa chuỗi (multiple sequence alignment) là rất quan trọng trong lĩnh vực sinh học nói chung và sinh học phân tử nói riêng (molecular biology). Dựa vào kết quả của các chương trình này các nhà khoa học có thể đi tới những kết luận đối với các chuỗi ADN và axit amin tương ứng như sau: − Xác định và chẩn đoán được chức năng mà đoạn ADN/axit amin này thực hiện trong cơ thể sinh vật. − Xác định các vị trí biến đổi liên quan tới các bệnh di truyền để từ đó tìm kiếm phương pháp phát hiện và cứu chữa − Phân tích các phép biến đổi để xây dựng quá trình tiến hóa giữa các loài sinh vật. − Xác định và chẩn đoán các cấu trúc bậc cao cho ADN/axit amin mới giải mã được. Các phép biến đổi thường làm cho chuỗi ADN(có thể là protein) tương đồng bị biến đổi cả về kích thước lẫn nội dung của nó. Khi đó ta có thể định nghĩa một cách đơn giản của việc sắp hàng đa chuỗi là quá trình chèn thêm các dấu cách (biểu diễn một phép chèn/xóa trong quá trình tiến hóa) vào các chuỗi sao cho tất cả các ADN(axit Page | 2
amin) ở cùng một vị trí thì tương đồng với nhau. Tuy dữ liệu đầu vào của một chương trình sắp hàng đa chuỗi thường là có độ dài các chuỗi khác nhau, nhưng kết quả của chúng luôn cho ra những chuỗi ADN(protein) có độ dài bằng nhau, kết quả này còn được gọi là “đa chuỗi thẳng hàng”. Chẳng hạn ta có 4 chuỗi cần được thực hiện sắp hàng đa chuỗi như sau Bảng 2: Ví dụ của sắp hàng đa chuỗi s1 = G C T G A T A T A G C s2 = G G G T G A T T A G C Input s3 = G C T A T C G C s4 = A G C G G A A C A C C s1’ = – G C T G A T A T A G C s2’ = G G G T G A T – T A G C Kết quả s3’ = – G C T – A T – –CGC s4’ = A G C G G A – A C A C C Như chúng ta nhận thấy độ dài của các chuỗi s1, s2 và s4 là khác so với độ dài của chuỗi s3. Tuy nhiên kết quả thu được thì độ dài của cả 4 chuỗi là tương đương nhau. Ngoài ra chúng ta cũng có thể dễ dàng phát hiện được những phép biến đổi được thực hiện khi nhìn vào kết quả của chương trình sắp hàng đa chuỗi. Chẳng hạn có một phép chèn/xóa tại vị trí thứ nhất của s1’ và s3’ hay một phép thay thế C bởi G tại s2’. Tương tự như vậy là các phép chèn xóa hay các phép thay thế còn lại. Một điều có thể nhận ra trong sắp hàng đa chuỗi đó chính là tồn tại nhiều cách chèn dấu cách khác nhau và khi đó ta có thể tạo ra nhiều kết quả khác nhau. Việc tồn tại nhiều phép biến đổi khác nhau này có thể được cải thiện bằng cách sử dụng mắt thường và dựa trên kinh nghiệm để bắt cặp. Tuy nhiên, cách thức này chỉ có thể áp dụng được với những chuỗi ADN ngắn vào số lượng chuỗi bắt cặp nhỏ. Đối với những Page | 3
trường hợp bắt cặp hàng trăm chuỗi và độ dài mỗi chuỗi lớn thì việc làm thủ công trên trờ nên không khả thi và mất tính hiệu quả ban đầu của nó. Để giải quyết bài toán này người ta đã đưa ra rất nhiều phương pháp tính toán và nghiên cứu nhằm mục đích tối ưu hóa bắt cặp đa chỗi. Các phương pháp này thường tiến hành sao cho nó tiến tới sấp xỉ một hàm mục tiêu cho trước. Hàm mục tiêu đơn giản nhất được đưa ra là cực tiểu hóa các phép biến đổi tồn tại giữa các cặp chuỗi sau khi sau khi đã bắt cặp xong. Tuy nhiên vẫn còn một vấn đề khá nan giải đó là việc rất khó để bắt cặp những chuỗi có sự liên hệ lẫn nhau thấp một cách chính xác mà không cần sự chỉnh sửa bằng tay dựa trên kinh nghiệm của các nhà khoa học. Đề giải quyết vấn đề này có rất nhiều phương án đã được đưa ra trong vòng 4 tới 5 thập kỉ qua. Năm 1970 Needleman và Wunsch[2] đã đưa ra một thuật toán để so sánh chuỗi ADN dựa trên quy hoạch động, thuật toán này giúp ta có khả năng bắt cặp 2 chuỗi ADN (pairwise alignment) và thu được một kết quả khá tốt. Mặc dù vậy việc mở rộng bài toán này lên thành sắp hàng đa chuỗi (multiple sequence alignment) lại là một câu chuyện hoàn toàn khác bởi độ phức tạp của thuật toán là Nk (trong đó k là số lượng chuỗi dùng để bắt cặp và N là độ dài của chuỗi). Sau đó một số phương pháp mới cũng được đưa ra, trong đó có phương pháp progessive[3] hay phương pháp chuẩn hóa lặp (iterative refinement)[4-5]. Các phương pháp này đều dựa trên các biến thể của quy hoạch động 2 chiều (two- dimentional dynamic programing) và giảm được độ phức tạp của bài toán xuống còn N2. Việc giảm được độ phức tạp của bài toán xuống còn N2 là một thành tựu rất lớn nhưng độ chính xác của sắp hàng đa chuỗi còn dựa trên chính hệ thống tính điểm của mỗi chương trình, hệ thống tính điểm càng chính xác thì độ chính xác của kết quả nó đưa ra càng cao. Nói tới hệ thống tính điểm này ta không thể không nhắc tới ClustalW, một phương pháp được phát triển bởi Thompson và các đồng nghiệp năm 1994[6]. ClustalW sử dụng cách tính toán hệ thống điểm phạt (điểm phạt cho các phép biến đổi) và hàm mục tiêu của ClustalW là làm nhỏ nhất có thể điểm phạt này. Đây chính là một trong những phương pháp đi tiên phong cho hệ thống điểm phạt ngày nay. Hiện tại, các phương pháp được phát triển nhằm mục đích giải quyết bài toán sắp hàng đa chuỗi ngày càng xuất hiện nhiều hơn. Mỗi thuật toán đều có khả năng chính xác và tính tin cậy khác nhau. Những phương pháp nổi bật nổi bật bởi độ chính xác của chúng có thể kể đến như: T-Coffee[7], MAFFT[8,14], PROBCONS[9], và MUSCLE[10]. Trong MAFFT nổi lên như một chương trình rất được ưa chuộng hiện Page | 4
nay nhờ vào tốc độ thực thi và độ tin cậy của thuật toán. Việc đánh giá độ tin cậy của một phương pháp hay thuật toán cần phải dựa trên một bộ dữ liệu chuẩn chứa đồng thời các chuỗi chưa được sắp hàng và dữ liệu chuẩn để đối sánh. Những bộ dữ liệu này thường là những bộ dữ liệu được trích chọn trong quá trình nghiên cứu của các nhà khoa học hoặc được các nhà khoa học sử dụng kinh nghiệm của mình để xác định. Kết luận: Mặc dù việc sắp hàng đa chuỗi đã được nghiên cứu và phát triển từ rất lâu nhưng nó vẫn là một bài toán cần được nghiên cứu và tiếp tục phát triển để giải quyết được các nhu cầu hiện tại cũng như trong tương lai gần. Mỗi phương pháp sắp hàng đa chuỗi đều có những ưu và nhược điểm riêng của nó và quan trọng hơn nữa là mỗi chỉ phù hợp với những kiểu dữ liệu nhất định. Chính vì vậy việc tập trung nghiên cứu nhằm mục đích cải thiện độ chính xác của các phương pháp này là điều rất cần thiết. Page | 5
Chương 2: Các phương pháp phổ biến hiện nay Sau đây, tôi xin trình bày tổng quan một số chương trình sắp hàng đa chuỗi tiêu biểu hiện nay trên thế giới. Các chương trình này đều đã khẳng định được khả năng của mình và được áp dụng khá nhiều trong lĩnh vực sinh học nói chung và sinh học phân tử nói riêng. 1.MUSCLE MUSCLE là chương trình sắp hàng đa chuỗi được phát triển bởi David Edgar năm 2004. Hiện tại MUSCLE đang được sử dụng khá rộng rãi bởi độ chính xác khá cao và tốc độ của chương trình có thể hỗ trợ người sử dụng với bộ dữ liệu lớn tới hàng ngàn chuỗi. Về mặt thuật toán, ta có thể chia thuật toán của MUSCLE ra làm ba bước chính đó là bước bắt cặp nháp, cải tiến, và bước chuẩn hóa lại. Ngoài ra tác giả đưa ra hai hệ thống tính điểm khác nhau đó là khoảng cách K-mers[11] cho bộ chuỗi chưa được bắt cặp với nhau và ma trận KIMURA[12] cho các chuỗi đã bắt cặp rồi. Hình 1: khoảng cách K-mers[10] K-mer được định nghĩa là một chuỗi các amino axit đứng liền kề nhau có độ dài bằng K. Đối với những sequence có liên hệ với nhau thì số lượng K-mer sẽ nhiều hơn các cặp sequence bình thường. Khoảng cách K-mers được định nghĩa dựa trên định nghĩa của K-mer khi ta sử dụng nó trong chuỗi kí tự. Phương pháp sử dụng K-mer này không đòi hỏi các chuỗi đã được align hay chưa và thu được kết quả với tốc độ khá Page | 6
cao. Hình 2 là một ví dụ cho khoảng cách K-mers, với K = 3 ta thu được tại phần trên K-mer là 6 và phần dưới K-mer là 13. Tương tự như vậy với K=4 tại phần trên K-mer là 4 và dưới là 9. Khoảng cách KIMURA[12] được định nghĩa là khoảng cách giữa 2 chuỗi đã được bắt cặp và được tính theo công thức: 1 11 DK 2 p = − ln(1 − 2 P − Q) − ln( Q) 2 42 Trong đó, P là số lượng transition đếm được giữa 2 chuỗi và Q là số lượng transversion đếm được giữa 2 chuỗi. Transition là dạng thay thế A – G hay C – T hoặc ngược lại. Trong khi đó Transversion là dạng thay thế A – C, T hay các trường hợp tương tự như vậy. Ngoài ra, còn một điểm đáng lưu ý ở MUSCLE đó là bắt cặp profiles (profile alignment). Đây là một dạng bắt cặp tương tự như bắp cặp sóng đôi (pairwise alignment) nhưng mỗi profile không còn là một chuỗi như bắt cặp sóng đôi mà là nhiều chuỗi được ghép vào. Hình 2: Các bước chạy của MUSCLE[10] Ở các bước một và hai của MUSCLE lần lượt sử dụng 2 hệ thống điểm là khoảng cách K-mers và ma trận KIMURA để dựng cây nhị phân dựa trên thuật toán Page | 7
UPGMA[13]. Mỗi nút trên cây được ghép lại bởi 2 profile và tạo ra một profile mới cho. Cứ làm như vậy cho tới gốc cuối cùng thì ta sẽ đạt được một alignment. Và đến đây coi như chúng ta đã hoàn thành việc sắp hàng đa chuỗi nếu người sử dụng không muốn chạy bước chuẩn hóa. Bước cuối cùng của MUSCLE là bước chuẩn hóa (refinement). Dựa trên cây được dựng sau hai bước trên bước này sẽ cắt bỏ một cạnh từ cây đó sau đó bắt cặp lại 2 profiles và sử dụng điểm sum of pair để tính toán nếu có cải thiện với điểm của kết quả trên thì giữ lại, nếu không thì bỏ đi. Điểm sum-of-pair là điểm để xác định khả năng bắt cặp giữa 2 chuỗi sẽ được nói tới sau trong phần kết quả thực nghiệm sử dụng BAliBASE. Về độ phức tạp của thuật toán, nếu ta chỉ chạy 2 bước đầu thì độ phức tạp thuật toán sẽ là O(N2 + NL + L2). Nếu có thêm bước chuẩn hóa lại thì độ phức tạp thuật toán là O(N3L). trong đó N là số chuỗi cần bắt cặp, L là độ dài của chuỗi. Dựa theo kết quả thực nghiệm sẽ nêu ở phần sau của tài liệu này, MUSCLE có tốc độ chạy rất tốt và có thể chạy được với bộ dữ liệu lớn, cỡ từ 1 tới vài nghìn cuỗi. 2.MAFFT MAFFT là viết tắt của Multiple Alignment using Fast Fourier Transform được đưa ra năm 2002 bởi một nhóm các tác giả người Nhật. Tại thời điểm hiện tại, MAFFT được đánh giá rất cao nhờ vào độ chính xác gần như là cao nhất trên những chuỗi full- length của bộ dữ liệu chuẩn BAliBASE đồng thời MAFFT cũng yêu cầu một thời gian để chạy tương đối dễ chịu với người sử dụng. Khác với các phương pháp khác, các tác giả của MAFFT sử dụng giả thuyết tần suất sự thay thế các amino axit phụ thộc lớn vào các thuộc tính lý hóa của nó, đặc biệt là 2 thuộc tính khối lượng(volume) và độ phân cực(polarity) [13]. Dựa trên 2 thuộc tính này người ta dựng nên 2 giá trị chuẩn hóa v(a) và p(a) tượng trưng lần lượt cho khối lượng và độ phân cực. Tiếp theo mối quan hệ giữa 2 chuỗi amino axit sẽ được tính toán bằng cách sử dụng biến đổi Fourier. Ý nghĩa chính của biến đổi Fourier ở bước này chính là giúp giảm độ phức tạp của thuật toán. Sau bước này ta sẽ thu được các giá trị c(k)[14] – tượng trưng cho mối quan hệ giữa 2 chuỗi, ở đây k là độ trễ của chuỗi 2 so với chuỗi 1 như hình 3. Page | 8
Hình 3: độ trễ k và tìm kiếm đoạn tương đồng[14] Từ hình vẽ ta có thể thấy nếu k bằng 2 thì chuỗi 1 sẽ đi trước chuỗi 2 khi bắt cặp với nhau để tìm đoạn tương đồng. Mặt khác bằng thực nghiệm cho thấy, c(k) càng lớn thì khả năng tìm được những đoạn tương đồng khi sắp xếp 2 chuỗi theo độ trễ k càng lớn. Và từ những đoạn tương đồng tìm được người ta xây dựng một ma trận tương đồng để từ đó có thể bắt cặp 2 chuỗi amino axit này lại với nhau (cách xác định đoạn tương đồng và xây dựng ma trận tương đồng có thể đọc thêm ở tài liệu tham khảo số 14). Hình 4 biểu diễn một ma trận tương đồng Hình 4, ma trận tương đồng[14] Trong trường hợp này, đường bắt cặp được sử dụng là S(5,5) -> S(4,4) -> S(2,3) -> S(1,1) vì giá trị của S(2,3) lớn hơn giá trị của S(3,2). Page | 9
Cũng giống như MUSCLE, để mở rộng bài toán từ bắt cặp sóng đôi lên sắp hàng đa chuỗi, MAFFT sử dụng bắt cặp profile – profile. Bằng cách tính toán lại c(k) cho mỗi cặp profile và xác định đoạn tương đồng cũng như ma trận tương đồng ta có thể hoàn thành các bước sắp hàng đa chuỗi của option đơn giản nhất MAFFT là FFT-Ns1. Các option còn lại của MAFFT hầu hết đều sử dụng kết quả của FFT-Ns1 và sử dụng các bước chuẩn hóa để thu được kết quả tốt hơn FFT-Ns1. Theo phiên bản mới nhất của MAFFT, chúng ta có thể có nhiều option để chọn lựa như FFT-Ns2, FFT-Nsi, Li-Nsi, Ei-Nsi, …. Mỗi option có thể đáp ứng cho người dùng những yêu cầu nhất định. Chẳng hạn đối với option FFT-Ns2 tốc độ bắt cặp là rất cao, nhanh hơn cả MUSCLE tuy nhiên lại thu được kết quả không tốt lắm. Để thu được kết quả tốt hơn, ta có thể sử dụng option Li-nsi của MAFFT. Option này tuy chạy chậm hơn MUSCLE nhưng lại có kết quả đáng tin cậy hơn. 3. ProbCons ProbCons có tên đầy đủ là Probabilistic consistency-based multiple sequence alignment. Đây là phần mềm sắp hàng đa chuỗi được tác giả gốc Việt Nam là Chương Đỗ, và các đồng nghiệp phát triển và lần đầu được công bố năm 2005. Cũng như MUSCLE và MAFFT, ProbCons cũng là một chương trình rất thông dụng và được sử dụng rộng rãi hiện nay. ProbCons có khả năng trả về một kết quả chính xác cao tuy nhiên về mặt tốc độ ProbCons không thể được như MAFFT và MUSCLE. Về mặt thuật toán, ProbCons đưa mô hình Markov ẩn vào thuật toán progressive. Điểm khác biệt chính giữa ProbCons và các phương án tiếp cận khác đó chính là việc sử dụng ước lượng cực đại về độ chuẩn xác chứ không phải là cách sử dụng mô hình Viterbi[15], mặt khác ProbCons còn sử dụng ước lượng các phép biến đổi để bảo toàn thông tin của các chuỗi trong khi bắt cặp. Ngoài ra ProbCons sử dụng ma trận chuyển đổi chuẩn BLOSUM62[16] và điểm phạt phát sinh khi thêm dấu cách trong việc bắt cặp cũng được huấn luyện bởi ước lượng cực đại. Để thực hiện sắp hàng đa chuỗi, ProbCons cần phải thực hiện qua ít nhất là 5 bước(thuật toán chi tiết có thể đọc thêm ở tài liệu tham khảo số 9). Các bước này sẽ được trình bày một cách tổng quát nhất như sau: Page | 10
− Bước 1: Xây dựng ma trận xác suất Pxy(i,j) trong đó x,y là 2 chuỗi bất kì cần phải bắt cặp, i và j lần lượt là vị trí của kí tự trong 2 chuỗi x,y. − Bước 2: Tính toán kì vọng của độ chính xác khi bắt cặp 2 chuỗi x, y. Với mỗi cặp chuỗi x, y xác định một kết quả bắt cặp 2 chuỗi này sao cho kì vọng của cách bắt cặp này là cao nhất. − Bước 3: Ước lượng tính vững chắc của các bước chuyển đổi. Ở bước này, ma trận xây dựng ở bước 1 sẽ được tính toán và chuẩn hóa lại. − Bước 4: Xây dựng cây cho các chuỗi cần bắt cặp bằng thuật toán phân cụm, trọng số sẽ được tính toán dựa trên giá trị tính ở bước 2. − Bước 5: Dựa vào cây đã dựng ở bước 4, ta tiến hành bắt cặp cho cả bộ dữ liệu. Ngoài ra còn có thể có thêm bước chuẩn hóa lại kết quả, bước chuẩn hóa này sẽ cắt kết quả làm 2 phần và tiến hành bắt cặp lại. Số lần bước chuẩn hóa thực hiện là không xác định trước. Kết quả của Proncons là rất đáng tin cậy, nó sẽ được thể hiện trong phần thực nghiệm sẽ được trình bày ở phần sau bản báo cáo này. Tuy nhiên, về mặt tốc độ ProbCons không thể so sánh với 2 thuật toán trên và có lẽ chỉ nên chạy ProbCons với những dữ liệu không vượt quá 50 chuỗi và có độ dài tối đa của chuỗi nằm trong khoảng 500 axit amin. Page | 11
Chương 3: EM-Coffee (Extended M-Coffee) 1.Đặt trọng số khi kết hợp các thuật toán Ba thuật toán đã được nêu ra trong chương 2 chính là ba phương pháp được sử dụng phổ biến nhất cho việc sắp hàng đa chuỗi hiện nay trên thế giới. Mỗi phương pháp đều có những ưu điểm và nhược điểm riêng của nó. Tuy nhiên, điều cần quan tâm nhất đó chính là mỗi phương pháp đưa ra kết quả tốt nhất với những bộ dữ liệu nhất định. Chúng không cho về kết quả ổn định và đáng tin cậy trong mọi trường hợp có thể xảy ra trong bộ dữ liệu. Việc đánh giá ba thuật toán sẽ được tóm tắt lại trong bảng sau: Bảng 3: nhận định về các thuật toán. Thuật toán Ưu điểm Nhược điểm Tốc độ cao, có thể chạy với bộ dữ Độ chính xác của muscle với Muscle liệu lớn các bộ dữ liệu chuẩn so với các thuật toán khác là không cao Độ chính xác và tính tin cậy của Tốc độ chậm, chỉ có thể chạy ProbCons ProbCons là lớn với những bộ dữ liệu nhỏ Có độ chính xác khá cao, nhiều Với những option có độ chính MAFFT option ứng với những bộ dữ liệu xác cao thì tốc độ không tốt, riêng đồng thời tốc độ chấp nhận và ngược lại. được Chính vì việc mỗi thuật toán đều có độ chính xác trên những bộ dữ liệu nhất định trong khi những dữ liệu cần phải được bắt cặp là rất đa dạng. Ta cần tìm cách kết hợp kết quả các thuật toán trên với nhau để đưa ra một kết quả mới với hi vọng kết quả này có được độ tin cậy trên càng nhiều bộ dữ liệu càng tốt. Page | 12
Vậy bài toán của chúng ta hiện nay chính là tìm cách sử dụng ba thuật toán trên cũng như kết quả của nó trong mỗi lần sắp hàng đa chuỗi để tạo ra một kết quả mới có độ chính xác với kì vọng là cao hơn và có khả năng ổn định trên nhiều bộ dữ liệu chứ không còn như từng thuật toán chỉ chạy tốt với một số bộ dữ liệu. Tất nhiên mỗi thuật toán đều có độ chính xác của riêng nó và không thể coi kết quả của mỗi thuật toán trước khi đưa vào sử dụng làm thư viện là như nhau, mỗi thuật toán cần có trọng số nhất định. Trọng số này không thể dùng mắt thường hoặc kinh nghiệm để đánh giá do số lượng chuỗi và độ dài mỗi chuỗi trong sắp hàng đa chuỗi không phải là nhỏ. 2.MUMSA Vào năm 2005, trên thế giới xuất hiện rất nhiều chương trình sắp hàng đa chuỗi, điều này làm cho người sử dụng không thể xác định chính xác nên chọn chương trình nào phù hợp cho bộ dữ liệu của mình. Việc nhận định độ tin cậy của một chương trình sắp hàng đa chuỗi trở thành vấn đề cấp bách. Trong bối cảnh đó Timo Lassmann và Erik Sonnhammer đã cho ra đời MUMSA[17], chương trình hỗ trợ người dùng xác định được tính tin cậy của một đa chuỗi thẳng hàng mà không cần đến bộ dữ liệu tham khảo. Thuật toán của MUMSA dựa trên việc so sánh các đa chuỗi thẳng hàng. Họ đưa ra một khái niệm đó là cặp amino axit được bắt cặp tương ứng(pair-of-aligned residues). Chẳng hạn ta có một đa chuỗi thẳng hàng, trong đó amino axit thứ 3 trong chuỗi 1 được bắt cặp tương ứng với amino axit thứ 5 trong chuỗi 7 thì 2 amino axit này được gọi là một cặp amino axit được bắt cặp tương ứng. Như vậy, từ đa chuỗi thẳng hàng là input đầu vào của chương trình ta có thể tạo ra rất nhiều cặp trên. Chú ý rằng chúng ta cần chia nhỏ đa chuỗi đầu vào thành các phần nhỏ nhất có thể nhưng vẫn giữ đủ thông tin của đa chuỗi đó để giảm thiểu số lượng các cặp amino axit được bắt cặp tương ứng. Để so sánh độ tin cậy của một đa chỗi thẳng hàng trong nhiều đa chuỗi khác, thuật toán của MUMSA tiến hành tính điểm cho mỗi cặp amino axit được bắt cặp tương ứng để biểu diễn số lần xuất hiện của chúng trong những đa chuỗi thẳng hàng. Xét một cặp α bất kì, ta gọi n(α) là số lần xuất hiện của α trong (m – 1) đa chuỗi thẳng hàng còn lại đang được so sánh. Một cặp xuất hiện trong tất cả mọi đa chuỗi sẽ cho ta giá trị n(α) = (m – 1) điều này đồng nghĩa với xác suất cặp α xảy ra trên thực tế là lớn, Page | 13
và ngược lại một cặp không xuất hiện trong các chuỗi còn lại cho ta kết quả n(α) = 0 hay xác suất cặp α xảy ra trên thực tế là rất nhỏ. Như vậy với một đa chuỗi A ban đầu, ta có thể dùng giá trị trên cho tất cả các cặp amino axit được bắt cặp tương ứng của nó để tính toán độ tin cậy của một đa chuỗi thẳng hàng. Độ tin cậy của một đa chuỗi thẳng hàng được tính theo công thức: ∑ {n(α ) | α ∈ A} MOS(A) = A ( m − 1) (|A| số lượng cặp amino axit tương ứng trong A) MOS là viết tắt của multiple overlap score và có giá trị biến thiên trong đoạn [0,1]. Khi MOS(A) = 1 tức là mọi cặp amino axit tương ứng xảy ra trong A đều xảy ra trong (m – 1) đa chuỗi khác và ngược lại khi MOS(A) = 0 là khi không có cặp amino axit nào xuất hiện trong A lại xuất hiện trong các đa chuỗi được so sánh với A. Bằng những kết quả thực nghiệm của mình, các tác giả của MUMSA đã chỉ ra rằng những đa chuỗi thẳng hàng có điểm MOS cao từ 0.8 trở lên là những đa chuỗi đáng tin cậy và có thể sử dụng chúng cho những công việc khác. Ngoài ra, những đa chuỗi chỉ có điểm MOS thấp hơn 0.5 thì có thể có nhiều phần được bắt cặp không chính xác và cần được chỉnh sửa lại. Chẳng hạn với bộ dữ liệu BAliBASE, nếu như kết quả của các chương trình sắp hàng đa chuỗi có điểm MOS nhỏ hơn 0.5 thì những đa chuỗi mà thuật toán của nó không thể nhận biết được những đoạn tương đồng đã được bắt cặp một cách thủ công của bộ dữ liệu này. Như vậy, mục đích chính của MUMSA là tính toán độ chính xác hay tính tin cậy của những đa chuỗi thẳng hàng khi mang chúng so sánh với nhau. Từ kết quả của MUMSA nếu áp dụng vào giả thuyết sử dụng thư viện từ MAFFT, MUSCLE, và ProbCons ở trên ta sẽ thu được độ tin cậy của từng thuật toán. Đồng thời từ đó ta cũng có thể xác định được trọng số của các thuật toán trên dựa vào kết quả của MUMSA 3.T-Coffee, M-Coffee 3.1. T-Coffee T-Coffee – Tree-based Consistency Objective Function for alignment Evaluation là phần mềm được công bố và phát triển và năm 2000. Vào thời điểm được công bố, Page | 14
T-Coffee chính là phần mềm có độ chính xác cao nhất trong các chương trình sắp hàng đa chuỗi đồng thời tốc độ chạy của T-Coffee là chấp nhận được. T-Coffee có 2 tính năng chính. Tính năng thứ nhất là nó sử dụng hệ thống dữ liệu thư viện được sinh ra từ bắt cặp sóng đôi các cặp chuỗi để tạo ra đa chuỗi thẳng hàng cuối cùng. Tính năng thứ 2 là tối ưu hóa, tính năng này có nhiệm vụ chọn đa chuỗi thẳng hàng phù hợp nhất với bộ dữ liệu được đưa vào. Như vậy nhìn chung, T-Coffee sử dụng thuật toán progressive cùng với khả năng cập nhật thư viện dữ liệu của mình thông qua mỗi bước thực hiện của nó. Điều này cho phép T-Coffee lấy được sự đơn giản và tốc độ của thuật toán progressive đồng thời giảm thiểu lỗi xảy ra trong quá trình bắt cặp. Hình 5 ở bên dưới là một lỗi thường xảy ra trong quá trình bắt cặp sử dụng thuật toán progressive thông thường, trong hình ta có thể thấy sự bắt cặp lỗi của từ CAT ở chuỗi B. Hình 5: lỗi xảy ra trong bắt cặp sử dụng thuật toán progressive thông thường[7] Về mặt thuật toán, T-Coffee có 5 bước chính như hình 6 đó là tạo thư viện chính, đặt trọng số cho thư viện chính, kết hợp thư viện, mở rộng thư viện, bắt cặp sử dụng thuật toán progressive. Chúng ta sẽ đi vào từng bước của thuật toán này. Page | 15
Hình 6: các bước thuật toán của T – Coffee[7] Page | 16