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. 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ể. 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: 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/. 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. 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: 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. 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.
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).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 Hầu hết SNP ở người là 2 alen (biallelic SNP), tức là các vị trí SNP chỉ chứa alen tham chiếu và alen biến thể, chiếm đến hơn 99% tổng số SNP [8]. Ngoài ra còn có một số ít các SNP đa alen (multiallelic SNP), là các vị trí SNP chứa alen tham chiếu và 2 hoặc nhiều alen biến thể (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. Dữ liệu haplotype 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 Haplotype là một nhóm các gen trong một sinh vật được di truyền cùng nhau từ bố hoặc mẹ của chúng.
Nhóm gen này được di truyền cùng nhau do liên kết di truyền, hoặc hiện tượng các gen gần nhau trên cùng một nhiễm sắc thể thường được di truyền cùng nhau. Ngoài ra, thuật ngữ "haplotype" cũng còn được đề cập đến là nhóm các SNP được di truyền cùng nhau trong các đoạn DNA [13] (Hình 1. Dữ liệu SNP haplotype này là dữ liệu quan trọng trong các nghiên cứu di truyền quần thể và là dữ liệu đầu vào cho bài toán xây dựng đồ thị ARG. Trong hệ gen người (và các loài lưỡng bội nói chung), mỗi người có 2 haplotype trong một vùng xác định của hệ gen.
Dữ liệu kiểu gen (genotype) Kiểu gen của một cá thể là tập hợp tất cả các alen – những dạng biến dị khác nhau của cùng một gen ở cá thể đó (https://www.com/scitable/definition/genotype- 234). Với các loài lưỡng bội, mỗi vị trí gen c sẽ có 2 alen. Nếu trạng thái alen tại vị trí c là P và Q, kí hiệu "P/Q" chỉ kiểu gen tại vị trí đó. Một vị trí được gọi là đồng hợp tử (homozygous) nếu kiểu gen tại vị trí đó mang 2 alen giống nhau, và được gọi là dị hợp tử (heterozygous) nếu kiểu gen tại vị trí đó mang 2 alen khác nhau.
Ví dụ, ta có kiểu gen tại 5 vị trí tương ứng của 1 cá thể X là: A/A, G/A, C/C, T/T, A/T. Vị trí thứ 1, 3 và 4 được gọi là đồng hợp tử còn vị trí thứ 2 và vị trí thứ 5 được gọi là dị hợp tử. Nếu chỉ biết dữ liệu kiểu gen, ta không thể suy luận được 2 haplotype của cá thể X này vì sẽ có 2 cặp haplotype phù hợp với dữ liệu kiểu gen này do 2 vị trí dị hợp tử: Cặp 1: A G C T A Cặp 2: A A C T A AACTT AGCTT 20 Bài toán tìm haplotype khi cho trước dữ liệu kiểu gen cũng như bài toán xác định kiểu gen và haplotype cho dữ liệu hệ gen thu được từ máy giải trình tự gen thế hệ mới là các bài toán đặc biệt quan trọng trong tin sinh [5,46,51]. Mạng phát sinh loài Theo học thuyết tiến hóa của Darwin tất cả các loài sinh vật đều tiến hóa từ một tổ tiên chung.
Mối quan hệ giữa các loài sinh vật được biểu diễn bởi một cây, gọi là cây phân loài (phylogenetic tree) với cấu trúc như 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. • Mỗi nút lá của cây biểu diễn cho một loài sinh vật hiện tại.
• Mỗi nút bên trong của cây biểu diễn cho một loài sinh vật tổ tiên. Thông thường, chúng ta không có thông tin về các loài sinh vật tổ tiên này.