[發明專利]采用分治法進行高相似性序列的比對方法

有效

• 申請號: 201710791282.5
• 申請日: 2017-09-05
• 公開（公告）號: CN107798216B
• 公開（公告）日: 2021-06-04
• 發明（設計）人: 許聞廉;林信男
• 申請（專利權）人: 中央研究院
• 主分類號: G16B30/10
• 分類號: G16B30/10
• 代理公司: 北京科龍寰宇知識產權代理有限責任公司 11139
• 代理人: 孫皓晨;馬鑫

1.一種采用分治法進行高相似性序列的比對方法，其特征在于，包括以下步驟：

提供包含至少一條參考序列的一數據庫；

以查詢序列Q在該數據庫中找尋所有區域性的最長一致片段作為簡易比對區，并將該些簡易比對區根據其序列區塊與基因體區塊的位置差進行分群，以建構出全長比對的基礎架構；以及

去除該些簡易比對區中的重疊區塊，并插入一般比對區以填補相鄰簡易比對區的間隙，所述一般比對區可以分別并平行地進行比對，所有比對區接合后產生完整的比對。

2.如權利要求1所述的比對方法，其特征在于，所述簡易比對區是通過塊排序壓縮(BWT)或哈希表(hash tables)搜尋而來，而該塊排序壓縮與該哈希表是該數據庫序列所建立的索引。

3.如權利要求1所述的比對方法，其特征在于，所述數據庫的該參考序列為基因體序列或染色體序列或基因體重組序列，而所述查詢序列為基因體序列或染色體序列或基因體重組序列或基因體測序機器所產生的短序列。

4.如權利要求1所述的比對方法，其特征在于，所述相鄰的簡易比對區的間隙是兩序列片段間的差異點所造成的，該些差異點為兩序列所發生的替代錯誤、插入錯誤或刪除錯誤所造成的。

5.如權利要求4所述的比對方法，其特征在于，所述相鄰的簡易比對區的間隙區塊為NP-gap free時，這部分只需要線性的無間隔比對，其中所述的NP-gap free是指查詢序列區塊與基因體區塊有相同大小，并且線性掃描后的相異點個數低于區塊大小的20％。