Xây dựng đồ thị tái tổ hợp di truyền cho dữ liệu lớn trên toàn hệ gen

Mã đề tài: VAST01.02/14-15, Tên chủ nhiệm: TS. Hồ Bích Hải, Xếp loại: Khá, Thời gian thực hiện: 2014-2015

Mục tiêu đề tài:

Nghiên cứu các thuật toán xây dựng đồ thị tái tổ hợp di truyền (Ancestral Recombination Graph – ARG) và phát triển thuật toán xây dựng đồ thị ARG cho phép thuật toán chạy được với dữ liệu lớn gồm hàng nghìn mẫu trên toàn hệ gen.

Kết quả đạt được:

Về khoa học:

Đồ thị tái tổ hợp di truyền đóng một vai trò quan trọng trong nghiên cứu di truyền quần thể và các bài toán liên quan đến tìm sự đa dạng trong hệ gen. Tuy nhiên, do độ phức tạp tính toán lớn nên hầu hết các thuật toán suy luận đồ thị ARG hiện nay đều chỉ chạy được với các tập dữ liệu nhỏ. Do đó chúng tôi đề xuất thuật toán ARG4WG dựa trên kinh nghiệm để xây dựng đồ thị ARG cho các tập dữ liệu lớn trên toàn hệ gen. Bằng việc sử dụng đoạn chung dài nhất từ phía bên phải hoặc phía bên trái của trình tự cho bước tái tổ hợp trong quá trình xây dựng đồ thị, thuật toán đề xuất đã cho ra các đồ thị ARG có số sự kiện tái tổ hợp ít hơn và đảm bảo số nút trong đồ thị ổn định sau các bước tái tổ hợp. Chiến lược này còn giúp cho thuật toán có thời gian tính toán nhanh gấp hàng trăm tới hàng nghìn lần so với thuật toán Margarita - một trong những thuật toán suy luận đồ thị ARG hiệu quả nhất hiện nay. Đặc biệt, ARG4WG có thể chạy được với hàng nghìn mẫu trên toàn nhiễm sắc thể trong một lần chạy trong một khoảng thời gian hợp lý.

Về ứng dụng:

Chúng tôi đã ứ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 trên tập dữ liệu Gambia gồm 2780 mẫu cá thể (1533 người khỏe mạnh, 1247 người bị bệnh) trên toàn bộ nhiễm sắc thể 11. Các kết quả thực nghiệm đã cho thấy khả năng ứng dụng của thuật toán đề xuất trong việc phát hiện ra vùng gen liên quan đến bệnh cho các nghiên cứu tương quan toàn bộ nhiễm sắc thể trên các tập dữ liệu lớn. Từ các kết quả này, chúng tôi tin tưởng rằng ARG4WG có thể được ứng dụng hiệu quả cho nhiều bài toán thực tế khác như bài toán tìm đa hình di truyền đơn nucleotide, bài toán xử lý dữ liệu bị khuyết,… trên các tập dữ liệu lớn.

Những đóng góp mới:

Đề tài đã đề xuất một thuật toán xây dựng đồ thị tái tổ hợp di truyền cho dữ liệu lớn gồm hàng nghìn mẫu trên toàn hệ gen, một điều mà các thuật toán trước đây chưa làm được. Thuật toán đề xuất cũng đã được thử nghiệm ứng dụng hiệu quả cho một bài toán dữ liệu lớn thực tế. Đây sẽ là bước đệm tạo đà cho việc phát triển và ứng dụng thuật toán vào các bài toán thực tế khác trong thời gian tới.

Sản phẩm đề tài:

- Các bài báo đã công bố:

Nguyen TTP, Le SV, Ho BH, Le SQ (2016). Building ancestral recombination graphs for whole genomes. IEEE/ACM Transactions on Computational Biology and Bioinformatics.

doi: 10.1109/TCBB.2016.2542801.

- Các sản phẩm cụ thể (mô tả sản phẩm, nơi lưu giữ):

Chương trình xây dựng đồ thị ARG – ARG4WG cho phép người dùng xây dựng đồ thị ARG cho dữ liệu lớn hàng nghìn mẫu trên toàn hệ gen.

ARG4WGđược để dưới dạng mã nguồn mở cho cộng đồng nghiên cứu tại địa chỉ: https://bitbucket.org/LeSiQuang/arg4wg