Khóa luận tốt nghiệp: Các phương sai sắp hàng đa chuỗi nhanh

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:
Khóa luận tốt nghiệp: Các phương sai sắp hàng đa chuỗi nhanh ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Hoàng DũngCÁC PHƯƠNG PHÁP SẮP HÀNG ĐA CHUỖI NHANHKHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUYNgành: Công Nghệ Thông TinCán bộ hướng dẫn: Tiến sĩ. Lê Sỹ Vinh HÀ NỘI - 2010 LỜI CẢM ƠN Đầu tiên, tôi xin gửi lời cảm ơn tới gia đình, nơi đã động viên và tạo mọi điềukiện giúp tôi học hành tốt nhất trong suốt những năm qua. Tôi xin chân thành cảm ơn các thầy cô giáo trong trường Đại học Công nghệ -Đại học Quốc gia Hà Nội đã tận tình giúp đỡ và truyền đạt kiến thức cho tôi trong suốt4 năm học qua để tôi có đủ kiến thức hoàn thành khóa luận này. Đặc biệt, tôi xin gửi lời cảm ơn sâu sắc tới thầy Lê Sỹ Vinh – người đã nhiệt tìnhgiúp đỡ, định hướng cũng như động viên tôi trong quá trình nghiên cứu và hoàn thànhkhóa luận. Tôi xin gửi lời cảm ơn chân thành tới thầy Từ Minh Phương trường đại học BưuChính Viễn Thông, người đã truyền dạy cho tôi những kiến thức quan trọng liên quantrực tiếp đến đề tài của khóa luận. Tôi cũng xin cảm ơn các bạn trong nhóm Tin sinh. Các bạn đã giúp đỡ tôi rấtnhiều trong việc hoàn thành khóa luận. Mặc dù đã rất cố gắng hoàn thành khóa luận này, xong khóa luận sẽ khó tránhkhỏi những thiếu sót, kính mong quý thầy cô tận tình chỉ bảo giúp tôi. Một lần nữa tôixin cảm ơn tất cả mọi người. Hà Nội, tháng 5 năm 2010 Sinh viên Nguyễn Hoàng Dũng Tóm tắt Tin Sinh học (bioinformatics) là một lĩnh vực khoa học sử dụng các công nghệcủa các ngành tin học, toán học ứng dụng, thống kê, khoa học máy tính, trí tuệ nhântạo, hóa học và hóa sinh để giải quyết các vấn đề sinh học. Sắp hàng đa chuỗi là mộtvấn đề quan trọng trong lĩnh vực tin sinh học. Trong những năm gần đây, chất lượngcủa các chương trình sắp hàng đa chuỗi đã được cải thiện rất nhiều bởi rất nhiều thuậttoán mới. Mặc dù vậy, lĩnh vực vẫn là một nhiệm vụ khó khăn cho các nhà khoa học.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ươngphá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ụngrộ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. Mục Lục:Chương 1. Giới thiệu .......................................................................................................1 1.1 Multiple alignment .................................................................................................1 1.2 Các chương trình sắp hàng đa chuỗi (multiple sequences alignment ) thông dụng hiện nay ........................................................................................................................3Chương 2. Các phương pháp bắt cặp đa chuỗi ................................................................5 2.1 CLUSTALW ..........................................................................................................5 2.1.1 Tính toán ma trận khoảng cách giữa mọi cặp chuỗi ........................................5 2.1.2 Tạo cây hướng dẫn (guide tree) .......................................................................5 2.1.3 Progressive alignment ......................................................................................6 2.2. MUSCLE ...............................................................................................................7 2.2.1 Các loại khoảng cách và các cách xây dựng cây hướng dẫn ...........................7 2.2.2 Profile alignment ..............................................................................................8 2.2.3 Thuật toán ........................................................................................................8 2.3 MAFFT .................................................................................................................10 2.3.1 Bắt cặp nhóm sử dụng FFT ............................................................................10 2.3.2 Hệ thống tính điểm.........................................................................................13 2.4 PROBCONS .........................................................................................................15Chương 3. Cây quyết định .............................................................................................17 3.1 Cách giải quyết của Chuong B. Do và Kazutaka Katoh ......................................17 3.2 Vấn đề tốc độ ........................................................................................................18 3.2.1 Dữ liệu với số lượng chuỗi lớn ( > 200 chuỗi) ..............................................18 3.2.2 Dữ liệu với số lượng sequence nhỏ, tổng số amino axit nhỏ .........................19 3.2.3 Dữ liệu với độ dài của chuỗi quá lớn ( > 2000 amino acids) .........................20 3.3 Vấn đề điểm chuẩn (benchmark) .........................................................................21 3.3.1 Với các chuỗi có độ tương đồng cao .............................................................21 3.3.2 Với các chuỗi có độ tương đồng thấp ............................................................21 3.4 Cây quyết định......................................................................................................22 3.4.1 Cây quyết định cho yêu cầu tốc độ xử lý cao ................................................23 ...