Báo cáo 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 Page | 1 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 | 2 Bảng 1: Ví dụ về các phép biến đổi 1 2 3 4 5 6 7 8 9 s1 A C A G C T G G T s2 A A G G C T - G T 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 | 3 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 s3 = G C T A T C G C Input 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 s3’ = – G C T – A T – – C G C Kết quả 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 | 4 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 | 5 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 | 6 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 | 7 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: 2 1 1 1ln(1 2 ) ln( ) 2 4 2K p D P Q Q= − − − − 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 | 8 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 | 9 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 | 10 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 | 11 − 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 | 12 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 Muscle Tốc độ cao, có thể chạy với bộ dữ liệu lớn Độ chính xác của muscle với các bộ dữ liệu chuẩn so với các thuật toán khác là không cao ProbCons Độ chính xác và tính tin cậy của ProbCons là lớn Tốc độ chậm, chỉ có thể chạy với những bộ dữ liệu nhỏ MAFFT Có độ chính xác khá cao, nhiều option ứng với những bộ dữ liệu riêng đồng thời tốc độ chấp nhận được Với những option có độ chính xác cao thì tốc độ không tốt, và ngược lại. 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 | 13 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 | 14 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: MOS(A) = { } ( ) ( ) | 1 n A A m α α ∈ − ∑ (|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 | 15 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 | 16 Hình 6: các bước thuật toán của T – Coffee[7] Page | 17 3.1.1. Tạo thư viện chính Thư viện chính của T-Coffee là tập hợp các cặp chuỗi thu được nhờ vào quá trình bắt cặp sóng đôi giữa các chuỗi nằm trong đầu vào. Như vậy với đầu vào có N chuỗi ta sẽ có N(N – 1)/2 cặp trong thư viện. Trong thư viện mỗi cặp có thể có liên kết với nhau và một điều cần chú ý đó là mỗi cặp đều có tính quan trọng khác nhau bởi một số có thể đưa ra những sự bắt cặp chính xác cho kết quả sau này. Việc xác định cặp nào quan trọng, cặp nào không sẽ được tính toán ở bước 2. Có 2 cách được sử dụng để tạo thư viện chính của T-Coffee. Cách thứ nhất là sử dụng thuật toán ClustalW[6] để bắt cặp 2 chuỗi tổng quát, có độ dài mặc định. Và cách thứ hai là sử dụng Lalign để bắt cặp khi 2 chuỗi được chia thành các đoạn nhỏ, có độ tương đồng cao (Lalign là chương trình nằm trong bộ chương trình FASTA và xây dựng dựa theo thuật toán Sim được đưa ra bởi Huang và Miller năm 1991 [18]). 3.1.2. Đặt trọng số cho thư viện chính Trọng số sẽ được gán cho tất cả các cặp có trong bộ thư viện chính. Ý nghĩa chính của trọng số này chính là biểu diễn cho sự giống nhau của các cặp. Thuật toán sử dụng tính đồng nhất (identity) của chuỗi, tính đồng nhất của chuỗi được đưa ra bởi Sander và Schneider năm 1991[19] và đã được chứng minh khi bắt cặp những chuỗi có tính đồng nhất lớn hơn 30%. Đồng thời trọng số này cũng thể hiện được tính đúng đắn của mình trong một bài viết trước đó của nhóm tác giả[20]. Như vậy Mỗi cặp chuỗi được bắt cặp trong thư viện chính sẽ nhận được trọng số bằng chính độ tương đồng giữa 2 chuỗi trong nó.Chẳng hạn với ví dụ của hình 5, ta sẽ có bộ thư viện như hình 7. Hình 7: Thư viện chính cùng với trọng số[7] Page | 18 3.1.3. Kết hợp thư viện Mục tiêu của thuật toán là kết hợp bộ thư viện được tạo thành bởi cả ClustalW và Lalign về với nhau. Điều này có thể thực hiện dựa trên một ý tưởng đơn giản, nếu một cặp trong thư viện này mà được lặp lại ở thư viện kia thì có thể ghép chúng làm một với trọng số bằng tổng trọng số của cặp này trong cả 2 thư viện. Nếu không có thì chỉ cần tạo một phần tử mới cho thư viện là chính cặp đang xét. Sau khi đã ghép xong, bộ thư viện mới này chúng ta có thể đưa sang việc sắp hàng đa chuỗi bằng cách tìm kiếm đa chuỗi thẳng hàng nào thích hợp nhất với trọng số của các cặp có trong thư viện. Tuy nhiên, thuật toán lại tiếp tục cải tiến độ chuẩn xác của thông tin trong mỗi cặp bằng cách mở rộng bộ thư viện. việc mở rộng bộ thư viện này chính là bước thứ tư của thuật toán 3.1.4. Mở rộng thư viện Hình 8: Mở rộng thư viện[7] Bài toán xây dựng đa chuỗi thẳng hàng từ một bộ dữ liệu có gán trọng số là một bài toán khá nổi tiếng được đưa ra bởi Kececioglu với cái tên “maximum weight trace”[21]. Trước thời điểm T-Coffee được công bố đã có 2 thuật toán được đưa ra bởi Notredame[22] và Reinert[23], thuật toán của Notredame dựa trên giải thuật gen di truyền trong khi đó thuật toán thứ 2 của Reinert dựa trên đồ thị. Mặc dù vậy cả 2 thuật toán này đều không đáp ứng được yêu cầu. Thuật toán của Notredame là khá thực tế tuy nhiên lại đòi hỏi thời gian thực hiện quá lớn. Trong khi đó thuật toán của Reinert lại quá phức tạp và có thể xảy ra những sai sót trong quá trình tính toán. Page | 19 Cuối cùng, vấn đề trên đã được giải quyết bằng cách sử dụng thuật toán heuristic bên trong phần mở rộng thư viện của T-Coffee. Ý tưởng chung của thuật toán này là trọng số cho mỗi cặp amino axit được bắt cặp với nhau có thể biểu diễn một phần thông tin cho cả bộ dữ liệu. Để làm được việc này một cách tiếp cận mới được đưa ra như hình 8, đây là cách mở rộng thư viện từ thư viện chuẩn ví dụ của hình 7. Thuật toán dựa trên việc sự dụng mỗi cặp amino axit được bắt cặp với nhau trong thư viện và kiểm tra xem sự xuất hiện của nó trong các cặp chuỗi đã được bắt cặp khác trong thư viện chính còn lại. Với ví dụ trong hình 8, ta giả thiết rằng có 4 chuỗi cần được bắt cặp là A, B, C, và D. Chúng ta gọi A(G) là kí tự G trong GARFIELD ở chuỗi A, tương tự như vậy với B(G). Đồng thời gọi W(A(G), B(G)) là trọng số đặc trưng cho cặp này ở trong thư viện chính. Trên thực tế A(G) và B(G) được bắt cặp với nhau trong thư viện chính và ta có thể thấy trọng số của cặp này là 88 (dựa trên trọng số của cặp chuỗi A – B). Nếu bây giờ ta đưa thêm chuỗi C vào để so sánh, ta có thể thấy A(G) và C(G) được bắt cặp với nhau, đồng thời đó là C(G) và B(G). Như vậy ta có thể nói là có một sự bắt cặp giữa A(G) và B(G) thông qua C. Ta xét 2 giá trị mới đó là W1 = W(A(G), C(G)) =77 và W2 = W(B(G), C(G)) = 100. Ta đặt trọng số mà A(G) được bắt cặp với B(G) thông qua C là giá trị nhỏ nhất giữa W1 và W2, ở đây do W1 = 77 và W2 = 100 nên ta đặt lại giá trị trong thư viện là 77. Khi đưa vào trong thư viện mở rộng cặp A(G) và B(G) sẽ có trọng số là giá trị 88 ban đầu cộng với giá trị 77 mới thu được kết quả mới là 165. Việc mở rộng thư viện đòi hỏi phải xét tới tất cả các bộ ba chuỗi trong thư viện chính ban đầu. Chẳng hạn việc bắt cặp A và B thông qua D không tồn tại thông tin liên quan tới A(G) và B(G) như vậy bộ ba chuỗi này được xem là không liên quan tới việc bắt cặp A(G) và B(G), đồng thời chúng cũng không làm ảnh hưởng tới trọng số khi bắt cặp 2 amino axit này với nhau. Như vậy trọng số để bắt cặp giữa 2 amino axit sẽ là tổng tất cả các trọng số được tính theo thuật toán trên. Một khi hoàn thành tất cả các cặp amino axit trên A và B thì mỗi cặp sẽ chứa thêm thông tin từ các chuỗi C và D. Độ phức tạp lý thuyết của thuật toán này là O(N3L2), trong đó N là số chuỗi và L là độ dài trung bình của các chuỗi. Tuy nhiên điều này chỉ xảy ra với thư viện có các cặp chuỗi không liên quan gì tới nhau, trên thực nghiệm độ phức tạp thuật toán lớn nhất cũng chỉ là O(N3L). Page | 20 Trọng số sẽ là 0 nếu cặp amino axit tương ứng không xuất hiện trên thư viện, điều này sẽ xảy ra trong phần lớn các cặp amino axit trong quá trình thực hiện thuật toán. Ngược lại, nếu trọng số lớn hơn 0, nó sẽ biểu diễn tính tương đồng giữa 2 chuỗi trong một cặp ở thư viện chính. Điểm này có thể được dùng để bắt cặp 2 chuỗi bất kì từ bộ dữ liệu của chương trình sử dụng quy hoạch động[24]. 3.1.5. Bắt cặp sử dụng thật toán progressive Trong bắt cặp progressive, đầu tiên 2 chuỗi sẽ được bắt cặp với nhau để tạo ma trận khoảng cách giữa tất cả các chuỗi, ma trận này được sử dụng để xây dựng cây và từ cây đó áp dụng thuật toán neighbor-joining[25] để nhóm các chuỗi có độ tương đồng với nhau nhất thành một nhóm. 2 chuỗi có khoảng cách gần nhất sẽ được bắt cặp trước sử dụng thuật toán quy hoạch động. Chú ý rằng thuật toán quy hoạch động này sử dụng trọng số được sinh ra trong bước mở rộng thư viện. Trong quá trình bắt cặp sóng đôi này, gap sẽ được tạo ra và những gap này sẽ được cố định và không thể thay đổi về sau này (gap chính là dấu cách được thêm vào, biểu thị cho một phép chèn/xóa). Việc bắt cặp các nhóm có khoảng cách gần nhau nhất sẽ được thực hiện cho tới khi đạt tới gốc của cây. Chú ý rằng, để bắt cặp hai nhóm, điểm vẫn sẽ được lấy từ thư viện mở rộng tuy nhiên sẽ là điểm trung bình của toàn bộ cột trong trong các cặp đó. Một điều đáng lưu ý nữa ở đây đó là trong bước sử dụng quy hoạch động, các điểm phạt hay bất kì tham số nào sẽ không được sử dụng, lý do ở đây chính là khi tạo ra thư viện mở rộng các điểm phạt đó đã được tính rồi. 3.2. M-Coffee M-Coffee[26] là một dạng mở rộng của T-Coffee, mục tiêu của M-Coffee là kết hợp các đa chuỗi thẳng hàng từ các chương trình và thuật toán khác trên thế giới để tạo thành đa chuỗi thẳng hàng mới với hi vọng kết quả này tốt hơn các kết quả được sinh ra từ các thuật toán đó. Dựa trên lý thuyết của T-Coffee ta có thể thấy nếu ta thay các bước tạo thư viện chính bởi ClustalW và Lalign thành các chương trình bắt cặp trên thì ta có thể chạy T- Coffee dựa trên bộ thư viện là các cặp chuỗi được bắt cặp bởi các thuật toán khác. Chính điều này làm cho M-Coffee thu nhận được thông tin từ các thuật toán khác và Page | 21 cho ra kết quả là đa chuỗi thẳng hàng mang thông tin phù hợp với tất cả các thuật toán đó. Một điều đáng nói ở M-Coffee là thuật toán này luôn cố gắng chạy tất cả các chương trình có cài đặt trong máy tính người sử dụng. Những chương trình đó có thể là những chương trình đã xuất hiện từ rất lâu, thuật toán có thể đã lỗi thời và kết quả của nó dường như là không tốt. Việc sử dụng thư viện dựa trên các kết quả này dẫn tới có thể có những đánh giá sai sót về những thông tin lưu trữ và thời gian chạy chương trình bị kéo dài. Điều này dẫn tới khả năng về mặt tốc độ của M-Coffee là hạn chế. Tuy nhiên, T-Coffee đã đưa ra một phiên bản mở rộng của mình với tư tưởng khá giống với M-Coffee. T-Coffee sẽ nhận chuỗi đầu vào cùng với các bộ dữ liệu được đưa làm thư viện nhưng các bộ dữ liệu này sẽ được coi như ngang bằng nhau – các trọng số của các đa chuỗi tham khảo đều là 1. 4.EM-Coffee Như vậy khi đi tới bước này chúng ta đã phần nào tìm ra được hướng giải quyết chính cho vấn để được đưa ra ở phần 1 chương 3. Trọng số biểu diễn độ tin cậy của một đa chuỗi thẳng hàng được giải quyết bằng MUMSA và sau đó dùng T-Coffee để sắp hàng đa chuỗi sử dụng bộ thư viện đã được gán trọng số trên. Nhìn chung thuật toán của EM-Coffee có thể được biểu diễn như hình 9. Dựa trên các kết quả thực nghiệm của các thuật toán hiện nay, 5 phương án cho kết quả tốt nhất được lựa chọn đó là MUSCLE, ProbCons, MAFFT FFT-nsi, MAFFT Li-nsi, MAFFT Ei-nsi. Bộ thư viện của T-Coffee sẽ chính là những dữ liệu kết quả từ các thuật toán này. Về mặt trọng số, ta cần chuẩn hóa các giá trị thu được từ MUMSA. Giả sử Ta có các giá trị MOS thu được từ các đa chuỗi thẳng hàng sinh ra bởi các thuật toán lần lượt như sau: MOS(muscle), MOS(ProbCons), MOS(fftnsi), MOS(linsi), MOS(einsi). Bước chuẩn hóa đầu tiên, ta sẽ tính điểm trung bình các giá trị MOS này OS( ) 5 pi P M pi M ∈= ∑ (pi tương ứng với các thuật toán) Page | 22 Hình 9: Thuật toán EM-Coffee Bước tiếp theo, trọng số của mỗi thuật toán sẽ là giá trị thu được khi lấy điểm MOS của nó chia cho giá trị trung bình trên. OS( )Wpi M pi M = Bước này chính là đưa các giá trị trọng số về những điểm ở xung quanh 1, và có điểm trung bình của các trọng số bằng 1. Việc đưa các trọng số về những điểm xung quanh 1 cũng là một bước khá quan trọng vì khi đưa các đa chuỗi này vào làm thư viện của T-Coffee những bộ có trọng số quá nhỏ so với những đa chuỗi khác sẽ có khả năng đóng góp thông tin cao hơn nhưng không làm ảnh hưởng quá nhiều tới kết quả của EM-Coffee. Page | 23 Chương 4: Kết quả thực nghiệm 1. Bộ dữ liệu BAliBASE Như chúng ta đã biết, trên thế giới hiện tại có rất nhiều chương trình sắp hàng đa chuỗi, mặc dù input giống nhau nhưng output của mỗi chương trình đó lại không giống nhau. Ở phần trước của bài khóa luận chúng ta có nhắc tới MUMSA, thuật toán xác định độ tin cậy của một đa chuỗi thẳng hàng khi mang so sánh nó với các đa chuỗi thẳng hàng khác. Tuy nhiên, việc xác định độ tin cậy này chỉ mang tính chất tương đối, vì điểm MOS cũng chỉ được tính toán dựa trên chính những thông tin có trong đa chuỗi thẳng hàng đó và không thể đối chiếu kết quả xem liệu với điểm MOS là cao thì nó có thực sự chính xác hơn so với những kết quả khác. Chính vì vậy việc tạo ra một bộ dữ liệu chuẩn nhằm mục đích xác định xem output của chương trình nào chính xác là một vấn đề rất cấp bách. Trên thực tế hiện nay đối với những chương trình mới được công bố hay cải tiến, bước đầu tiên là họ đều sử dụng những bộ dữ liệu này để kiểm tra khả năng của chương trình mới đạt được đến đâu. Chỉ với những trường hợp sắp hàng đa chuỗi lớn và không có trong thư viện thì MUMSA mới được sử dụng tới. BAliBASE - Benchmark Alignment dataBASE[28] là một bộ dữ liệu được xây dựng bởi các nhà khoa học Julie D. Thompson, Olovier Poch và một số nhà khoa học khác. Việc xây dựng bộ dữ liệu BAliBASE hoàn toàn dựa trên những kết quả đã được kiểm chứng trước đó đồng thời bắt cặp dựa trên kinh nghiệm của chính những nhà khoa học này. Hiện nay, BAliBASE đã phát triển tới bộ dữ liệu 3.0 vào năm 2005. Trong bộ dữ liệu mới này, BAliBASE có 9 bộ dữ liệu con. Tuy nhiên, với những chương trình sắp hàng đa chuỗi hiện nay, ta chỉ dùng các bộ dữ liệu từ 1 tới 5. Một điều đáng chú ý đó là trong mỗi bộ dữ liệu của BAliBASE 3.0 đều có hai phần, 1 phần là các dữ liệu với chuỗi full-length với 2 chữ cái của tên bắt đầu bởi BB và phần còn lại vẫn là các chuỗi đó nhưng chỉ đưa ra các đoạn tương đồng có thể bắt cặp với nhau. Như vậy khi thực hiện kiểm tra kết quả của bất kì chương trình nào ta đều phải tách riêng 2 phần này. Page | 24 Dưới đây là bảng các số liệu cơ bản như số lượng và số chuỗi tổng của BAliBASE 3.0 khi so sánh với BAliBASE 2.01. Bảng 3: Số liệu BAliBASE 3.0 và BAliBASE 2.01 RV1 Version RV11 RV12 RV13 RV20 RV30 RV40 RV50 Total 2.01 27 27 28 23 12 12 12 141 Số test 3.0 38 44 N/A 41 30 49 16 218 2.01 125 119 123 487 292 150 148 1444 Số chuỗi 3.0 265 411 N/A 1896 1882 1317 483 6254 Nhìn vào bảng ta có thể thấy sự thay đổi lớn khi chuyển bộ test dữ liệu từ BAliBASE 2.01 sang BAliBASE 3.0. Ở đây ta có thể thấy bộ RV1 là bộ test với những chuỗi được coi là ngang hàng nhau với độ tương đồng của bộ RV11 là từ 0 tới 20% và độ tương đồng của bộ RV12 là từ 20 tới 40%. Bộ thứ hai là RV20 bộ này bao gồm những test giữa dòng họ và những cá thể bị biến dổi. Bộ thứ 3 là RV30, đây là bộ bao gồm những test giữa các nhánh có chung tổ tiên. Bộ thứ RV40 bao gồm những test có sự mở rộng lớn giữa các chuỗi gen. Cuối cùng là bộ RV50, bộ này gồm những test có mật độ chèn/xóa là rất cao. Ngoài ra số lượng chuỗi cũng như số lượng test của BAliBASE 3.0 là lớn hơn rất nhiều so với BAliBASE 2.01. nếu như số lượng test ở bản 2.01 chỉ là 141 thì ở 3.0 số lượng test là hơn 200. Đồng thời, tổng số chuỗi trong tất cả bộ dữ liệu của bản 3.0 là 6254, lớn hơn hẳn so với của phiên bản 2.01 với tổng số 1444 chuỗi. Như vậy có thể thấy nếu sử dụng BAliBASE 3.0 để kiểm tra kết quả của các thuật toán sắp hàng đa chuỗi khả năng ta sẽ thu được kết quả chính xác hơn so với BAliBASE 2.01. Tuy nhiên, đi kèm theo đó là thời gian đòi hỏi để mỗi thuật toán hoàn tất quá trình bắt cặp cho bộ dữ liệu BAliBASE 3.0 là lớn hơn rất nhiều so với phiên bản 2.01. BAliBASE sử dụng hai hệ số điểm để xác định độ chính xác của một đa chuỗi thẳng hàng so với kết quả mà các nhà khoa học tự tay bắt cặp. đó là điểm sum-of- Page | 25 pair(SP) và điểm total-column(TC). Điểm SP có thể được tính một cách đơn giản như sau: - Đặt s(a,b) – a,b là 2 amino axit, là điểm khỉ bắt cặp a với b. khi đó ta sẽ có giá tị của s(a,b) tương ứng là: s(a,b) = 1 nếu a và b là một amino axit s(a,b) = -1 nếu a và b khác nhau s(a,b) = -2 nếu a là gap, b không là gap hoặc ngược lại s(a,b) = 0 nếu cả a và b đều là gap. - Đặt SP(mi) là giá trị điểm ở cột i của đa chuỗi thẳng hàng, giá trị của SP(mi) được tính bằng tổng các s(a,b) trong đó a,b là các amino axit được lấy từ cột thứ i của đa chuỗi. Một ví dụ đơn giản cho việc tính toán SP(mi) được thể hiện ở bảng 4 Bảng 4: tính toán SP(mi) m1 m2 m3 m4 m5 m6 Seq1 T _ G C _ G Seq2 _ A G C T G Seq3 _ A G C _ G SP(mi) -4 -3 3 3 -4 3 Trong đó: SP(m1) = s(T, -) + s (T, -) + s (-, -) = -2 + -2 + 0 = -4. Tương tự với các điểm của cột m2, m3, m4, m5, m6. - Điểm SP của cả chuỗi được tính theo công thức ( ) ( ) m M SP M SP m ∈ = ∑ như vậy, với kết quả của ví dụ trên, SP(M) = -2; Page | 26 - Kết quả của điểm SP(M) với đa chuỗi thẳng hàng đầu vào sẽ được so sánh với với SP(R) của bộ dữ liệu tham khảo có sẵn trong BAliBASE và điểm SP cuối cùng sẽ là tỉ lệ phần trăm khi chia SP(M) cho SP(R). Đây chính là điểm sum-of-pair của BAliBASE. Điểm TC còn đơn giản hơn điểm sum of pair rất nhiều. Điểm TC chính là tỉ lệ số cột mà đa chuỗi đầu vào chứa các amino axit giống hệt so với thư viện của BAliBASE. Với hai hệ số điểm SP và TC ta có thể xác định được phần nào độ chính xác của kết quả quá trình sắp hàng đa chuỗi với dữ liệu chuẩn ban đầu. Cần chú ý khi tính kết quả của một bộ dữ liệu con, chẳng hạn RV11. Ta tính kết quả của từng test trong RV11 và lấy kết quả trung bình cuối cùng làm kết quả của cả bộ RV11. Nhưng kết quả của toàn bộ bộ dữ liệu BAliBASE thì ta cần tính trung bình khi nhân trọng số với mỗi bộ dữ liệu con. Trọng số đó chính là số test trong bộ dữ liệu con đó. Ba bảng ở dưới đây là các bảng kết quả so sánh phương pháp áp dụng MUMSA vào M-Coffee với bộ dữ liệu BAliBASE 2.01 và BAliBASE 3.0 đối với cả những test full-length và những test chỉ xét những đoạn tương đồng với các thuật toán tiên tiến trên thế giới. Thời gian thực hiện được tính dựa trên máy tính có vi sử lý intel core 2 dual 2.4GHz, RAM 3GB. Các thuật toán sử dụng tương ứng là MUSCLE ver.3.7, MAFFT ver.6.240, ProbCons ver.1.12, T-Coffee 8.47 với các thư viện tương đương với EM-Coffee và được viết tắt là TD-Coffee. Ngoài ra bộ dữ liệu BAliBASE ko có RVS40. Chú ý rằng nếu chưa có thư viện thì thời gian chạy của EM-Coffee sẽ là tổng thời gian chạy các thuật toán. Page | 27 Bảng 5: Kết quả các thuật toán với bộ dữ liệu BAliBASE 2.01(Các chỉ số làm tròn tới 2 số sau dấu phảy) RV11 RV12 RV13 RV20 RV30 RV40 RV50 Average Program SP TC SP TC SP TC SP TC SP TC SP TC SP TC SP TC Time (s) Muscle 84.82 77.86 88.25 80.51 88.53 82.98 92.47 56.14 80.44 53.07 90.05 67.38 97.37 88.72 88.60 73.76 42 Fft-nsi 83.11 75.49 87.33 81.15 87.52 81.86 92.00 56.86 80.77 56.78 91.83 75.52 96.44 84.97 87.92 74.02 39 ProbCons 88.36 83.43 90.26 84.30 90.65 85.47 93.26 60.50 82.93 62.10 92.63 78.74 97.38 89.32 90.65 78.55 465 Li-nsi 83.37 77.00 89.76 82.99 88.34 82.22 92.66 52.96 79.42 55.56 92.94 76.15 97.77 92.89 88.80 74.72 70 Ei-nsi 83.37 77.00 89.58 82.73 88.27 82.19 92.64 52.77 79.21 54.85 95.41 83.56 97.84 91.88 88.95 75.12 76 EM-Coffee 87.08 81.15 91.03 85.01 89.68 83.79 93.24 60.33 83.05 60.67 92.56 78.61 98.49 93.78 90.45 78.13 182 TD-Coffee 87.30 81.84 90.44 93.74 89.86 84.74 93.12 59.42 83.97 63.57 91.51 75.22 97.70 91.72 90.32 77.85 182 Những giá trị được in đậm là giá trị lớn nhất trong cột đó. Page | 28 Bảng 6: kết quả các thuật toán đối với các chuỗi full-length trong BAliBASE 3.0 (Các giá trị được làm tròn tới 2 số thập phân sau dấu phảy) RV11 RV12 RV20 RV30 RV40 RV50 Average Program SP TC SP TC SP TC SP TC SP TC SP TC SP TC Time (s) Muscle 58.92 34.76 91.99 81.66 88.99 36.34 81.44 38.40 87.15 45.73 83.87 44.88 82.53 48.23 1735 Fft-nsi 61.44 39.45 90.82 79.57 90.83 37.51 83.30 49.00 89.87 54.61 86.44 52.88 84.13 52.89 690 ProbCons 66.97 41.68 94.11 85.52 91.67 40.49 84.60 54.30 90.24 52.86 89.17 56.69 86.38 55.66 30092 Li-nsi 66.19 43.79 93.46 83.39 92.70 45.10 86.79 59.33 92.61 61.51 90.25 59.06 87.22 59.27 3335 Ei-nsi 66.02 43.74 93.46 83.39 92.52 44.61 86.81 59.43 92.26 60.53 89.86 59.62 87.05 59.00 3680 EM-Coffee 68.72 44.87 93.71 84.07 92.28 43.95 86.00 58.50 91.86 58.10 89.96 60.44 87.33 58.60 6404 TD-Coffee 68.66 44.61 93.82 84.75 91.63 43.78 86.17 56.87 91.41 58.04 89.57 59.69 87.12 58.15 6404 Những giá trị được in đậm là giá trị lớn nhất trong cột đó. Page | 29 Bảng 7: Kết quả của thuật toán chỉ đối với những đoạn tương đồng trong bộ dữ liệu BAliBASE 3.0 (Các giá trị được làm tròn tới 2 chữ số thập phân sau dấu phảy) RVS11 RVS12 RVS20 RVS30 RVS40 RVS50 Average Program SP TC SP TC SP TC SP TC SP TC SP TC SP TC Time (s) Muscle 74.08 52.50 93.10 82.70 94.62 53.44 86.93 55.93 N/A N/A 87.46 49.20 87.56 60.89 279 Fft-nsi 71.63 50.61 91.86 81.82 94.00 51.22 87.84 59.80 N/A N/A 87.18 51.07 86.67 60.56 141 ProbCons 81.03 63.08 95.04 87.07 95.72 60.39 90.69 64.97 N/A N/A 90.91 60.53 90.89 68.77 7437 Li-nsi 72.17 52.21 93.90 84.52 94.52 51.66 88.83 63.5 N/A N/A 90.03 56.53 87.90 62.90 673 Ei-nsi 71.98 51.87 93.92 84.52 94.57 52.22 88.83 63.33 N/A N/A 89.93 58.60 87.86 63.12 823 EM-Coffee 77.31 57.39 94.43 85.55 95.15 56.56 89.40 63.63 N/A N/A 90.31 59.27 89.47 65.81 4668 TD-Coffee 77.12 56.66 94.49 85.95 95.11 56.24 89.49 61.57 N/A N/A 89.83 57.60 89.41 65.14 4668 Những giá trị được in đậm là giá trị lớn nhất trong cột đó. Page | 30 Chúng ta sẽ lần lượt phân tích kết quả thu được ở cả 3 bảng 5,6, và 7. Bằng việc phân tích kết quả này chúng ta sẽ nhận ra được tính đúng đắn của EM-Coffee khi sử dụng trọng số cũng như khả năng sử dụng thông tin của các đa chuỗi đầu vào để sắp hàng đa chuỗi của T-Coffee. Bảng 5 là kết quả của các chương trình với bộ dữ liệu BAliBASE 2.01. Như đã nói tới phần trên, BAliBASE 2.01 nhỏ hơn BAliBASE 3.0 rất nhiều và có thể cho kết quả không được chính xác như BAliBASE 3.0. Tuy nhiên nếu xét trên phương diện là một bộ dữ liệu chuẩn thì BAliBASE 2.01 vẫn khá đáng tin cậy. Nhìn vào bảng ta thấy rằng khi chạy bộ dữ liệu BAliBASE 2.01 thì ProbCons có kết quả trung bình là cao nhất. Tiếp theo đó ta có thể kể tới EM-Coffee nhỉnh hơn một chút so với TD-Coffee. Các thuật toán còn lại đều bị 3 thuật toán này bỏ khá xa về độ chính xác. Nếu chỉ nhìn tập trung vào 2 thuật toán EM-Coffee và TD-Coffee ta có thể dễ dàng nhận thấy hầu hết các kết quả của EM-Coffee đều cao hơn TD-Coffee trong khi thời gian thực hiện chương trình gần như là tương đương. Bảng 6 là kết quả của các chương trình với các chuỗi full-length. Ta có thể dễ dàng nhận ra các option của MAFFT chạy ra kết quả rất tốt trên các bộ RV20 tới RV50 và luôn có điểm SP cũng như TC cao nhất. Tuy nhiên với bộ RV11 và RV12 thì lần lượt EM-Coffee và ProbCons mới là thuật toán đứng đầu. Ngoài ra trong các bộ RV20 tới RV50 kết quả của EM-Coffee cũng không quá thấp so với các option của MAFFT như kết quả của ProbCons, nó luôn khá sát với các kết quả đó. Mặc dù không đạt vị trí cao nhất trong tất cả các kết quả, EM-Coffee vẫn cho thấy sự ổn định của mình, và bằng chứng rõ nhất có thể nhận ra chính là việc giá trị SP tại kết quả trung bình của EM-Coffee nhỉnh hơn toàn bộ các thuật toán khác trong đó có cả TD-Coffee. Bảng 7 là kết quả của các chương trình với các chuỗi tương đồng. Ở bảng này ProbCons độc chiếm vị trí dẫn đầu trogn mọi bộ dữ liệu con và những thuật toán còn lại đều có những kết quả thấp một cách đáng ngạc nhiên. Chẳng hạn như bộ dữ liệu RVS11 của ProbCons là hơn 81% trong khi đó các option của MAFFT chỉ cho kết quả kém hơn tới 8%. Tuy kết quả không thể cao bằng kết quả của ProbCons nhưng EM- Coffee cũng cho những kết quả không tệ như những thuật toán khác. Và có cảm giác EM-Coffee thu được những kết quả khá ổn định. Page | 31 Chương 5: Kết luận Như chúng ta đã biết, hiện nay có 2 bài toán cần được giải quyết trong sắp hàng đa chuỗi. Đó là tốc độ chạy của thuật toán và sự ổn định của chương trình trong tất cả các bộ dữ liệu. Tốc độ của chương trình có thể được cải thiện bằng các thuật toán tiên tiến nhằm làm giảm độ phức tạp đi, tuy nhiên kèm theo đó là độ chính xác và tính tin cậy của thuật toán đó lại dần mất đi. Ngược lại để có được sự ổn định với mọi bộ dữ liệu thì thông thường chương trình lại chạy rất chậm. MAFFT và ProbCons chính là 2 ví dụ cho 2 trường hợp này. MAFFT có tốc độ chạy rất tốt tuy nhiên nếu test trong bộ dữ liệu BAliBASE 3.0 thì nó chỉ tốt với những chuỗi full-length trong khi với những chuỗi tương đồng MAFFT cho kết quả rất kém. Trái ngược với MAFFT, ProbCons có kết quả khá ổn định trong cả 2 trường hợp của BAliBASE 3.0 là full-length và tương đồng. Tuy nhiên, yếu điểm lớn của ProbCons chính là tốc độ chạy của thuật toán này. Đối với bộ dữ liệu BAliBASE 3.0, nếu option chậm nhất của MAFFT chỉ chạy mất khoảng hơn 1 tiếng thì ProbCons mất hơn 10 tiếng. Điều này làm ảnh hưởng tới người dùng rất nhiều khi họ phải đợi thời gian quá lớn để thu được kết quả. EM-Coffee là một chương trình phát triển thêm từ gói M-Coffee trong bộ T- Coffee. Ý tưởng chính của M-Coffee chính là kết hợp thông tin thu được từ nhiều thuật toán khác nhau để tạo thành một đa chuỗi thẳng hàng mới với hi vọng chúng đáng tin cậy hơn các đa chuỗi thẳng hàng sinh ra từ mỗi thuật toán riêng lẻ. EM- Coffee cũng khá giống với TD-Coffee tuy nhiên khi đưa các đa chuỗi thẳng hàng từ mỗi thuật toán riêng lẻ vào thành bộ thư viện chung thì khác với TD-Coffee, EM- Coffee đặt thêm trọng số cho mỗi đa chuỗi này dựa vào kết quả của MUMSA – một chương trình đánh giá độ tin cậy của các đa chuỗi thẳng hàng. Kết quả thực nghiệm đã cho thấy, tính ổn định của thuật toán EM-Coffee là hơn hẳn so với MAFFT ở bộ dữ liệu đánh giá BAliBASE 3.0. Tuy không phải lúc nào cũng cho kết quả đứng đầu khi mang so sánh với các thuật toán khác, nhưng bù vào đó EM-Coffee lại cho thấy một sự ổn định rất khả quan trong hầu hết các bộ dữ liệu của BAliBASE. Mặc dù không thể giúp tăng được tốc độ của chương trình nhưng nếu áp dụng EM-Coffee với các dữ liệu có khoảng 40 chuỗi là hoàn toàn khả thi. Page | 32 Tài liệu tham khảo [1]. Darwin, C. (1872) On the Origin of Species. John Murray, London, 6th edn. [2]. Needleman, S.D. and Wunsch, C.D. (1970) A general method applicable to the search for similarities in the aminno acid sequence of two proteins. J. Mol. Biol., 48, 443 – 453. [3]. Feng, D.F. and Doolittle, R.F. (1987) Progressive sequence alignmen as a prerequisite to correct phylogenetic trees. J. Mol. Evol., 25, 351 – 360. [4]. Barton , G.J. and Sternberg, M.J. (1987) A strategy for rapid multiple alignment of protein sequences. Confidence levels from tertiary structure comparisions. J. Mol. Biol., 198, 327 – 337. [5]. Berger, M.P. and Munson, P.J. (1991) A novel randomized iterative strategy for aligning multiple protein seuqneces. Comput. Appl. Biosci., 7, 479 – 484. [6]. Thompson, J.D., Higgins, D.G. and Gibson, T.J. (1994) CLUSTALW: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic Acids Res, 22 [7]. Notredame C, Higgins D.G., Herina J (2000) T-Coffee: A novel method for fast and accurate multiple sequence alignment. J Mol Biol, 302:205-217. [8]. Katoh K, Kuma K, Toh H, Miyata T (2005) MAFFT version 5: improvement in accuracy of multiple sequence alignment. Nucleic Acids Res, 33: 511 – 518. [9]. Do CB, Mahabhashyam MS, Brudno M, Batzoglou S (2005) ProbCons: probabilistic consistency-base multiple sequence alignment. Genome Res 15: 303 – 340. [10]. Edgar, R.C. (2004) MUSCLE: multiple sequence alignment, Current Opinion in Structural Biology. Nucleic Acids Res, 32: 1792 – 1797. [11]. Edgar, R.C. (2004) Local homology recognition and distance measures in linear times using compressed amino acid alphabets. Nucleic Acids Res., 32, 380 – 385 [12]. Kimura, M. (1983) the Neutral Theory of Molecular Evolution. Cambridge University Press. Page | 33 [13]. Miyata, T., Miyazawa, S. and Yasunaga, T. (1979) Two types of amino acid substitutions in protein evolution. J. Mol. Evol., 12, 219 – 236. [14]. Katoh, K., Misawa, K., Kuma, K., Miyata, T.. (2002) MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform. Nucleic Acids Res., 30, 3059 – 3066. [15]. Forney, G.D. (1973) The Viterbi algorithm. Proceedings ò the IEEE, 61: 268 – 278. [16]. Henikoff, S., Henikoff, J.G. (1992) Amino Acid Substitution Matrices from Protein Blocks. PNAS 89: 10915 – 10919. [17]. Lassman, T., Sonnhammer, E.L.L. (2005) Automatic assessment of alignment quality. Nucleic Acids Res., 33, 7120 – 7128. [18]. Huang, X., Miller, W. (1991). A time-efficient linearspace local similarity algorithm. Advan. Appl. Math. 12, 337 – 375. [19]. Sander, C., Schineider, R. (1991). Database of homology-derived protein structures and the structural meaning of sequence alignment. Proteins: Struct. Funct. Genet. 9, 56 – 68. [20]. Notredame, C., Holm, L., Higgins, D.G. (1998). Coffee: an objective function for multiple sequence alignments. Bioinformatics, 14, 407 – 422. [21]. Kececioglu, J.D. (1993) the maximum weight trace problem in multiple sequence alignment. Lect. Notes Comput. Sci. 684. 106 – 119. [22]. Notredame, C., Higgins, D.G. (1996). SAGA: sequence alignment by genetic algorithm. Nucl. Acids Res. 24, 1515 – 1524. [23]. Reinert, K., Lenhof, H.P., Mutzel, P., Meihorn, K. Kececioglu, J.D. (1997). A branch- and-cut algorithm for multiple sequence alignment. Recomb97, 241 – 249. [24]. Gotoh, O. (1982) An improved algorithm for matching biological sequecens. J. Mol. Biol. 162, 705 – 708. [25]. Saitou, N., Nei, M. (1987). The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol, 4, 406 – 425. [26]. Wallace, I.M., O’Sullivan, O., Higgins, D.G., Notredame, C. (2006). M-Coffee: combining multiple sequence alignment methods with T-Coffee. Nucleic Acids Res., 34, 1692 – 1699. Page | 34 [27]. Thompson, J.D., Plewniak, F., Poch O., (1999). BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics applications note, 15, 87 – 88. [28]. Bahr, A., Thompson, J.D., Thierry, J.C., Poch, O. (2001) BAliBASE(Benchmark Alignment dataBASE): enhancements for repeats, transmembrane sequences and circular permutations. Nucleic Acids Res., 29, 323 – 326. [29]. Thompson, J.D., Koehl, P., Ripp, T., Poch, O.. (2005) BAliBASE 3.0: Latest Developments of the Multiple Sequence Alignment Benchmark. PROTEINS: structure, Function, and Bioinformatics. 61, 127 – 136. [30]. Felsenstein, J. (2004). Inferring Phylogenies. Sinauer Associates, Sunderland, Mass. [31]. Le Sy Vinh (2005) Phylogenetic tree reconstruction. Heinrich-Heine-University Duesseldorf, Germany.