[發明專利]一種建立基因比對表的方法、系統、設備及介質

有效

• 申請號: 202010174947.X
• 申請日: 2020-03-13
• 公開（公告）號: CN111402958B
• 公開（公告）日: 2022-05-17
• 發明（設計）人: 葛沅;史宏志;尹云峰;崔星辰
• 申請（專利權）人: 蘇州浪潮智能科技有限公司
• 主分類號: G16B30/10
• 分類號: G16B30/10;G16B50/00;G06F16/22
• 代理公司: 北京連和連知識產權代理有限公司 11278
• 代理人: 張濤

本發明公開了一種建立基因比對表的方法、系統、設備和存儲介質，方法包括以下步驟：從參考基因組序列中讀取連續第一長度的子序列作為種子，并確定種子對應的最長讀取長度；將多個種子依次存放到緩存區，將第一個種子作為待選種子，并判斷緩存區中種子的數量是否達到閾值；響應于緩存區中種子的數量未達到閾值，判斷向緩存區存放的當前種子對應的最長讀取長度是否大于第一長度和閾值的和；響應于當前種子對應的最長讀取長度大于第一長度和閾值的和，判斷當前種子的哈希值是否小于待選種子的哈希值；以及響應于當前種子的哈希值小于待選種子的哈希值，將當前種子寫入基因比對表，并將當前種子更新為待選種子。

技術領域

本發明涉及基因比對領域，更具體地，特別是指一種建立基因比對表的方法、系統、計算機設備及可讀介質。

背景技術

大多數全基因比對使用的典型種子鏈對齊程序基因測序，為了快速準確的將DNA子序列映射到參考基因組上，大體流程都是收集參考基因組reference，并按照K-mer或其他算法將參考基因組分片成多個種子，將種子編入哈希表中。然后將每一個待比對的序列進行分割，通過查表檢索其在表上對應的位置。

現在主流基因比對經常使用全文索引等，比如后綴數組或FM索引。這種方法的優點是我們可以使用任意長度的種子，有助于增加種子的獨特性減少不成功的擴展。但是在實際實踐中，這種方式僅限于通用的CPU和GPU環境。而采用固定長度的種子，可以計算更多處理數據更快。哈希表是理想的數據結構，尤其是用于映射長噪聲序列，同時哈希表能夠很好的適應FPGA異構加速平臺，進行硬件加速。

如果所有reference的種子信息都添加到哈希表中，那么哈希表項的規模非常大，占用的空間也會非常多。尤其是如果按照不同seed長度創建多個擴展表，那么內存的壓力將會成倍數增加。而且，后續查表的計算速度都會非常慢。如果只是簡單的按照一定間隔讀取reference的seed，那么又會存在很多遺漏項，造成表項信息缺失，影響最后的準確性。

發明內容

有鑒于此，本發明實施例的目的在于提出一種建立基因比對表的方法、系統、計算機設備及計算機可讀存儲介質，通過設置多級判斷提高了種子篩選的精度，并大大減少了基因比對表，減少后續大量無效的比對計算，提升了運行效率。

基于上述目的，本發明實施例的一方面提供了一種建立基因比對表的方法，包括如下步驟：從參考基因組序列中讀取連續第一長度的子序列作為種子，并確定所述種子對應的最長讀取長度；將多個所述種子依次存放到緩存區，將第一個種子作為待選種子，并判斷所述緩存區中種子的數量是否達到閾值；響應于所述緩存區中種子的數量未達到閾值，判斷向緩存區存放的當前種子對應的最長讀取長度是否大于所述第一長度和所述閾值的和；響應于所述當前種子對應的最長讀取長度大于所述第一長度和所述閾值的和，判斷所述當前種子的哈希值是否小于待選種子的哈希值；以及響應于所述當前種子的哈希值小于待選種子的哈希值，將所述當前種子寫入基因比對表，并將所述當前種子更新為待選種子。

在一些實施方式中，還包括：響應于所述當前種子對應的最長讀取長度等于所述第一長度和所述閾值的和，判斷所述當前種子的哈希值與所述待選種子的哈希值是否相同。

在一些實施方式中，還包括：響應于所述當前種子的哈希值與所述待選種子的哈希值相同，判斷所述當前種子和所述待選種子在所述參考基因組的標識是否相同。

在一些實施方式中，還包括：響應于所述緩存區中種子的數量達到閾值，把所述待選種子寫入所述基因比對表，并在所述緩存區中確定哈希值最小的種子作為待選種子。