[發明專利]雙向多步DeBruijn圖的自環雙向邊識別與去除方法

有效

• 申請號: 201310672187.5
• 申請日: 2013-12-10
• 公開（公告）號: CN103699817B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 孟金濤;張慧琳;彭豐斌;魏彥杰;馮圣中
• 申請（專利權）人: 深圳先進技術研究院
• 主分類號: G06F19/20
• 分類號: G06F19/20
• 代理公司: 深圳市科進知識產權代理事務所(普通合伙)44316
• 代理人: 沈祖鋒,郝明琴

技術領域

本發明涉及基因測序領域，具體涉及雙向多步De?Bruijn圖的自環雙向邊識別與去除方法。?

背景技術

基因序列分析以算法與數學模型為核心，包括：基因數據的存儲與獲取、序列比對、測序與拼接、基因預測、生物進化與系統發育分析、蛋白質結構預測、RNA結構預測、分子設計與藥物設計、代謝網絡分析、基因芯片、DNA計算等。生物技術和計算機信息處理技術的緊密結合，加快了處理生物信息數據的速度，使得在盡短的時間內對生物學做出準確的詮釋，加快生物信息學的發展。?

基因序列分析是對海量基因序列數據進行分析，從而提取和挖據新的生物信息知識。涉及到計算機技術中的機器學習、模式識別、書籍分析與挖掘、組合數學、隨機模型、字符串、圖形算法、分布式計算、高性能計算、并行計算等。?

基因是人類最基本的遺傳密碼，代表著每個人的生命信息。基因序列上存在著遺傳位點的細微差異，這些遺傳密碼的多態性與人類的健康、致病機理、醫學治療有著相當密切的關系。?

自1977年Sanger測序技術問世以來，經過三十多年的發展，DNA測序技術發展突飛猛進，以高通量、短序列為特點的第二代測序技術逐漸占領市場，以單分子測序為特點的第三代測序技術也逐漸出現，分別在測序特點上占有不同的優勢。傳統的基因測序方法的數據提取和分析軟件經過近10年來的研究與開發，目前已經較為完善。但是，測序技術的發展，帶來了測序數據的變化，使得當前存在的數據處理軟件不能滿足當前生物醫學研究的需求。?

新一代高通量測序方法在技術的應用，可以在短時間內完成整個基因?組數據的測定。高通量測序方法的日新月異也同時對獲取的基因數據的分析處理方法提出了挑戰。目前，迫切需要開發能滿足高通量測序技術的海量數據處理的生物信息學平臺。面對個人基因組計劃及未來的個性化醫療前景，高效低成本的測序技術成為必然的趨勢。同時，簡化高效的一站式完備的生物信息學數據分析平臺等完備的測序解決方案，也是極為重要不可或缺的發展方向。?

然而新一代的高通量測序方法雖然測序通量高，但是卻會引入測序誤差，同時測序樣本本身由于基因突變，測序不均勻而導致有SNP的出現，而上述測序誤差，測序不均將會在基因組組裝時構造的多步雙向De?Bruijn圖中引入一些錯誤的雙向邊，其中有一部分是自環雙向邊。而上述錯誤的自環雙向邊在De?Bruijn圖中，能夠阻礙圖的收縮，contig無法擴展，最終使得contig的長度和質量都很低。?

新一代的高通量測序方法產生的短基因片段的組裝導致大量的測序錯誤，加大了組裝算法的計算量。大量的測序錯誤，使得組裝錯誤率增加，嚴重影響了組裝結果。?

目前組裝算法策略分為兩類，一是基于Overlap-Layout-Consensus(OLC)的算法，另一個是基于DeBruijn圖的算法。其中，基于OLC組裝算法開發的軟件，如SSAKE、VCAKE、SHARCGS等，在基因長序列組裝中更占有優勢，但并不完全適用于新一代的短序列組裝。與OLC組裝算法不同，DeBruijn算法不再以read為單位組織數據，而是以k-mers為單位進行數據組裝，其優點主要有以下幾個方面：首先，以k-mers為單位進行序列組裝，不影響節點的質量，減少了冗余數據量；其次，在圖中重復區域只出現一次，便于識別，可以避免錯誤的組裝，減小出錯率；最后，采取將有重疊區域映射到同一條弧上的策略，從而簡化了搜索路徑。目前，很多短序列組裝算法都使用這種框架，如Velvet、IDBA、SOAPdenovo，ABySS。?

Velvet有效的利用De?Bruijn圖，實現了高效的短序列組裝。Velvet以k-mer為基本單位構建De?Bruijn圖，利用圖的結構，結合相應的序列特征，簡化圖的構造，最終找到一條最優路徑完成組裝過程。Velvet把焦點集中在錯誤的數據產生的三種結構上，即tip、bubble、以及erroneous?connection。依照長度原則和少數性原則，將長度小于2k的均去除；利用Tour?Bus算法?中的深度優先搜索策略合并bubble，最后利用覆蓋度閾值法去除了erroneous?connection。該方法也充分利用了paired-end雙端信息，進一步解決repeat問題，優化了組裝效果。Velvet充分利用圖的結構性質，簡化了數據冗余，速度較之前的算法有了很大的改進。雖然它沒有在預處理階段對序列進行糾錯，但是其對錯誤的預防機制，很大程度上的彌補了這方面的缺陷。這使得它更好的應用在大型基因組序列的組裝中。?