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

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.0 và ARG4WG cho: (a) 500 haplotype; (b) 1000 haplotype; và (c) 2000 haplotype.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.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.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.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.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.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.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.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).5: Lưu đồ thuật toán GAMARG.