ĐẠ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