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
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
2
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
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
4
2.3.1. Định dạng chuỗi cơ sở dữ liệu .............................................. 16
2.3.2. 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 .................................................................... 17
2.4. Đánh giá phƣơng pháp tìm kiếm chuỗi tƣơng tự nhanh áp
dụng N-Gram .......................................................................................... 17
2.4.1. Cải thiện thời gian tìm kiếm ................................................. 17
2.4.2. Tiết kiệm bộ nhớ trong quá trình tìm kiếm ........................... 18
CHƢƠNG 3. THỰC NGHIỆM SO SÁNH PHƢƠNG PHÁP TÌM KIẾM
TƢƠNG TỰ NHANH DỰA TRÊN N-GRAM VỚI PHƢƠNG PHÁP
BLAST VÀ PHƢƠNG PHÁP SMITH-WATERMAN ........................... 19
3.1. Môi trƣờng thực nghiệm ............................................................ 19
3.2. Thực nghiệm đánh giá phƣơng pháp tìm kiếm tƣơng tự nhanh
áp dụng N-Gram với phƣơng pháp BLAST và phƣơng pháp Smith-
Water Man .............................................................................................. 21
KẾT LUẬN ................................................................................................. 22
TÀI LIỆU THAM KHẢO .......................................................................... 23
5
DANH MỤC KÍ HIỆU VÀ CHỮ VIẾT TẮT
Kí hiệu
Tiếng Anh
Tiếng Việt
DNA
Deoxy Ribonucleic Acid
Phân tử mang cấu trúc
gen di truyền
NST
Chromosome
Nhiễm sắc thể
A
Adenine
T
Thymine
G
Guanine
C
Cytosine
SNP
Single nucleotide
polymorphisms
Tính đa hình của phân tử
nucleotit. Mỗi SNP biểu
diễn một biến đổi trong
một khối chuỗi DNA
CPU
Cental Processing Unit
Bộ xử lý trung tâm
RAM
Random access memory
Bộ nhớ truy cập ngẫu
nhiên
NCBI
National Center for
Biotechnology Information
Trung tâm quốc gia
thông tin công nghệ sinh
Differential Direct coding
Mã hóa trực tiếp phần
khác biệt
HMM
Hidden Markov Modeling
Mô hình Markov ẩn
BLAST
Basic Local Alignment Search
Tool
Công cụ tìm kiếm cục bộ
theo mẫu có sẵn
HTS
High – Throughput Sequencing
Trình tự chuỗi đa lượng