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

有效

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

技術領域

本發明涉及生物信息處理領域，尤其涉及一種核酸序列拼接方法及裝置。

背景技術

在基因組測序技術發展歷程中，具有低成本、高測序通量（又稱高通量，指一定時間內獲得的數據輸出量）、更精準特點的第二代測序技術帶來了前所未有的應用前景，如基因組組裝、結構變異檢測等。第二代測序技術得到的read（讀段，指隨機打亂DNA序列所得的小片段）不僅長度短，數量又極為巨大，覆蓋度高，這給序列拼接帶來了前所未有的難題，而基因組測序中的一個關鍵步驟就是序列拼接。序列拼接是將小的reads進行比對合并成大的DNA序列或者RNA序列，這些reads是由堿基A、G、C、T或A、G、C、U組成，reads的長度表示其含有的A、G、C、T或A、G、C、U的個數。含有A、G、C、T或A、G、C、U的reads經過拼接得到更長的reads，該更長的reads再經過拼接或比對最終可得到DNA或RNA序列。

第二代測序技術所面臨的基本拼接問題是，由于第二代測序技術read長度偏短的特點，由此給拼接算法帶來難題，包括如何處理測序錯誤，以及如何處理重復序列。在真實的基因組項目中，大基因組尤其是植物基因組的重復序列含量十分高，有的重復序列高達60%以上，在使用現有拼接算法進行序列拼接過程中，由于重復序列的影響，將產生很多短碎的contig（重疊群）序列，使得后續拼接過程的scaffold（支架，是由順序確定的contigs連接組成）構建、補洞等環節受其影響，效果不佳。

已有研究提出使用長reads來處理拼接過程的重復序列。長reads可通過例如測通的Illumina數據得到。研究表明，長read有利于在contig構建過程中利用新的算法理論與新的拼接策略解決更多的重復序列的問題，得到更長的contig序列，提升contig構建的效果。

發明內容

依據本發明的一方面，提供一種核酸序列拼接方法，包括：接收測序序列，所述測序序列包括讀段和測通數據；根據所述讀段構建原始拼接圖；將所述測通數據比對到所述原始拼接圖的邊上；從原始拼接圖的邊集中選擇錨點邊，所述錨點邊的兩端沒有分叉且跨過該錨點邊的讀段的路徑沒有沖突；構建以所述錨點邊為中心的局部子圖；化簡所述局部子圖，在化簡結果中重復選擇錨點邊進行處理直至不存在新的錨點邊；對處理后剩余的局部子圖進行合并，將合并結果作為拼接結果輸出。

依據本發明的另一方面，提供一種核酸序列拼接裝置，包括：接收模塊，用于接收測序序列，所述測序序列包括讀段和測通數據；原始構建模塊，用于根據所述讀段構建原始拼接圖；比對模塊，用于將所述測通數據比對到所述原始拼接圖的邊上；選擇模塊，用于從原始拼接圖的邊集中選擇錨點邊，所述錨點邊的兩端沒有分叉且跨過該錨點邊的讀段的路徑沒有沖突；子圖構建模塊，用于構建以所述錨點邊為中心的局部子圖；化簡模塊，用于化簡所述局部子圖，在化簡結果中重復選擇錨點邊進行處理直至不存在新的錨點邊；合并模塊，用于對處理后剩余的局部子圖進行合并，將合并結果作為拼接結果輸出。

依據本發明的又一方面，提供一種包括上述核酸序列拼接裝置的基因組測序設備。

依據本發明的再一方面，提供一種計算機可讀存儲介質，用于存儲供計算機執行的程序，本領域普通技術人員可以理解，在執行該程序時，通過指令相關硬件可完成上述核酸序列拼接方法的全部或部分步驟。所稱存儲介質可以包括：只讀存儲器、隨機存儲器、磁盤或光盤等。

依據本發明的方法，通過將測通數據比對到由讀段構建得的原始拼接圖，從原始拼接圖中選擇出錨點邊并據此構建局部子圖，再通過對局部子圖的化簡和合并得到更長的路徑，達到解決錨點邊之間的重復序列的路徑選擇問題，進而可完成測序序列的拼接任務，為提升scaffold構建效果提供可能。

附圖說明

本發明的上述和/或附加的方面和優點從結合下面附圖對實施方式的描述中將變得明顯和容易理解，其中：

圖1為依據本發明的一種實施例的核酸序列拼接方法的流程示意圖；

圖2至圖4為由于片段中間的堿基錯誤形成的環形結構和由測序錯誤形成的嵌合體示意圖；

圖5和圖6分別為邊出現分叉路徑和路徑存在沖突的示意圖；

圖7為通過錨點邊D獲得的所有局部子圖及其化簡結果示意圖；

圖8為由錨點邊D構成的局部子圖與由錨點邊F構成的局部子圖的合并示意圖；

圖9為局部子圖合并過程中弧關系的處理示意圖；

圖10為依據本發明的一種實施例的核酸序列拼接方法的流程示意圖；