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