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.