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

Abstract

i. Đề xuất thuật toán ARG4WG xây dựng đồ thị tái tổ hợp di truyền (Ancestral Recombination Graph – ARG) gần đúng với ý tưởng sử dụng chiến lược tìm kiếm đoạn chung dài nhất giữa 2 đầu của 2 trình tự cho bước tái tổ hợp. Thuật toán được cài đặt và để dưới dạng nguồn mở cho cộng đồng nghiên cứu tại địa chỉ: https://github.com/thaontp711/arg4wg. ARG4WG có các đặc điểm nổi trội sau: (1) ARG4WG là thuật toán duy nhất hiện nay có khả năng xây dựng được đồ thị ARG đầy đủ cho dữ liệu hàng nghìn hệ gen trong một lần chạy trong khoảng thời gian hợp lý; (2) ARG4WG nhanh gấp hàng trăm tới hàng nghìn lần Margarita – một trong những thuật toán xây dựng đồ thị ARG hợp lý hiệu quả nhất hiện nay; (3) Thực nghiệm ứng dụng ARG4WG trong 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 Gambia đã chứng minh tính hợp lý của các đồ thị ARG sinh ra và khả năng ứng dụng hiệu quả của thuật toán đề xuất trong bài toán thực tế tìm vùng gen liên quan đến bệnh trên dữ liệu lớn. ii. Đề xuất 2 cải tiến cho thuật toán ARG4WG để rút gọn đồ thị ARG: (1) Thuật toán REARG kết hợp chiến lược độ dài đoạn đầu chung dài nhất với các đặc trưng về độ tương đồng nhiều nhất giữa các trình tự và độ dài của trình tự; (2) Thuật toán GAMARG kết hợp phương pháp kiểm thử 4 giao tử với chiến lược độ dài đoạn đầu chung dài nhất trong bước tái tổ hợp nhằm tối ưu số sự kiện tái tổ hợp trong quá trình xây dựng đồ thị ARG. Các kết quả thực nghiệm trên các bộ dữ liệu thật và dữ liệu mô phỏng cho thấy REARG giúp xây dựng đồ thị ARG với số sự kiện tái tổ hợp nhỏ cho các tập dữ liệu vừa và lớn. Tuy nhiên, GAMARG tổng quát hơn và có khả năng xây dựng được những ARG gần với nghiệm tối ưu hơn.