[發(fā)明專利]超長基因序列的相似性快速比對方法及系統(tǒng)

在審

• 申請?zhí)枺?/td>: 202010218462.6
• 申請日: 2020-03-25
• 公開（公告）號: CN111445952A
• 公開（公告）日: 2020-07-24
• 發(fā)明（設(shè)計(jì)）人: 劉衛(wèi)國;秦梓恒;殷澤坤;徐曉明;劉美洋
• 申請（專利權(quán)）人: 山東大學(xué)
• 主分類號: G16B30/10
• 分類號: G16B30/10;G16B40/00;G16B50/00
• 代理公司: 濟(jì)南圣達(dá)知識產(chǎn)權(quán)代理有限公司 37221
• 代理人: 黃海麗

1.超長基因序列的相似性快速比對方法，其特征是，包括：

獲取超長參考基因序列；對超長參考基因序列構(gòu)建增強(qiáng)型系數(shù)后綴數(shù)組ESSA；

獲取超長待查詢基因序列；對超長待查詢基因序列構(gòu)建增強(qiáng)型系數(shù)后綴數(shù)組ESSA；

將超長參考基因序列的增強(qiáng)型系數(shù)后綴數(shù)組ESSA，與超長待查詢基因序列的增強(qiáng)型系數(shù)后綴數(shù)組ESSA進(jìn)行匹配，匹配出重疊部分MEM；

對二者的重疊部分MEM進(jìn)行去冗余處理，得到最大唯一匹配部分MUM；

對超長參考基因序列的MUM和超長待查詢基因序列的最大唯一匹配部分MUM進(jìn)行相似度計(jì)算，將相似度大于設(shè)定閾值的超長參考基因序列對應(yīng)的基因類型作為超長待查詢基因序列對應(yīng)的基因類型。

2.如權(quán)利要求1所述的方法，其特征是，所述對超長參考基因序列構(gòu)建增強(qiáng)型系數(shù)后綴數(shù)組ESSA；是指構(gòu)建4個類型的數(shù)組，分別是后綴數(shù)組Suffix、最長公共前綴數(shù)組、后綴鏈接數(shù)組以及子數(shù)組。

3.如權(quán)利要求1所述的方法，其特征是，所述對超長參考基因序列構(gòu)建增強(qiáng)型系數(shù)后綴數(shù)組ESSA；具體步驟包括：先將超長參考基因劃分成若干個核苷酸序列kmer，然后根據(jù)劃分好的核苷酸序列kmer進(jìn)行構(gòu)建四個類型的數(shù)組：后綴數(shù)組、最長公共前綴數(shù)組LCP、后綴鏈接數(shù)組以及子數(shù)組。

4.如權(quán)利要求1所述的方法，其特征是，所述將超長參考基因序列的增強(qiáng)型系數(shù)后綴數(shù)組ESSA，與超長待查詢基因序列的增強(qiáng)型系數(shù)后綴數(shù)組ESSA進(jìn)行匹配，匹配出重疊部分MEM；具體步驟包括：

將超長待查詢基因序列的增強(qiáng)型系數(shù)后綴數(shù)組ESSA同超長參考基因序列的增強(qiáng)型系數(shù)后綴數(shù)組ESSA進(jìn)行匹配，直到出現(xiàn)錯配或者達(dá)到所規(guī)定的重疊部分MEM最小長度，輸出重疊部分MEM。

5.如權(quán)利要求4所述的方法，其特征是，對于長度為n的參考序列R和長度為m的查詢序列Q，R的稀疏因子是K，Q的稀疏因子是s，通過MEM-finding算法得到R和Q之間滿足最小長度L的MEM。

6.如權(quán)利要求4所述的方法，其特征是，匹配出重疊部分MEM的操作是：構(gòu)造稀疏因子是K的參考序列的ESSA以及稀疏因子是s的查詢序列的ESSA，然后設(shè)置步長是offset，步長的取值范圍是0到K-1，當(dāng)步長小于m-(K-offset)時，就用該數(shù)組和最長公共前綴數(shù)組LCP一起模擬稀疏后綴樹的遍歷過程，或者使用二分搜索算法進(jìn)行遍歷查找，直到出現(xiàn)錯配或者得到所規(guī)定的最小長度，輸出MEM。

7.如權(quán)利要求4所述的方法，其特征是，對超長參考基因序列的MUM和超長待查詢基因序列的MUM進(jìn)行相似度計(jì)算；具體步驟包括：

相似度距離MUMi的計(jì)算方法為：

MUMi＝1-L_mum/L_av

其中，L_mum是MUM的長度之和，L_av是超長參考基因序列的長度與超長待查詢基因序列長度的平均值。

8.超長基因序列的相似性快速比對系統(tǒng)，其特征是，包括：

第一獲取模塊，其被配置為：獲取超長參考基因序列；對超長參考基因序列構(gòu)建增強(qiáng)型系數(shù)后綴數(shù)組ESSA；

第二獲取模塊，其被配置為：獲取超長待查詢基因序列；對超長待查詢基因序列構(gòu)建增強(qiáng)型系數(shù)后綴數(shù)組ESSA；

匹配模塊，其被配置為：將超長參考基因序列的增強(qiáng)型系數(shù)后綴數(shù)組ESSA，與超長待查詢基因序列的增強(qiáng)型系數(shù)后綴數(shù)組ESSA進(jìn)行匹配，匹配出重疊部分MEM；

去冗余模塊，其被配置為：對二者的重疊部分MEM進(jìn)行去冗余處理，得到最大唯一匹配部分MUM；

分類模塊，其被配置為：對超長參考基因序列的MUM和超長待查詢基因序列的最大唯一匹配部分MUM進(jìn)行相似度計(jì)算，將相似度大于設(shè)定閾值的超長參考基因序列對應(yīng)的基因類型作為超長待查詢基因序列對應(yīng)的基因類型。