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ũng CÁC PHƯƠNG PHÁP SẮP HÀNG ĐA CHUỖI NHANH KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công Nghệ Thông Tin Cá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ều kiệ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ốt 4 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ình giúp đỡ, định hướng cũng như động viên tôi trong quá trình nghiên cứu và hoàn thành khó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ưu Chí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 quan trự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ất nhiề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ánh khỏ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ôi xin 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ân tạ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ột vấn đề quan trọng trong lĩnh vực tin sinh học. Trong những năm gần đây, chất lượng củ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ật toá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ươ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. 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 ........................................................................................................................3 Chươ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.........................................................................................................15 Chươ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 3.4.2 Cây quyết định cho yêu cầu tốc điểm chuẩn cao...........................................24 Chương 4: Kết quả thực nghiệm và bình luận...............................................................26 4.1 Giới thiệu về BAliBASE......................................................................................26 4.1.1 BAliBASE 2...................................................................................................26 4.1.2 BAliBASE 3...................................................................................................26 4.1.3 Cách đánh giá của BAliBASE.......................................................................27 4.2 Kết quả thực nghiệm ............................................................................................28 Chương 5: Kết Luận ......................................................................................................34 Tài Liệu Tham Khảo......................................................................................................35 ... - tailieumienphi.vn