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ó thể bạn quan tâm!

Xem toàn bộ 50 trang tài liệu này.

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ỗilà 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

Mục Lục Bảng:

Bảng 1: Bắt cặp đa chuỗi ADN của Người, Mèo, Khỉ, Chó, Ngựa, Gà và Vịt với các phép thay thế ở vị trí số 2, 3, 11, 13 và phép chén/xóa ở vị trí số 7 và số 10. 2

Bảng 2: Các chương trình bắt cặp đa chuỗi phổ biến nhất hiện nay. 3

Bảng 3: Kiểm tra các MUSCLE, FFT-NS2, FFT-NS1 với các test có số lượng chuỗi từ 200 đến 500 chuỗi. 18

Bảng 4: Kiểm tra FFT-NS2 với các dữ liệu có số lượng chuỗi lớn hơn 400 19

Bảng 5: Thời gian chạy của PROBCONS theo tống số amino acid 20

Bảng 6: Tính toán SP(mi) 27

Bảng 7: Kết quả các phương pháp với BAliBASE 2 29

Bảng 8: Kết quả các phương pháp với BAliBASE 3 – homologous 30

Bảng 9: Kết quả các phương pháp với BAliBASE 3 – ful llength 31

Mục Lục Hình:

Hình 1: Ví dụ về k-mer [6] 7

Hình 2: Các bước thực hiện của MUSCLE [6] 9

Hình 3: Ví dụ về độ trễ [4] 12

Hình 4: Ví dụ về việc tạo ma trận tương đồng [4] 13

Hình 5: Ví dụ về global homology [4] 21

Hình 6: Ví dụ về local homology [4] 22

Hình 7: Ví dụ về các đoạn gap nội khối [4] 22

Hình 8: Cây quyết định với yêu cầu xử lý tốc độ cao 23

Hình 9: Cây quyết định với yêu cầu xử lý với điểm chuẩn cao 24

Chương 1. Giới thiệu

1.1 Multiple alignment‌

Trình bày tổng quan dưới đây được tham khảo từ luận văn tiến sỹ của thầy Lê Sỹ Vinh[1] và cuốn Inferring Phylogenies[2] của giáo sư Felsenstein.

Với sự phát triển như vũ bão của khoa học kỹ thuật, trong vài thập kỷ qua, sinh học phân tử đã có nhiều bước tiến mạnh mẽ. Kèm theo đó là sự ra đời của hàng loạt loại công cụ phục vụ cho sinh học, qua đó góp phần thúc đẩy mạnh mẽ quá trình giải mã một số lượng lớn trình tự gen ở nhiều loài sinh vật. Cho đến nay, nhiều bộ gen của nhiều loài vi khuẩn và sinh vật bậc cao đã được giải mã gần như hoàn toàn. Trong đó, một khám phá đặc biệt là việc giải mã bộ gen người. Dự án Bản đồ gen người là một dự án nghiên cứu khoa học mang tầm quốc tế. Dự án khởi đầu vào năm 1990 với người đứng đầu là tiến sĩ James D. Watson. Bản phác thảo đầu tiên của bộ gen đã được cho ra đời vào năm 2000 và hoàn thiện vào năm 2003. Một dự án song song cũng được thực hiện bởi một công ty tư nhân tên là Celera Genomics. Tuy nhiên, hầu hết trình tự chuỗi được xác định là tại các trường đại học và các viện nghiên cứu từ các nước Mỹ Cannada và Anh. Việc xác định toàn bộ bộ gen người là một bước tiến quan trọng trong việc phát triển thuốc và các khía cạnh chăm sóc sức khỏe khác. Qua những phát kiến này, lượng thông tin sinh học ngày càng phong phú và đa dạng. Để có thể xử lý và ứng dụng khối lượng thông tin đồ sộ như vậy, ngành Tin Sinh học (Bioinformatics) ra đời, đó là sự kết hợp giữa công nghệ thông tin và sinh học nhằm phục vụ nhiều mục đích khác nhau. Trong số đó, việc nghiên cứu phân tích trình tự (chuỗi AND và protein) đóng một vai trò vô cùng quan trọng. Để đơn giản cho việc nghiên cứu, các trình tự DNA, protein được tuần tự hóa và nghiên cứu dưới dạng chuỗi các kí tự. Khi một gen mới được phát hiện, một trong những yêu cầu quan trọng là làm sao tìm được chức năng, tác dụng của gen này, yêu cầu tương tự cũng được đặt ra với các amino acid mới. Một phương pháp đơn giản để xử lý yêu cầu này là so sánh, đánh giá sự giống nhau (tương đồng) của các chuỗi mới tìm ra với các chuỗi đã biết, từ đó ta có thể đưa ra dự đoán về các chức năng của những chuỗi mới phát hiện này. Do đó, sắp hàng đa chuỗi (multiple sequence alignment) các đoạn ADN / protein là một trong những bài toán phổ biến và quan trọng nhất trong sinh học phân tử và các lĩnh vực liên quan. Sắp hàng đa chuỗi giúp chúng ta giải quyết một số vấn đề sau:

- Tìm kiếm và chẩn đoán chức năng cho các chuỗi ADN / protein mới giải mã