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

Xây dựng đồ thị tái tổ hợp di truyền từ dữ liệu hệ gen. Khám phá phương pháp phân tích hệ gen tiên tiến, ứng dụng trong nghiên cứu và chẩn đoán bệnh.

• Người hướng dẫn: Tư Song Quân
• Trường học: Đại học Công nghệ, Đại học Quốc gia Hà Nội
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Xây dựng đồ thị tái tổ hợp di truyền cho dữ liệu hệ gen
• Loại tài liệu: Luận án tiến sĩ
• Năm xuất bản: 2020
• Địa điểm: Hà Nội

Tóm tắt

I. Đồ thị tái tổ hợp di truyền GRG Tổng quan Giá trị

Đồ thị tái tổ hợp di truyền (Genetic Recombination Graph - GRG), hay còn gọi là đồ thị tái tổ hợp, là một công cụ mạnh mẽ trong tin sinh học và phân tích di truyền. Nó biểu diễn lịch sử tiến hóa của một tập hợp các chuỗi DNA, cho thấy mối quan hệ tổ tiên và quá trình tái tổ hợp di truyền đã diễn ra. GRG không chỉ là một sơ đồ; nó là một bản đồ di truyền, tiết lộ cách các đoạn DNA được trao đổi và kết hợp qua các thế hệ. GRG có vai trò quan trọng trong việc giải quyết các vấn đề phức tạp như xác định các vùng gen liên quan đến bệnh, nghiên cứu biến dị di truyền và hiểu rõ hơn về cơ chế tái tổ hợp. Việc xây dựng đồ thị GRG từ dữ liệu bộ gen là một thách thức lớn, đòi hỏi các thuật toán và phương pháp tính toán phức tạp. Nó cho phép chúng ta tái hiện lại các sự kiện di truyền đã xảy ra trong quá khứ, giúp giải mã những bí ẩn của sự sống.

1.1. Định nghĩa và vai trò của Đồ thị tái tổ hợp

Đồ thị tái tổ hợp, hay Ancestral Recombination Graph (ARG), là một đồ thị có hướng mô tả lịch sử tổ tiên của một tập hợp các chuỗi DNA. Nó bao gồm các nút đại diện cho các cá thể (tổ tiên và hậu duệ) và các cạnh đại diện cho các sự kiện di truyền như đột biến và tái tổ hợp. Vai trò chính của GRG là cung cấp một cái nhìn toàn diện về lịch sử tiến hóa của các chuỗi DNA, cho phép các nhà khoa học nghiên cứu các quá trình di truyền phức tạp và xác định các yếu tố ảnh hưởng đến sự đa dạng di truyền. Nó đóng vai trò quan trọng trong việc phân tích bộ gen.

1.2. Mối liên hệ giữa GRG và Tái tổ hợp di truyền

Tái tổ hợp di truyền là quá trình trao đổi vật liệu di truyền giữa hai nhiễm sắc thể, tạo ra sự kết hợp mới của các alen. GRG mô hình hóa quá trình này bằng cách biểu diễn các sự kiện tái tổ hợp dưới dạng các nút đặc biệt trên đồ thị. Mỗi nút tái tổ hợp đại diện cho một sự kiện trao đổi vật liệu di truyền giữa hai tổ tiên, tạo ra một hậu duệ mang thông tin di truyền từ cả hai. Sự kết hợp Tái tổ hợp di truyền cho phép xây dựng cấu trúc đồ thị. Mô hình hóa di truyền này giúp các nhà khoa học xác định các vùng gen dễ bị tái tổ hợp và nghiên cứu tác động của tái tổ hợp lên sự tiến hóa của bộ gen.

1.3. Ứng dụng tiềm năng của Đồ thị tái tổ hợp trong nghiên cứu

GRG có nhiều ứng dụng tiềm năng trong nghiên cứu di truyền, bao gồm xác định các vùng gen liên quan đến bệnh, nghiên cứu biến dị di truyền và hiểu rõ hơn về cơ chế tái tổ hợp. Nó cũng có thể được sử dụng để phân tích phả hệ, phân tích liên kết và phát hiện đột biến. Ngoài ra, GRG còn có thể giúp các nhà khoa học mô hình hóa sự tiến hóa của các loài và dự đoán tác động của các thay đổi di truyền lên sức khỏe con người. Nhờ đó, các nhà nghiên cứu có thể xây dựng mô hình di truyền hiệu quả.

II. Thách thức trong Xây dựng Đồ thị Tái tổ hợp Di truyền GRG

Việc xây dựng đồ thị tái tổ hợp di truyền (GRG) không phải là một nhiệm vụ dễ dàng. Nó đòi hỏi việc giải quyết nhiều thách thức kỹ thuật và tính toán. Một trong những thách thức lớn nhất là sự phức tạp của dữ liệu di truyền. Bộ gen người chứa hàng tỷ cặp base, và việc xử lý và phân tích lượng dữ liệu khổng lồ này đòi hỏi các thuật toán và phương pháp tính toán hiệu quả. Thêm vào đó, quá trình tái tổ hợp di truyền là một quá trình ngẫu nhiên và phức tạp, và việc mô hình hóa nó một cách chính xác là một thách thức lớn. Các nhà nghiên cứu phải đối mặt với những hạn chế về dữ liệu, sự không chắc chắn về lịch sử tiến hóa và sự phức tạp của các thuật toán. Vượt qua những thách thức này đòi hỏi sự kết hợp giữa kiến thức sinh học, kỹ năng tính toán và sự sáng tạo trong việc phát triển các phương pháp mới.

2.1. Độ phức tạp của dữ liệu Hệ gen và Khó khăn liên quan

Dữ liệu hệ gen có độ phức tạp cao do kích thước lớn, tính đa dạng và sự hiện diện của nhiều loại biến thể di truyền. Việc xử lý và phân tích dữ liệu này đòi hỏi các thuật toán và phương pháp tính toán hiệu quả, cũng như các công cụ khoa học dữ liệu chuyên dụng. Một trong những khó khăn lớn nhất là việc xác định các biến thể di truyền có ý nghĩa sinh học từ một lượng lớn các biến thể trung tính. Các nhà nghiên cứu cần phải sử dụng các phương pháp thống kê và tin sinh học để lọc ra các biến thể có khả năng ảnh hưởng đến sức khỏe con người.

2.2. Mô hình hóa quá trình Tái tổ hợp Di truyền Phức tạp

Quá trình tái tổ hợp di truyền là một quá trình ngẫu nhiên và phức tạp, và việc mô hình hóa nó một cách chính xác là một thách thức lớn. Các nhà nghiên cứu phải đối mặt với những hạn chế về dữ liệu, sự không chắc chắn về lịch sử tiến hóa và sự phức tạp của các thuật toán. Một trong những khó khăn lớn nhất là việc xác định các vị trí tái tổ hợp và tần suất tái tổ hợp. Các nhà nghiên cứu cần phải sử dụng các mô hình thống kê và mô hình di truyền để ước tính các tham số này.

2.3. Giới hạn về tính toán và bộ nhớ trong Xây dựng GRG

Việc xây dựng đồ thị GRG đòi hỏi một lượng lớn tài nguyên tính toán và bộ nhớ. Các thuật toán xây dựng GRG thường có độ phức tạp cao, và việc xử lý dữ liệu hệ gen lớn có thể mất nhiều thời gian và tài nguyên. Các nhà nghiên cứu cần phải sử dụng các kỹ thuật tối ưu hóa thuật toán và phần cứng để giảm thiểu chi phí tính toán và bộ nhớ. Ngoài ra, việc sử dụng các phương pháp song song hóa và phân tán có thể giúp tăng tốc quá trình xây dựng GRG. Các nhà nghiên cứu về tin sinh học luôn phải đối mặt với bài toán này.

III. Giải pháp Thuật toán ARG4WG Xây dựng GRG Hợp lý

Thuật toán ARG4WG là một giải pháp hiệu quả để xây dựng đồ thị tái tổ hợp di truyền (GRG) hợp lý từ dữ liệu hệ gen lớn. Nó dựa trên ý tưởng sử dụng đoạn chung dài nhất giữa các cặp trình tự để xác định các sự kiện tái tổ hợp di truyền. Thay vì cố gắng tìm kiếm đồ thị GRG tối thiểu, ARG4WG tập trung vào việc xây dựng một đồ thị hợp lý trong thời gian ngắn. Thuật toán này có thể xử lý hàng nghìn trình tự DNA, làm cho nó trở thành một công cụ mạnh mẽ cho các nghiên cứu di truyền quần thể và phân tích bộ gen. ARG4WG được thiết kế để khắc phục những hạn chế của các thuật toán trước đây, đặc biệt là khả năng xử lý dữ liệu lớn và tốc độ tính toán.

3.1. Ý tưởng chính của Thuật toán ARG4WG

Ý tưởng chính của thuật toán ARG4WG là sử dụng đoạn chung dài nhất giữa các cặp trình tự để xác định các sự kiện tái tổ hợp di truyền. Thuật toán này giả định rằng các trình tự có đoạn chung dài nhất có khả năng có quan hệ tổ tiên gần gũi và đã trải qua ít sự kiện tái tổ hợp hơn so với các trình tự có đoạn chung ngắn hơn. Bằng cách tập trung vào các đoạn chung dài nhất, ARG4WG có thể xây dựng một đồ thị GRG hợp lý trong thời gian ngắn. Từ đó xây dựng được cấu trúc đồ thị hiệu quả.

3.2. Các bước cơ bản trong Thuật toán ARG4WG

Thuật toán ARG4WG bao gồm các bước cơ bản sau: (1) Tính toán đoạn chung dài nhất giữa tất cả các cặp trình tự DNA. (2) Chọn cặp trình tự có đoạn chung dài nhất. (3) Thực hiện sự kiện tái tổ hợp di truyền giữa hai trình tự này. (4) Lặp lại các bước 2 và 3 cho đến khi tất cả các trình tự được kết nối vào một đồ thị duy nhất. (5) Thêm các sự kiện đột biến vào đồ thị để giải thích các khác biệt giữa các trình tự. Các bước này được lặp lại cho đến khi đạt được một đồ thị GRG hợp lý. Điều này giúp phân tích di truyền hiệu quả.

3.3. Ưu điểm của ARG4WG so với các Thuật toán khác

ARG4WG có một số ưu điểm so với các thuật toán khác, bao gồm khả năng xử lý dữ liệu lớn, tốc độ tính toán nhanh và khả năng xây dựng đồ thị GRG hợp lý. Thuật toán này cũng dễ dàng triển khai và sử dụng, làm cho nó trở thành một công cụ hữu ích cho các nhà nghiên cứu di truyền. So với thuật toán Margarita, ARG4WG cho kết quả nhanh hơn và hiệu quả hơn với dữ liệu lớn. Giúp cho lập bản đồ di truyền trở nên khả thi.

IV. Tối ưu hóa số Sự kiện Tái tổ hợp khi Xây dựng Đồ thị ARG

Một trong những mục tiêu quan trọng trong việc xây dựng đồ thị tái tổ hợp di truyền (GRG) là tối ưu hóa số lượng sự kiện tái tổ hợp di truyền. Số lượng sự kiện tái tổ hợp càng ít, đồ thị GRG càng đơn giản và dễ hiểu. Tuy nhiên, việc tìm kiếm đồ thị GRG với số lượng sự kiện tái tổ hợp tối thiểu là một bài toán NP-khó. Các nhà nghiên cứu đã phát triển nhiều phương pháp khác nhau để tối ưu hóa số lượng sự kiện tái tổ hợp, bao gồm sử dụng các thuật toán heuristic, các mô hình thống kê và các phương pháp học máy. Mục tiêu là tìm ra sự cân bằng giữa độ chính xác và hiệu quả tính toán.

4.1. Các yếu tố ảnh hưởng đến số lượng Sự kiện Tái tổ hợp

Có nhiều yếu tố ảnh hưởng đến số lượng sự kiện tái tổ hợp di truyền trong một đồ thị GRG, bao gồm kích thước của dữ liệu hệ gen, mức độ đa dạng di truyền và các giả định về quá trình tiến hóa. Dữ liệu lớn và đa dạng thường dẫn đến số lượng sự kiện tái tổ hợp lớn hơn. Các giả định về quá trình tiến hóa, chẳng hạn như tỷ lệ đột biến và tỷ lệ tái tổ hợp, cũng có thể ảnh hưởng đến số lượng sự kiện tái tổ hợp. Từ đó ảnh hưởng đến mô hình hóa di truyền.

4.2. Phương pháp giảm thiểu Sự kiện Tái tổ hợp trong GRG

Có nhiều phương pháp khác nhau để giảm thiểu số lượng sự kiện tái tổ hợp di truyền trong một đồ thị GRG. Một phương pháp phổ biến là sử dụng các thuật toán heuristic để tìm kiếm các giải pháp gần tối ưu. Các phương pháp khác bao gồm sử dụng các mô hình thống kê để ước tính tỷ lệ tái tổ hợp và sử dụng các phương pháp học máy để dự đoán các vị trí tái tổ hợp. Việc kết hợp nhiều phương pháp khác nhau có thể mang lại kết quả tốt nhất. Các thuật toán giúp giải trình tự gen chính xác.

4.3. Thuật toán REARG và GAMARG Giải pháp Cải tiến

Thuật toán REARG và GAMARG là hai giải pháp cải tiến để tối ưu hóa số lượng sự kiện tái tổ hợp di truyền trong đồ thị GRG. REARG sử dụng một phương pháp dựa trên nhánh và cận để tìm kiếm các giải pháp tối ưu, trong khi GAMARG sử dụng một phương pháp dựa trên thuật toán di truyền. Cả hai thuật toán đều có thể giảm đáng kể số lượng sự kiện tái tổ hợp so với các phương pháp truyền thống. Tuy nhiên, chúng có thể đòi hỏi nhiều tài nguyên tính toán hơn. Giúp cho phân tích SNPs và phân tích haplotype dễ dàng hơn.

V. Ứng dụng GRG trong Phân tích Di truyền và Nghiên cứu Bệnh

Đồ thị tái tổ hợp di truyền (Genetic Recombination Graph - GRG) không chỉ là một công cụ lý thuyết; nó có nhiều ứng dụng thực tế trong phân tích di truyền và nghiên cứu bệnh. GRG có thể được sử dụng để xác định các vùng gen liên quan đến bệnh, nghiên cứu biến dị di truyền, phân tích liên kết và phát hiện đột biến. Nó cũng có thể giúp các nhà khoa học hiểu rõ hơn về cơ chế tái tổ hợp và mô hình hóa sự tiến hóa của các loài. Các ứng dụng của GRG đang ngày càng mở rộng, nhờ vào sự phát triển của công nghệ giải trình tự gen và các thuật toán tính toán hiệu quả.

5.1. Xác định vùng gen liên quan đến Bệnh bằng GRG

GRG có thể được sử dụng để xác định các vùng gen liên quan đến bệnh bằng cách so sánh đồ thị GRG của những người mắc bệnh với đồ thị GRG của những người khỏe mạnh. Các vùng gen có sự khác biệt đáng kể giữa hai nhóm có thể là các ứng cử viên cho các gen gây bệnh. Phương pháp này đã được sử dụng thành công để xác định các gen liên quan đến nhiều bệnh khác nhau, bao gồm bệnh tim, ung thư và bệnh tiểu đường. Việc phân tích bộ gen trở nên đơn giản hơn.

5.2. Nghiên cứu Biến dị di truyền và Phân tích Haplotype

GRG có thể được sử dụng để nghiên cứu biến dị di truyền và phân tích haplotype bằng cách biểu diễn các biến thể di truyền và các haplotype trên đồ thị GRG. Điều này cho phép các nhà khoa học xác định các haplotype phổ biến và các biến thể di truyền liên quan đến bệnh. GRG cũng có thể được sử dụng để nghiên cứu sự tiến hóa của các haplotype và các biến thể di truyền. Công cụ này giúp cho phân tích cây phả hệ và phân tích dòng dõi trở nên dễ dàng hơn.

5.3. GRG trong phát triển Thuốc và liệu pháp điều trị

GRG có thể được sử dụng trong phát triển thuốc và liệu pháp điều trị bằng cách xác định các mục tiêu thuốc tiềm năng và dự đoán hiệu quả của các liệu pháp điều trị. Bằng cách hiểu rõ hơn về các cơ chế di truyền của bệnh, các nhà khoa học có thể phát triển các loại thuốc và liệu pháp điều trị hiệu quả hơn. GRG cũng có thể được sử dụng để cá nhân hóa điều trị bằng cách xác định các bệnh nhân có khả năng đáp ứng tốt nhất với một loại thuốc hoặc liệu pháp điều trị cụ thể. GRG giúp phân tích SNPs (Single Nucleotide Polymorphisms) hiệu quả.

VI. Tương lai của Đồ thị Tái tổ hợp Di truyền GRG và Ứng dụng

Tương lai của đồ thị tái tổ hợp di truyền (Genetic Recombination Graph - GRG) rất hứa hẹn. Với sự phát triển của công nghệ giải trình tự gen và các thuật toán tính toán, GRG sẽ trở thành một công cụ ngày càng mạnh mẽ cho phân tích di truyền và nghiên cứu bệnh. Các nhà khoa học đang khám phá các ứng dụng mới của GRG trong nhiều lĩnh vực khác nhau, bao gồm y học, nông nghiệp và tin sinh học. GRG có tiềm năng cách mạng hóa cách chúng ta hiểu về sự sống và phát triển các phương pháp điều trị bệnh.

6.1. Hội tụ GRG với Học máy và Trí tuệ nhân tạo AI

Sự kết hợp giữa GRG, học máy và trí tuệ nhân tạo (AI) sẽ mở ra những khả năng mới cho phân tích di truyền. Các thuật toán học máy có thể được sử dụng để phân tích dữ liệu GRG và dự đoán các kết quả quan trọng, chẳng hạn như nguy cơ mắc bệnh và hiệu quả của các liệu pháp điều trị. AI có thể giúp các nhà khoa học tự động hóa quá trình xây dựng GRG và khám phá các mẫu di truyền phức tạp. Giúp cho phân tích dòng dõi và phân tích gen hiệu quả hơn.

6.2. GRG trong Y học Cá nhân hóa và Liệu pháp Gen

GRG sẽ đóng một vai trò quan trọng trong y học cá nhân hóa và liệu pháp gen. Bằng cách phân tích đồ thị GRG của từng bệnh nhân, các bác sĩ có thể đưa ra các quyết định điều trị phù hợp với đặc điểm di truyền của họ. GRG cũng có thể được sử dụng để thiết kế các liệu pháp gen nhắm mục tiêu vào các gen gây bệnh. Giúp quá trình giải trình tự gen đạt hiệu quả cao.

6.3. Mở rộng ứng dụng GRG sang các lĩnh vực Khoa học khác

Các ứng dụng của GRG không giới hạn trong lĩnh vực y học. GRG có thể được sử dụng trong nhiều lĩnh vực khoa học khác, chẳng hạn như nông nghiệp, sinh học tiến hóa và tin sinh học. Trong nông nghiệp, GRG có thể giúp các nhà khoa học phát triển các giống cây trồng và vật nuôi mới có năng suất cao hơn và khả năng chống chịu bệnh tốt hơn. Trong sinh học tiến hóa, GRG có thể giúp các nhà khoa học hiểu rõ hơn về lịch sử tiến hóa của các loài. Trong tin sinh học, GRG có thể được sử dụng để phân tích dữ liệu hệ gen lớn và khám phá các mối quan hệ di truyền phức tạp.

Trích đoạn nội dung tài liệu

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.