ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
---------------------

Vũ Thị Diệu

ỨNG DỤNG THUẬT TOÁN BURROWS-WHEELER TRANSFORM
TRONG QUÁ TRÌNH GIẢI MÃ HỆ GEN LÚA TẠI VIỆT NAM

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội – Năm 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
---------------------

Vũ Thị Diệu

ỨNG DỤNG THUẬT TOÁN BURROWS-WHEELER TRANSFORM
TRONG QUÁ TRÌNH GIẢI MÃ HỆ GEN LÚA TẠI VIỆT NAM

Chuyên ngành: Cơ sở toán cho tin học
Mã số:60480104

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN CƯỜNG

Hà Nội – Năm 2015

của các Thầy, Cô và các đồng nghiệp đồng thời cũng rất mong được các nhà nghiên
cứu tiếp tục hiệu chỉnh, bổ sung.Tôi xin chân thành cảm ơn!
TÁC GIẢ LUẬN VĂN

Vũ Thị Diệu


MỤC LỤC
DANH MỤC CÁC HÌNH VẼ........................................................................................ 7
DANH MỤC CÁC BẢNG BIỂU .................................................................................. 9
MỞ ĐẦU ......................................................................................................................... 1
CHƢƠNG 1: CƠ SỞ LÝ THUYẾT ............................... Error! Bookmark not defined.
1.1 Đặt vấn đề ................................................................. Error! Bookmark not defined.
1.1.1

Tin – Sinh học ................................................... Error! Bookmark not defined.

1.1.2

Khai phá dữ liệu trong Tin – Sinh học .............. Error! Bookmark not defined.

1.1.3

Hướng phát triển của ngành Tin – Sinh học tại Việt NamError!

Bookmark

not defined.
1.2 Mục tiêu của luận văn ............................................. Error! Bookmark not defined.
1.3 Các khái niệm cơ bản trong sinh học phân tử ...... Error! Bookmark not defined.

Giải mã hệ gen và quy trình .............................. Error! Bookmark not defined.

2.1.2

Nội dung bài toán gióng hàng trình tự (Sequence Alignment) ................. Error!

Bookmark not defined.
2.1.3

Ý nghĩa sinh học của bài toán gióng hàng trình tựError!

Bookmark

not

defined.
2.1.4

Phân loại bài toán gióng hàng trình tự .............. Error! Bookmark not defined.

2.2 Một số thuật toán cơ bản cho bài toán gióng hàng trình tựError!

Bookmark

not defined.
2.2.1

Thuật toán ma trận điểm ................................... Error! Bookmark not defined.

2.2.2

LIỆU SINH HỌC ............................................................. Error! Bookmark not defined.
3.1 Quy trình thực nghiệm ............................................ Error! Bookmark not defined.
3.2 Cài đặt ứng dụng ..................................................... Error! Bookmark not defined.
3.3 Chuẩn bị dữ liệu ...................................................... Error! Bookmark not defined.


3.4 Kết quả và đánh giá ................................................. Error! Bookmark not defined.
3.5 Đánh giá kết quả của luận văn ............................... Error! Bookmark not defined.
KẾT LUẬN ....................................................................... Error! Bookmark not defined.
TÀI LIỆU THAM KHẢO ............................................................................................. 3

DANH MỤC CÁC HÌNH VẼ
Hình 1.1

Mô hình cấu trúc phân tử DNA .................. Error! Bookmark not defined.

Hình 1.2

Mô hình cấu trúc gen .................................. Error! Bookmark not defined.

Hình 1.3

Định dạng dữ liệu FASTA .......................... Error! Bookmark not defined.

Hình 1.4

Định dạng FASTQ ...................................... Error! Bookmark not defined.

Hình 2.1



Minh họa việc giải mã BWT xâu „CT$ATGA‟Error!

Bookmark

not

defined.
Hình 2.8

Mô tả quá trình tạo chuỗi BWT .................. Error! Bookmark not defined.

Hình 2.9

Vị trí xuất hiện của kí tự “a” trong chuỗi X =”agcagcagact ............ Error!

Bookmark not defined.
Hình 2.10 Giá trị SA = [9,10] của chuỗi W=“gca” ... Error! Bookmark not defined.
Hình 2.11 Công thức tính khoảng cách SA ................. Error! Bookmark not defined.
Hình 2.12 Kết quả của quá trình tìm kiếm W=”gca” . Error! Bookmark not defined.
Hình 3.1

Mô phỏng nhiệm vụ thực nghiệm trong chương 3Error! Bookmark not

defined.
Hình 3.2

Ví dụ mô phỏng mục tiêu của ứng dụng ..... Error! Bookmark not defined.

Hình 3.3

Thông tin về máy chủ được sử dụng để cài đặt thử nghiệm ............... Error!

Bookmark not defined.
Bảng 3.2

Thông tin chi tiết về dữ liệu mô phỏng thu được. ...... Error! Bookmark not

defined.
Bảng 3.3

Kết quả tìm kiếm SNP với BWA và BWTAligner với các độ sâu trình tự

khác nhau. ...................................................................... Error! Bookmark not defined.
Bảng 3.4

Thống kê : TP - dương tính thật, FP – dương tính giả, FN – âm tính giả
Error! Bookmark not defined.

Bảng 3.5

So sánh độ đúng giữa BWA và BWTAligner gọi SNP Error! Bookmark not

defined.
Bảng 3.6
not defined.

Bảng thống kê số lượng trên từng SNP với 2 phần mềm . Error! Bookmark


MỞ ĐẦU

trình tự. Trọng tâm của chương 2 giới thiệu ý tưởng và quá trình xây dựng thuật toán
Burrows–Wheeler Transform trong quá trình giải mã hệ gen.
Chương 3 Trình bày về quá trình thực nghiệm và ứng dụng thuật toán trên dữ liệu
sinh học. Tác giả tham gia cùng nhóm nghiên cứu thuộc phòng Tin – Sinh học, viện
Công nghệ Sinh học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam xây dựng công
cụ dóng hàng trình tự BWTAligner dựa trên thuật toán BWT đã tìm hiểu. Đối chứng
kết quả khi dóng hàng trình tự trên công cụ dóng hàng phổ biến BWA. Trong chương
này thực hiện từng bước chuẩn bị dữ liệu, cài đặt môi trường, sử dụng công cụ, đưa ra
kết quả thực nghiệm và đánh giá kết quả của luận văn.

2


TÀI LIỆU THAM KHẢO

Tiếng Việt

1. Nguyễn Văn Cách (2006), Giáo trình tin sinh học, NXB Khoa học kỹ thuật,
Hà Nội..
Tiếng Anh

2. Burrows,M. and Wheeler,D.J. (1994),“A block-sorting lossless data
compression algorithm”,Technical report, 124.
3. Campagna,D.

et

al.

(2009),“PASS: