[發明專利]一種基因序列比對的方法、系統及相關組件

有效

• 申請號: 201810827902.0
• 申請日: 2018-07-25
• 公開（公告）號: CN109326325B
• 公開（公告）日: 2022-02-18
• 發明（設計）人: 趙健;史宏志;李龍;崔星辰;尹云峰
• 申請（專利權）人: 鄭州云海信息技術有限公司
• 主分類號: G16B25/00
• 分類號: G16B25/00
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 羅滿

本申請公開了一種基因序列比對的方法，所述方法包括確定待對比序列和參考序列，并根據參考序列確定指針表和候選對比位置表；從待對比序列中提取預設長度的種子序列，并確定種子序列的索引值；根據種子序列的索引值查詢指針表和候選對比位置表判斷參考序列中是否存在種子序列對應的位置信息；若是，則將種子序列作為待擴展序列，根據位置信息以參考序列為基準對待擴展序列進行擴展操作得到中間序列，并對比中間序列與待對比序列得到基因序列比對結果。本方法能夠能夠降低存儲參考序列索引值的表的存儲空間，提高基因序列比對速率。本申請還公開了一種基因序列比對的系統、一種計算機可讀存儲介質及一種電子設備，具有以上有益效果。

技術領域

本發明涉及計算機技術與生物基因技術交叉學科領域，特別涉及一種基因序列比對的方法、系統、一種電子設備及一種計算機可讀存儲介質。

背景技術

基因序列比對的策略通常主要包括seed(種子序列)查找和seed擴展兩個階段。seed查找階段的主要是在read(待比對序列)上查找一定長度且在參考序列上能夠完全精確匹配的子序列，即seed(種子序列)。擴展階段對查找到的seed在參考序列的種子序列上進行擴展。最后根據在各個種子序列上的打分情況選擇最佳的比對結果。

現有技術中，為了使seed能夠快速地精確匹配到參考序列上，可以對參考序列進行預先索引，在seed查找階段根據索引值直接獲取的seed在參考序列上的位置。參考序列的索引表基本單元為index,pos，index的長度可根據索引的策略選擇，pos為seed在參考序列上的位置。但是，由于索引表需要在整個參考序列上逐位建立，需要的存儲空間十分巨大。因此利用FPGA(Field－Programmable Gate Array，即現場可編程門陣列)根據索引值進行對比索引表的訪問為隨機訪問的訪問速率較低。

因此，如何降低存儲參考序列索引值的表的存儲空間，提高基因序列比對速率是本領域技術人員目前需要解決的技術問題。

發明內容

本申請的目的是提供一種基因序列比對的方法、系統、一種電子設備及一種計算機可讀存儲介質，能夠降低存儲參考序列索引值的表的存儲空間，提高基因序列的索引值比對速率。

為解決上述技術問題，本申請提供一種基因序列比對的方法，該方法包括：

確定待對比序列和參考序列，并根據所述參考序列確定指針表和候選對比位置表；其中，所述候選對比位置表為描述參考子序列在所述參考序列上的位置信息與所述參考子序列的R位索引值的后M位的對應關系，且所述索引值前R-M位相同的參考子序列的位置信息連續排列的表，所述指針表為描述所述索引值前N位相同、第N+1位至第R-M位不同的參考子序列在所述候選對比位置表中的偏移地址的表；所述參考子序列為按照預設長度對所述參考序列逐位提取得到；

從待對比序列中提取預設長度的種子序列，并確定所述種子序列的索引值；

根據所述種子序列的索引值查詢所述指針表和所述候選對比位置表判斷所述參考序列中是否存在所述種子序列對應的位置信息；

若是，則將所述種子序列作為待擴展序列，根據所述位置信息以所述參考序列為基準對所述待擴展序列進行擴展操作得到中間序列，并對比所述中間序列與所述待對比序列得到基因序列比對結果。

可選的，根據所述參考序列確定指針表和候選對比位置表包括：

對所述參考序列逐位提取預設長度的所述參考子序列，記錄所述參考子序列的位置信息，并將所述參考子序列轉換為索引值；

按照預設規則將所述索引值進行字節劃分得到第一子索引值、第二子索引值和第三子索引值；其中，所述第一子索引值為所述索引值的前N位，所述第三子索引值為所述索引值的后M位，所述第二子索引值為所述索引值的第N+1位至第R-M位；