[發明專利]核酸序列拼接方法及裝置

有效

• 申請號: 201410053255.4
• 申請日: 2014-02-17
• 公開（公告）號: CN104850761B
• 公開（公告）日: 2017-11-07
• 發明（設計）人: 李振宇;陳燕香;張浩;袁劍穎;張廣鑫;李一萱
• 申請（專利權）人: 深圳華大基因科技有限公司
• 主分類號: G06F19/18
• 分類號: G06F19/18;G06F19/20
• 代理公司: 深圳鼎合誠知識產權代理有限公司44281
• 代理人: 彭家恩,羅瑤

1.一種核酸序列拼接方法，其特征在于，包括：

接收測序序列，所述測序序列包括讀段和測通數據；

根據所述讀段構建原始拼接圖；

將所述測通數據比對到所述原始拼接圖的邊上；

從原始拼接圖的邊集中選擇錨點邊，所述錨點邊的兩端沒有分叉且跨過該錨點邊的讀段的路徑沒有沖突；

構建以所述錨點邊為中心的局部子圖；

化簡所述局部子圖，在化簡結果中重復選擇錨點邊進行處理直至不存在新的錨點邊；

對處理后剩余的局部子圖進行合并，將合并結果作為拼接結果輸出；

從原始拼接圖的邊集中選擇錨點邊這一步驟包括：

根據比對結果和拓撲結構，去除原始拼接圖中含有測序錯誤的讀段及該讀段關聯的所有邊；

根據原始拼接圖的邊集中各條邊的邊覆蓋深度信息和邊末端分叉信息，從原始拼接圖的邊集中確定出各邊的類型；

選擇原始拼接圖的邊集中的非錯誤邊和非重復邊作為錨點邊。

2.如權利要求1所述的核酸序列拼接方法，其特征在于，將所述測通數據比對到所述原始拼接圖的邊上這一步驟或這一步驟之前包括：

對構建得到的原始拼接圖，根據所述原始拼接圖的拓撲結構，去除因堿基錯誤和/或測序錯誤形成的讀段及該讀段關聯的所有邊。

3.如權利要求1所述的核酸序列拼接方法，其特征在于，所述選擇原始拼接圖的邊集中的非錯誤邊和非重復邊作為錨點邊這一步驟包括：

選擇原始拼接圖的邊集中的符合標準的雜合邊作為錨點邊，所述雜合邊包括形成為泡狀結構且組成泡狀結構的兩條邊的覆蓋深度相近且都不大于平均覆蓋深度；所述符合標準指，將所述組成泡狀結構的兩條邊進行比對，兩條邊的堿基數量相差不超過第一閾值且錯配堿基數量不超過第二閾值。

4.如權利要求3所述的核酸序列拼接方法，其特征在于，所述組成泡狀結構的兩條邊的覆蓋深度為0.1-0.8倍的平均覆蓋深度。

5.如權利要求3所述的核酸序列拼接方法，其特征在于，所述第一閾值為10，所述第二閾值為10％。

6.如權利要求1所述的核酸序列拼接方法，其特征在于，構建以所述錨點邊為中心的局部子圖這一步驟包括：

對每一條所述錨點邊，通過跨過所述錨點邊的讀段的比對信息，得到所述錨點邊向兩端延伸的邊界信息，根據所述邊界信息獲得所述錨點邊的局部子圖。

7.如權利要求1所述的核酸序列拼接方法，其特征在于，化簡所述局部子圖這一步驟包括：

根據局部子圖中各分叉的支持數和/或覆蓋度，去除低于預設支持數和/或預設覆蓋度的分叉，并根據該分叉對應的讀段，去除包含該讀段的其余局部子圖；

和/或，對局部子圖中的一條錨點邊，以該條錨點邊為中心，將與該條錨點邊關聯且不存在路徑沖突的所有局部子圖融合為一個局部子圖。

8.如權利要求1所述的核酸序列拼接方法，其特征在于，對處理后剩余的局部子圖進行合并這一步驟包括：

對處理后剩余的局部子圖，判斷其中的第一局部子圖是否包含第二局部子圖的一個錨點邊，

如果是，再判斷所述第一局部子圖的各邊和所述第二局部子圖的各邊之間是否存在沖突，

如果不存在，則合并所述第一局部子圖和所述第二局部子圖為最終拼接圖。

9.如權利要求8所述的核酸序列拼接方法，其特征在于，合并所述第一局部子圖和所述第二局部子圖為最終拼接圖這一步驟包括：

選擇所述第一局部子圖的第一個錨點邊作為最終拼接圖的邊集的起點，選擇所述第二局部子圖的最后一個錨點邊作為最終拼接圖的邊集的終點，

將所述起點與所述終點之間的第一局部子圖和第二局部子圖中的邊進行復制，并將復制的邊加入最終拼接圖的邊集中。