1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN HOÀNG ANH
NGHIÊN CỨU THUẬT TOÁN TÌM KIẾM CHUỖI
DNA SỬ DỤNG PHƢƠNG PHÁP TÌM KIẾM TƢƠNG
TỰ NHANH
LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN
HÀ NỘI – 2016
2
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN HOÀNG ANH
NGHIÊN CỨU THUẬT TOÁN TÌM KIẾM CHUỖI
DNA SỬ DỤNG PHƢƠNG PHÁP TÌM KIẾM TƢƠNG
TỰ NHANH
Ngành: Hệ thống thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 01 04
LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC: Tiến sĩ Nguyễn Thị Hậu
HÀ NỘI – 2016
3
LỜI CAM ĐOAN
Tôi xin cam đoan nội dung của luận văn “Nghiên cứu thuật toán tìm kiếm
chuỗi DNA sử dụng phương pháp tương tự nhanh” là sản phẩm do tôi thực hiện
dưới sự hướng dẫn của TS. Nguyễn Thị Hậu. Trong toàn bộ nội dung của luận văn,
những điều được trình bày hoặc là của cá nhân hoặc là được tổng hợp từ nhiều
nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích
dẫn hợp pháp.
Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy
định cho lời cam đoan của mình.
Hà Nội, ngày 20 tháng 9 năm 2016
TÁC GIẢ
Nguyễn Hoàng Anh
4
LỜI CẢM ƠN
Trước tiên tôi xin gửi lời cảm ơn chân thành tới tập thể các các thầy cô giáo
trong Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia
Hà Nội đã giúp đỡ tận tình và chu đáo để tôi có môi trường tốt học tập và nghiên
cứu.
Đặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Nguyễn Thị Hậu, người
trực tiếp đã hướng dẫn, chỉ bảo tôi tận tình trong suốt quá trình nghiên cứu và hoàn
thiện luận văn này.
Một lần nữa tôi xin được gửi lời cảm ơn đến tất cả các thầy cô giáo, bạn bè và
gia đình đã giúp đỡ tôi trong thời gian vừa qua. Tôi xin kính chúc các thầy cô giáo,
các anh chị và các bạn mạnh khỏe và hạnh phúc.
Hà Nội, ngày 20 tháng 9 năm 2016
TÁC GIẢ
Nguyễn Hoàng Anh
5
MỤC LỤC
LỜI CAM ĐOAN ..................................................................................................... 3
LỜI CẢM ƠN ........................................................................................................... 4
DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT ....................................................... 7
GIỚI THIỆU ............................................................................................................ 8
CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN TÌM KIẾM CHUỖI
DNA .........................................................................................................................13
1.1. Phƣơng pháp tìm kiếm chuỗi DNA sử dụng mô hình Markov ẩn ............ 13
1.2. Phƣơng pháp liên kết nhạy cảm đầy đủ....................................................... 15
1.3. Phƣơng pháp tìm kiếm tƣơng tự nhanh ...................................................... 21
1.4. Phƣơng pháp sử dụng mô hình phù hợp gần đúng .................................... 25
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 ........ 31
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. ......................................................................35
2.1. Mô hình N-Gram ............................................................................................ 35
2.1.1. Một số khái niệm ...................................................................................................... 35
2.1.2. Mô hình ngôn ngữ N-gram ....................................................................................... 36
2.1.3. Khó khăn khi xây dựng mô hình ngôn ngữ N-gram : ............................................... 37
2.1.4. Các phương pháp khắc phục cụm N-Gram phân bố không đều ............................... 38
2.2. Phƣơng pháp tƣơng tự nhanh áp dụng N-gram tìm kiếm chuỗi DNA. .... 39
2.2.1. Phân đoạn DNA ........................................................................................................ 39
2.2.2. Các “từ DNA” ........................................................................................................... 40
2.2.3. Quá trình tìm kiếm chuỗi và hiển thị kết quả............................................................ 40
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 ............................................................................................................ 48
2.3.1. Định dạng chuỗi cơ sở dữ liệu .................................................................................. 48
