ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thị Phương Thảo
XÂY DỰNG ĐỒ THỊ TÁI TỔ HỢP DI TRUYỀN
CHO DỮ LIỆU HỆ GEN
LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội – 2020
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thị Phương Thảo
XÂY DỰNG ĐỒ THỊ TÁI TỔ HỢP DI TRUYỀN
CHO DỮ LIỆU HỆ GEN
Chuyên ngành: Khoa học Máy tính
Mã số: 9480101.01
LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC:
1.PGS.TS. Lê Sỹ Vinh
2.PGS.TS. Lương Chi Mai
Hà Nội – 2020
Lời cam đoan
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết
chung với các tác giả khác đều được sự đồng ý của các đồng tác giả trước khi đưa
vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công
bố trong các công trình nào khác.
Tác giả
Nguyễn Thị Phương Thảo
Lời cảm ơn
Luận án được thực hiện tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội,
dưới sự hướng dẫn của PGS. TS. Lê Sỹ Vinh và PGS. TS. Lương Chi Mai.
Tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Lê Sỹ Vinh, PGS. TS. Lương Chi
Mai và TS. Lê Sĩ Quang, những người đã có những định hướng giúp tôi thành công
trong việc nghiên cứu của mình. Các Thầy Cô cũng đã động viên và khích lệ tinh
thần, giúp tôi vượt qua những khó khăn để tôi hoàn thành được luận án này. Tôi
cũng chân thành cảm ơn thầy Hồ Tú Bảo, Thầy đã cho tôi nhiều kiến thức quý báu
về nghiên cứu khoa học. Những sự chỉ bảo quý giá của các Thầy Cô đã giúp tôi
hoàn thành tốt luận án này.
Tôi cũng xin cảm ơn tới các Thầy, Cô thuộc Khoa Công nghệ Thông tin, Trường
Đại học Công nghệ, Đại học Quốc gia Hà Nội đã tạo mọi điều kiện thuận lợi giúp
tôi trong quá trình làm nghiên cứu sinh.
Tôi xin chân thành cảm ơn các đồng nghiệp trong phòng Nhận dạng và Công nghệ
Tri thức, Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt
Nam đã luôn động viên, tạo điều kiện thuận lợi, bố trí thời gian tốt nhất cho tôi
trong suốt quá trình làm nghiên cứu sinh.
Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc tới gia đình và bạn bè, những người đã
cho tôi điểm tựa vững chắc để tôi có được thành công như ngày hôm nay.
2
MỤC LỤC
Lời cam đoan ............................................................................................................... 1
Lời cảm ơn .................................................................................................................. 2
MỤC LỤC ................................................................................................................... 3
Danh mục các ký hiệu và chữ viết tắt ......................................................................... 6
Danh mục các bảng ..................................................................................................... 7
Danh mục các hình vẽ, đồ thị ...................................................................................... 8
Danh mục các thuật toán ........................................................................................... 12
MỞ ĐẦU 13
Chương 1. GIỚI THIỆU ............................................................................................ 16
1.1. Giới thiệu chung ........................................................................................... 16
1.1.1. Hệ gen người ...................................................................................... 16
1.1.2. Mạng phát sinh loài ............................................................................ 21
1.2. Xây dựng đồ thị tái tổ hợp di truyền ........................................................... 23
1.2.1. Sự kiện tái tổ hợp ............................................................................... 23
1.2.2. Đồ thị tái tổ hợp di truyền .................................................................. 25
1.2.3. Bài toán xây dựng đồ thị ARG .......................................................... 32
1.3. Các phương pháp xây dựng đồ thị ARG ..................................................... 35
1.3.1. Các phương pháp xây dựng đồ thị ARG tối thiểu ............................. 35
1.3.2. Các phương pháp xây dựng đồ thị ARG hợp lý ................................ 39
1.3.3. Tổng hợp các phần mềm xây dựng đồ thị ARG ................................ 41
1.4. Ứng dụng ARG trong nghiên cứu tương quan toàn hệ gen......................... 42
3
1.5. Kết luận chương .......................................................................................... 45
Chương 2. THUẬT TOÁN ARG4WG XÂY DỰNG ĐỒ THỊ TÁI TỔ HỢP DI
TRUYỀN HỢP LÝ CHO DỮ LIỆU HỆ GEN........................................ 47
2.1. Giới thiệu ..................................................................................................... 47
2.1.1. Các định nghĩa ................................................................................... 47
2.1.2. Thuật toán Margarita xây dựng đồ thị ARG ...................................... 48
2.2. Thuật toán ARG4WG .................................................................................. 51
2.2.1. Chiến lược tìm đoạn đầu chung dài nhất ........................................... 51
2.2.2. Thuật toán ARG4WG ........................................................................ 54
2.3. Kết quả thực nghiệm.................................................................................... 61
2.3.1. Các kết quả trên dữ liệu thật .............................................................. 61
2.3.2. Các kết quả trên dữ liệu mô phỏng .................................................... 65
2.4. Kết quả ứng dụng ARG4WG vào bài toán tìm vùng gen liên quan đến bệnh
sốt rét ở Châu Phi ......................................................................................... 67
2.5. Kết luận chương .......................................................................................... 72
Chương 3. PHƯƠNG PHÁP TỐI ƯU HÓA SỐ SỰ KIỆN TÁI TỔ HỢP TRONG
QUÁ TRÌNH XÂY DỰNG ĐỒ THỊ ARG ............................................. 75
3.1. Giới thiệu ..................................................................................................... 75
3.2. Một số định nghĩa và khái niệm sử dụng trong các thuật toán .................... 76
3.3. Hạn chế của thuật toán ARG4WG .............................................................. 78
3.4. Thuật toán REARG ..................................................................................... 79
3.4.1. Động cơ nghiên cứu ........................................................................... 79
3.4.2. Thuật toán REARG ............................................................................ 80
4
3.5. Thuật toán GAMARG ................................................................................. 83
3.5.1. Động cơ nghiên cứu ........................................................................... 83
3.5.2. Thuật toán GAMARG........................................................................ 83
3.6. Kết quả thực nghiệm.................................................................................... 88
3.6.1. Kết quả trên các tập dữ liệu nhỏ ........................................................ 89
3.6.2. Các kết quả trên các tập dữ liệu từ dự án 1kGP ................................. 90
3.7. Kết luận chương .......................................................................................... 98
KẾT LUẬN ............................................................................................................. 100
DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN
ĐẾN LUẬN ÁN .................................................................................... 102
TÀI LIỆU THAM KHẢO ....................................................................................... 103
5
Danh mục các ký hiệu và chữ viết tắt
D
Tập các trình tự
N
Số lượng trình tự trong một tập các trình tự
m
độ dài của trình tự
Sx
Trình tự thứ x trong một tập các trình tự
Sx[i]
Giá trị của Sx tại vị trí thứ i
ARG
Đồ thị tái tổ hợp di truyền
1KGP
Dự án 1000 hệ gen
GWAS
Nghiên cứu tương quan toàn hệ gen
SNP
Đa hình đơn nucleotit
MRCA
Tổ tiên chung gần nhất
CwR
Mô hình kết hợp và tái tổ hợp
STT
Số thứ tự
RF
Khoảng cách Robinson-Fould
6
Danh mục các bảng
Bảng 1.1: Các phần mềm xây dựng đồ thị ARG tiêu biểu........................................41
Bảng 2.1: Tập dữ liệu trích xuất từ dự án 1000 hệ gen người. .................................62
Bảng 3.1: Tập dữ liệu từ dự án 1kGP. ......................................................................89
Bảng 3.2: Các kết quả của các thuật toán khác nhau trên các tập dữ liệu nhỏ. ........89
Bảng 3.3: Số sự kiện tái tổ hợp ít nhất được tìm thấy bởi 5 thuật toán cho 100 trình
tự của (a) DS1, (b) DS2 và (c) DS3. .........................................................................91
Bảng 3.4: Số sự kiện tái tổ hợp ít nhất được tìm thấy bởi 5 thuật toán cho 200 trình
tự của (a) DS1, (b) DS2 và (c) DS3. .........................................................................92
Bảng 3.5: Trung bình thời gian chạy (giây) của 5 thuật toán cho 100 trình tự của các
tập dữ liệu (a) DS1, (b) DS2, và (c) DS3. .................................................................95
Bảng 3.6: Trung bình thời gian chạy (giây) của 5 thuật toán cho 200 trình tự của các
tập dữ liệu (a) DS1, (b) DS2, và (c) DS3. .................................................................97
7
Danh mục các hình vẽ, đồ thị
Hình 1.1: Cấu trúc hệ gen người. Hệ gen người gồm 23 cặp nhiễm sắc thể, có
khoảng 3 tỉ phân tử DNA, khoảng 20.000 đến 25.000 gen. Nguồn hình:
https://genomainternational.com/introduction-to-genomics/. ...................................16
Hình 1.2: Các kiểu biến thể trình tự: (a) Thay thế một cặp bazơ đơn. Trong ví dụ,
biến thể xuất hiện ở 2 vị trí so với trình tự tham chiếu, đó là thay thế nucleotit T↔A
và G↔A. (b) Chuỗi GCA được chèn vào so với trình tự tham chiếu. (c) Chuỗi CG
bị xóa so với trình tự tham chiếu...............................................................................17
Hình 1.3: Các loại biến thể cấu trúc: xóa, thêm, lặp, đảo hay lặp nhiều lần 1 đoạn
DNA. Đoạn đột biến cấu trúc có kích thước lớn hơn 1kb. .......................................18
Hình 1.4: Ví dụ dữ liệu SNP chứa biến thể 2 alen và nhiều alen. Có 8 vị trí SNP đều
là 2 alen, gồm alen tham chiếu và 1 alen biến thể, ví dụ như A và G ở vị trí 1; T và
C ở vị trí 2. Chỉ có vị trí 7 là 3 alen: alen tham chiếu (G) và 2 alen biến thể C, T. ..19
Hình 1.5: Ví dụ 4 haplotype của 4 cá thể trên một vùng gen. Một haplotype được
tạo thành từ sự kết hợp của các SNP được di truyền cùng nhau trong các đoạn DNA.
...................................................................................................................................19
Hình 1.6: Cây phân loài biểu diễn mối quan hệ tiến hóa của một số loài linh trưởng.
Đười ươi và Khỉ đột rẽ nhánh sớm hơn các loài linh trưởng khác. Con người rẽ ra
một nhánh riêng và nhánh còn lại cho ra Tinh tinh và vượn Bonobo. ......................21
Hình 1.7: Khái quát hóa các mạng phát sinh loài điển hình [36]..............................23
Hình 1.8: Hai hiện tượng tái tổ hợp phổ biến của người: (a) trao đổi chéo và (b)
chuyển đổi gen. .........................................................................................................24
Hình 1.9: Biến đổi dữ liệu SNP thành dạng nhị phân. Vị trí có giá trị giống với tham
chiếu là 0, giá trị khác tham chiếu là 1. .....................................................................28
8
Hình 1.10: Đồ thị ARG cho tập dữ liệu M gồm 7 trình tự độ dài 5 [26]. Trình tự tổ
tiên là “00000”; 5 sự kiện đột biến tại các vị trí tương ứng (1,2,3,4,5) được ghi trên
các cạnh xảy ra đột biến của đồ thị; 2 sự kiện tái tổ hợp xảy ra tại vị trí 3 và 4. ......29
Hình 1.11: Điểm cắt tái tổ hợp. .................................................................................30
Hình 1.12: Một ví dụ đồ thị ARG cho 4 trình tự với các ký hiệu: ■: trạng thái di
truyền, ◘: trạng thái di truyền đột biến, □: trạng thái không xác định. .....................31
Hình 1.13: Các cây thành phần (đường đậm nét) của đồ thị ARG trong Hình 1.12.
Nguồn hình [43]. .......................................................................................................33
Hình 1.14: (a) Ví dụ cặp vị trí tương thích: cặp vị trí này chỉ chứa 3 loại giao tử và
có thể có được từ 1 tổ tiên chung thông qua 2 sự kiện đột biến. (b) Cặp vị trí không
tương thích: cặp vị trí chứa 4 loại giao tử và trong trường hợp này phải có ít nhất 1
sự kiện tái tổ hợp xảy ra dưới giả định các vị trí vô hạn (kí hiệu * biểu thị vị trí
không có thông tin). ..................................................................................................36
Hình 1.15: Một cây có nốt sùi cho tập trình tự giống với tập trong Hình 1.10 với 2
nốt sùi tương ứng với 2 chu trình tái tổ hợp không chung nút với nhau [27]. ..........38
Hình 1.16: (a) Đồ thị ARG cho tập 4 trình tự, trong đó trình tự s1, s2 là từ 2 cá thể
khỏe mạnh, trình từ s3, s4 là từ 2 cá thể bị bệnh. (b) Đột biến 3 (vùng khoanh tròn)
trên cây biên tại vị trí 3 của đồ thị ARG trong (a) cho ra sự phân biệt rõ nhất giữa
các trình tự bệnh và trình tự không bệnh. .................................................................44
Hình 2.1: Lưu đồ thuật toán Margarita. ....................................................................49
Hình 2.2: Vấn đề trong việc thực hiện sự kiện tái tổ hợp của Margarita. Hai trình tự
S1 và S2 với đoạn chung dài nhất giữa hai trình tự được biểu diễn bằng đoạn màu
đen. Thuật toán thực hiện lần lượt 2 sự kiện tái tổ hợp R1 và R2 trên trình tự S1 để
sinh ra 3 trình tự con S11, S12 và S13. Sau đó, trình tự con chứa đoạn chung dài nhất
S13 sẽ được kết hợp với S2. Vì vậy, khi đoạn chung dài nhất được tìm thấy bên trong
9
trình tự, thuật toán phải thực hiện 2 sự kiện tái tổ hợp trên một trình tự và từ 2 trình
tự ban đầu (S1 và S2) sẽ thành 3 trình tự ở thế hệ tiếp theo (S11, S12 và S' (S' = S2)). 50
Hình 2.3: Tất cả các trình tự con từ phía bên trái của s mà có thể kết hợp với một
trình tự trong D là một tập con của đoạn bên trái dài nhất của s ( sl ).......................52
Hình 2.4: Phân tách s bằng cách chọn các đoạn chung dài nhất trong s để kết hợp
với các trình tự trong D có thể không dẫn tới số cực tiểu sự kiện tái tổ hợp. ...........53
Hình 2.5: Sự kiện tái tổ hợp được biểu thị trong thuật toán ARG4WG. (a) Xét 2
trình tự S1 và S2, các đoạn đầu chung của 2 trình tự từ phía bên trái (hình lượn sóng)
và từ phía bên phải (màu đen) được xác định. (b) Với 1 tập 3 trình tự S1, S2 và S3,
các đoạn đầu chung của mỗi cặp được tính toán (hình lượn sóng) và đoạn đầu chung
dài nhất được xác định được mô tả bằng đoạn màu đen giữa trình tự S1 và S2. (c)
Một sự kiện tái tổ hợp được thực hiện trên trình tự S1 để sinh ra 2 trình tự con S11 và
S12. S12 chứa đoạn đầu chung dài nhất sau đó sẽ được kết hợp với S2. Như vậy,
ARG4WG luôn thực hiện 1 tái tổ hợp trên 1 trình tự và từ 2 trình tự ban đầu (S1, S2)
sẽ thành 2 trình tự ở thế hệ tiếp theo (S11, S’), trong đó S’ = S2 và S11 có ít vật liệu di
truyền hơn S1. ............................................................................................................55
Hình 2.6: Trung bình thời gian chạy của Margarita, Margarita1.0 và ARG4WG cho:
(a) 500 haplotype; (b) 1000 haplotype; và (c) 2000 haplotype. ................................63
Hình 2.7: Trung bình số sự kiện tái tổ hợp của Margarita, Margarita1.0 và
ARG4WG cho: (a) 500 haplotype; (b) 1000 haplotype; và (c) 2000 haplotype. ......65
Hình 2.8: Khoảng cách RF của các cây được tạo ra bởi thuật toán Margarita và
ARG4WG so với các cây đúng tương ứng trên các khoảng tỉ lệ đột biến và tái tổ
hợp khác nhau. ..........................................................................................................67
Hình 2.9: Sự tương quan đến bệnh từ 106 kiểm định hoán vị trên: (A) 10 ARG xây
dựng trên toàn bộ NST 11; (B) 30 ARG xây dựng trên vùng 5000 SNP quanh gen
10
HBB; và (C) Tổng hợp kết quả cho các thực nghiệm trên vùng 1000 SNP quanh gen
HBB. ..........................................................................................................................70
Hình 2.10: Sự tương quan với bệnh khi sử dụng thuật toán Margarita trên vùng 4M6M quanh gen HBB. .................................................................................................72
Hình 3.1: Một ví dụ đồ thị ARG tối thiểu cho tập dữ liệu D(5) gồm 5 trình tự độ dài
5. Xét ngược chiều thời gian, thứ tự thực hiện các sự kiện đột biến, kết hợp hay tái
tổ hợp để xây dựng đồ thị ARG được đánh số trong hình tròn. Trong ví dụ này, sự
kiện tái tổ hợp được thực hiện đầu tiên trên trình tự “01010” sinh ra 2 trình tự
“01***” và “**010”. Tiếp theo là sự kiện kết hợp trình tự “**010” và “00010”
thành trình tự “00010”. Sự kiện đột biến được thực hiện sau đó biến đổi trình tự
“00010” thành trình tự “00000”. Quá trình xây dựng đồ thị ARG được tiếp tục thực
hiện cho tới khi tổ tiên chung “10001” được tìm thấy. .............................................77
Hình 3.2: Quá trình xây dựng đồ thị ARG cho tập dữ liệu D={S1,S2,S3,S4,S5} của
thuật toán ARG4WG. 𝑅𝑖, 𝑗 biểu thị một sự kiện tái tổ hợp giữa vị trí i và vị trí j; 𝐶𝑥
biểu thị sự kiện kết hợp thứ x; 𝑀𝑖 biểu thị một sự kiện đột biến tại vị trí i. .............79
Hình 3.3: Thuật toán ARG4WG xác định được 3 cặp ứng cử viên có cùng đoạn đầu
chung dài nhất cho tập 5 trình tự như trong các khung hình chữ nhật. Một trong 3
cặp sẽ được chọn ngẫu nhiên để thực hiện tái tổ hợp. ..............................................80
Hình 3.4: Cho tập dữ liệu D={S1,S2,S3,S4,S5}, lựa chọn thực hiện tái tổ hợp trên trình
tự S4 giữa vị trí 1 và vị trí 2 dẫn đến việc phải thực hiện thêm 1 sự kiện tái tổ hợp
nữa để phá vỡ cặp vị trí không tương thích (1,2). .....................................................84
Hình 3.5: Lưu đồ thuật toán GAMARG. ..................................................................85
Hình 3.6: Số sự kiện tái tổ hợp ít nhất được tìm thấy bởi 3 thuật toán ARG4WG,
REARG và GAMARG cho 100 và 200 trình tự với 2000, 5000, và 10000 SNP của
tập DS1, DS2, và DS3. ..............................................................................................94
11
Danh mục các thuật toán
Thuật toán 2.1: Thuật toán ARG4WG xây dựng một ARG từ một tập trình tự D cho
trước. .........................................................................................................................60
Thuật toán 3.1: Thuật toán REARG. .........................................................................81
Thuật toán 3.2: Thuật toán GAMARG. ....................................................................87
12
MỞ ĐẦU
Những thành tựu gần đây trong công nghệ giải trình tự hệ gen thế hệ mới (Next
Generation Sequencing - NGS) đã giảm đáng kể chi phí giải trình tự toàn bộ hệ gen
và dẫn đến sự gia tăng nhanh chóng về số lượng chuỗi DNA và cả hệ gen. Do đó,
việc phát triển các mô hình và phương pháp tính toán mới là vấn đề thời sự đang
được các nhà tin sinh học quan tâm để có thể quản lý, phân tích và khai thác bộ dữ
liệu lớn các trình tự này một cách hiệu quả.
Những dữ liệu này đại diện cho một nguồn thông tin rất hữu ích và đặt ra các vấn đề
tính toán mới trong các nghiên cứu trên toàn hệ gen, điển hình là các nghiên cứu về
phân bố của các biến thể di truyền trong một quần thể hay xác định các vùng gen có
tác động và có ý nghĩa về mặt sinh học đối với các đặc điểm quan trọng mà ta quan
tâm. Để giải quyết những bài toán này đòi hỏi nhiều phương pháp mới, trong đó có
những hướng đi mới sử dụng lý thuyết đồ thị và thuật toán để mô hình hóa và tính
toán các mô hình tiến hóa trong quần thể. Đáng chú ý trong số đó là đồ thị tái tổ hợp
di truyền (Ancestral Recombination Graph - ARG), một công cụ quan trọng trong
nghiên cứu di truyền quần thể và các bài toán liên quan đến tìm sự đa dạng trong hệ
gen [1,58].
Với một tập các chuỗi nhiễm sắc thể, đồ thị ARG đầy đủ sẽ mô tả một cách chi tiết
lịch sử di truyền, mối quan hệ của chúng với nhau và với một tổ tiên chung
(common ancestor) thông qua ba sự kiện: đột biến (mutation), tái tổ hợp
(recombination) và kết hợp (coalescence). Trong quá trình xây dựng đồ thị ARG, sự
kiện tái tổ hợp và sự kiện đột biến là 2 sự kiện cốt lõi ảnh hưởng tới đồ thị kết quả,
từ đó ảnh hưởng trực tiếp tới các ứng dụng liên quan như tìm vùng gen liên quan
đến bệnh, đột biến gây bệnh, đặc trưng của quần thể quan sát, … Tuy nhiên, số sự
kiện tái tổ hợp và sự kiện đột biến cũng như vị trí thực sự xảy ra trong quá trình tiến
hóa là không biết trước. Do đó, chúng ta không thể biết được ARG thực sự mà
chúng ta chỉ có thể suy diễn chúng từ dữ liệu với các giả định tối ưu số sự kiện tái tổ
hợp và sự kiện đột biến nhằm có được ARG với các sự kiện sát nhất với thực tế.
13
Nhiều phương pháp xây dựng đồ thị ARG đã được đề xuất [26], tập trung vào 2
cách tiếp cận chính: (1) xây dựng đồ thị ARG tối thiểu (minimal ARG), tức là đồ thị
có chính xác số sự kiện tái tổ hợp nhỏ nhất; và (2) xây dựng đồ thị ARG hợp lý
(plausible ARG), tức là đồ thị có số sự kiện tái tổ hợp tùy thuộc vào thuật toán xấp
xỉ chúng. Tuy nhiên, các phương pháp xây dựng đồ thị ARG hiện tại vẫn gặp những
hạn chế sau:
-
Đa số các phương pháp xây dựng đồ thị ARG mới chỉ giới hạn với những tập dữ
liệu nhỏ và vừa hàng trăm trình tự [52,58,62].
-
Các phương pháp xây dựng đồ thị ARG với hàm mục tiêu có chính xác số sự
kiện tái tổ hợp ít nhất hiện thời còn tốn rất nhiều thời gian và chỉ khả thi với
những tập dữ liệu rất nhỏ chứa vài chục trình tự [62,71].
Ngày nay, những thành tựu trong công nghệ giải trình tự gen thế hệ mới, sự phát
triển và ngày càng hoàn thiện của các thư viện đặc tả biến dị di truyền trong quần
thể người đã tạo tiền đề cho các nghiên cứu trên toàn hệ gen. Để có thể ứng dụng
được vào các nghiên cứu về biến thể di truyền liên quan đến bệnh ở người một cách
hiệu quả, các phương pháp phải có khả năng tính toán được trên dữ liệu liên quan
đến hàng nghìn hệ gen. Từ đó, mục tiêu và kết quả của luận án đã đạt được là:
1. Nghiên cứu các phương pháp xây dựng đồ thị ARG hiện tại, từ đó đề xuất thuật
toán gần đúng xây dựng đồ thị ARG cho hàng nghìn trình tự, thậm chí hàng
nghìn hệ gen nhằm ứng dụng hiệu quả vào các bài toán thực tế trên các tập dữ
liệu lớn.
2. Đề xuất thuật toán xây dựng đồ thị ARG với hàm mục tiêu tối thiểu hóa số sự
kiện tái tổ hợp trong quá trình xây dựng đồ thị ARG bằng việc kết hợp thuật
toán đề xuất trong (1) với một số đặc trưng của dữ liệu và kĩ thuật tối ưu được sử
dụng trong các phương pháp tìm cận dưới tái tổ hợp và các phương pháp xây
dựng đồ thị ARG tối thiểu đã có.
14
Các kết quả của luận án đã được công bố trong 1 bài tạp chí ISI (công trình khoa
học số 1) và 2 báo cáo hội nghị quốc tế (công trình khoa học số 2 và 3). Ngoài phần
kết luận, luận án được tổ chức như sau:
Chương 1 đầu tiên giới thiệu khái quát về hệ gen người và các mạng phát sinh loài
(phylogenetic networks). Sau đó là phần giới thiệu về bài toán xây dựng đồ thị
ARG. Phần cuối của chương trình bày các cách tiếp cận giải bài toán xây dựng đồ
thị ARG và ứng dụng của ARG trong nghiên cứu tương quan toàn hệ gen.
Chương 2 đề xuất một thuật toán xây dựng đồ thị ARG cho dữ liệu lớn hàng nghìn
trình tự độ dài hệ gen người. Để làm được điều đó, chúng tôi đưa ra các nhược điểm
của các cách tiếp cận hiện có, đặc biệt là những hạn chế trong thuật toán Margarita
xây dựng đồ thị ARG hợp lý được đề xuất bởi Minichiello và Durbin [52], từ đó
đưa ra thuật toán đề xuất nhằm khắc phục các nhược điểm đó. Các kết quả thực
nghiệm ở phần sau của chương đã chứng tỏ hiệu quả của thuật toán đề xuất. Phần
cuối của chương giới thiệu kết quả ứng dụng thuật toán đề xuất vào bài toán tìm
vùng gen liên quan đến bệnh sốt rét ở Châu Phi trên tập dữ liệu lớn gồm 5560 trình
tự trên toàn nhiễm sắc thể 11. Các kết quả trong phần này đã khẳng định thêm hiệu
quả, khả năng ứng dụng của thuật toán đề xuất trong các bài toán thực tế trên dữ
liệu lớn.
Chương 3 của luận án giới thiệu các phương pháp nhằm cực tiểu hóa số sự kiện tái
tổ hợp trong quá trình xây dựng đồ thị ARG. Cụ thể, chúng tôi đề xuất hai phương
pháp: (1) kết hợp một số đặc trưng của dữ liệu; (2) kết hợp kĩ thuật sử dụng trong
các phương pháp xây dựng đồ thị ARG tối thiểu với chiến lược thực hiện sự kiện tái
tổ hợp đề xuất trong chương 2 để tối ưu hóa số sự kiện tái tổ hợp. Các thực nghiệm
trên các bộ dữ liệu khác nhau đã chứng tỏ hiệu quả của các phương pháp đề xuất.
15
Chương 1. GIỚI THIỆU
1.1. Giới thiệu chung
Trong phần này luận án sẽ giới thiệu về hệ gen người, cụ thể là cấu trúc bộ gen
người, các nguyên nhân dẫn tới các biến thể di truyền ở người, các loại biến thể di
truyền phổ biến và một số loại dữ liệu hệ gen quan trọng. Luận án cũng giới thiệu
sơ lược về các loại mạng phát sinh loài (phylogenetic networks), một công cụ quan
trọng để biểu diễn các mối quan hệ tiến hóa trong nghiên cứu di truyền quần thể.
1.1.1. Hệ gen người
Bộ gen người là tất cả vật liệu di truyền của một người được di truyền từ thế hệ này
sang thế hệ khác. Bộ gen chứa các gen, mỗi gen là một đoạn DNA
(deoxyribonucleic acid) mã hóa cho những sản phẩm riêng lẻ như các mRNA được
sử dụng trực tiếp cho tổng hợp các enzim, các protein cấu trúc hay các chuỗi
polypeptide để gắn lại tạo ra protein có hoạt tính sinh học. Các gen được đóng gói
trong nhiễm sắc thể, nhiễm sắc thể nằm trong nhân tế bào, mỗi nhân tế bào có 23
cặp nhiễm sắc thể (Hình 1.1) [54].
Hình 1.1: Cấu trúc hệ gen người. Hệ gen người gồm 23 cặp nhiễm sắc thể, có khoảng 3 tỉ
phân tử DNA, khoảng 20.000 đến 25.000 gen. Nguồn hình:
https://genomainternational.com/introduction-to-genomics/.
16
Chuỗi DNA người có cấu trúc xoắn kép, gồm 2 chuỗi DNA đơn cuộn xoắn vào
nhau. Tại mỗi vị trí cụ thể trên một chuỗi DNA đơn là một trong 4 loại nucleotit: A,
T, C, hoặc G. Hệ gen người có khoảng 3 tỉ phân tử DNA, trong đó có các vùng chứa
thông tin mã hóa protein gọi là các gen. Con người có từ 20.000 đến 25.000 gen.
Hầu hết các gen ở mọi người là như nhau, nhưng có khoảng 0.1% vị trí mà các
nucleotit là khác nhau giữa 2 người gọi là các biến thể di truyền. Biến thể di truyền
giúp cho mỗi người chúng ta là một cá thể duy nhất, không giống bất kì ai [54].
Đột biến và tái tổ hợp là 2 nguyên nhân chính của biến thể di truyền [22]. Đột biến
là nguồn gốc của biến thể mới, xảy ra khi có lỗi trong quá trình sao chép DNA mà
không được sửa chữa bởi các enzyme sửa chữa DNA. Trong khi tái tổ hợp di truyền
là nguyên nhân chính của biến thể di truyền ở thế hệ con cái. Mỗi người có sự pha
trộn các vật liệu di truyền từ cha mẹ. Tái tổ hợp góp phần vào biến đổi gen bằng
cách xáo trộn DNA của cha mẹ và tạo ra các tổ hợp biến thể mới. Chi tiết về sự kiện
tái tổ hợp được giới thiệu trong Mục 1.2.1.
Hình 1.2: Các kiểu biến thể trình tự: (a) Thay thế một cặp bazơ đơn. Trong ví dụ, biến thể
xuất hiện ở 2 vị trí so với trình tự tham chiếu, đó là thay thế nucleotit T↔A và G↔A. (b)
Chuỗi GCA được chèn vào so với trình tự tham chiếu. (c) Chuỗi CG bị xóa so với trình tự
tham chiếu.
Biến thể di truyền có thể được phân loại thành biến thể trình tự và biến thể cấu trúc
[20,57]. Các biến thể trình tự gồm dạng thay thế một cặp bazơ (base pair, viết tắt là
bp) hay còn gọi là đa hình đơn nucleotit (Single Nucleotide Polymorphisms – SNP)
và xóa hoặc thêm một đoạn DNA kích thước nhỏ hơn 1kb (1kb = 1000 bp) (Hình
1.2). Các trường hợp chèn và xóa phạm vi lớn hơn, cũng như các trường hợp đảo
17
ngược (inversion) hay lặp lại 2 lần (duplication) hoặc nhiều lần (copy-number
variant) 1 đoạn DNA được gọi chung là các biến thể cấu trúc (Hình 1.3). Biến thể
cấu trúc thường làm thay đổi cấu trúc của hệ gen, cấu trúc của protein tương ứng.
Đoạn DNA biến thể có kích thước từ 1kb đến hơn 5Mb (1Mb = 106 bp).
Hình 1.3: Các loại biến thể cấu trúc: xóa, thêm, lặp, đảo hay lặp nhiều lần 1 đoạn DNA.
Đoạn đột biến cấu trúc có kích thước lớn hơn 1kb.
Biến thể SNP là loại biến thể di truyền phổ biến nhất trong hệ gen người. Một biến
đổi điểm có tần số xuất hiện trong quần thể lớn hơn 1% thì được gọi là SNP.
Dữ liệu SNP
Các dự án hệ gen người [12,13,40] đã chỉ ra có khoảng 10 triệu SNP trong hệ gen
người và chúng đóng vai trò như là các dấu hiệu sinh học giúp phân biệt sự khác
nhau giữa người với người. Chúng giải thích cho sự khác nhau về màu mắt, màu
tóc, nhóm máu của con người. Một số SNP có thể ảnh hưởng tới nguy cơ phát triển
một số bệnh hay rối loạn nào đó. Dữ liệu SNP đóng một vai trò đặc biệt quan trọng
trong các nghiên cứu tương quan toàn hệ gen (Genome-Wide Association Study –
GWAS) nhằm so sánh các vùng trong hệ gen người để định vị vùng gen và các biến
thể di truyền có ảnh hưởng tới sức khỏe hay liên quan đến bệnh quan tâm, từ đó
giúp cho quá trình chẩn đoán và điều trị [4,6,49,67].
18
- Xem thêm -