I. Giới thiệu chung
Luận án tiến sĩ này tập trung vào việc xây dựng đồ thị tái tổ hợp di truyền (ARG) cho dữ liệu hệ gen, một lĩnh vực quan trọng trong công nghệ thông tin và di truyền học. Luận án nhằm giải quyết các vấn đề liên quan đến phân tích dữ liệu và mô hình hóa di truyền thông qua việc sử dụng khoa học máy tính và kỹ thuật di truyền. Đồ thị tái tổ hợp là công cụ chính để mô tả lịch sử di truyền của các trình tự gen, giúp hiểu rõ hơn về sự kiện tái tổ hợp và đột biến trong quá trình tiến hóa.
1.1. Hệ gen người
Hệ gen người bao gồm 23 cặp nhiễm sắc thể, chứa khoảng 3 tỷ phân tử DNA. Các biến thể di truyền như SNP và biến thể cấu trúc là nguyên nhân chính tạo nên sự đa dạng di truyền. Đột biến và tái tổ hợp là hai cơ chế chính dẫn đến các biến thể này. Dữ liệu hệ gen từ các dự án như 1000 hệ gen cung cấp nguồn thông tin quý giá cho nghiên cứu.
1.2. Mạng phát sinh loài
Mạng phát sinh loài là công cụ quan trọng để biểu diễn mối quan hệ tiến hóa giữa các loài. Trong nghiên cứu di truyền, mạng này giúp xác định tổ tiên chung và các sự kiện tái tổ hợp. Đồ thị ARG là một dạng mạng phát sinh loài, mô tả chi tiết lịch sử di truyền của các trình tự gen.
II. Xây dựng đồ thị tái tổ hợp di truyền
Luận án đề xuất các phương pháp xây dựng đồ thị ARG hiệu quả, đặc biệt là thuật toán ARG4WG, nhằm xử lý dữ liệu lớn hàng nghìn trình tự gen. Thuật toán Margarita được cải tiến để khắc phục các hạn chế trong việc xác định đoạn chung dài nhất và sự kiện tái tổ hợp. ARG4WG tối ưu hóa quá trình xây dựng đồ thị bằng cách giảm thiểu số lượng sự kiện tái tổ hợp, giúp đồ thị gần với thực tế hơn.
2.1. Thuật toán ARG4WG
Thuật toán ARG4WG sử dụng chiến lược tìm đoạn đầu chung dài nhất để xác định vị trí tái tổ hợp. Phương pháp này giúp giảm số lượng sự kiện tái tổ hợp và cải thiện hiệu suất tính toán. Kết quả thực nghiệm trên dữ liệu thật và dữ liệu mô phỏng cho thấy hiệu quả vượt trội của ARG4WG so với các phương pháp truyền thống.
2.2. Ứng dụng thực tế
ARG4WG được áp dụng 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 quả cho thấy khả năng ứng dụng cao của thuật toán trong việc phân tích dữ liệu hệ gen lớn, giúp xác định các vùng gen có ý nghĩa sinh học.
III. Tối ưu hóa số sự kiện tái tổ hợp
Luận án đề xuất hai 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: REARG và GAMARG. Các phương pháp này kết hợp đặc trưng dữ liệu và kỹ thuật tối ưu để giảm thiểu số lượng sự kiện tái tổ hợp, giúp đồ thị gần với thực tế hơn. Kết quả thực nghiệm trên các tập dữ liệu nhỏ và dữ liệu từ dự án 1kGP chứng minh hiệu quả của các phương pháp này.
3.1. Thuật toán REARG
Thuật toán REARG tập trung vào việc tối ưu hóa sự kiện tái tổ hợp bằng cách sử dụng các đặc trưng dữ liệu và kỹ thuật tìm cận dưới. Phương pháp này giúp giảm số lượng sự kiện tái tổ hợp mà vẫn đảm bảo độ chính xác của đồ thị.
3.2. Thuật toán GAMARG
Thuật toán GAMARG kết hợp kỹ thuật di truyền với chiến lược tái tổ hợp để tối ưu hóa quá trình xây dựng đồ thị. Kết quả thực nghiệm cho thấy GAMARG hiệu quả hơn so với các phương pháp truyền thống trong việc giảm thiểu sự kiện tái tổ hợp.
