1

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN VĂN THÀNH

PHÁT HIỆN CÁC ĐỘT BIẾN ĐẢO ĐOẠN
TRONG HỆ GEN GIẢI MÃ TỪ THIẾT BỊ
ĐỌC TRÌNH TỰ THẾ HỆ MỚI

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên – 2014


2

LỜI CAM ĐOAN
Tôi xin cam đoan: Luận văn này là công trình nghiên cứu thực sự của
cá nhân, được thực hiện dưới sự hướng dẫn khoa học của Tiến sĩ Nguyễn
Cường. Các số liệu, những kết luận nghiên cứu được trình bày trong luận
văn này trung thực và chưa từng được công bố dưới bất cứ hình thức nào.
Tôi xin chịu trách nhiệm về nghiên cứu của mình.

Học viên

Nguyễn Văn Thành


3

Chương 1.TỔNG QUAN VỀ TIN SINH HỌC VÀ BÀI TOÁN PHÁT HIỆN
ĐỘT BIẾN ĐẢO ĐOẠN....................................................................................... 11
1.1 - Tổng quan về Tin sinh học ......................................................................... 11
1.2 – Cơ sở lý thuyết bài toán đột biến đảo đoạn ............................................... 12
1.2.1 - Gen và đột biến cấu trúc hệ gen ...................................................... 12
1.2.2 - Phương pháp phát hiện sự biến đổi cấu trúc trong bản đồ gen ...............
15
1.2.3 - Định dạng cơ sở dữ liệu ................................................................... 23
1.2.3 - Bài toán đột biến đảo đoạn .............................................................. 27
1.3 - Các công cụ giải quyết bài toán đảo đoạn .............................................. 33
1.3.1 - Chương trình Wgsim ........................................................................ 33
1.3.2 - Chương trình TMAP ........................................................................ 33
1.3.3 - Chương trình BWA và Bowtie. ....................................................... 33
Chương 2. MỘT SỐ THUẬT TOÁN PHÁT HIỆN ĐỘT BIẾN ....................... 34
2.1 - Thuật toán ma trận điểm............................................................................. 35
2.2 - Thuật toán Blast.......................................................................................... 37


5

2.3 - Thuật toán lai GA-SA................................................................................. 42
2.4 - Thuật toán Needleman – Wunsch .............................................................. 45
2.5 - Thuật toán Smith-Waterman ...................................................................... 49
Chương 3. CÀI ĐẶT THUẬT TOÁN VÀ ĐÁNH GIÁ KẾT QUẢ .................. 56
3.1 - Ánh xạ các đoạn trình tự. ........................................................................... 57
3.2 - Xử lý SAM và khởi tạo điểm dừng khả dĩ. ................................................ 58
3.3 - Lọc và hoàn thiện điểm dừng. .................................................................... 61
3.4 - Mô phỏng dữ liệu và thống kê kết quả ánh xạ. .......................................... 64
3.5 - Đánh giá kết quả phân tích. ........................................................................ 68
3.6 - So sánh với các phương pháp hiện tại........................................................ 74

Hình 3.12: PPV ở pha 1 và pha 2 cho trình tự có lỗi........................................ 74


7

Hình 3.13: So sánh Inverse Variant vớiBreakDancer dựa vào điểm dừng. .... 76
Hình 3.15: So sánh Inverse Variant với BreakDancer dựa vào tính nhạy cảm, PPV
và FScore....................................................................................................................... 76

DANH MỤC CÁC BẢNG BIỂU
Bảng 1.1: Các thẻ định danh trong SAM .............................................................. 25
Bảng 1.2: Định nghĩa cờ đảo bit trong SAM ........................................................ 25
Bảng 1.3: Mô tả chuỗi CIGAR ............................................................................. 26
Bảng 1.4 Bảng cho thấy CNVs và đảo đoạn ......................................................... 28
Bảng 3.1: Những tham số được đặt mô phỏng cho các đoạn trình tự có lỗi. ....... 66
Bảng 3.2: Kết quả của Inverse Variant ở trình tự lý tưởng có độ dài 100bp ........ 69
Bảng 3.3: Kết quả của Inverse Variant ở trình tự lý tưởng có độ dài 200bp ........ 69
Bảng 3.4: Kết quả của Inverse Variant ở trình tự lý tưởng có độ dài 400bp ........ 69
Bảng 3.5: Kết quả của Inverse Variant ở trình tự lý tưởng với độ bao phủ 10X.. 70
Bảng 3.6: Kết quả của Inverse Variant ở trình tự lỗi với độ bao phủ là 10X ....... 70
Bảng 3.7: Bảng so sánh InverseVariantvới BreakDancer..................................... 75


8

DANH MỤC CÁC TỪ VIẾT TẮT-THUẬT NGỮ
STT
1

Từ viết tắt/thuật ngữ


6

HGP

Dự án hệ giải trình tự hệ gen con người

7

Nucleotide

Là các trình tự A,T,G,C

8

SBS

Đọc trình tự bằng sợ tổng hợp

9

SBL

Đọc trình tự gắn nối

10

PCR

Kỹ thuật khuếch đại gen

Vị trí thể hiện sự chèn hoặc xóa trong gen

16

BWA (hoặc Bowtie)

Công cụ ánh xạ trình tự với dữ liệu tham chiếu

17

TMAP

Chương trình để xây dựng bản đồ di truyền

18

Wgsim

Công cụ mô phỏng các đoạn trình tự ngắn từ dữ
liệu hệ gen tham chiếu

19

Single end reads

Phương pháp đọc trình tự theo chiều đơn

20

PPV

(pyrosequencing) của các thiết bị đọc trình tự trước đó, đọc trình tự thế hệ
mới cho phép đọc được từ 8gb đến 600gb, có nghĩa là cho phép đọc trình tự
nguyên bộ gen của bất kỳ loài sinh vật nào.
Với mong muốn hiểu chi tiết về cấu trúc gen các nhà nghiêncứu sinh
học luôn muốn đọc trình tự hoàn chỉnh các gen của tất cả các loài sinh vât
trong tự nhiên, bao gồm cả hệ gen của con người và toàn bộ trình tự gen
khác của nhiều động, thực vật, vi sinh vật, đồng thời qua việc nghiên cứu đó
có thể phát hiện ra những đột biến cấu trúc trong hệ gen được giải mã. Đặc
biệt là dạng đột biến đảo đoạn, loại đột biến này ít gây ảnh hưởng đến sức
sống của cá thể, nhưng nógóp phần lớn tăng cường sự sai khác giữa các
nhiễm sắc thể (NST) tương đồng điều này dẫn đến tăng sự đa dạng giữa các
thứ,các nòi trong cùng một nòi, ít ảnh hưởng tới sức sống của cá thểvà trong
đó sự sắp xếp lại hệ gen trên NST do đột biến đảo đoạn góp phần tạo sự đa
dạng trong tự nhiên. Đối với con người việc đọc trình tự hệ 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...Nhận thấy tính thiết thực của vấn đề và với sự


10

định hướng của giáo viên hướng dẫn, học viên đã chọn đề tài “Phát hiện
các đột biến đảo đoạn trong hệ gen giải mã từ thiết bị đọc trình tự thế
hệ mới” để làm rõ các vấn đề đã nêu trên.
Đối tượng và phạm vi nghiên cứu
Kiến trúc về các thành phần và các đột biến cấu trúc trong hệ gen.
Ứng dụng thiết bị đọc trình tự thế hệ mới trong công nghệ sinh học.
Ph ương pháp phát hiện các đột biến đảo đoạn khi sử dụng các thiết bị
đọc trình tự thế hệ mới để giải mã.
Hướng nghiên cứu của đề tài

bắt cặp trình tự (sequence alignment), bắt cặp cấu trúc protein (protein
structural alignment), dự đoán cấu trúc protein (protein structural
prediction), dự đoán biểu hiện gen (gene expression), tương tác protein protein (protein-protein interaction), mô hình hoá quá trình ti ến hoá. Thuật
ngữ tin sinh học và sinh học tính toán thường được dùng hoán đổi cho nhau,
nhưng nói một cách nghiêm túc thì cái trước là tập con của cái sau. Mối
quan tâm chính ở tin sinh học và sinh học tính toán là việc sử dụng các công
cụ toán học để phân chiết các thông tin hữu ích từ các dữ liệu hỗn độn thu
nhận được bằng các kỹ thuật sinh học với lưu lượng và mức độ lớn. Như
vậy, về phương diện này lĩnh vực khai phá dữ liệu (data mining) có sự trùng
lắp với sinh học tính toán. Bài toán đặc trưng trong sinh học tính toán bao
gồm việc lắp ráp (assembly) những trình tự ADN chất lượng cao từ những
đoạn ngắn ADN được thu nhận từ kỹ thuật xác định ADN và việc dự đoán
quy luật điều hoà gen (gene regulation) với dữ liệu từ các mARN,
microarray hay khối phổ (mass-spectrometry).
Các lĩnh vực nghiên cứu chính của tin sinh học gồm hệ gen học phân
tích trình tự, tìm kiếm gen, tìm kiếm các đột biến, phân loại học phân tử,
bảo tồn đa dạng sinh học, phân tích chức năng gen hay biểu hiện nhận diện
chuỗi polypeptid dự đoán cấu trúc của protein các hệ thống sinh học kiểu
mẫu, phân tích hình ảnh mức độ cao, công cụ phần mềm.
Định hướng nghiên cứu tìm kiếm các đột biến là một bài toán rộng
trong Tin sinh học. Bởi vì, các hệ gen thường có nhiều kiểu đột biến với


12

mức độ đột biến khác nhau như là: Đột biến cấu trúc (trong đó có đột biến
mất đoạn, đột biến thêm đoạn, đột biến đảo đoạn, …), đột biến điểm (đột
biến đa hình đơn SNP, đột biến mất nucleotide, đột biến thêm nucleotite, ..).
Trong luận văn này, tôi sẽ tiến hành nghiên cứu phương pháp phát
hiện đột biến đảo đoạn, một dạng của đột biến cấu trúc hệ gen.

Hình 1.3: Cấu trúc một phần 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ể


14

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ổ chức của gen trong cơ thể con người là một
điều tất yếu để mang lại những tiến bộ mới và quan trọng của y sinh học.
Nhưng không phải gen nào cũng có chức năng rõ ràng. Trong thực tế, có
khoảng 47% gen không có chức năng cụ thể (hay chúng ta chưa biết chức
năng của chúng).
Đột biến gen là những biến đổi nhỏ xảy ra trong cấu trúc của gen. Những
biến đổi này thường liên quan đến 1 cặp nucleotide (đột biến điểm) hoặc 1 số
cặp nucleotide.
Trong những cá thể tự nhiên, các gen đều có thể bị đột biến nhưng với tần
-6

-4

số thấp (từ 10 đến 10 ). Các cá thể mang đột biến đã biểu hiện thành kiểu hình
là thể đột biến. Đột biến gen làm thay đổi cấu trúc của gen từ đó tạo ra alen mới
so với dạng ban đầu.
VD: Ở ruồi giấm gen A qui định mắt đỏ, sau khi bị đột biến tạo thành gen
a qui định mắt trắng
Các dạng đột biến
Độ t b iến mấ t đoạ n : Đột biến này làm NST bị mất đoạn (đoạn đó
không chứa tâm động), làm giảm số lượng gen trên NST thường gây chết hoặc

1.2.2 - Phương pháp phát hiện sự biến đổi cấu trúc trong bản đồ
gen
a. Phương pháp lai dựa trên tiếp cận mảng


16

Phƣơng pháp tiếp cận sử dụng vi mảng[7] đƣợc xem là bƣớc đột phá
đầu tiên trong việc phát hiện và xác định số lượng cũng như kiểu biến đổi
cấu trúc hệ gen. Theo kỹ thuật này, hai cách tiếp cận phổ biến nhất, trước
tiên là ghép hệ gen so sánh mảng (mảng CGH), thứ hai là vi mảng SPN.
Mặc dù cả hai kỹ thuật này được dựa trên suy luận tăng hoặc giảm số lượng
bản sao so với một mẫu tham chiếu hoặc bản gốc khác nha u về chi tiết và áp
dụng các xét nghiệm phân tử. Tuy nhiên với kỹ thuật này có thể phát hiện ra
sự thay đổi cấu trúc như chèn, xóa là đáng kể, phát hiện đảo đoạn gen chỉ là
số ít.
b. Phương pháp đơn phân tích phân tử
Đơn phân tích phân tử[7] là một cách quan trọng để hình dung và
hiểu được vị trí và cấu trúc của các biến thể lớn hơn ở cấp độ đơn phân tử.
Phương pháp phân tích này bao gồm các kỹ thuật như huỳnh quang lai tại
chỗ (FISH), Fiber-FISH. Kỹ thuật này mang lại hiệu quả cho việc xác định
những sự biến đổi cấu trúc chung và hiếm có của hệ gen. Tuy nhiên, chất
lượng và độ phân giải không cao của các kỹ thuật trên gây ra giới hạn ứng
dụng của chúng khi thực hiện trên các cấu trúc đặc biệt lớn (~ 500 kb - 5
Mb). Nhiều phương pháp khác nhau đang được phát triển để sử dụng các
đoạn DNA lớn hoặc dài hơn với quy mô lớn để hiển thị trực tiếp cải thiện
độ phân giải và khả năng mở rộng của phương pháp này. Lập bản đồ quang
học là một kỹ thuật dựa trên một sửa đổi của bản đồ hạn chế truyền thống.
Trong kỹ thuật này sự tiêu chuẩn hóa kỹ thuật được thực hiện trên DNA cố
định để xác định kích thước mảnh, nhỏ và thay đổi thứ tự tương đối của

pyrosequencing[14]. Đối với phương pháp đọc trình tự Sanger, quá trình đọc
trình tự được thực hiện sau phản ứng khuếch đại DNA. Đối với phương
pháp pyrosequencing, quá trình đọc trình tự được thực hiện ngay trong giai
đoạn tổng hợp sợi DNA bổ sung cho sợi khuôn, nghĩa là tổng hợp sợi DNA
bổ sung đến đâu thì đọc trình tự đến đó.
Nguyên lý của kỹ thuật đọc trình tự trong pyrorequencing là ghi nhận
tín hiệu phát quang từ giếng phản ứng mỗi khi sợi bổ sung dựa trên sợi
Số hóa bởi Trung tâm Học
liệu

tnu.edu.vn/


18

khuôn kéo dài được một nucleotide. Để làm được điều này, dung dịch chứa
các loại nucleotide A hoặcT hoặc C hoặc G được lập trình để cho vào giếng
phản ứng có chứa đoạn DNA muốn đọc trình tự, mồi đọc trình tự, và các
thành phần cho phản ứng tổng hợp sợi khuôn. Mỗi khi dung dịch nucleotide
cho vào là đúng với nucleotide được bắt cặp vào sợi khuôn để tổng hợp sợi
bổ sung thì sẽ giải phóng ra một pyrophosphate (PPi) sẽ được phóng ra và
được enzyme sulfurylase chuyển hóa tạo ra một ATP, ATP này sẽ giúp hệ
thống phát quang luciferin-luciferase phát ra ánh sáng do enzyme luciferase
oxi hóa luciferin thành oxyluciferin và phát quang [15] . Với sự ghi nhận tín
hiệu phát quang từ ống phản ứng theo trình tự bổ sung dung dịch các loại
nucleotide, thiết bị pyrosequencing sẽ dịch ra trình tự các nucleotide trên
đoạn DNA được đọc trình tự. Để huỷ được ATP và các nucleotide tự do còn
thừa sau mỗi lần bổ sung nucleotide, enzyme apyrase cũng được cho vào
giếng phản ứng sau khi tín hiệu phát quang được ghi nhận.
Pyrosequencing là một bước tiến về kỹ thuật trong đọc trình tự, cho

thường được các thế hệ máy Roche 454, Ion Torrent và Illumina s ử dụng.
SBS liên quan đến việc sử dụng một hỗn hợp các dNTP được biến đổi tại vị
trí 2‟. Hỗn hợp này bao gồm các dNTP bổ sung tự nhiên và các dNTP bổ
sung có đánh dấu huỳnh quang. Quá trình xác định trình tự sẽ diễn ra tương
tự như phản ứng PCR thông thường. Đầu tiên một đoạn trình tự mồi nằm
trên đoạn adapter sẽ được gắn vào phần cuối của đoạn gDNA khuôn cần đọc
trình tự. Sau đó, việc xác định trình tự được thực hiện bằng cách gắn lần
lượt từng dNTP bổ sung có đánh dấu huỳnh quangvào phần cuối của trình tự
mồi trên theo chu trình 3 bước:
Một polymerase kết hợp với một dNTP kết thúc có đánh dấu huỳnh
quang và gắn bổ sung với base trên đoạn gen cần đọc trình tự;
Thiết bị sẽ ghi lại hình ảnh, phần mềm sẽ phân tích hình ảnh thu được
để xác định phân tử dNTP nào được kết hợp và từ đó tìm ra được trình tự bổ sung.
Nhóm kết thúc đầu 3‟ và tín hiệu huỳnh quang sẽ được cắt bỏ bằng
phương pháp hóa học. SBS xác định trình tự các đoạn gen theo chiều từ đầu
5‟ đến 3‟.
Quá trình này được lặp lại cho đến khi toàn bộ chiều dài của đoạn gen
được đọc trình tự. Về mặt lý thuyết, độ dài đoạn được đọc bằng SBS có thể
lên đến hàng trăm trình tự.
Nguyên lý thứ hai, đọc trình tự gắn nối (sequencing by ligation, SBL)
được sử dụng ở máy SOLiD. Phương pháp xác định trình tự bằng phản ứng
ghép nối (SBL): được phát minh bởi George Church. SBL đã được sử dụng
Số hóa bởi Trung tâm Học
liệu

tnu.edu.vn/


20


/>

21

PCR mỗi vi hạt chỉ có một loại sản phẩm khuếch đại bám lên. Sau đó, các vi
hạt được loại bỏ nhủ dịch và bơm vào một vi chip có chứa hàng chục ngàn

Số hóa bởi Trung tâm Học
liệu

tnu.edu.vn/


21

đến hàng trăm ngàn giếng kích thước nano (nanowell), kích thước này cho
phép mỗi nanowell chỉ chứa được một vi hạt.
Bước 3: Đọc trình tự dựa trên hai nguyên lý SBS và SBL đã được
trình bày ở trên. Nguyên tắc tương tự với pyrosequencing, tuy nhiên có một
số điểm khác biệt bao gồm:
 Thay vì phải huỷ bỏ các thành phần A T, C, và G còn dư thừa
trong phản ứng trước khi cho thành phần tham gia mới vào thì ở đọc trình
tự thế
hệ mới, thành phần tham gia đọc trình tự dư thừa này được thu hồi sau khi
thu được tín hiệu;
 Tín hiệu tổng hợp được ghi nhận sau mỗi lần bơm các thành
phần tham gia vào có thể là tín hiệu phát quang dựa trên hệ thống
luciferin
luciferase (Roche 454) [9] ,tín hiệu điện do thay đổi pH (Ion-Torrent), tín
hiệu huỳnh quang được đánh dấu trên các nucleotide A, T, C hay G


23

từng cụm. Vì có đến hàng trăm ngàn cụm nên sẽ có hàng trăm ngàn trình tự
sẽ được đọc, tương ứng với hàng trăm ngàn đoạn DNA từ bộ gen sẽ đọc
được. Các trình tự của các đoạn đọc được sẽ được phần mềm của thiết bị nối
lại với nhau bằng cách so sánh trình tự, tìm các đoạn trùng lặp ở hai đầu và
như vậy là sẽ có kết quả của trình tự nguyên bộ gen.
Do phương pháp dựa trên tình tự gen có chi phí thấp và có độ chính
xác cao nên phương pháp này được nghiên cứu và phát triển rộng rãi. Trong
khuôn khổ luận văn này, tôi sẽ đi sâu vào ngh iên cứu các thuật toán theo
phương pháp dựa trên trình tự gen được giải mã từ các thiết bị đọc trình tự
thế hệ mới.
1.2.3 - Định dạng cơ sở dữ liệu
a) Định dạng FASTA
Định dạng FASTA[2] được dùng để mô tả thông tin về một chuỗi
DNA (protein) bao gồm 2 phần: Phần tiêu đề và phần nội dung
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ự
DNA (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...
Trình tự nucleotit hoặc axit amin.Tất cả các kí tự không thuộc về phần
tiêu đề sẽ là dữ liệu mô tả các nucleotit của chuỗi DNA. Phần thông tin này
có thể chứa các dấu cách.
VD: >gi|142864|gb|M10040.1|BACDNAE
encoding DNA primase, complete cds

B.subtilis

dnaE

Dòng 2 là trình tự nucleotit của chuỗi (giống với FASTA)
Dòng 3 bắt đầu với kí tự “+” và có thể bao gồm thêm thông tin để
định danh chuỗi
Dòng 4 là điểm chất lượng khi giải mã các nucletit bởi các thiết bị đọc
trình tự. Chất lượng của trình tự được mã hóa dưới dạng mã ASCII.
VD:
@SRR566546.970 HWUSI-EAS1673_11067_FC7070M:4:1:2299:1109 length=50
TTGCCTGCCTATCATTTTAGTGCCTGTGAGGTGGAGATGTGAGGAT
+
hhhhhhhhhhghhghhhhhfhhhhhfffff

c) Định dạng SAM
Định dạng SAM (Sequence Aligment Map) là chu ẩn lưu trữ dữ liệu
trình tự được lắp ráp hoặc ánh xạ tới tham chiếu được cộng đồng Tin sinh
học trên thế giới thừa nhận và sử dụng phổ biến trong tất cả các phần mềm.
Số hóa bởi Trung tâm Học
liệu

tnu.edu.vn/