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

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....
Nội dung trích xuất từ tài liệu:
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 đangcông tác tại SUlab công ty FPT. Thầy đã tạo điều kiện và đưa ra những lờikhuyê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ảiquyế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 đachuỗ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ũngxin đư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à tincậ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áchInferring 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ácADN 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ồngốc được gọi chung là các ADN tương đồng(homology). Và tổng quát hơn nữa, mộtchuỗ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ủacá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ênchú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 địnhcủ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ỗiADN chứ không làm thay đổi độ dài của chuỗi ADN đó, một phép chèn hay một phépxó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óanê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 ch ...