风暴魔域挂机刷魔石,快速培养幻兽升星教程 | 文獻求助論文范文 | 論文題目 | 參考文獻 | 開題報告 | 論文格式 | 摘要提綱 | 論文致謝 | 論文查重 | 論文答辯 | 論文發表 | 期刊雜志 | 論文寫作 | 論文PPT
风暴魔域挂机刷魔石,快速培养幻兽升星教程您當前的位置:风暴魔域挂机刷魔石,快速培养幻兽升星教程 > 生物學論文 > 基因工程論文

风暴魔域军团宴会:高通量測序技術和序列拼接算法探析

時間:2019-05-27 來源:計算機科學 作者:周衛星,石海鶴 本文字數:16853字

风暴魔域挂机刷魔石,快速培养幻兽升星教程 www.awyiy.icu   摘    要: 高通量測序 (High-throughput Sequencing, HTS) 技術是繼第一代測序技術之后發展起來的一種新型測序方式, 又被稱為下一代測序技術。與第一代測序技術中采用基于Sanger方法的自動、半自動毛細管測序方法不同, 高通量測序技術采用了基于焦磷酸測序的并行測序技術, 是對傳統測序技術的一項重要技術突破, 它不僅克服了第一代測序技術高成本、低通量、低速度的缺點, 而且能滿足現代分子生物學和基因組學快速發展的需求, 達到低成本、高通量以及快速的目的。相較于第一代測序數據, 高通量測序數據具有典型的長度短、覆蓋度不均勻以及準確率低的特點, 同時第三代測序技術雖保持了高通量測序技術邊測序邊合成的思想, 但采用了更為高效的單分子實時測序技術和納米孔測序技術, 具有高通量、低成本和測序數據長的優勢。因此, 要獲得完整的全基因組基因序列, 生物學家就需要使用一種技術將短測序reads拼裝成一條完整的基因單鏈序列。在這種情況下, 序列拼接算法應運而生。首先, 介紹了序列拼接算法的發展背景以及高通量測序技術的相關概念, 分析了高通量測序技術在序列拼接算法中所具有的優勢;其次, 通過總結序列拼接算法的發展成果, 按基于greedy策略、基于Overlap-Layout-Consensus (OLC) 策略和基于De Bruijn Graph (DBG) 策略的分類對序列拼接算法進行闡述;最后, 探討了序列拼接算法的相關研究方向和發展趨勢。

  關鍵詞: 高通量測序技術; 序列拼接算法; greedy; Overlap-Layout-Consensus; De Bruijn Graph;

  Abstract: High-throughput sequencing technology is a new sequencing method developed after the first generation sequencing technology, also known as next-generation sequencing technology.Different from the automatic and semi-automatic capillary sequencing method based on Sanger, the high-throughput sequencing technology adopts the parallel sequencing technology based on pyrosequencing.It not only conquers the shortcomings of high cost, low throughput and low speed of the first generation sequencing technology, but also meets the demands of the rapid development of modern molecular biology and genomics with low cost, high throughput and fast speed.Compared with the first generation sequencing data, high-throughput sequencing data are characterized by short lengths, uneven coverage and low accuracy, and the third-generation sequencing technology adopts more efficient single molecular real-time sequencing and Nanopore sequencing technology as well as the principle of sequencing and synthesis, which has the advantages of high throughput, low cost and long sequencing data.Therefore, in order to obtain complete genome sequence, a technique is needed to assemble short sequencing reads into a complte single-stranded sequence of genes.In this case, the sequence assembly algorithm was proposed.Firstly, the development background of sequence assembly algorithms and the related concepts of high-throughput sequencing technology were introduced, and the advantages of high-throughput sequencing technology on sequence assembly were analyzed.Secondly, by summarizing the development of sequence assembly algorithms.The sequence assembly algorithms were illustrated, according to the algorithm classifications, respectively, by greedy strategy, Overlap-Layout-Consensus (OLC) strategy and De Bruijn Graph (DBG) strategy.Finally, the research direction and development trend of sequence assembly algorithms were discussed.

  Keyword: High-throughput sequencing; Sequence assembly algorithms; Greedy; Overlap-layout-consensus; De bruijn graph;

  1、 引言

  隨著測序技術的發展, 生物學家獲得了海量的生物測序數據, 這些測序數據被廣泛應用于醫學、遺傳科學和生物學等諸多領域。為了通過分析這些測序數據來更多地了解生物之間的功能、結構和進化關系等生物學含義, 研究人員建立了大量的公共測序數據庫, 如美國國家生物技術信息中心NCBI、歐洲生物信息研究所EBI、日本DNA數據庫DDBJ, 從而有利于高效地整合、處理以及分析不同類型的測序數據, 使得人們可以通過互聯網來更為方便地進行交流和研究, 保證資源和信息共享[1];同時, 大量的相似性比對工具[2,3,4,5,6]也被成功地用于解決同源性數據庫搜索和高通量測序數據相似性比對問題。由于一些生物基因組全序列的成功測定, 人們可從整個基因組的規模來全面了解現有生物基因之間的功能和結構關系及差異, 同時能夠清晰了解并研究導致生物病變的侯選基因, 進而促進生物基因科技的發展, 對生物學研究、探索與認識生物進化的本質提供重要參考, 為序列拼接算法的快速發展奠定基礎。

高通量測序技術和序列拼接算法探析

  高通量測序技術的發展使得研究人員能夠以更高的效率來獲得細菌、真菌乃至動植物的全基因組序列圖譜, 加快了對相應物種基因的研究, 使得研究相近物種間的進化關系成為可能。在人類基因組計劃[7]完成以來, 通過蛋白質序列測定、基因組測序和分子結構解析等試驗, 千人基因組工程[8]和UK10K[9]成功地測序完成了上千人的基因組圖譜, 且對單個人的測序花費降低至1 000美元以下[10]。然而, 高通量測序數據的膨脹式發展已然成為了現有計算條件下進行基因組測序的桎梏, 同時, 高通量測序數據存在測序reads短、重復率高以及覆蓋度不均勻等不足。因此, 要獲得生物的完整全基因組基因序列, 生物學家就需要使用一種技術將短測序reads拼裝成一條完整的基因單鏈序列。在不斷研究后, 生物學家發現可以使用計算機, 根據短測序reads間的重疊關系將這些reads數據拼接成一個或多個較長的序列片段, 最終獲得生物的全基因組基因序列, 該拼接過程被稱為序列拼接。因此, 研發一種針對超高量基因序列數據的基因組拼接組裝技術是打破上述瓶頸的重要途徑之一, 這也是人類全基因組序列研究的重要內容。

  針對現有組裝算法的研究與發展, 本文第2節簡要介紹高通量測序技術的相關概念;第3節按基于greedy策略、基于OLC策略和基于DBG策略將序列拼接算法分成3類, 并闡述每類中具有代表性的算法;最后進行總結, 分析并探討序列拼接組裝算法研究中存在的問題和相關發展方向。

  2、 高通量測序技術

  高通量測序技術是在第一代測序技術基礎上改進而來的一種新型基因組測序技術。第一代測序技術主要以基于Sanger[11]方法的自動、半自動毛細管測序技術為標志。在2003年, 科學家采用該技術完成了首個人類全基因組測序, 總共耗時3年并花費了4.37億美元。為了解決第一代測序技術存在的成本高、通量低、速度低的缺點, 滿足現代分子生物學和基因組學快速發展的需求, 達到低成本、高通量以及快速的目的, 454 Life Sciences公司于2005年開發了一種基于焦磷酸測序法的超高通量基因組測序系統, 其能夠快速、準確地測定一段較短的DNA序列, 成為了第二代測序技術的開端。因此, 第二代基因組測序技術也被稱為高通量測序技術或下一代測序技術。2007年, 科學家們首次使用高通量測序技術, 以耗時4個月和不到150萬美元的花費完成了“DNA之父”詹姆斯·沃森的個人基因組測序。

  隨著HTS的發展, 所需拼接的基因組數據量也急速增長, 而且二代測序產生的reads較短 (30~500 bp) [12], 導致不僅HTS數據無法滿足大多數序列分析的需要[13], 而且難以設計一種通用數據融合技術去處理高度不確定性、多源性和雜合度的基因組數據以及通過獲取局部信息來反映全局問題[14]。為了應對該挑戰, 越來越多的針對提高組裝效率和適應不同測序序列數據的基因組拼接技術不斷出現, 例如并行化拼接過程以及優化算法結構等。自2007年以來, 已經有70多個測序工具[15]嘗試解決該問題。然而, 計算機的微處理性能和存儲設備的容量平均每18~24個月增長一倍, 而基因組測序數據平均4~5個月就增長一倍, 因此延長測序序列長度和提升基因組組裝算法效率成為了目前拼接龐大基因數據的重要方式。為了解決這一問題, 3GS (Third Generation Sequencing) 測序技術應運而生。3GS雖然保持了第二代測序技術的邊合成邊測序的思想[16], 但與第二代測序技術不同, 其在測序過程中使用了單分子熒光測序技術或納米孔測序技術[17,18,19,20,21]。3GS在保證了原有高精度的情況下, 測序讀長超過10 kB[22], 并且無需進行PCR擴增, 具有更快的測序速度和更低的測序成本, 為拼接基因組序列提供了便利。

  HTS進行基因組測序時具有如下優勢[23]:突破了一系列限制平行測序規模的瓶頸, 極大地提高了平行測序的能力;能夠處理龐大的基因組序列, 具有高通量的特點;極大地降低了測序成本等。但是由于新一代測序技術的發展, 測序所產生的序列片段太短、覆蓋度不均勻以及3GS產生的序列數據的錯誤率較高等問題, 不僅導致了在進行序列拼接組裝的過程中需要進行大量計算, 而且降低了序列拼接組裝的精確度。因此, 在現有計算能力大致不變的情況下, 學者們提出了一種新型的數據結構算法。該算法主要研究序列拼接算法的并行化問題, 以提高計算機的并行計算能力, 同時通過增加序列片段的長度來減小重復序列片段的影響, 從而極大地提高針對高通量測序技術所產生序列的組裝速度和精確度, 并且已經產生了大量的融合二代數據和三代數據優勢的拼接算法[24,25,26], 即利用“linked reads”來提高拼接的完整度。

  3、 序列拼接算法

  根據拼接策略的不同, 可以將序列拼接算法分為3種:基于greedy策略的算法、基于Overlap-Layout-Consensus策略的算法和基于De Bruijn Graph策略的算法。按照出版時間和拼接策略進行分類的結果如表1所列。

  表1 主要序列拼接算法的分類
表1 主要序列拼接算法的分類

  3.1、 基于greedy策略的拼接算法

  Greedy策略是最早被應用于HTS拼接算法的策略?;趃reedy策略的拼接算法首先通過一定的最優化規則來獲取reads或contigs (重疊群) 作為初始種子序列, 然后基于這個種子序列向兩邊添加更多的reads或contigs, 延伸方案一般有基于最大重疊長度和投票機制兩種[27], 直到reads或contigs無法再繼續延伸為止, 最后重復上述過程, 直到所有序列拼接完成, 如圖1所示。

  圖1 Greedy策略拼接示意圖
圖1 Greedy策略拼接示意圖

  Fig.1 Assembly graph based on greedy strategy

  圖1中, 在序列1的拼接過程中, 第一條待拼接序列和序列1在序列比對過程中有一個錯配G (用深灰色表示, 下同) , 且有9個堿基匹配, 而下面的其他3條序列錯配數分別為2, 3, 2, 匹配數分別為8, 5, 4, 因此將選取第一條進行拼接。但需要注意的是, 由于重復序列3 (淺灰色序列) 的影響, greedy策略可能會導致在實際拼接過程中序列1和序列4拼接在一起, 從而產生錯誤拼接, 進而影響拼接精確度。

  在greedy策略中, reads或contigs的選取是按照堿基拼接質量遞減的順序來考慮的, 且該類算法能夠應用于基于OLC策略以及DBG策略的拼接算法中。然而, 該類算法不僅容易陷入局部最優, 而且未充分考慮重復序列以及錯誤序列所造成的拼接歧義, 使得組裝序列的錯誤率較高, 一般僅適用于小型基因組的拼接。其中比較經典的算法有SSAKE[28], VCAKE[29], SHARCGS[30], 這幾種算法不顯示使用拼接圖, 而是基于重疊關系使用貪婪算法建立一致性序列。

  wiseScaffolder[31]是一種建立在重疊群上并支持手工控制的迭代擴展策略。該算法把由paired-end reads拼接而成的重疊群與Meta-pair reads進行比對, 利用該比對信息檢測出重疊群中的嵌合體位置并利用覆蓋度估計重疊群拷貝數, 從而在嵌合體位置分割重疊群, 以消除嵌合體位置對序列拼接的影響。wiseScaffolder按照單拷貝重疊群長度從大到小的順序進行兩端擴展, 并利用比對信息將未參與scaffolding的重疊群插入到圖中以消除空位。最后, 算法利用Meta-pair reads與拼接序列進行比對糾錯, 以提高拼接序列的質量和完整度。

  npScarf[32]是一種能在長reads測序過程中進行短reads序列拼接的迭代擴展算法。算法利用了Nanopore測序的實時特征, 首次實現了實時控制測序器的數據流并獲得測序狀態信息, 降低了過度測序的花費。算法利用重疊群拼接過程的覆蓋度識別出獨立重疊群, 然后找出同時與兩個獨立重疊群重疊且得分最大的reads用于橋接重疊群, 并按照重疊得分由大到小的順序迭代橋接所有的獨立重疊群, 從而形成大型重疊群, 同時通過與非獨立重疊群比對消除大型重疊群中的空位, 獲得一致性序列。

  ALPS[33]是一種基于貪心策略的從頭拼接算法, 該算法通過整合已測序的肽序列、序列的位置置信度、數據庫以及同源性搜索信息, 首次以較高的精確度自動地拼接出完整的單克隆抗體序列。首先, 利用測序產生的肽序列、相近數據庫序列和同源性搜索序列建立以 (k-1) -mer為頂點、邊長為k的有向DBG。為提高拼接質量, 算法綜合序列強度和位置置信度對圖中各頂點加權, 從而獲得加權DBG。然后, 以圖中最大權重頂點為重疊群種子, 向兩邊選取鄰近權重最高的節點進行擴展, 并刪除圖中已擴展節點, 直到圖為空或達到指定重疊群數為止。當未得到完整序列時, 算法需要利用相近數據庫序列進行空位填充, 并將重疊群合并為單個完整序列。

  ISEA[34]是由中南大學的王建新教授團隊提出來的一種利用雙端信息和拼接距離分布進行從頭拼接的迭代種子擴展算法。該算法利用基于DBG的種子擴展策略和打分函數進行處理, 在數學統計層次上保證了序列的拼接精確度并提高了拼接效率, 具有較好的統計學意義。

  3.2、 基于OLC策略的拼接算法

  基于該策略的拼接算法主要分為3個階段。

  1) Overlap階段:

  該階段對所有參與拼接的reads進行兩兩比對, 計算其reads間的重疊關系。當兩比對reads的重疊區域達到一定閾值時, 將其保留, 用于建立重疊圖。

  2) Layout階段:

  根據上一步中的重疊關系建立關于整個reads序列之間的重疊圖, 通過遍歷重疊圖找出能夠經過圖中大多數節點且只經過一次的路徑作為contigs。

  3) Consensus階段:

  通過多序列比對, 使用配對信息將這些contigs拼接組裝成一致性序列。但是, 由于目前無法有效降低多序列比對的復雜度, 因此常使用漸進式雙序列比對算法替代?;詬貌唄緣鈉唇鈾惴ㄈ繽?所示。

  圖2中, 左邊區域表示了建立多個reads間的重疊關系, 右邊則表示根據已建立的重疊關系而生成的重疊圖, 這里設置重疊數量至少為7, 其中淺灰色線則表示兩連接對象的重疊堿基數也滿足條件。Consensus階段則表示在獲得contigs之后, 將其與原始pair-end數據進行比對, 以確定contigs之間的相對位置并消除空位, 從而將contigs連接成一致性序列。

  圖2 OLC策略拼接示意圖
圖2 OLC策略拼接示意圖

  Fig.2 Assembly graph based on OLC strategy

  基于OLC策略的拼接算法[35,36,37]由于涉及到大量的序列比對過程, 用于拼接短reads序列時的計算開銷過大, 因此常用于組裝一代或三代測序技術產生的較長序列數據。但對于三代測序技術, 其測序reads堿基的錯誤率達到了15%, 拼接組裝該類測序數據時一般都需要對其初始序列進行預糾錯。

  文獻[38]提出的HINGE利用拆分重復序列的最優化方案來解決重復序列影響從頭拼接長reads的問題。HINGE利用從重疊圖中獲得的比對信息在reads上加入hinges標記, 這些標記被放置在與無橋接重復序列匹配的reads所對應的開始與結束位置。算法傳播該標記信息來處理與拼接無關的重復序列, 并建立一個只能夠合并無橋接重復序列片段的最大拆分重復序列重疊圖。同時, 該算法利用DALIG-NER[39]能夠滿足在15%錯誤率下進行比對的性質, 使得在數據預處理時僅需過濾嵌合體reads, 最后在Consensus階段中修正拼接錯誤。

  文獻[40]提出的Canu是一種高效且準確利用自適應k-mers權重以及拆分重復序列來拼接包含大量重復序列以及高錯誤率reads的PacBio或者Nanopore測序數據的組裝算法, 具有低開銷、高覆蓋度的優勢。該算法利用基于tf-idf加權技術的重疊策略來構建關于k-mers的重疊圖, 能夠最優化處理重復序列對拼接的影響, 并突破計算具有高噪音單分子測序數據重疊關系的瓶頸。另外, 為了最大化Canu算法的準確性以及完整性, Canu在整個拼接過程中多次對reads和重疊區域進行糾錯。該算法可運行于獨立電腦或者集群服務器上, 并自動選取相對應的算法執行方式。

  文獻[41]提出的DBG2OLC拼接算法是一種綜合利用NGS (Next-Generation Sequencing) 和3GS數據來解決高錯誤率3GS長reads拼接問題并降低測序開銷的混合算法。它利用SparseAssembler[42]拼接NGS數據獲得帶索引的contigs, 并將contigs與3GS數據進行比對, 從而可使用contigs標識符來壓縮表示長reads。該操作不僅可以降低算法對測序覆蓋度的需求, 而且可以極大地減小建立長reads重疊圖以及糾正錯誤的計算開銷。此外, 該算法對長reads利用多序列比對來消除重疊圖中的嵌合體reads以及錯誤contigs標識。

  文獻[43]提出的miniasm算法是一種用于拼接SMRT (Single-Molecule Sequencing in Real Time) 以及ONT (Oxford Nanopore Technologies) 測序所產生的高噪聲長reads而無需進行錯誤糾正和拋光的基于OLC策略的從頭拼接算法。該算法能夠在實現一定連續性以及精確性的預期下快速且簡便地組裝序列, 首先通過minimap算法計算所有reads間的重疊信息, 特別地, 該算法中提出的序列比對格式PAF使得它可以與其他比對算法進行融合以支持后續拼接;然后尋求已簡化重疊圖中滿足通過出入度為1的節點的路徑作為unitigs。鑒于該算法暫無consensus步驟, Racon[44]算法在其基礎上設計了consensus步驟, 通過利用測序長reads與拼接產生的unitigs進行比對, 產生了高質量的一致性序列。

  文獻[45]提出的TULIP拼接算法是一種將大型基因組拼接問題分割為局部從頭拼接其長reads子集合的算法。算法在拼接過程中通過比對Illumina測序的短reads序列以及ONT測序的長reads序列來獲取它們的比對信息, 并建立以短reads為頂點、比對在同一長reads中連接短reads的序列片段作為邊的重疊圖, 從而極大地簡化了拼接算法的重疊計算過程, 使得計算復雜度接近于線性。此外, 該算法在拼接之前也無需對長reads數據預糾錯, 而是利用ONT對最后產生的一致性序列進行拋光處理。

  文獻[46]提出的SSVAGE拼接算法是第一個基于重疊圖策略的從頭拼接病毒準種的算法。該算法有3種不同的重疊圖構建模式:SSVAGE-de-novo表示無參考序列的重疊圖構建;SAVAGE-b-ref表示使用其他算法組裝樣本序列而產生的一致性序列作為參考序列構建重疊圖;SAVAGE-h-ref表示輸入已存在的高質量參考序列構建重疊圖。對于無參考序列的重疊圖構建, 算法使用FM-index方法計算reads間的重疊, 反之則通過比對reads與參考序列來建立reads間的重疊關系。該算法通過計算圖中的團來識別變異與測序錯誤, 從而生成了具有高質量的一致性序列。

  3.3、 基于DBG策略的拼接算法

  基于DBG策略的拼接算法一般包含如下過程。

  1) DBG建立階段:首先將所有待拼接的reads分割成長度為k的序列片段, 稱為k-mers, 且同一reads中的相鄰k-mers有k-1個堿基重疊;然后利用這些k-mers建立DBG, 其中k-mers作為圖的節點, 圖中相鄰節點間有k-1個堿基重疊, 只有兩k-mers首尾的第一個堿基不同。

  2) contigs構建階段:在DBG建立完成后, 拼接算法一般需要利用啟發式算法消除由測序錯誤以及雜合位點引起的tips和bubbles等錯誤來簡化圖結構, 并找出只經過DBG圖中每條邊一次的歐拉路徑作為contigs。

  3) scaffolding階段:將上一步中獲得的contigs與原始測序reads進行比對, 并根據比對信息以及reads位置信息填充無連接contigs之間的空位, 通過組裝得到最后的一致性序列。

  基于DBG策略的拼接算法如圖3所示。

  圖3 DBG策略拼接示意圖
圖3 DBG策略拼接示意圖

  Fig.3 Assembly graph based on DBG

  在DBG圖中, k-mers的大小為3 (k值一般為奇數) , 淺灰色圖節點表示tips結構, 深灰色圖節點則為重復序列, 其中上下兩回路所連接的圖節點都表示bubbles結構。簡化該氣泡結構后可得堿基序列, 如圖3中的序列TCCGTA和TCTCCA。右下角為contigs拼接結果, 其中Consensus階段和OLC策略類似。

  基于DBG策略的拼接算法[47,48,49]被廣泛應用于拼接來自SOLiD和Solexa平臺測序產生的短reads序列。DBG結構最早是介紹并運用在EULER[38]拼接算法中, 該數據結構非常適合于對具有重疊關系的短重復reads序列進行測序, 且能夠極大地減少序列冗余所帶來的內存消耗等問題。DBG算法很好地彌補了HTS數據中測序序列長度較短的缺點, 在拼接過程中支持并行化且只需要較少的比對操作, 極大地縮短了基因組序列的拼接時間, 提高了拼接效率。但由于錯誤的k-mers和大量重復序列會極大地降低基于該種策略算法的組裝效果, 因此該類算法一般都需要對拼接reads和DBG圖或已拼接完成的一致性序列進行糾錯, 以提高拼接精確度, 同時需利用三代測序數據、“linked reads”數據以及光學圖譜技術提高拼接的完整度。現有拼接算法大部分都以該策略作為主要的算法數據結構。

  3.3.1、 ALLPATHS

  ALLPATHS[50]是一種被用于拼接大型基因組序列的基于DBG策略的算法, 它由Broad Institute of MIT and Harvard研究中心于2009年研發出來, 主要是為了解決難以利用具有高重復率特征的二代測序短reads進行從頭拼接的問題。該算法不僅可以處理短reads基因組數據, 而且可以應用于所有的DNA序列數據, 同時具有較高的拼接完整性、連續性以及正確性, 并保留了由序列多樣性所引起的內在歧義。

  該算法主要有兩個關鍵過程。首先, 對于一個配對read, 找出通過該read的所有序列路徑;其次, 使用配對信息對基因組進行分離, 同時選取滿足一定長度和復本數量的路徑合并成無分支結構的unipaths, 從而建立unipaths圖, 使局部拼接可并行化。在執行過程中, 超短reads (一般長度為25~50 bp) 之間具有大量的overlaps信息, 但這些overlaps信息大部分是錯誤的 (不是連續的短reads) 。為了解決這一問題, ALLPATHS算法引入了k-mers編號算法, 使得k-mers可以按照reads的順序進行連續編號, 進而可以根據編號的差別來避免不必要的overlaps計算開銷, 同時提高序列拼接的連續性。為了達到更高的拼接準確性和完整性, ALLPATHS在拼接過程中對所有的reads進行錯誤糾正[51], 同時利用所有局部拼接產生的結果之間的重疊信息組合生成一個全局拼接圖, 最后利用pair-end信息消除該全局圖中的錯誤分支結構。

  2011年, Broad Institute of MIT and Harvard研發中心基于并行測序技術產生的大規模哺乳動物基因組序列的拼接組裝問題提出了ALLPATHS-LG[52]拼接算法。該算法是測序技術與高性能計算方法的結合體, 對ALLPATHS中算法在處理重復序列、錯誤糾正等方面進行改進, 并使用了跳查文庫。該算法雖然要求必須至少制備一個具有overlapping的paired-reads文庫, 但是在序列組裝錯誤率與拼接序列連續性方面卻取得了平衡, 具有較好的基因組覆蓋度和精確度, 是一種公認的較好基因組從頭拼接組裝軟件。

  3.3.2、 SOAPdenovo

  SOAPdenovo[53]基因組序列拼接軟件是華大基因在2010年研究設計的一種解決難以從頭拼接由NGS并行DNA測序技術產生的大規模重復短序列的拼接器, 在處理序列中產生的SV (Structure Variation) 問題和indels問題 (插入和缺失等) 方面具有較大的優勢, 能夠更好地促進在核苷酸層次上準確理解生物進化歷史和生物學過程, 是一種用于構造大型參考基因組的有效從頭拼接組裝算法, 可以進行較高精確度的探索, 并分析未知個體生物基因。

  該算法首先對所有的k-mers建立哈希索引, 并行化處理已分割的reads數據集, 同時利用動態規劃算法和等位基因的方式來消除或修正低頻率的k-mers。其將從已修正的DBG中獲得的歐拉路徑作為contigs, 并將獲得的contigs重新與所有的reads進行比對來確定contigs間的相對順序, 以正確連接contigs。在scaffolding階段, 算法通過迭代合并重疊的contigs以及pair-end信息消除由重復序列導致的contigs間空位, 使得待組裝序列更為完整。

  SOAPdenovo的擴展版本SOAPdenovo2[54]和SOAPdenovo-Tran[55]在DBG構建階段利用一種多k-mers值策略, 通過由小到大迭代地利用k值來消除不同長度的重復序列, 充分利用了小k-mers處理低覆蓋度與錯誤reads的優勢以及大k-mers處理重復序列的高效性特征;在scaffolds構建階段也使用迭代的拼接距離來消除空位和雜合contigs, 進一步提高了拼接組裝的效率、敏感性以及準確率。文獻[55]可被用于拼接轉錄組。

  3.3.3、 IDBA-UD

  IDBA-UD[56]是由香港大學的彭煜等提出的一種解決單細胞測序與宏基因組測序技術難以對不同物種間或同物種中基因組的不同區域的不均勻測序深度進行測序的從頭拼接算法。相較于其他已存在的組裝算法, 該算法能夠在不均勻測序深度數據條件下構造出較長且高拼接精確度的contigs。

  該算法首先對待測序的reads使用合適的k值進行質控, 然后對于建立的DBG, 根據序列中測序深度的高低兩種情況, 利用與測序深度相關的閾值來消除圖結構中的錯誤k-mers, 并且使用雙端測序信息來解決圖中的重復分支問題, 獲得了完整且準確的contigs。算法的主要執行過程為:首先, 針對序列的不同測序深度建立相應的k值, 并根據k值從小到大迭代地建立DBG;然后, 求各圖中的歐拉路徑并將其作為contigs, 對獲得的contigs和失配的k-mers使用雙端信息消除錯誤分支, 提高局部拼接的精確度并填補空位。在每一個過程中, 都需要將獲得的contigs與包含待測序reads數最多的置信contigs進行比對來糾正錯誤, 每個迭代的DBG建立都需不斷進行錯誤修正來保證局部拼接過程的正確性, 從而提高拼接的精確度。

  在進行單細胞序列數據或宏基因組序列數據拼接時, 由于測序深度不均勻的影響, 常見的處理DBG圖中出現錯誤k-mers、空位問題以及錯誤分支結構的方法難以提高序列拼接性能。因此, IDBA-UD改進了velvet-SC[57]中利用一個固定的閾值來解決在不同測序深度下的單細胞序列數據的算法, 根據測序深度的不同對相關閾值作適應性處理, 從而更能符合單細胞與宏基因組中測序深度不均勻的特性。IDBA-UD算法中對不同測序深度設置不同閾值的方法已經被成功應用于轉錄基因組組裝算法[54,58]。

  3.3.4、 metaSPAdes

  metaSPAdes[59]是一種通過融合已經被證明了的一系列SPAdes[60,61,62,63,64]工具中的方法來拼接單細胞和高度多態的二倍體基因組的拼接器, 其能夠并行化處理宏基因組拼接過程中的各項挑戰, 如菌株之間差異細微、不同物種的冗余度水平各異、菌株共享高保守區域以及大量冗余度不同的相近菌株混合等。算法基于交叉合成的數據集和與被拼接宏基因組相關的真實數據集, 解決了在宏基因組基準測試中無參考基因組的問題。測試結果顯示, 該算法在scaffold長度、基因預測能力以及read與scaffold比對統計等方面具有較大優勢。

  算法首先利用SPAdes[60]對文庫中所有的reads建立DBG, 然后通過簡化該圖將其轉化為拼接圖, 并將拼接圖中獲得的一致性路徑作為該宏基因組中的長基因組片段。該算法適用于對具有多種不同的測序深度混合菌株進行拼接, 并在拼接精確度以及連續性方面取得了平衡。在簡化DBG操作中, 算法刪除了圖中的tips, 但在去除bulge (類似bubbles結構) 結構的過程中保留了其原始信息, 該信息可用于識別scaffolding中的重復序列, 提高了拼接混合菌株的一致性序列質量。與傳統拼接算法使用全局覆蓋度閾值來刪除圖中低覆蓋度的邊不同, metaSPAdes首先計算點與邊的覆蓋度值, 若邊覆蓋度乘以閾值比例小于所連接點的覆蓋度, 則斷開該連接, 而非直接刪除該邊, 這樣可以盡可能保留稀有菌株的信息。在scaffolding階段時, 算法在ExSPAnder[61]算法的重復序列確定規則中考慮了局部覆蓋度因素, 消除了重復路徑的影響, 并利用局部覆蓋度與分支間邊的覆蓋度的關系處理了圖中的分支問題。

  該算法支持簡化DBG階段的并行化, 同時對k-mers使用了hash存儲和擴展矩陣, 從而快速地提高了簡化DBG階段以及scaffold階段的存儲效率, 使得算法能夠拼接大規模的復雜宏基因組數據集。

  結束語 高通量測序技術是基因組序列拼接算法發展的重要催化劑之一。處理快速增長的海量基因組序列數據, 對基因疾病進行預測與治療, 以及對生物同源性分析等問題的研究, 成為了序列拼接組裝算法發展的關鍵目標和主要研究動力, 但也給未來的基因組拼接組裝算法的研究與發展帶來了巨大的挑戰。相比于第一代測序技術, 研究人員能夠利用高通量測序技術獲得較高的序列測序深度, 但測序reads長度變短、reads錯誤率增高以及重復序列對拼接的影響越來越大, 且研究方向由傳統的單個物種的全基因組序列組裝轉變為目前多物種混雜的短reads數據集組裝與分析, 同時計算方式也由本地計算逐漸發展為以“云計算”為基礎的互聯網云計算。因此, 研究人員需開發出新型的拼接組裝算法來應對高通量測序下大量短reads數據迅速增長的需求, 并結合三代測序技術的優勢, 解決在序列拼接組裝過程中出現的拼接組裝精確度低、內存利用率不高和基因序列拼接不完整等問題。根據對以上算法項目的分析與對比, 將來的研究可從以下幾個方面做出努力。

  1) 構建實用的支持高效序列拼接算法開發的系統。該系統應具有較為簡單的使用界面以及配置環境, 能夠集成在現有運算條件下解決生物信息拼接問題域的大規模算法庫以增強算法的交互性, 并具有較廣泛的應用前景和較高的應用價值。

  2) 探究具有綜合裝配組裝能力的組裝算法。產生式編程是一種為了發現超出對象、概念與特征范疇之外的編程和設計表達形式。因此, 研究一種面向動態裝配的產生式算法, 能夠極大地整合對現有分布式下的基因組序列數據集的計算方式;對其進行分配與管理, 以無障礙地組合現有算法, 甚至產生新式的基因組拼接算法。

  3) 開發聯合機器學習與統計計算的基因組拼接算法。目前算法主要還是以基于統計計算為主, 尚需人為地進行序列參數調整與實現, 同時只適用于解決人類已知的相關生物信息拼接問題域。因此, 將機器學習的智能化優勢運用于統計計算算法中, 實現兩者的有機結合, 是一條有希望的途徑。

  參考文獻

  [1] WARD R M, SCHMIEDER R, HIGHNAM G, et al.Big data challenges and opportunities in high-throughput sequencing[J].Systems Biomedicine, 2013, 1 (1) :29-34.
  [2] PEARSON W R Y, LIPMAN D J.Improved tools for biological sequence analysis[J].Proceedings of the National Academy of Sciences of the United Sates of America, 1988, 85 (46) :16138-16143.
  [3] ALTSCHUL S F, MADDEN T L, SCH?FFER A A, et al.Gapped BLAST and PSI-BLAST:a new generation of protein database search programs[J].Nucleic Acids Research, 1997, 25 (17) :3389-3402.
  [4] LARKIN M A, BLACKSHIELDS G, BROWN N P, et al.Clus- tal W and Clustal X version 2.0[J].Bioinformatics, 2007, 23 (21) :2947-2948.
  [5] DARLING A E, MAU B, PERNA N T.progressive Mauve:Mul- tiple Genome Alignment with Gene Gain, Loss and Rearrangement[J].PLOS One, 2010, 5 (6) :e11147.
  [6] BLANCHETTE M, KENT W J, RIEMER C, et al.Aligning multiple genomic sequences with the threaded blockset aligner[J].Genome Research, 2004, 14 (4) :708-715.
  [7] CANTOR C R.Orchestrating the Human Genome Project[J].Science, 1990, 248 (4951) :49-51.
  [8] CONSORTIUM T G P.A global reference for human genetic variation, the 1000 Genomes Project Consortium[J].Nature, 2015, 526:68-74.
  [9] CONSORTIUM T U.The UK10K project identifies rare va- riants in health and disease[J].Nature, 2015, 526 (7571) :82-90.
  [10] WATSON M.Illuminating the future of DNA sequencing[J].Genome Biology, 2014, 15 (2) :108.
  [11] Sanger F, Nicklen S, Coulson A R.DNA sequencing with chain-terminating inhibitors[J].Proceedings of the National Academy of Sciences of the United States of America, 1977, 74 (12) :5463-5467.
  [12] MOROZOVA O.Applications of next-generation sequencing technologies in functional genomics[J].Genomics, 2008, 92 (5) :255-264.
  [13] WOOLEY J C, GODZIK A, FRIEDBERG I.A Primer on Meta- genomics[J].PLOS Computational Biology, 2010, 6 (2) :e1000667.
  [14] WU X, ZHU X, WU G Q, et al.Data Mining with Big Data[J].IEEE Transactions on Knowledge & Data Engineering, 2014, 26 (1) :97-107.
  [15] FONSECA N A, RUNG J, BRAZMA A, et al.Tools for mapping high-throughput sequencing data[J].Bioinformatics, 2012, 28 (24) :3169-3177.
  [16] NIEDRINGHAUS T P, MILANOVA D, KERBY M B, et al.Landscape of Next-Generation Sequencing Technologies[J].Analytical Chemistry, 2011, 83 (12) :4327-4341.
  [17] HARRIS T D, BUZBY P R, BABCOCK H, et al.Single-molecule DNA sequencing of a viral genome[J].Science, 2008, 320 (5872) :106-109.
  [18] FLUSBERG B A, WEBSTER D, LEE J, et al.Direct detection of DNA methylation during single-molecule, real-time sequencing[J].Nature Methods, 2010, 7 (6) :461-465.
  [19] RUSK N.Cheap third-generation sequencing[J].Nature Me- thods, 2009, 6 (4) :244-244.
  [20] CHIN C S, PELUSO P, SEDLAZECK F J, et al.Phased Diploid Genome Assembly with Single Molecule Real-Time Sequencing[J].Nature Methods, 2016, 13 (12) :1050-1054.
  [21] HEEREMA S J, DEKKER C.Graphene nanodevices for DNA sequencing[J].Nature Nanotechnology, 2016, 11 (2) :127-136.
  [22] HEATHER J M, CHAIN B.The sequence of sequencers:The history of sequencing DNA[J].Genomics, 2016, 107 (1) :1-8.
  [23] SHENDURE J, JI H.Next-generation DNA sequencing[J].Nature Biotechnology, 2008, 26 (10) :1135-1145.
  [24] JACKMAN S D, VANDERVALK B P, MOHAMADI H, et al.ABySS 2.0:resource-efficient assembly of large genomes using a Bloom filter[J].Genome Research, 2017, 27 (5) :768-777.
  [25] ZIMIN A V, STEVENS K A, CREPEAU M W, et al.An improved assembly of the loblolly pine mega-genome using long-read single-molecule sequencing[J].GIGA Science, 2017, 6 (1) :1-4.
  [26] MOSTOVOY Y, LEVYSAKIN M, LAM J, et al.A hybrid approach for de novo human genome sequence assembly and phasing[J].Nature Methods, 2016, 13 (7) :587-590.
  [27] LIU Y, BERTIL S, MASKELL D L.Parallelized short read assembly of large genomes using de Bruijn graphs[J].BMC Bioinformatics, 2011, 12 (1) :354.
  [28] WARREN R L, SUTTON G G, JONES S J M, et al.Assembling millions of short DNA sequences using SSAKE[J].Bioinforma-tics, 2007, 23 (4) :500-501.
  [29] JECK W R, REINHARDT J A, BALTRUS D A, et al.Extending assembly of short DNA sequences to handle error[J].Bioinformatics, 2007, 23 (21) :2942-2944.
  [30] DOHM J C, LOTTAZ C, BORODINA T, et al.SHARCGS, a fast and highly accurate short-read assembly algorithm for de novo genomic sequencing[J].Genome Research, 2007, 17 (11) :1697-1706.
  [31] FARRANT G K, HOEBEKE M, PARTENSKY F, et al.WiseScaffolder:an algorithm for the semi-automatic scaffolding of Next Generation Sequencing data[J].BMC Bioinformatics, 2015, 16 (1) :281.
  [32] CAO M D, NGUYEN S H, GANESAMOORTHY D, et al.Scaffolding and completing genome assemblies in real-time with na-nopore sequencing[J].Nature Communications, 2017, 8:14515.
  [33] HIEU T N, ZIAUR R M, HE L, et al.Complete De NovoAssembly of Monoclonal Antibody Sequences[J].Scientific Reports, 2016, 6:31730.
  [34] MIN L, LIAO Z, HE Y, et al.ISEA:Iterative Seed-Extension Algorithm for De Novo Assembly Using Paired-End Information and Insert Size Distribution[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2017, 14 (4) :916-925.
  [35] MYERS E W, SUTTON G G, DELCHER A L, et al.A Whole-Genome Assembly of Drosophila[J].Science, 2000, 287 (5461) :2196-2204.
  [36] DE L B M, MCCOMBIE W R.Assembling genomic DNA se- quences with PHRAP[J].Current Protocols in Bioinformatics, 2007, 17 (1) :11.4.1-11.4.15.
  [37] MARGULIES M, EGHOLM M, ALTMAN W E, et al.Genome sequencing in microfabricated high-density picolitre reactors[J].Nature, 2005, 437 (7057) :376-380.
  [38] KAMATH G M, SHOMORONY I, XIA F, et al.HINGE:long-read assembly achieves optimal repeat resolution[J].Genome Research, 2017, 27 (5) :747-756.
  [39] MYERS G.Efficient Local Alignment Discovery amongst Noisy Long Reads[M]//Algorithms in Bioinformatics.Berlin:Sprin-ger, 2014:52-67.
  [40] KOREN S, WALENZ B P, BERLIN K, et al.Canu:scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation[J].Genome Research, 2017, 27 (5) :722-736.
  [41] YE C, HILL C M, WU S, et al.DBG2OLC:Efficient Assembly of Large Genomes Using Long Erroneous Reads of the Third Generation Sequencing Technologies[J].Scientific Reports, 2016, 6 (X) :31900.
  [42] YE C, MA Z S, CANNON C H, et al.Exploiting sparseness in de novo genome assembly[J].BMC Bioinformatics, 2012, 13 (S6) :S1.
  [43] LI H.Minimap and miniasm:fast mapping and de novo assembly for noisy long sequences[J].Bioinformatics, 2015, 32 (14) :2103-2110.
  [44] VASER R, SOVI, et al.Fast and accurate de novo genome assembly from long uncorrected reads[J].Genome Research, 2017, 27 (5) :737-746.
  [45] JANSEN H J, LIEM M, JONGRAADSEN S A, et al.Rapid de novo assembly of the European eel genome from nanopore sequencing reads[J].Scientific Reports, 2017, 7 (1) :7213.
  [46] BAAIJENS J A, AZE A, RIVALS E, et al.De novo assembly of viral quasispecies using overlap graphs[J].Genome Research, 2017, 27 (5) :835-848.
  [47] PENG G, JI P, ZHAO F.A novel codon-based de Bruijn graph algorithm for gene construction from unassembled transcriptomes[J].Genome Biology, 2016, 17 (1) :232.
  [48] CAMERON D L, SCHROEDER J, PENINGTON J S, et al.GRIDSS:sensitive and specific genomic rearrangement detection using positional de Bruijn graph assembly[J].Genome Research, 2017, 27 (12) :1-11.
  [49] WEISENFELD N I, KUMAR V, SHAH P, et al.Direct determination of diploid genome sequences[J].Genome Research, 2017, 27 (5) :757-767.
  [50] BUTLER J, MACCALLUM I, KLEBER M, et al.ALLPATHS:de novo assembly of whole-genome shotgun microreads[J].Genome Research, 2008, 18 (5) :810-820.
  [51] PEVZNER P A, TANG H, WATERMAN M S.An Eulerian path approach to DNA fragment assembly[J].Proceedings of the National Academy of Sciences of the United Sates of America, 2001, 98 (17) :9748-9753.
  [52] GNERRE S, JAFFE D B.High-quality draft assemblies of mammalian genomes from massively parallel sequence data[J].Proceedings of the National Academy of Sciences of the United Sates of America, 2011, 108 (4) :1513-1518.
  [53] LI R, ZHU H, RUAN J, et al.De novo assembly of human genomes with massively parallel short read sequencing[J].Genome Research, 2010, 20 (2) :265-272.
  [54] LUO R, LIU B, XIE Y, et al.SOAPdenovo2:an empirically improved memory-efficient short-read de novo assembler[J].GIGA Science, 2012, 1 (1) :18.
  [55] XIE Y, WU G, TANG J, et al.SOAPdenovo-Trans:de novo transcriptome assembly with short RNA-Seq reads[J].Bioinformatics, 2014, 30 (12) :1660-1666.
  [56] PENG Y, LEUNG H C M, YIU S M, et al.IDBA-UD:a de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth[J].Bioinformatics, 2012, 28 (11) :1420-1428.
  [57] CHITSAZ H, YEE-GREENBAUM J L, TESLER G, et al.Efficient de novo assembly of single-cell bacterial genomes from short-read data sets[J].Nature Biotechnology, 2011, 29 (10) :915-921.
  [58] PENG Y, LEUNG H C M, YIU S M, et al.IDBA-tran:a more robust de novo de Bruijn graph assembler for transcriptomes with uneven expression levels[J].Bioinformatics, 2013, 29 (13) :326-334.
  [59] NURK S, MELESHKO D, KOROBEYNIKOV A, et al.metaSPAdes:a new versatile metagenomics assembler[J].Genome Research, 2017, 27 (5) :824-834
  [60] BANKEVICH A, NURK S, ANTIPOV D, et al.SPAdes:A New Genome Assembly Algorithm and Its Applications to Single-Cell Sequencing[J].Journal of Computational Biology, 2012, 19 (5) :455-477.
  [61] PRJIBELSKI A D, VASILINETC I, BANKEVICH A, et al.ExSPAnder:a universal repeat resolver for DNA fragment assembly[J].Bioinformatics, 2014, 30 (12) :293-301.
  [62] SAFONOVA Y, BANKEVICH A, PEVZNER P A.dipSPAdes:Assembler for Highly Polymorphic Diploid Genomes[C]//International Conference on Research in Computational Molecular Biology.New York:Springer-Verlag, 2014:265-279.
  [63] ANTIPOV D, KOROBEYNIKOV A, MCLEAN J S, et al.hybridSPAdes:an algorithm for hybrid assembly of short and long reads[J].Bioinformatics, 2015, 32 (7) :1009-1015.
  [64] VASILINETC I, PRJIBELSKI A D, GUREVICH A, et al.Assembling short reads from jumping libraries with large insert sizes[J].Bioinformatics, 2015, 31 (20) :3262-3268.

    周衛星,石海鶴.高通量測序中序列拼接算法的研究進展[J].計算機科學,2019,46(05):36-43.
      相關內容推薦
    相近分類: