Luận án Xây dựng đồ thị tái tổ hợp di truyền cho dữ liệu hệ gen
ĐẠ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
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
3
1.5. Kết luận chương ..........................................................................................45
2.1. Giới thiệu.....................................................................................................47
2.1.1. Các định nghĩa ...................................................................................47
2.2. Thuật toán ARG4WG..................................................................................51
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
sốt rét ở Châu Phi.........................................................................................67
2.5. Kết luận chương ..........................................................................................72
3.1. Giới thiệu.....................................................................................................75
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.6. Kết quả thực nghiệm....................................................................................88
3.7. Kết luận chương ..........................................................................................98
KẾT LUẬN.............................................................................................................100
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ự
độ dài của trình tự
m
Sx
Trình tự thứ x trong một tập các trình tự
Giá trị của Sx tại vị trí thứ i
Đồ thị tái tổ hợp di truyền
Dự án 1000 hệ gen
Sx[i]
ARG
1KGP
GWAS
SNP
MRCA
CwR
STT
RF
Nghiên cứu tương quan toàn hệ gen
Đa hình đơn nucleotit
Tổ tiên chung gần nhất
Mô hình kết hợp và tái tổ hợp
Số thứ tự
Khoảng cách Robinson-Fould
6
Danh mục các bảng
Bảng 3.1: Tập dữ liệu từ dự án 1kGP. ......................................................................89
tự của (a) DS1, (b) DS2 và (c) DS3. .........................................................................91
tự của (a) DS1, (b) DS2 và (c) DS3. .........................................................................92
tập dữ liệu (a) DS1, (b) DS2, và (c) DS3..................................................................95
tập dữ liệu (a) DS1, (b) DS2, và (c) DS3..................................................................97
7
Danh mục các hình vẽ, đồ thị
bị xóa so với trình tự tham chiếu...............................................................................17
chuyển đổi gen. .........................................................................................................24
chiếu là 0, giá trị khác tham chiếu là 1......................................................................28
8
Hình 1.11: Điểm cắt tái tổ hợp..................................................................................30
Nguồn hình [43]. .......................................................................................................33
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
9
hiện cho tới khi tổ tiên chung “10001” được tìm thấy..............................................77
cặp sẽ được chọn ngẫu nhiên để thực hiện tái tổ hợp. ..............................................80
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
tập DS1, DS2, và DS3...............................................................................................94
11
Danh mục các thuật toán
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
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:
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)
17
ngược (inversion) hay lặp lại 2 lần (duplication) hoặc nhiều lần (copy-number
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
Tải về để xem bản đầy đủ
112 trang
13620
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận án Xây dựng đồ thị tái tổ hợp di truyền cho dữ liệu hệ gen", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- luan_an_xay_dung_do_thi_tai_to_hop_di_truyen_cho_du_lieu_he.pdf
