ĐẠ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ứ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Ẽ



DANH MỤC CÁC BẢNG BIỂU


MỞ ĐẦU

Tin - Sinh học (Bioinformatics) là một lĩnh vực khoa học sử dụng các công nghệ
của các ngành toán học ứng dụng, tin học, thống kê, khoa học máy tính, trí tuệ nhân
tạo, hóa học và hóa sinh để giải quyết các vấn đề sinh học. Sự ra đời của Tin - Sinh học
là sự hợp tác chặt chẽ giữa các nhà Tin học và các nhà nghiên cứu Sinh học nhằm khai
phá dữ liệu hiệu quả, Tin – Sinh học đã trở thành mục tiêu công nghệ của ngành Sinh
học trong thế kỉ mới. Bắt kịp xu thế phát triển của khoa học thế giới, những năm gần
đây các nhà Tin - Sinh học Việt Nam đã xác định được những hướng đi phù hợp và đạt
được thành công bước đầu với một số công trình nghiên cứu mang tính ứng dụng cao.
Trong sinh học, việc giải mã trình tự gen rất quan trọng, nó góp phần trong
việc nghiên cứu sinh học cơ bản và trong nhiều lĩnh vực ứng dụng như chẩn đoán
bệnh tật, công nghệ sinh học, sinh học pháp y, sinh học hệ thống... Do đặc tính khí
hậu nhiệt đới, Việt Nam có những lợi thế về những nguồn dữ liệu Sinh học to lớn, hữu
ích, điều đó trở thành một điều kiện thuận lợi và cũng là thách thức cần đến sự đóng

Tin - Sinh học là một lĩnh vực mới mẻ trong phạm vi nghiên cứu tại Việt Nam.
Những năm gần đây, Tin - Sinh học đã được các nhà nghiên cứu Việt Nam tiếp cận gần
hơn và đạt được những thành công bước đầu nổi trội. Trong chương đầu của luận văn,
tác giả sẽ giới thiệu đến những khái niệm cơ bản của Tin - Sinh học, hướng phát triển
của Tin – Sinh học nói chung và tại Việt Nam nói riêng, từ đó làm tiền đề để phát biểu
mục tiêu của luận văn. Phần cuối chương một sẽ trình bày các định nghĩa cơ bản trong
bài toán Tin – Sinh học mà sẽ được nhắc đến xuyên suốt trong những phần sau của
luận văn này.
1.1 Đặt vấn đề
1.1.1 Tin – Sinh học
Tin - Sinh học (Bioinformatics) là một lĩnh vực khoa học sử dụng các công nghệ
của các ngành toán học ứng dụng, tin học, thống kê, khoa học máy tính, trí tuệ nhân
tạo, hóa học và hóa sinh để giải quyết các vấn đề sinh học. Tin - Sinh học thiên về việc
phát triển các giải thuật, lý thuyết và các kĩ thuật thống kê tính toán để giải quyết các
bài toán bắt nguồn từ nhu cầu quản lí và phân tích dữ liệu sinh học.
Những lĩnh vực nghiên cứu chính của Tin - Sinh học gồm phân tích trình tự, tìm
kiếm gen, tìm kiếm các đột biến, phân tích chức năng gen …vv. Mọi sinh vật đều có hệ
gen, và người ta khẳng định rằng hệ gen mã hóa hầu hết thông tin di truyền của sinh
vật. Do vậy, việc giải mã hệ gen là một bài toán có ý nghĩa vô cùng quan trọng trong
ngành sinh học trên thế giới nói chung, và với một nước đang phát triển như Việt Nam
nói riêng. Giải mã trình tự gen là một bài toán có quy mô rộng lớn trong ngành Tin –
Sinh học và đã đem lại được những thành tựu nghiên cứu có ý nghĩa vô cùng to lớn:
Năm 2003, thành công của dự án giải mã 1000 hệ gen người (Human Genome
Project ) đã mang tới bước đột phá lớn của sinh học trong công nghệ, khởi đầu cho

10


hàng loạt các dự án giải mã hệ gen cho các loài khác nhau trên thế giới. Một số dự án
nổi bật khác trên thế giới có thể kể tên như dự án “750 người Hà Lan” giải trình tự tại

sinh học (biotechnology) và y sinh (biomedical). Nó có các ứng dụng như điều chế
dược phẩm, khoa học pháp y (forensic DNA analysis), và công nghệ sinh học trong
nông nghiệp.
1.1.3 Hướng phát triển của ngành Tin – Sinh học tại Việt Nam
Bắt kịp xu thế phát triển của khoa học thế giới, các nhà Tin - Sinh học Việt Nam
đã xác định được những hướng đi phù hợp và đạt được thành công bước đầu với một
số công trình nghiên cứu mang tính ứng dụng cao. Ví dụ như một số nghiên cứu trong
lĩnh vực phân tích gen, xác định trình tự DNA của một số loài để đánh giá về mặt di
truyền, biến dị, xác định hệ số di truyền tìm ra các họ hàng thân thích, đánh giá mức độ
biến đổi tính di truyền, nghiên cứu về đa dạng sinh học, xây dựng ngân hàng gen (gen
bank)...
Một số đơn vị nghiên cứu trong nước đã lựa chọn Tin - Sinh học là hướng nghiên
cứu và phát triển có thể kể đến như: Khoa Công nghệ Sinh học, Trường Đại học Khoa
học Tự nhiên TP Hồ Chí Minh; Viện Công nghệ Sinh học, Viện Khoa học và Công
nghệ Việt Nam; Trường Đại học Y Dược TP Hồ Chí Minh. Tuy là một ngành khoa học
mới mẻ tại Việt Nam trong những năm gần đây nhưng cộng đồng Tin - Sinh học Việt
Nam nói chung cũng đã có những đóng góp và thành tựu đang kể. Đáng chú ý là sản
phẩm phần mềm Tin - Sinh học do PGS. TS. Trần Văn Lăng (Viện Công nghệ thông tin
tại TP Hồ Chí Minh) chủ trì đã tạo ra phần mềm HiBio riêng với một số tính năng cần
thiết cho việc tìm hiểu về sinh học phân tử và việc tiếp cận với những bài toán Tin Sinh
trở nên trực quan và ưu Việt. Năm 2012, Viện Hàn lâm Khoa học và Công nghệ Việt
Nam khởi động dự án xây dựng bản đồ gen người cho 54 dân tộc Việt Nam và thành
lập Viện hệ gen học. Cuối năm 2013, TS. Lê Sỹ Vinh – giảng viên Trường Đại học
Công nghệ và các cộng sự đã công bố những kết quả đầu tiên về việc nghiên cứu xây

12


dựng và phân tích hệ gen người Việt, bắt đầu từ tiếp cận của các kỹ thuật tính toán Tin
– Sinh học. Và còn nhiều công trình nghiên cứu khác đã được công bố thể hiện những

Với những tổng quan về Tin – Sinh học và mục tiêu của luận văn mà tôi đã trình
bày ở nội dung trên, trong nội dung tiếp theo tôi sẽ trình bày về các khái niệm cơ bản
trong sinh học phân tử. Các khái niệm được trình bày dưới đây sẽ là những khái niệm
được sử dụng xuyên suốt trong nội dung tiếp theo của luận văn.
1.3.1 DNA
Acid Deoxyribo Nucleic (viết tắt ADN theo tiếng Pháp hay DNA theo tiếng Anh)
là một phân tử acid nucleic mang thông tin di truyền mã hóa cho hoạt động sinh
trưởng và phát triển của các vật chất hữu cơ bao gồm cả một số virus. ADN thường
được coi là vật liệu di truyền ở cấp độ phân tử tham gia quyết định các tính trạng.
Trong quá trình sinh sản, phân tử ADN được nhân đôi và truyền cho thế hệ sau.Về mặt
cấu trúc cơ bản, DNA là các đại phân tử (polymer) mà các đơn phân (monomer) là các
nucleotide. Mỗi nucleotide được tạo thành từ một phân tử đường ribose, một
gốc phosphate và một bazơ nitơ (nucleobase). Trong DNA chỉ có 4 loại nucleotide và
những loại này khác nhau ở thành phần nucleobase. Do đó tên gọi của các loại
nucleotide xuất phát từ gốc nucleobase mà nó mang: ademine (A), thy mine(T),
Cytosine (C), và guanine (G). Trong đó, A và G là các purine (có kích thước lớn)
còn T và X, có kích thước nhỏ hơn (pyrimidine).

14


Hình 1.1 Mô hình cấu trúc phân tử DNA
1.3.2 Gen
Gen hay còn gọi là gien, gene, ren hay di tố là một đoạn DNA mang một chức
năng nhất định trong quá trình truyền thông tin di truyền. Trên nhiễm sắc thể, một gen
thường có một vị trí xác định và liên kết với các vùng điều hòa phiên mã và các vùng
chức năng khác để bảo đảm và điều khiển hoạt động của gen.
Gen có chức năng gửi các tín hiệu hóa học đi đến tất cả các nơi trong cơ thể.
Những tín hiệu này có chứa đầy đủ các thông tin, các chỉ thị cụ thể cho các cơ quan
trong cơ thể ta phải hoạt động ra sao. Việc tìm hiểu số lượng gen cũng như cơ cấu tổ

sau đây sẽ giới thiệu chi tiết về các định dạng dữ liệu cơ bản này.

16


a. Định dạng FASTA
Định dạng FASTA là định dạng phổ biến nhất được dùng để lưu trữ thông tin
về một chuỗi ADN hoặc protein. Định dạng dữ liệu FASTA lưu trữ thông tin hệ
gen tham chiếu (giới thiệu hệ gen tham chiếu: 1.3.3), bao gồm 2 phần: phần tiêu
đề và phần nội dung
-

Phần tiêu đề: bao gồm 1 dòng bắt đầu với kí từ “>” và kết thúc bởi một kí tự
xuống dòng. Phần này sẽ lưu trữ toàn bộ thông tin mô tả về đoạn trình tự ADN
(protein) như tên chuỗi, độ dài chuỗi, ngày tháng tiến hành giải mã, loại dữ liệu
(nếu có)

-

Phần nội dung: Chứa trình tự có thể là nucleotide hoặc axit amin. Các trình tự này
có thể ở trên một dòng hoặc có thể được chia thành nhiều dòng.

Hình 1.3 Định dạng dữ liệu FASTA

b. Định dạng FASTQ
Định dạng FASTQ là định dạng được sử dụng để lưu trữ dữ liệu được tạo ra từ
các máy giải trình tự thế hệ mới (FastQ = FastA + Quality). Do đó, FASTQ chỉ chứa

17


19


1
2
3
4
5
6
7
8
9
10
11
12

Tên truy vấn / khuôn mẫu / cặp
Cờ (FLAG) (Cờ đảo bit)
Tên tham chiếu
Vị trí (tại 1 vị trí cuối cùng bên trái)
Chất lượng ánh xạ (Trong quy mô Phred )
CIGAR(Dạng chuỗi )
Tên tham chiếu ghép nối ( = nếu tương tự như tên tham chiếu )
Vị trí ghép nối ( tại 1 vị trí )
Kích thước đoạn chèn
Trình tự truy vấn
Chất lượng truy vấn
Trường biến tùy chọn
Bảng 3.1 Các thẻ định danh trong định dạng SAM



21


CHƯƠNG 2 : CƠ SỞ LÝ THUYẾT VÀ THUẬT TOÁN
BURROWS WHEELER TRANSFORM
Trong quy trình giải mã hệ gen, bước xác định biến dị/ đa hình là một bước quan
trọng và góp phần lớn trong việc đưa ra cảnh báo, phòng ngừa và điều trị sớm, phát
triển các phương pháp điều trị và chữa bệnh hướng đến từng cá thể của loài. Trong
chương hai, tác giả giới thiệu về bài toán gióng hàng trình tự - một bài toán quan
trọng nhằm xác định biến dị/ đa hình trong quá trình giải mã hệ gen. Tiếp theo của
chương 2 sẽ giới thiệu một số thuật toán cơ bản giải quyết bài toán gióng hàng trình
tự. Nội dung trọng tâm của chương hai là giới thiệu thuật toán Burrows – Wheeler
Tranform (BWT) nhằm giải quyết hiệu quả bài toán gióng hàng trình tự một cách
nhanh chóng, chính xác và hiệu quả.
2.1 Quy trình giải mã hệ gen và bài toán gióng hàng trình tự
2.1.1 Giải mã hệ gen và quy trình
Hệ gen được cấu tạo từ các phân tử ADN là một phân tử acidnucleic mang
thông tin di truyền mã hóa cho hoạt động sinh trưởng và phát triển của sinh vật. Hệ
gen bao gồm 4 loại nucleotide: A (Adenine), T (Thymine), G (Guanine) và C
(Cytosine). Máy giải trình tự thế hệ mới (Next-generation sequencing) có thể giải
trình tự được toàn bộ hệ gen. Máy giải trình tự không chỉ tạo ra duy nhất một chuỗi
trình tự toàn bộ hệ gen, mà tạo ra hàng triệu đoạn trình tự nhỏ được cắt ra từ hệ gen,
gọi là các trình tự đoạn ngắn (read). Các read được gióng hàng với một trình tự tham
chiếu để tìm kiếm các khác biệt. Trong phần này, luận văn sẽ nêu tầm quan trọng của
gióng hàng trong quy trình để phát hiện các biến dị/đa hình.

22



tự (Sequence Alignment) là quá trình nghiên cứu sự giống nhau giữa các chuỗi trình tự
(sequence), là cách thức so sánh giữa 2 hay nhiều trình tự dựa trên việc so sánh một
chuỗi các thành phần (ký tự) của trình tự để tìm ra những điểm tương đồng, giống nhau
giữa các trình tự.
Sequence 1



G A A T T C A G T T A
|

Sequence 2



|

|

G G A T -

24

|

|

C -

G -