Trang nhan đề

Tóm tắt đề tài

Mục lục

Danh mục kí hiệu, chữ viết tắt

Danh mục bảng

Danh mục hình vẽ

Danh mục đồ thị

Chương_1: Tổng quan

Chương_2: Thuật toán quy hoạch động và lũy tiến toàn cực

Chương_3: Chương trình CMSA

Chương_4: Kết quả thực nghiệm

Chương_5: Kết luận

Tài liệu tham khảo

MỤC LỤC

NHẬN XÉT CỦA CÁN BỘ PHẢN BIỆN . . . 2

TÓM TẮT ĐỀ TÀI . . . 3

MỤC LỤC . . . . . 4

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT . . 6

DANH MỤC CÁC BẢNG . . 7

DANH MỤC CÁC HÌNH VẼ . . . 8

DANH MỤC CÁC ĐỒ THN . . . 10

CHƯƠNG 1: TỔNG QUAN . . . 11

1.1 GIỚI THIỆU . . . . 11

1.2 SẮP HÀNG TRÌNH TỰ . . 13

1.2.1 Định nghĩa . . . 13

1.2.2 Phân loại . . . . 14

1.2.3 Sắp hàng từng cặp (Pairwise Sequence Alignment-PSA) . 14

1.2.4 Sắp hàng đa trình tự (Multiple Sequence Alignment-MSA) . 15

1.2.5 Các khái niệm khác . . . 16

1.2.5.1 Trình tự: . . . 16

1.2.5.2 GAP . . . 16

1.2.5.3 Giá trị của GAP . . 17

1.2.5.4 Ma trận đánh giá . . 18

1.2.5.5 Phương pháp đánh giá (score method): . 21

1.3 MỘT SỐ PHƯƠNG PHÁP SẮP HÀNG TRÌNH TỰ 22

1.3.1 Phương pháp sắp hàng chính xác (Exact algorithms) . 22

1.3.2 Phương pháp sắp hàng lũy tiến toàn cục (Progressive algorithms) 22

Trang 5

1.3.3 Phương pháp sắp hàng lặp (Iterative algorithms) 23

1.3.4 Phương pháp dựa trên mô hình Makov Nn (Hidden Markov Model-

HMM) . . . . . 23

CHƯƠNG 2: THUẬT TOÁN QUI HOẠCH ĐỘNG VÀ LŨY TIẾN TOÀN CỤC

. . . . 25

2.1 THUẬT TOÁN QUI HOẠCH ĐỘNG . . 25

2.2 GIẢI BÀI TOÁN PSA BẰNG THUẬT TOÁN QUI HOẠCH ĐỘNG 25

2.3 THUẬT TOÁN LŨY TIẾN TOÀN CỤC: . . 28

CHƯƠNG 3: CHƯƠNG TRÌNH CMSA . . . 31

3.1 PHẦN MỀM CLUSTALW . . . 31

3.1.1 Giới thiệu phần mềm ClustalW . . . 31

3.2.2 Nhận xét clustalW . . 35

3.2 CẢI TIẾN CLUSTALW . . 36

3.3 CHƯƠNG TRÌNH CMSA . . 37

CHƯƠNG 4: KẾT QUẢ THỰC NGHIỆM . . 44

4.1 DỮ LIỆU KIỂM TRA . . 44

4.2 KIỂM THỬ CÂY HƯỚNG DẪN . . . 46

4.3 KIỂM THỬ KẾT QUẢ VỚI BALIBASE . . 55

CHƯƠNG 5: KẾT LUẬN . . 64

5.1 KẾT LUẬN . . . . 64

5.2 HƯỚNG Phát triển . . . 65

TÀI LIỆU THAM KHẢO . . . 6