[發(fā)明專利]一種基于讀數(shù)和距離分布的基因組Denovo序列拼接方法

有效

• 申請?zhí)枺?/td>: 201410482300.8
• 申請日: 2014-09-19
• 公開（公告）號: CN104200133B
• 公開（公告）日: 2017-03-29
• 發(fā)明（設(shè)計）人: 王建新;羅軍偉;李敏
• 申請（專利權(quán)）人: 中南大學(xué)
• 主分類號: G06F19/18
• 分類號: G06F19/18
• 代理公司: 長沙正奇專利事務(wù)所有限責任公司43113
• 代理人: 馬強

1.一種基于讀數(shù)和距離分布的基因組De?novo序列拼接方法，其特征在于，包括以下步驟：

1)輸入雙端讀數(shù)文庫，構(gòu)建初始De?Bruijn圖，并對初始De?Bruijn圖進行優(yōu)化；

2)以De?Bruijn圖為基礎(chǔ)，選擇種子序列，并利用打分函數(shù)對候選擴展序列進行打分，選擇得分最高的候選擴展序列與種子序列合并，并繼續(xù)進行擴充，直到結(jié)束條件為止。擴展后的每個種子序列即為一條contig，所有的contig構(gòu)成一個contig集合；

3)建立scaffold圖，每個結(jié)點代表一個contig，邊代表兩條contig在真實基因組序列上的位置緊鄰；

4)填充scaffold圖中有邊相連的兩個結(jié)點之間的空白區(qū)域，通過匹配上的雙端讀數(shù)長生一個局部讀數(shù)集合，在局部讀數(shù)集合上構(gòu)建新的De?Bruijn圖，并在該De?Bruijn圖上尋找能夠連接兩個結(jié)點的路徑，如果存在這樣的路徑，則以該路徑填充空白區(qū)域。

2.根據(jù)權(quán)利要求1所述的基于讀數(shù)和距離分布的基因組De?novo序列拼接方法，其特征在于，所述步驟1)中，構(gòu)建初始De?Bruijn圖的過程如下：依次讀取讀數(shù)文庫中的每條讀數(shù)，每條讀數(shù)分解成r-k+1個k-mer，在De?Bruijn圖中查找每個k-mer對應(yīng)的結(jié)點，如果某k-mer對應(yīng)的結(jié)點不存在，則在De?Bruijn圖中創(chuàng)造一個新的結(jié)點并對應(yīng)于該k-mer；如果一個k-mer最后k-1個堿基和另一個k-mer前k-1個堿基相同，則在這兩個k-mer對應(yīng)的結(jié)點之間加一條有向邊；當遍歷完所有的讀數(shù)時，初始De?Bruijn圖建立完成；其中r為每條讀數(shù)的長度；k為k-mer的長度；且k為奇整數(shù)。

3.根據(jù)權(quán)利要求1或2所述的基于讀數(shù)和距離分布的基因組De?novo序列拼接方法，其特征在于，對所述初始De?Bruijn圖進行優(yōu)化的方法為：首先De?Bruijn圖中的簡單路徑合并為一個結(jié)點；簡單路徑是指一個路徑中起始結(jié)點的出度為1，最終結(jié)點的入度為1，并且所有中間結(jié)點的出度和入度均為1；刪除初始De?Bruijn圖中長度小于2*k，并且出度或入度為0的結(jié)點。

4.根據(jù)權(quán)利要求3所述的基于讀數(shù)和距離分布的基因組De?novo序列拼接方法，其特征在于，所述步驟2)中，contig集合構(gòu)建的具體步驟為：

1)將初始De?Bruijn圖中結(jié)點長度大于雙端讀數(shù)文庫insertsize的結(jié)點為種子序列，以所述種子序列的前驅(qū)結(jié)點和后繼結(jié)點為候選擴展序列；其中，insertsize為雙端讀書文庫中每對讀數(shù)之間的間距；

2)如果候選擴展序列的長度小于minLen，則以該候選擴展序列為起點，采取深度優(yōu)先遍歷方法，抽取出所有長度大于minLen的子路徑，每個子路徑對應(yīng)于一個二級候選擴展序列，對所有的二級候選擴展序列打分，并以最高分作為候選擴展序列的得分值；minLen取值為2*k；

3)針對一個種子序列ss和一個候選擴展序列ec，采用公式F(ss,ec)＝RM(ss,ec)^MC(ss,ec)計算ec的得分值，其中RM是匹配上ss和ec的雙端讀數(shù)的相對值；由匹配上的雙端讀數(shù)得到一個距離集合，MC用于衡量該距離集合和整體insertsize分布的偏移大小；如果在ec中的實際存在讀數(shù)個數(shù)不符合二項式分布B(minLen，p)，則將所述ec的得分值減去一個罰分值其中a是罰分系數(shù)，b為ec中的k-mer平均頻次與讀數(shù)文庫中的k-mer平均頻次的比值；re是在ec中實際存在的讀數(shù)個數(shù)，p是讀數(shù)出現(xiàn)在讀數(shù)文庫中的概率；

4)如果一個種子序列只有一個候選擴展序列，則將該候選擴展序列直接合并到種子序列中；如果一個種子序列存在多個候選擴展序列，并且得分最高的兩個候選擴展序列得分值都大于0.7或者相差小于0.2，或者沒有候選擴展序列，則擴展終止，否則把得分最高的候選擴展序列合并到種子序列中去；迭代地對種子序列進行左右擴展，直到達到上述的擴展終止條件，最終的種子序列作為一條contig加入到contig集合中；

5)當擴展完所有的種子序列，則contig集合構(gòu)建完成。