Genome là gì

Introduction

Trong nội dung bài viết này, ta đã cùng mày mò về giải chuỗi trình tự gene - đó cũng là bài báo cáo của mình trong môn tin sinh học mình học tập ở kì trước cơ mà mình lười giờ mới bao gồm dịp đăng để số đông người rất có thể hiểu thêm một chút về một môn cực kỳ thú vị phối kết hợp giữa sinh học và tin học tập này.

Bạn đang xem: Genome là gì

Newspaper Problem

*

Vấn đề trên còn cạnh tranh hơn tưởng tượng bởi vì ta tất cả nhiều phiên bản sao của và một ấn bản tờ báo, và chắc chắn là ta cũng mất thông tin trong vụ nổ, bọn họ không thể gắn ráp như 1 trò chơi ghép hình bình thường. Thế vào đó, ta cần thực hiện sự chồng chéo từ các phiên bản sao khác biệt của tờ báo nhằm tái tạo thành tin tức vào ngày.

Genome sequencing

Bạn sẽ tự hỏi, vấn đề trên liên quan gì mang đến sinh học tập ? xác minh trình tự các nucleotide (As, Ts, Cs với Gs) vào một gene (hay còn được gọi là ADN), xuất xắc trình tự bộ gen (Genome sequencing) là trong số những nhiệm vụ cơ bản của tin sinh học. Bộ gen của chính họ có độ dài khoảng 3 tỷ nucleotide.

Bộ gene được giải trình tự đầu tiên, trực thuộc về một vi trùng φX174 chỉ gồm 5.386 nucleotide cùng được trả thiện vào năm 1977 vì Frederick Sanger . Bốn thập kỷ sau phạt hiện đoạt giải Nobel này, giải trình tự gen đã dẫn đầu trong nghiên cứu tin sinh học, khi giá thành giải trình tự sút mạnh. Do giá thành giải trình tự càng ngày giảm, họ hiện có hàng trăm bộ gen được giải trình tự, bao gồm cả cỗ gen của rất nhiều loài động vật hoang dã có vú.

*

Hình: trong giải trình trường đoản cú DNA, nhiều phiên bản sao tương đồng nhau của bộ gen bị phá vỡ tại phần ngẫu nhiên để tạo ra các short reads, sau đó giải trình tự và lắp ráp thành trình từ bỏ nucleotide của bộ gen.

Ta hoàn toàn có thể xem công việc rõ rộng trong thực tiễn ở hình ảnh sau:

*

Hình: sau quá trình thì hiệu quả sẽ giữ ở định hình FASTQ. Chúng ta đọc có thể vào https://en.wikipedia.org/wiki/FASTQ_format để hiểu thêm chi tiết.

Các nhà nghiên cứu không biết những reads này tự đâu trong bộ gen, bởi vậy họ phải sử dụng những reads chồng chéo cánh để tái tạo bộ gen. Bởi vì vậy, việc đặt một cỗ gen trở lại từ những việc các reads của nó hay genome assembly (tập hợp bộ gen) tương đương y Newspaper Problem

Sequence assembly

Trong nội dung bài viết này, họ sẽ tò mò về shotgun sequencing là một phương pháp được sử dụng để giải trình tự những sợi DNA tự dưng ( ta rất có thể tưởng tượng là như súng shotgun khi bắn đạn đã vỡ thành từng mảng ngẫu nhiên). Gồm 2 cách tiếp cận nhằm lắp ráp những trình tự shotgun reads thành các chuỗi gen liền kề dài thêm hơn là:

Cách tiếp cận gắn ráp trình tự de novo, các reads được đối chiếu với nhau, tiếp đến được ông xã lên nhau để kiến thiết liền kề dài ra hơn nữa ( không thực hiện thêm kiến thức nào).Cách tiếp cận dựa trên tham chiếu tương quan đến việc ánh xạ mỗi read tới một trình tự cỗ gen tham chiếu ( sử dụng kỹ năng và kiến thức dựa bên trên tham chiếu)

De novo sequence assembly

reads được tạo nên bởi các trình tự bây giờ thường tất cả cùng độ dài, chúng ta cũng có thể giả định một cách bình yên rằng reads gần như là k-mers với cùng một số quý giá k. Phần đầu của bài sẽ trả định một tình huống lý tưởng với không thực tiễn là toàn bộ các read đều đến từ cùng một chuỗi, không tồn tại lỗi và biểu lộ mức độ che phủ hoàn hảo. Sau đó, ta sẽ trình bày cách giảm bớt các mang định này để có bộ dữ liệu thực tế hơn.

The String Reconstruction Problem

Cho một chuỗi Text, k-mer composition ký kết hiệu là Compositionk(Text)Composition_k(Text)Compositionk​(Text) là tập hợp các chuỗi con k-mer của Text ( bao gồm cả các k-mers lặp).

Ví dụ Composition3(TATGGGGTGC)=ATG,GGG,GGG,GGT,GTG,TAT,TGC,TGGComposition_3(TATGGGGTGC) = ATG, GGG, GGG, GGT, GTG, TAT, TGC, TGGComposition3​(TATGGGGTGC)=ATG,GGG,GGG,GGT,GTG,TAT,TGC,TGG. Chú ý rằng ở đây ta liệt kê k_mer theo sản phẩm công nghệ tự trường đoản cú điển chứ chưa hẳn thứ từ của nó xuất hiện thêm trong chuỗi TATGGGGTGC. Ta làm điều này vì sản phẩm công nghệ tự đúng chuẩn của những reads không được biết lúc nào chúng được tạo ra ra.

Giải việc tìm tập hợp các k-mer xuất phát điểm từ một chuỗi là 1-1 giản, mà lại để tập phù hợp thành một bộ gen, họ cần việc nghịch hòn đảo của nó: xây đắp chuỗi trường đoản cú k-mers.

Trước khi chúng ta giải quyết vấn đề tái sinh sản chuỗi, hãy xem lấy một ví dụ sau về các thành phần 3-mer: AAT , ATG , GTT, TAA, TGT.

Cách thoải mái và tự nhiên nhất nhằm giải việc tái lập chuỗi là bắt chiếc cách giải của vấn đề báo và "nối" một cặp k -mers nếu chúng trùng nhau k -1 cam kết tự. Đối với lấy ví dụ trên, thuận lợi thấy rằng chuỗi phải ban đầu bằngTAA chính vì không bao gồm 3-mer dứt bằng TA. Điều này ý niệm rằng 3-mer tiếp theo sau trong chuỗi phải bước đầu bằng AA. Chỉ gồm một 3-mer vừa lòng điều kiện này là AAT, ta được: TAA AAT. Tiếp theo, AAT tiếp theo nó chỉ rất có thể là ATG, sau ATG vẫn là TGT, liên tục như vậy ta được chuỗi TAATGTT.

*

Có vẻ ta đã xử lý bài toán tái chế tác chuỗi ? tuy thế để chắc chắn là ta thêm một số trong những thành phần 3-mer nữa như sau:

*

Nếu chúng ta bắt đầu lại TAA, 3-mer tiếp theo trong chuỗi sẽ bước đầu với AA cùng chỉ có AAT, tiếp theo ATT chỉ tất cả ATG.

*

ATG tiếp theo sau đang là TGC, TGG, TGT. Chúng ta sẽ thử chọn TGT:

*

Sau TGT, chúng ta chỉ rất có thể chọn GTT:

*

Đến trên đây thì thuyệt vọng vì không có 3-mer ban đầu TT!. Chúng ta cũng có thể mở rộng lớn TAA sang bên trái nhưng không có 3-mer nào ngừng bằng TA.

Chuỗi đúng bắt buộc là TAATGCCATGGGATGTT.

Khó khăn trong câu hỏi lắp ráp bộ gen mô rộp này nảy sinh bởi vì ATG được lặp lại 3 lần, khiến họ có tía lựa chọn TGG, TGCTGT bằng phương pháp đó để mở rộng ATG. Những chuỗi con lặp đi lặp lại trong hệ gen không phải là sự việc nghiêm trọng khi bọn họ chỉ gồm 15 reads, tuy vậy với hàng triệu reads, vấn đề lặp lại khiến cho việc "nhìn trước" và kiến tạo tập hợp đúng đắn trở nên khó khăn hơn nhiều. Thật vậy, khoảng 1/2 bộ gen fan được chế tạo ra thành từ các lần lặp lại, ví dụ, trình từ Alu dài khoảng 300 nucleotit được lặp lại hơn một triệu lần, với có một vài nucleotit được chèn / xóa / sửa chữa mỗi lần.

String Reconstruction as a Walk in the Overlap Graph

Sự lặp lại trong một cỗ gen yên cầu một số ý kiến trước để xem trước sự lắp ráp bao gồm xác. Quay lại ví dụ trên ta thấy rằng TAATGCCATGGGATGTTTAATGCCATGGGATGTTTAATGCCATGGGATGTT là một trong những lời giải của 15 yếu tố 3-mers như hình minh họa sau:

*

Trong hình dưới, 3-mers tiếp tục trong TAATGCCATGGGATGTTTAATGCCATGGGATGTTTAATGCCATGGGATGTT được links với nhau cùng nhau thành genome path của chuỗi này. Ở đây, ta sẽ vận dụng quy tắc là hậu tố khớp ứng với k-1 ký tự cuối của thành phần này giả dụ là tiền tố của k-1 cam kết tự đầu thành phần kia thì sẽ có được mối links giữa chúng. Ví dụ, Prefix(TAA) = TA cùng Suffix(TAA) = AA.

*

Quan gần kề này cho thấy một cách thức xây dựng đường đi bộ gen của một chuỗi trường đoản cú nó k -mer thành phần: chúng ta sẽ áp dụng một mũi tên nhằm kết nối ngẫu nhiên k -mer mẫu mã này nhằm một k -mer mẫu kia nếu hậu tố của chủng loại này bằng tiền tố của mẫu mã kia.

Nếu ta tuân thủ nghiêm ngặt quy tắc trên, thì ta đang nối tất cả các 3-mer vào TAATGCCATGGGATGTTTAATGCCATGGGATGTTTAATGCCATGGGATGTT, mặc dù nhiên chúng ta không biết trước về cỗ gen này chỉ biết những 3-mer nên chúng ta cũng phải liên kết nhiều cặp 3-mer khác.

Hình overlap_graph.png: Genome path đã bặt tăm với mất thường hầu như nó vẫn ở đó, vì họ chỉ đơn giản dễ dàng là sắp xếp những nút của đồ gia dụng thị.

Nếu họ cho chúng ta đồ thị overlap_graph trên nhằm bắt đầu, bạn sẽ cần nên tìm đường đi trong thứ thị thế nào cho đi qua từng nút đúng đắn một lần. Một bé đường như thế sẽ giới thiệu cho ta một cỗ gen. Mặc dù việc tìm ra một tuyến đường như vậy hiện khó khăn như việc nỗ lực lắp ráp cỗ gen bởi tay, mặc dù nhiên, biểu đồ cho chúng ta một phương pháp hay để tưởng tượng mối quan hệ chồng chéo giữa reads.

Xem thêm: Câu Chủ Đề Có Vai Trò Như Thế Nào Là Câu Chủ Đề Của Đoạn Văn : Diễn Dịch

*

Bây giờ họ biết rằng để xử lý vấn đề tái thiết chuỗi, chúng ta đang tra cứu kiếm một đường dẫn trong biểu đồ chồng chéo mà tầm nã cập đúng mực mỗi nút một lần. Một con đường trong biểu đồ truy vấn mỗi nút một lượt được call là con đường Hamilton , để vinh danh bên toán học tín đồ Ireland William Hamilton. Nhưng vấn đề Hamilton thì chưa có thuật toán hiệu quả để giải nó cả.

Thay vào đó chúng ta sẽ chạm chán Nicolaas de Bruijn, một nhà toán học fan Hà Lan. Năm 1946, de Bruijn quan tâm đến việc giải quyết một vấn đề kim chỉ nan thuần túy, được biểu lộ như sau. Một chuỗi nhị phân là một trong chuỗi chỉ có 0 cùng 1 của; một chuỗi nhị phân là k -universal giả dụ nó chứa mỗi k -mer nhị phân đúng một lần. Ví dụ 0001110100 là 1 chuỗi 3 phổ quát, bởi nó chứa một trong số tám chuỗi 3 nhị phân (000, 001, 011, 111, 110, 101, 010 và 100) đúng chuẩn một lần.

Tìm một chuỗi k -universal tương đương với việc giải câu hỏi Tái tạo chuỗi lúc thành phần k -mer là tập phù hợp của tất cả các k -mer nhị phân. Do đó, việc tìm kiếm một chuỗi k -universal rất có thể được rút gọn thành việc tìm một đường Hamilton trong đồ gia dụng thị ông chồng lấp được hình thành trên toàn bộ các k -mers nhị phân (xem hình mặt dưới). Mang dù có thể dễ dàng kiếm tìm thấy đường đi Hamilton sau đây bằng tay, de Bruijn lưu ý đến việc xây dựng những chuỗi k -universal cho các giá trị tùy ý của k. Ví dụ, để tìm một 20-universal, các bạn sẽ phải xem xét một biểu đồ tất cả hơn một triệu nút. Hoàn toàn không rõ ràng làm thế nào nhằm tìm ra một đường đi Hamilton vào một đồ vật thị khủng như vậy, hoặc thậm chí là liệu một lối đi như vậy bao gồm tồn tại tuyệt không!

*

Hình: Một lối đi Hamilton (nút kết nối 000 đến 100) trong thứ thị chồng chéo của tất cả các 3-mers nhị phân.

Thay do tìm kiếm những đường đi Hamilton trong những đồ thị khổng lồ, de Bruijn đã cải cách và phát triển một cách hoàn toàn khác để biểu diễn thành phần k -mer bằng cách sử dụng thứ thị. Phần sau của chương này, bọn họ sẽ khám phá cách ông sử dụng cách thức này nhằm xây dựng những chuỗi càng nhiều (universal strings).

Walking in the de Bruijn Graph

Ta trở về với ví dụ cỗ gen TAATGCCATGGGATGTT cùng với chuỗi 3-mers của nó:

*

Lần này nuốm vì sử dụng 3-mers làm những nút như trước, ta sẽ dùng nó làm cho edge (cạnh):

*

Vì từng cặp cạnh liên tiếp đại diện cho 3 nucleotit liên tiếp xen phủ nhau, chúng ta sẽ gắn nhãn từng nút của trang bị thị này bằng 2-mer đại diện thay mặt cho các nucleotit chồng chéo được chia sẻ bởi những cạnh ở hai bên của nút.

*

Sau đó bọn họ gộp những nút hệt nhau nhau. Hình dưới ta gộp những AT thành một.

*

Cuối cùng, họ dán nhị nút bao gồm nhãn GG, tạo ra một nhiều loại cạnh đặc biệt gọi là vòng liên kết GG cho chính nó. Số lượng nút trong biểu đồ hiệu quả (hiển thị bên yêu cầu bên dưới) đã sút từ 16 xuống còn 11, trong khi số cạnh vẫn duy trì nguyên.

Đồ thị này được gọi là vật dụng thị de Bruijn của TAATGCCATGGGATGTTTAATGCCATGGGATGTTTAATGCCATGGGATGTT, ký kết hiệu là DeBruijn3(TAATGCCATGGGATGTT)DeBruijn_3(TAATGCCATGGGATGTT)DeBruijn3​(TAATGCCATGGGATGTT)

*

Từ đồ dùng thị de Bruijn của TAATGCCATGGGATGTTTAATGCCATGGGATGTTTAATGCCATGGGATGTT, vấn đề giải bài toán tái thiết chuỗi sẽ bớt thành việc đào bới tìm kiếm đường trong vật thị de Bruijn cơ mà truy cập đúng đắn mỗi cạnh một lần. Đường bởi vậy được call là lối đi euler.

Quay ngược vấn đề, ta tạo ra đồ thị De Bruijn từ những thành phần k-mers: đến tập vừa lòng Patterns tất cả toàn k-mers, các node trong DeBruijnk(Patterns)DeBruijn_k(Patterns)DeBruijnk​(Patterns) là tất cả các k-1 mers duy nhất mở ra ở tiền tố hoặc hậu tố trong Patterns. Ví dụ đến tập đúng theo 3-mers:

*

Sau đó, tập đúng theo 2-mers duy nhất mở ra dưới dạng tiền tố hoặc hậu tố của 3-mers trong tập hợp trên như sau:

*

Đối với tất cả k-mer vào Patterns, chúng ta kết nối nút tiền tố của chính nó với nút hậu tố của nó bằng một cạnh được đặt theo hướng để tạo nên DeBruijn(Patterns) như sau:

*

Sau khi trải qua chu kỳ màu xanh lá cây đã phát hành trước kia Cycle0Cycle_0Cycle0​, Leo tiếp tục đi bộ và cuối cùng tạo ra một chu kỳ lớn hơn Cycle1Cycle_1Cycle1​ được xuất hiện từ cả chu kỳ màu xanh da trời lá cây và blue color lam gộp lại thành một chu kỳ luân hồi duy nhất.

*

Trong hình trên, chu kỳ luân hồi 2 là Eulerian, tuy nhiên điều này chắc chắn là không yêu cầu là trường phù hợp của một vật dụng thị tùy ý. Nói chung, Leo tạo ra các chu kỳ lớn hơn và to hơn ở mỗi lần lặp, và vì chưng vậy bọn chúng ta đảm bảo rằng sớm tốt muộn một số Chu kỳ m sẽ đi qua tất cả các cạnh trong Đồ thị . Chu kỳ này cần là Eulerian, cùng như vậy bọn họ (và Leo) đã kết thúc.

Từ công việc trên ta có mã giả nhằm xay dựng quy trình Euler đến đồ thị Euler như sau:

*

Bây giờ bạn cũng có thể kiểm tra coi một thứ thị được đặt theo hướng có quy trình Eulerian hay là không , cơ mà còn con đường Eulerian thì sao? Hãy lưu ý biểu vật dụng de Bruijn ở bên trái trong hình bên dưới, mà chúng ta đã biết gồm đường Eulerian, nhưng không tồn tại chu trình Eulerian vì những nút TA cùng TT không cân bằng. Tuy nhiên, chúng ta cũng có thể biến đổi con đường Eulerian này thành một quy trình Eulerian bằng phương pháp thêm một cạnh nhất nối TT cùng TA, như vào hình mặt dưới.

*

Reference based mapping/alignment

Như tên gọi ở trên đây ta sẽ sử dụng một bộ gen được gắn thêm ráp trước đó được sử dụng làm tài liệu tham khảo. Những lần reads theo trình từ bỏ được căn chỉnh độc lập với trình tự tham chiếu này. Từng reads được đặt tại vị trí có tác dụng nhất

Phương pháp ngây thơ: Đánh giá hầu như vị trí bên trên tham chiếu.

*

=> Quá chậm chạp với mặt hàng tỷ reads trên một tham chiếu lớn.

Sử dụng chỉ mục nhằm tham chiếu.

*

Ở đây, ta vẫn tìm toàn bộ vị trí căn chỉnh có thể ( call là seed) và ta mang lại Read review với rất nhiều seed một.

*

Sau đó, ta xác minh sự link tối ưu cho các vị trí ứng viên giỏi nhất, tuy vậy nếu trong read mở ra việc chèn hoặc xóa một số ít nucleotide thì sẽ làm tăng độ phức tạp của bài toán căn chỉnh.

Sử dụng dynamic programming

Đây là phương pháp phổ vươn lên là nhất. Phần đa thuật toán hay sử dụng là Smith-Watherman , Gotoh ...

Bài toán sẽ gửi về xác định các vùng tựa như giữa nhị chuỗi của trình từ axit nucleic. Hình dưới miêu tả cho thuật toán Smith – Waterman.Mọi người có thể tham khảo ở đường dẫn wikipedia sau : https://en.wikipedia.org/wiki/Smith–Waterman_algorithm

*

Các khó khăn khi sử dụng cách thức này.

Các reads có thể khác với chuỗi tham chiếu ( các biến thể về cấu trúc).Tham chiếu có rất nhiều vị trí duplicateCó nhiều chiến lược khác biệt xử lý vấn đề trên:Bỏ qua readsĐặt ở các vị tríChọn 1 địa điểm ngẫu nhiênĐặt vào địa điểm đầu tiênCác chuỗi ko được chỉnh sửa có thể được nhằm trong "thùng rác" để giải pháp xử lý sau vì phải thêm thông tinSequences không tương xứng tại địa chỉ nàoSequences với nhiều vị trí hoàn toàn có thể căn chỉnh.

*

De novo vs. Reference

Căn chỉnh dựa trên tham chiếu (Reference based alignment)

Tốt cho SNV ( single nucleotide variants ), small indelsGiới hạn về độ nhiều năm của Reads nhằm phát chỉ ra tính năng.Làm bài toán với deletions với duplications (CNVs - Copy-number variation)+ Sử dụng thông tin bao phủPhương pháp này khôn cùng nhanhKết quả của việc căn chỉnh không nhất thiết phải tương tự như trình từ bỏ tham chiếuYêu cầu phải có trình từ tham chiếu ( reference sequences) tương tự với tài liệu đầu vào

Lắp ráp De novo

Cố gắng tạo nên original sequence (trình từ mẫu)Tốt cho các biến dị tất cả cấu trúcTốt cho các trình tự hoàn toàn mới không tồn tại trong tham chiếuChậm hơn cùng yêu cầu hạ tầng để tính toán

Tóm lại khi ban đầu giải trình một bộ gen thì ta đang sử dụng phương thức dựa trên tham chiếu.