[發明專利]堿基序列對準系統及方法

在審

• 申請號: 201410276504.6
• 申請日: 2014-06-19
• 公開（公告）號: CN104239749A
• 公開（公告）日: 2014-12-24
• 發明（設計）人: 樸旻壻
• 申請（專利權）人: 三星SDS株式會社
• 主分類號: G06F19/18
• 分類號: G06F19/18
• 代理公司: 北京銘碩知識產權代理有限公司 11286
• 代理人: 孫昌浩;韓芳

技術領域

本發明的實施例涉及一種用于分析基因組的堿基序列的技術。

背景技術

用于生產大容量的短序列的下一代測序(NGS：Next?Generation?Sequencing)因其低廉的費用和快速的數據生成而正在迅速地取代傳統的桑格(Sanger)測序方式。并且，聚焦于準確率而開發出多種多樣的NGS序列對準程序。

序列重組的第一個步驟為通過堿基序列對準(alignment)算法而將短片段(read)映射(mapping)于參考序列的準確的位置。為此，普通的現有堿基序列對準算法首先將從短片段中選取的預定長度的種子(seed)映射于參考序列，然后在映射的位置上對其余短片段進行全局對準(Global?Alignment)。

對于這種現有技術中的序列對準算法而言，需要在利用種子獲得的參考序列內的所有候選位置上執行全局對準。然而全局對準的復雜度為O(N²)，其為執行時間很長的作業，因此如果按照現有技術，尤其隨著候選位置的增加，堿基序列對準時間按照幾何級數增長。

發明內容

本發明的實施例的目的在于當進行利用從測序儀接收的短片段的序列對準時，通過考慮由短片段獲得的各個種子在參考序列內的映射位置以及允許的誤差值而減少全局對準的執行次數，從而提高堿基序列分析的速度和準確率。

根據本發明的一個實施例的一種堿基序列對準系統，包括：種子生成單元，由所接收的短片段(read)生成多個種子(seed)；篩選單元，將生成的所述種子映射于參考序列(reference?sequence)，并通過考慮映射的種子之間的間隔(gap)而選擇所述映射的種子中的全局對準對象種子；對準單元，在被選擇的所述種子的所述參考序列上的映射位置上執行所述短片段的針對所述參考序列的全局對準(global?alignment)。

所述篩選單元可將映射于所述參考序列的種子當中的、種子之間的間隔之和在設定值以下的種子選擇為所述全局對準對象種子。

所述篩選單元可將映射于所述參考序列的種子當中的、滿足如下數學式的種子選擇為所述全局對準對象種子：

A≤MaxError+B

其中，A為被選擇的各個種子在所述參考序列內的間隔之和，B為被選擇的各個種子在所述短片段內的間隔之和，MaxError為最大誤差允許值。

所述系統還可以包括：精確匹配單元，執行所接收的短片段的針對所述參考序列的精確匹配；誤差個數估計單元，針對在所述精確匹配單元中沒有得到精確匹配的短片段，估計出將相關短片段對準于所述參考序列時的誤差個數，其中，所述種子生成單元可在估計出的所述誤差個數在設定的最大誤差允許值以下時由所述短片段生成多個種子。

另一方面，根據本發明的一個實施例的一種堿基序列對準方法，包括如下步驟：在種子生成單元中，由所接收的短片段(read)生成多個種子(seed)；在篩選單元中，將生成的所述種子映射于參考序列(reference?sequence)，并通過考慮映射的種子之間的間隔(gap)而選擇所述映射的種子中的全局對準對象種子；在對準單元中，在被選擇的所述種子的所述參考序列上的映射位置上執行所述短片段的針對所述參考序列的全局對準(global?alignment)。

在選擇所述全局對準對象種子的步驟中，可將映射于所述參考序列的種子當中的、種子之間的間隔之和在設定值以下的種子選擇為所述全局對準對象種子。

在選擇所述全局對準對象種子的步驟中，可將映射于所述參考序列的種子當中的、滿足如下數學式的種子選擇為所述全局對準對象種子：

A≤MaxError+B

其中，A為被選擇的各個種子在所述參考序列內的間隔之和，B為被選擇的各個種子在所述短片段內的間隔之和，MaxError為最大誤差允許值。

在所述方法中，在執行生成所述種子的步驟之前，還可以包括如下步驟：在精確匹配單元中，執行所接收的短片段的針對所述參考序列的精確匹配；在誤差個數估計單元中，針對在執行所述精確匹配的步驟中沒有得到精確匹配的短片段，估計出將相關短片段對準于所述參考序列時的誤差個數，其中，在生成所述種子的步驟中，可在估計出的所述誤差個數在設定的最大誤差允許值以下時由所述短片段生成多個種子。

根據本發明的實施例，不是在由短片段獲得的各個種子的參考序列內的所有映射位置上執行全局對準，而是考慮各個種子在參考序列內的映射位置以及允許的誤差值而只在判斷為合適的位置上執行全局對準，從而具有可提高堿基序列分析速度的優點。