Link tải luận văn miễn phí cho ae Kết nối
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
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
CHƯƠNG 1: TỔNG QUAN
1.1 GIỚI THIỆU
Trong lĩnh vực nghiên cứu phân tích cấu trúc và chức năng của gene và protein,
phân tích trình tự (chuỗi DNA, protein) đóng vai trò quan trọng. Thông thường, khi
phát hiện ra một gene hay một protein mới, một trong những yêu cầu quan trọng là
làm thế nào xác định được chức năng và cấu trúc của gene hay protein này. Một
cách tiếp cận phổ biến là so sánh đoạn gene hay protein này với đoạn gene hoặc
protein đã biết, từ đó có thể đoán chức năng và cấu trúc của chúng. Tuy nhiên,
với số lượng tế bào trong cơ thể là khoảng 1014 và mỗi tế bào mang khoảng 3.109 ký
tự trong đoạn gene của chúng thì việc so sánh là vô cùng mất thời gian và công sức.
Sắp hàng đa trình tự là một trong những bài toán quan trọng và phổ biến nhằm hỗ
trợ phân tích các trình tự sinh học. Bản thân nó là bài toán cơ sở cho những bài toán
khác. Từ kết quả đạt được của việc giải bài toán này, người ta có thể sử dụng để
phát hiện và chứng minh sự tương đồng giữa các trình tự mới so với các trình tự
sinh học đã tồn tại; xác định quá trình tiến hóa của các họ trình tự đễ xây dựng các
cây sinh loài; hỗ trợ để chNn đoán cấu trúc của các protein, v.v...
Hình 1.1 Ứng dụng của MSA
Trong việc giải quyết bài toán sắp hàng trình tự, trước hết phải xem xét bài toán sắp
hàng 2 trình tự (Pairwise Sequence Alighment – PSA). Bài toán này đã được giải
quyết trọn vẹn bằng nhiều phương pháp khác nhau. Đồng thời với việc giải quyết
bài toán sắp hàng hai trình tự này, xuất hiện nhu cầu sắp hàng đa trình tự (Multiple

pNHEi3zLW4tZc5H

---