3
MỤC LỤC
LỜI CAM ĐOAN ......................................................................................... 2
DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT ............................................ 5
GIỚI THIỆU ................................................................................................. 6
CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM
CHUỖI DNA ................................................................................................ 7
1.1. Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov
ẩn 7
1.2. Phƣơng pháp liên kết nhạy cảm đầy đủ ..................................... 8
1.3. Phƣơng pháp tìm kiếm tƣơng tự nhanh ..................................... 9
1.4. Phƣơng pháp sử dụng mô hình phù hợp gần đúng ................. 10
1.5. Phƣơng pháp sử dụng mô hình kết hợp chính xác và gần chính
xác 10
CHƢƠNG 2. N-GRAM VÀ PHƢƠNG PHÁP TÌM KIẾM CHUỖI
TƢƠNG TỰ NHANH ÁP DỤNG N-GRAM. ........................................... 12
2.1. Mô hình N-Gram ........................................................................ 12
2.1.1. Một số khái niệm .................................................................. 12
2.1.2. Mô hình ngôn ngữ N-gram ................................................... 12
2.1.3. Công thức tính “xác suất thô” ............................................... 12
2.1.4. Khó khăn khi xây dựng mô hình ngôn ngữ N-gram : ........... 13
2.2. Phƣơng pháp tƣơng tự nhanh áp dụng N-gram tìm kiếm chuỗi
DNA. ...................................................................................................... 13
2.2.1. Phân đoạn DNA .................................................................... 13
2.2.2. Các “từ DNA” ...................................................................... 13
2.2.3. Quá trình tìm kiếm chuỗi và hiển thị kết quả ....................... 14
2.3. Bảng kết quả các lần thử phƣơng pháp tìm kiếm chuỗi tƣơng
tự nhanh áp dụng N-Gram .................................................................... 16
