Luận án Tiến sĩ Công nghệ thông tin: Xây dựng đồ thị tái tổ hợp di truyền cho dữ liệu hệ gen

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:112

Thêm vào BST

Báo xấu

39
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu của luận án là 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. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Công nghệ thông tin: 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 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 4M- 6M 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