Xây dựng đồ thị tái tổ hợp di truyền cho dữ liệu hệ gen

ĐẠI HỌC YALE 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 – 19 ĐẠI HỌC YALE 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. TƯ SONG QUÂN 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ả 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. Lê Sỹ Vinh và PGS. Lương Chi Mai. Tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS.

Lê Sỹ Vinh, PGS. 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. 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 chung.

Hệ gen người. Mạng phát sinh loài. Xây dựng đồ thị tái tổ hợp di truyền. Sự kiện tái tổ hợp.

Đồ thị tái tổ hợp di truyền. Bài toán xây dựng đồ thị ARG. Các phương pháp xây dựng đồ thị ARG. Các phương pháp xây dựng đồ thị ARG tối thiểu.

Các phương pháp xây dựng đồ thị ARG hợp lý. Tổng hợp các phần mềm xây dựng đồ thị ARG. Ứng dụng ARG trong nghiên cứu tương quan toàn hệ gen. Kết luận chương.

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. Thuật toán Margarita xây dựng đồ thị ARG. Thuật toán ARG4WG. Chiến lược tìm đoạn đầu chung dài nhất.

Thuật toán ARG4WG. Kết quả thực nghiệm. Các kết quả trên dữ liệu thật. Các kết quả trên dữ liệu mô phỏng.

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. Kết luận chương. 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. Một số định nghĩa và khái niệm sử dụng trong các thuật toán.

Hạn chế của thuật toán ARG4WG. Thuật toán REARG. Động cơ nghiên cứu. Thuật toán REARG.

Thuật toán GAMARG. Động cơ nghiên cứu. Thuật toán GAMARG. Kết quả thực nghiệm.

Kết quả trên các tập dữ liệu nhỏ. Các kết quả trên các tập dữ liệu từ dự án 1kGP. Kết luận chương. 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.1: Tập dữ liệu trích xuất từ dự án 1000 hệ gen người.1: Tập dữ liệu từ dự án 1kGP.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ỏ.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.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.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.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. Nguồn hình: https://genomainternational.com/introduction-to-genomics/.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.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.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.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.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.7: Khái quát hóa các mạng phát sinh loài điển hình [36].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.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.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.11: Điểm cắt tái tổ hợp.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.13: Các cây thành phần (đường đậm nét) của đồ thị ARG trong 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.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].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.1: Lưu đồ thuật toán Margarita.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)).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 ).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.5: Sự kiện tái tổ hợp được biểu thị trong thuật toán ARG4WG.

(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.6: Trung bình thời gian chạy của Margarita, Margarita1.