Luận án Tiến sĩ: Xây dựng Đồ thị Tái tổ hợp Di truyền cho Dữ liệu Hệ gen - Nguyễn Thị Phương Thảo
Luận án TS Công nghệ thông tin: Đồ thị tái tổ hợp di truyền cho dữ liệu hệ gen. Giải pháp đột phá trong phân tích dữ liệu sinh học phức tạp.
Năm xuất bản
Số trang
112
Thời gian đọc
17 phút
Lượt xem
0
Lượt tải
0
Phí lưu trữ
40 Point
Tổng quan nhanh
- Chủ đề:
- 1. Tổng quan đồ thị tái tổ hợp di truyền dữ liệu hệ gen
- Số trang:
- 112 trang
- Trường:
- Đại học Yale
- Chuyên ngành:
- Khoa học máy tính
- Tác giả:
- Luan An
- Năm:
- 2020
Tóm tắt nội dung luận án
I. Tổng quan đồ thị tái tổ hợp di truyền dữ liệu hệ gen
Hệ gen người chứa hàng tỷ cặp base mang thông tin di truyền quan trọng. Dữ liệu hệ gen phản ánh toàn bộ lịch sử tiến hóa của quần thể sinh vật. Đồ thị tái tổ hợp tổ tiên (Ancestral Recombination Graph - ARG) là mô hình toán học và tin sinh học then chốt. Cấu trúc này mô tả lịch sử phả hệ di truyền phức tạp qua hàng nghìn thế hệ. Đồ thị ARG tích hợp cả hai quá trình sinh học cơ bản: đột biến và tái tổ hợp. Các đột biến tạo ra những biến thể đa hình đơn nucleotit mới. Tái tổ hợp làm xáo trộn các đoạn nhiễm sắc thể giữa các cá thể. Mô hình ARG vượt trội hơn hẳn các cây tiến hóa đơn lẻ thông thường. Cấu trúc này biểu diễn chính xác mối quan hệ giữa các trình tự DNA hiện đại và tổ tiên chung gần nhất. Việc nghiên cứu đồ thị tái tổ hợp di truyền mở ra hướng tiếp cận đột phá cho lĩnh vực di truyền học quần thể (Population genomics).
1.1. Khái niệm đồ thị tái tổ hợp tổ tiên ARG và mô hình sinh học
Đồ thị tái tổ hợp tổ tiên (Ancestral Recombination Graph - ARG) là một đồ thị có hướng không chu trình. Đồ thị này biểu diễn đầy đủ lịch sử tiến hóa của một tập hợp các trình tự DNA. Trong cấu trúc đồ thị, các nút lá đại diện cho các mẫu trình tự quan sát ở hiện tại. Các nút bên trong biểu diễn các sự kiện sinh học xảy ra trong quá khứ. Hai sự kiện tiến hóa quan trọng nhất là sự kiện hợp nhất và sự kiện tái tổ hợp. Sự kiện hợp nhất kết hợp hai dòng dõi tổ tiên thành một tổ tiên chung gần nhất. Sự kiện tái tổ hợp chia tách một dòng dõi tổ tiên thành hai nguồn gốc vật liệu di truyền khác nhau. Tại mỗi vị trí nucleotide cụ thể, lịch sử di truyền được thu gọn thành một cây phả hệ gen (Gene genealogy) cục bộ. Toàn bộ hệ gen tương ứng với một chuỗi cây phát sinh (Tree sequence / tskit) liên tục dọc theo nhiễm sắc thể. Mô hình đồ thị nắm bắt trọn vẹn toàn bộ biến dị di truyền của quần thể.
1.2. Lý thuyết hợp nhất có tái tổ hợp trong dữ liệu haplotype
Lý thuyết hợp nhất có tái tổ hợp (Coalescent with recombination) là nền tảng toán học quan trọng của mô hình ARG. Lý thuyết này phát triển mở rộng từ mô hình hợp nhất tiêu chuẩn của Kingman. Quá trình toán học mô tả sự truy ngược thời gian từ các thế hệ hiện tại về quá khứ xa xưa. Dữ liệu Haplotype và SNP đóng vai trò là nguồn dữ liệu đầu vào chính cho các mô hình suy luận. Haplotype thể hiện tổ hợp các alen liên kết chặt chẽ trên cùng một phân tử DNA. Khoảng cách vật lý giữa các vị trí SNP quyết định trực tiếp tần số xuất hiện tái tổ hợp di truyền. Hai locus nằm gần nhau thường có xu hướng di truyền cùng nhau qua nhiều thế hệ. Hiện tượng liên kết chặt chẽ này dẫn đến trạng thái mất cân bằng liên kết (Linkage Disequilibrium - LD). Mô hình hợp nhất có tái tổ hợp giúp giải thích thỏa đáng cấu trúc LD quan sát được trên hệ gen thực tế. Lý thuyết cung cấp khung phân tích vững chắc cho nghiên cứu tiến hóa hệ gen quy mô lớn.
II. Thuật toán suy luận cấu trúc đồ thị tái tổ hợp di truyền
Suy luận cấu trúc ARG (ARG inference algorithms) là một trong những bài toán tính toán thách thức nhất trong tin sinh học. Không gian trạng thái của các cấu trúc đồ thị khả dĩ tăng theo cấp số nhân theo độ dài trình tự và số lượng mẫu. Bài toán tìm kiếm đồ thị ARG với số sự kiện tái tổ hợp nhỏ nhất thuộc lớp bài toán NP-khó. Các nhà nghiên cứu đã phát triển hai trường phái tiếp cận chính để giải quyết vấn đề này. Hướng tiếp cận thứ nhất tập trung vào việc tìm kiếm đồ thị ARG tối thiểu về mặt toán học. Hướng tiếp cận thứ hai tập trung vào việc ước lượng đồ thị ARG hợp lý dựa trên các quy luật xác suất sinh học. Mỗi hướng tiếp cận phục vụ các bài toán phân tích di truyền đặc thù. Việc phát triển các thuật toán hiệu năng cao là điều kiện tiên quyết để xử lý dữ liệu hệ gen thế hệ mới.
2.1. Phân loại bài toán xây dựng ARG tối thiểu và ARG hợp lý
Bài toán ARG tối thiểu tìm kiếm cấu trúc đồ thị có số lượng sự kiện tái tổ hợp ít nhất có thể. Mục tiêu trọng tâm là giải thích dữ liệu quan sát được với số lượng giả định tiến hóa tối thiểu. Hướng tiếp cận này thường sử dụng các kỹ thuật tối ưu hóa toán học như quy hoạch động, nhánh cận hoặc quy hoạch nguyên. Tuy nhiên, các thuật toán chính xác có độ phức tạp tính toán rất lớn và chỉ chạy được trên tập dữ liệu rất nhỏ. Ngược lại, bài toán ARG hợp lý mô phỏng quá trình tiến hóa tuân theo các phân phối xác suất sinh học. Phương pháp này dựa trên khung lý thuyết hợp nhất có tái tổ hợp (Coalescent with recombination). Các thuật toán xấp xỉ và giải thuật heuristic được áp dụng rộng rãi để tìm cấu trúc gần tối ưu. Hướng tiếp cận ARG hợp lý phản ánh đúng thực tế sinh học hơn và có khả năng mở rộng xử lý các tập dữ liệu Haplotype và SNP lớn với hàng nghìn cá thể.
2.2. Đánh giá thuật toán suy luận cấu trúc ARG trong thực tế
Nhiều công cụ và thuật toán suy luận cấu trúc ARG đã được xây dựng và phát triển trong những năm gần đây. Các phần mềm tiêu biểu bao gồm Margarita, BEAST, FastARG, ARGweaver và thư viện tsinfer. Mỗi công cụ sở hữu những ưu điểm và hạn chế riêng về tốc độ xử lý cũng như độ chính xác mô hình. Margarita áp dụng kỹ thuật chuỗi Markov Monte Carlo (MCMC) để lấy mẫu các đồ thị ARG hợp lý từ dữ liệu thực nghiệm. Tuy nhiên, thời gian tính toán của Margarita tăng rất nhanh khi kích thước dữ liệu mở rộng. FastARG và tsinfer tập trung vào việc tối ưu hóa bộ nhớ và tốc độ xử lý dữ liệu quy mô lớn. Các công cụ hiện đại biểu diễn đồ thị thông qua chuỗi cây phát sinh (Tree sequence / tskit). Quá trình đánh giá thuật toán dựa trên các tiêu chí: thời gian chạy, tài nguyên bộ nhớ và độ tương đồng của cây phả hệ gen. Khoảng cách Robinson-Foulds là độ đo phổ biến để so sánh sai lệch topo giữa các cây phả hệ gen được tái dựng.
III. Thuật toán ARG4WG tái tổ hợp di truyền toàn bộ hệ gen
Dữ liệu giải trình tự toàn bộ hệ gen hiện đại đặt ra thách thức lớn về khả năng mở rộng thuật toán. Thuật toán ARG4WG ra đời nhằm giải quyết bài toán xây dựng đồ thị ARG hợp lý cho dữ liệu hệ gen quy mô lớn. ARG4WG kế thừa nền tảng lý thuyết vững chắc từ thuật toán Margarita kinh điển. Thuật toán giới thiệu chiến lược tìm kiếm cải tiến giúp thu hẹp đáng kể không gian trạng thái cần duyệt. Tốc độ xử lý của ARG4WG vượt trội rõ rệt so với các công cụ truyền thống trước đây. Thuật toán vẫn đảm bảo độ tin cậy và tính hợp lý sinh học cao của cấu trúc đồ thị tái dựng. ARG4WG mở ra khả năng tái hiện chi tiết lịch sử tiến hóa trên quy mô toàn bộ nhiễm sắc thể của quần thể người.
3.1. Cải tiến tìm đoạn tiền tố chung dài nhất từ Margarita
Thuật toán Margarita truyền thống gặp nút thắt cổ chai nghiêm trọng tại bước tính toán ma trận tương đồng giữa các trình tự. Thuật toán ARG4WG giải quyết triệt để hạn chế này bằng chiến lược tìm đoạn tiền tố chung dài nhất. Chiến lược này tối ưu hóa việc ghép cặp các dòng dõi tổ tiên trong quá trình truy ngược thời gian. ARG4WG nhanh chóng xác định các đoạn Haplotype trùng khớp dài nhất giữa các mẫu phân tích. Quá trình tìm kiếm tiền tố chung giúp nhận diện chính xác các sự kiện hợp nhất tiềm năng có xác suất cao nhất. Thuật toán loại bỏ phần lớn các phép so sánh dư thừa không cần thiết. Độ phức tạp tính toán giảm mạnh trong mỗi bước lùi thời gian. Cải tiến cấu trúc dữ liệu và giải thuật giúp ARG4WG xử lý mượt mà các tập dữ liệu chứa hàng trăm nghìn vị trí SNP.
3.2. Hiệu năng của ARG4WG trên dữ liệu mô phỏng và sốt rét
Hiệu năng của ARG4WG đã được kiểm chứng toàn diện thông qua các thực nghiệm trên dữ liệu mô phỏng và dữ liệu thực tế. Trên các bộ dữ liệu mô phỏng theo mô hình coalescent, ARG4WG đạt tốc độ thực thi nhanh hơn Margarita nhiều lần. Độ chính xác trong việc tái dựng cây phả hệ gen (Gene genealogy) cục bộ luôn duy trì ở mức rất cao. Đặc biệt, ARG4WG được ứng dụng thành công trên dữ liệu hệ gen thực tế về bệnh sốt rét ở Châu Phi. Dữ liệu bao gồm các vùng gen liên quan đến khả năng đề kháng sốt rét của các quần thể người bản địa. ARG4WG xác định chính xác các điểm đột biến quan trọng và các sự kiện chọn lọc tự nhiên tích cực. Cấu trúc đồ thị ARG giúp khoanh vùng hiệu quả các biến thể di truyền liên quan chặt chẽ đến cơ chế kháng bệnh.
IV. Tối ưu hóa số sự kiện tái tổ hợp với REARG và GAMARG
Tối ưu hóa số lượng sự kiện tái tổ hợp là yếu tố quyết định chất lượng của đồ thị ARG. Sự xuất hiện của các sự kiện tái tổ hợp dư thừa làm giảm độ tin cậy của mô hình tiến hóa. Thuật toán ARG4WG có ưu thế về tốc độ nhưng đôi khi tạo ra số sự kiện tái tổ hợp nhiều hơn mức cần thiết. Hai phương pháp cải tiến REARG và GAMARG được phát triển nhằm tối ưu hóa triệt để vấn đề này. Cả hai thuật toán đều tập trung vào việc giảm thiểu số nút tái tổ hợp mà vẫn duy trì tính hợp lý sinh học. Các thử nghiệm trên dữ liệu chuẩn khẳng định tính vượt trội của REARG và GAMARG so với các công cụ tiền nhiệm.
4.1. Cải tiến thuật toán REARG giảm thiểu sự kiện tái tổ hợp
Thuật toán REARG tập trung vào việc tối ưu hóa cục bộ quá trình lựa chọn các sự kiện hợp nhất và tái tổ hợp. REARG phân tích kỹ lưỡng cấu trúc ma trận biến dị để xác định điểm cắt tái tổ hợp chính xác nhất. Thuật toán ưu tiên thực hiện các sự kiện hợp nhất có khả năng triệt tiêu tối đa các xung đột phân đoạn di truyền. REARG kiểm tra tính tương thích giữa các vị trí SNP lân cận nhằm hạn chế tối đa các phân tách nhánh không cần thiết. Chiến lược thông minh này giúp loại bỏ hiệu quả các sự kiện tái tổ hợp giả tạo do nhiễu dữ liệu. Đồ thị ARG thu được từ REARG có cấu trúc cô đọng, rõ ràng và phản ánh sát lịch sử tiến hóa thực tế. Hiệu quả giảm thiểu số sự kiện tái tổ hợp của REARG được chứng minh rõ rệt qua các thử nghiệm thực tế.
4.2. Giải thuật GAMARG dựa trên thuật toán di truyền cho 1kGP
Thuật toán GAMARG áp dụng nguyên lý giải thuật di truyền (Genetic Algorithm) để tìm kiếm đồ thị ARG tối ưu trên quy mô lớn. GAMARG khởi tạo một quần thể đa dạng gồm nhiều cấu trúc đồ thị ARG ứng viên ban đầu. Thuật toán thiết kế các toán tử lai ghép và đột biến chuyên biệt cho cấu trúc mạng phả hệ phức tạp. Hàm thích nghi được xây dựng để đánh giá đồng thời số lượng sự kiện tái tổ hợp và độ hợp lý theo mô hình sinh học. Quá trình chọn lọc tự nhiên qua nhiều thế hệ giúp thuật toán thoát khỏi các cực trị địa phương và tiến tới cấu trúc tối ưu toàn cục. GAMARG được thử nghiệm thành công trên các tập dữ liệu trích xuất từ Dự án 1000 Hệ gen người (1kGP). Kết quả thực nghiệm khẳng định GAMARG tìm ra số sự kiện tái tổ hợp ít hơn đáng kể so với các thuật toán hiện có.
V. Ứng dụng đồ thị tái tổ hợp di truyền trong y sinh học
Đồ thị tái tổ hợp tổ tiên (Ancestral Recombination Graph - ARG) mang lại giá trị ứng dụng to lớn trong y sinh học và di truyền hiện đại. Mô hình này cung cấp bức tranh toàn diện và chi tiết nhất về cấu trúc di truyền học quần thể (Population genomics). Đồ thị ARG biểu diễn đồng thời lịch sử đột biến, sự kiện tái tổ hợp và quan hệ dòng dõi của toàn bộ quần thể. Nhờ đó, các nhà khoa học có thể giải quyết nhiều bài toán phức tạp trong y học cá thể hóa và dịch tễ học di truyền. Từ việc định vị gen gây bệnh đến tái dựng nguồn gốc tiến hóa loài người, ARG đều thể hiện sức mạnh vượt trội. Cấu trúc đồ thị ARG đang trở thành công cụ tiêu chuẩn trong kỷ nguyên phân tích dữ liệu hệ gen lớn.
5.1. Nghiên cứu tương quan toàn hệ gen GWAS và phân tích LD
Ứng dụng đột phá nhất của đồ thị ARG là trong các nghiên cứu tương quan toàn hệ gen (GWAS). Phân tích GWAS truyền thống thường gặp nhiều khó khăn do hiện tượng mất cân bằng liên kết (Linkage Disequilibrium - LD). Sự liên kết chặt giữa các SNP lân cận gây khó khăn lớn cho việc xác định chính xác biến thể gây bệnh thực sự. Đồ thị ARG khắc phục triệt để nhược điểm này bằng cách cung cấp cây phả hệ gen (Gene genealogy) chuẩn xác tại từng vị trí locus. Nhà nghiên cứu có thể phân tích trực tiếp mối tương quan giữa kiểu hình bệnh lý và lịch sử phân nhánh di truyền. Phương pháp GWAS dựa trên nền tảng ARG giúp nâng cao sức mạnh thống kê phát hiện gen và giảm thiểu tỷ lệ dương tính giả. Cách tiếp cận này hỗ trợ đắc lực cho việc xác định các mục tiêu phân tử phục vụ phát triển thuốc mới.
5.2. Tái hiện lịch sử quần thể và phát hiện điểm nóng tái tổ hợp
Đồ thị ARG là công cụ mạnh mẽ hỗ trợ bài toán suy luận lịch sử nhân khẩu học quần thể (Demographic history inference). Phân bố thời gian của các nút hợp nhất trong đồ thị phản ánh chính xác sự biến động kích thước quần thể qua các thời kỳ lịch sử. Đồ thị cho phép tái hiện chi tiết các sự kiện thắt cổ chai di truyền, biến cố di cư và sự phân tách giữa các nhóm quần thể cổ xưa. Bên cạnh đó, đồ thị ARG giúp xác định chính xác vị trí của các điểm nóng tái tổ hợp (Recombination hotspots) trên toàn bộ hệ gen. Việc nắm bắt tần suất và vị trí tái tổ hợp giúp hiểu sâu hơn về cơ chế tiến hóa ở cấp độ phân tử. Đây là chìa khóa then chốt để giải mã cơ chế bệnh sinh của nhiều hội chứng di truyền phức tạp ở người.
Mục lục chi tiết luận án
Tải xuống file đầy đủ để xem toàn bộ nội dung
Tải đầy đủ (112 trang)Trích đoạn nội dung luận án
Tải xuống để đọc toàn bộĐẠI HỌC YALE XÂY DỰNG ĐỒ THỊ TÁI TỔ HỢP DI TRUYỀN CHO DỮ LIỆU HỆ GEN LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 19 ĐẠI HỌC YALE XÂY DỰNG ĐỒ THỊ TÁI TỔ HỢP DI TRUYỀN CHO DỮ LIỆU HỆ GEN Chuyên ngành: Khoa học Máy tính Mã số: 9480101.01 LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. TƯ SONG QUÂN Hà Nội – 2020 Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của các đồng tác giả trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong các công trình nào khác.
Tác giả Lời cảm ơn Luận án được thực hiện tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, dưới sự hướng dẫn của PGS. Lê Sỹ Vinh và PGS. Lương Chi Mai. Tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS.
Lê Sỹ Vinh, PGS. Lương Chi Mai và TS. Lê Sĩ Quang, những người đã có những định hướng giúp tôi thành công trong việc nghiên cứu của mình. Các Thầy Cô cũng đã động viên và khích lệ tinh thần, giúp tôi vượt qua những khó khăn để tôi hoàn thành được luận án này.
Tôi cũng chân thành cảm ơn thầy Hồ Tú Bảo, Thầy đã cho tôi nhiều kiến thức quý báu về nghiên cứu khoa học. Những sự chỉ bảo quý giá của các Thầy Cô đã giúp tôi hoàn thành tốt luận án này. Tôi cũng xin cảm ơn tới các Thầy, Cô thuộc Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã tạo mọi điều kiện thuận lợi giúp tôi trong quá trình làm nghiên cứu sinh. Tôi xin chân thành cảm ơn các đồng nghiệp trong phòng Nhận dạng và Công nghệ Tri thức, Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã luôn động viên, tạo điều kiện thuận lợi, bố trí thời gian tốt nhất cho tôi trong suốt quá trình làm nghiên cứu sinh.
Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc tới gia đình và bạn bè, những người đã cho tôi điểm tựa vững chắc để tôi có được thành công như ngày hôm nay. 2 MỤC LỤC Lời cam đoan. 3 Danh mục các ký hiệu và chữ viết tắt. 6 Danh mục các bảng.
7 Danh mục các hình vẽ, đồ thị. 8 Danh mục các thuật toán. 12 MỞ ĐẦU 13 Chương 1. Giới thiệu chung.
Hệ gen người. Mạng phát sinh loài. Xây dựng đồ thị tái tổ hợp di truyền. Sự kiện tái tổ hợp.
Đồ thị tái tổ hợp di truyền. Bài toán xây dựng đồ thị ARG. Các phương pháp xây dựng đồ thị ARG. Các phương pháp xây dựng đồ thị ARG tối thiểu.
Các phương pháp xây dựng đồ thị ARG hợp lý. Tổng hợp các phần mềm xây dựng đồ thị ARG. Ứng dụng ARG trong nghiên cứu tương quan toàn hệ gen. Kết luận chương.
THUẬT TOÁN ARG4WG XÂY DỰNG ĐỒ THỊ TÁI TỔ HỢP DI TRUYỀN HỢP LÝ CHO DỮ LIỆU HỆ GEN. Thuật toán Margarita xây dựng đồ thị ARG. Thuật toán ARG4WG. Chiến lược tìm đoạn đầu chung dài nhất.
Thuật toán ARG4WG. Kết quả thực nghiệm. Các kết quả trên dữ liệu thật. Các kết quả trên dữ liệu mô phỏng.
Kết quả ứ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. Kết luận chương. 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. Một số định nghĩa và khái niệm sử dụng trong các thuật toán.
Hạn chế của thuật toán ARG4WG. Thuật toán REARG. Động cơ nghiên cứu. Thuật toán REARG.
Thuật toán GAMARG. Động cơ nghiên cứu. Thuật toán GAMARG. Kết quả thực nghiệm.
Kết quả trên các tập dữ liệu nhỏ. Các kết quả trên các tập dữ liệu từ dự án 1kGP. Kết luận chương. 100 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN.
102 TÀI LIỆU THAM KHẢO. 103 5 Danh mục các ký hiệu và chữ viết tắt D Tập các trình tự N Số lượng trình tự trong một tập các trình tự m độ dài của trình tự Sx Trình tự thứ x trong một tập các trình tự Sx[i] Giá trị của Sx tại vị trí thứ i ARG Đồ thị tái tổ hợp di truyền 1KGP Dự án 1000 hệ gen GWAS Nghiên cứu tương quan toàn hệ gen SNP Đa hình đơn nucleotit MRCA Tổ tiên chung gần nhất CwR Mô hình kết hợp và tái tổ hợp STT Số thứ tự RF Khoảng cách Robinson-Fould 6 Danh mục các bảng Bảng 1.1: Các phần mềm xây dựng đồ thị ARG tiêu biểu.1: Tập dữ liệu trích xuất từ dự án 1000 hệ gen người.1: Tập dữ liệu từ dự án 1kGP.2: Các kết quả của các thuật toán khác nhau trên các tập dữ liệu nhỏ.3: Số sự kiện tái tổ hợp ít nhất được tìm thấy bởi 5 thuật toán cho 100 trình tự của (a) DS1, (b) DS2 và (c) DS3.4: Số sự kiện tái tổ hợp ít nhất được tìm thấy bởi 5 thuật toán cho 200 trình tự của (a) DS1, (b) DS2 và (c) DS3.5: Trung bình thời gian chạy (giây) của 5 thuật toán cho 100 trình tự của các tập dữ liệu (a) DS1, (b) DS2, và (c) DS3.6: Trung bình thời gian chạy (giây) của 5 thuật toán cho 200 trình tự của các tập dữ liệu (a) DS1, (b) DS2, và (c) DS3.97 7 Danh mục các hình vẽ, đồ 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/.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.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.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.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.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.7: Khái quát hóa các mạng phát sinh loài điển hình [36].8: Hai hiện tượng tái tổ hợp phổ biến của người: (a) trao đổi chéo và (b) chuyển đổi gen.9: Biến đổi dữ liệu SNP thành dạng nhị phân. Vị trí có giá trị giống với tham chiếu là 0, giá trị khác tham chiếu là 1.10: Đồ thị ARG cho tập dữ liệu M gồm 7 trình tự độ dài 5 [26]. Trình tự tổ tiên là “00000”; 5 sự kiện đột biến tại các vị trí tương ứng (1,2,3,4,5) được ghi trên các cạnh xảy ra đột biến của đồ thị; 2 sự kiện tái tổ hợp xảy ra tại vị trí 3 và 4.11: Điểm cắt tái tổ hợp.12: Một ví dụ đồ thị ARG cho 4 trình tự với các ký hiệu: ■: trạng thái di truyền, ◘: trạng thái di truyền đột biến, □: trạng thái không xác định.13: Các cây thành phần (đường đậm nét) của đồ thị ARG trong Hình 1.14: (a) Ví dụ cặp vị trí tương thích: cặp vị trí này chỉ chứa 3 loại giao tử và có thể có được từ 1 tổ tiên chung thông qua 2 sự kiện đột biến.15: Một cây có nốt sùi cho tập trình tự giống với tập trong Hình 1.10 với 2 nốt sùi tương ứng với 2 chu trình tái tổ hợp không chung nút với nhau [27].16: (a) Đồ thị ARG cho tập 4 trình tự, trong đó trình tự s1, s2 là từ 2 cá thể khỏe mạnh, trình từ s3, s4 là từ 2 cá thể bị bệnh. (b) Đột biến 3 (vùng khoanh tròn) trên cây biên tại vị trí 3 của đồ thị ARG trong (a) cho ra sự phân biệt rõ nhất giữa các trình tự bệnh và trình tự không bệnh.1: Lưu đồ thuật toán Margarita.2: Vấn đề trong việc thực hiện sự kiện tái tổ hợp của Margarita.
Hai trình tự S1 và S2 với đoạn chung dài nhất giữa hai trình tự được biểu diễn bằng đoạn màu đen. Thuật toán thực hiện lần lượt 2 sự kiện tái tổ hợp R1 và R2 trên trình tự S1 để sinh ra 3 trình tự con S11, S12 và S13. Sau đó, trình tự con chứa đoạn chung dài nhất S13 sẽ được kết hợp với S2. Vì vậy, khi đoạn chung dài nhất được tìm thấy bên trong 9 trình tự, thuật toán phải thực hiện 2 sự kiện tái tổ hợp trên một trình tự và từ 2 trình tự ban đầu (S1 và S2) sẽ thành 3 trình tự ở thế hệ tiếp theo (S11, S12 và S' (S' = S2)).3: Tất cả các trình tự con từ phía bên trái của s mà có thể kết hợp với một trình tự trong D là một tập con của đoạn bên trái dài nhất của s ( sl ).4: Phân tách s bằng cách chọn các đoạn chung dài nhất trong s để kết hợp với các trình tự trong D có thể không dẫn tới số cực tiểu sự kiện tái tổ hợp.5: Sự kiện tái tổ hợp được biểu thị trong thuật toán ARG4WG.
(b) Với 1 tập 3 trình tự S1, S2 và S3, các đoạn đầu chung của mỗi cặp được tính toán (hình lượn sóng) và đoạn đầu chung dài nhất được xác định được mô tả bằng đoạn màu đen giữa trình tự S1 và S2. (c) Một sự kiện tái tổ hợp được thực hiện trên trình tự S1 để sinh ra 2 trình tự con S11 và S12. S12 chứa đoạn đầu chung dài nhất sau đó sẽ được kết hợp với S2. Như vậy, ARG4WG luôn thực hiện 1 tái tổ hợp trên 1 trình tự và từ 2 trình tự ban đầu (S1, S2) sẽ thành 2 trình tự ở thế hệ tiếp theo (S11, S’), trong đó S’ = S2 và S11 có ít vật liệu di truyền hơn S1.6: Trung bình thời gian chạy của Margarita, Margarita1.
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ
Trích dẫn luận án này
Đồ thị Tái tổ hợp Di truyền cho Dữ liệu Hệ gen (2020) [Luận án tiến sĩ, Đại học Yale]. LuanAn.net. https://luanan.net/cong-nghe-thong-tin/luan-an-tien-si-xay-dung-do-thi-tai-to-hop-di-truyen-cho-du-lieu-he-gen
Câu hỏi thường gặp
Luận án "Đồ thị Tái tổ hợp Di truyền cho Dữ liệu Hệ gen" nghiên cứu về vấn đề gì?
Luận án TS Công nghệ thông tin: Đồ thị tái tổ hợp di truyền cho dữ liệu hệ gen. Giải pháp đột phá trong phân tích dữ liệu sinh học phức tạp.
Luận án "Đồ thị Tái tổ hợp Di truyền cho Dữ liệu Hệ gen" được bảo vệ tại trường nào?
Luận án này được bảo vệ tại Đại học Yale. Năm bảo vệ: 2020.
Luận án "Đồ thị Tái tổ hợp Di truyền cho Dữ liệu Hệ gen" thuộc chuyên ngành gì?
Luận án "Đồ thị Tái tổ hợp Di truyền cho Dữ liệu Hệ gen" thuộc chuyên ngành Khoa học Máy tính. Danh mục: Công Nghệ Thông Tin.
Luận án "Đồ thị Tái tổ hợp Di truyền cho Dữ liệu Hệ gen" có bao nhiêu trang?
Luận án "Đồ thị Tái tổ hợp Di truyền cho Dữ liệu Hệ gen" có 112 trang. Bạn có thể xem trước một phần tài liệu ngay trên trang web trước khi tải về.
Cách tải luận án "Đồ thị Tái tổ hợp Di truyền cho Dữ liệu Hệ gen" về máy như thế nào?
Để tải luận án về máy, bạn nhấn nút "Tải xuống ngay" trên trang này, sau đó hoàn tất thanh toán phí lưu trữ. File sẽ được tải xuống ngay sau khi thanh toán thành công. Hỗ trợ qua Zalo: 0559 297 239.