Thạc Sĩ Cải tiến clustalw cho bài toán sắp hàng đa trình tự

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 . 66