[發(fā)明專利]使用分級(jí)反向索引表的DNA比對(duì)

有效

• 申請(qǐng)?zhí)枺?/td>: 201680061446.2
• 申請(qǐng)日: 2016-10-21
• 公開（公告）號(hào): CN108140071B
• 公開（公告）日: 2022-04-29
• 發(fā)明（設(shè)計(jì)）人: M·B·多爾;J·D·加瑪尼;S·V·伍德;D·G·阿拉斯塔斯;M·A·亨特
• 申請(qǐng)（專利權(quán)）人: 相干邏輯公司
• 主分類號(hào): G16B40/00
• 分類號(hào): G16B40/00;G16B20/20
• 代理公司: 中國(guó)貿(mào)促會(huì)專利商標(biāo)事務(wù)所有限公司 11038
• 代理人: 鮑進(jìn)

1.一種用于將檢索序列與參考數(shù)據(jù)匹配的方法，所述方法包含：

通過計(jì)算裝置執(zhí)行：

a)將參考數(shù)據(jù)存儲(chǔ)在存儲(chǔ)器中；

b)基于所述參考數(shù)據(jù)創(chuàng)建分級(jí)索引表，

其中所述創(chuàng)建包含創(chuàng)建在所述分級(jí)索引表中的多個(gè)層級(jí)中的每一層級(jí)處的多個(gè)條目，其中在多個(gè)層級(jí)中的每一層級(jí)處創(chuàng)建多個(gè)條目而無需參考檢索序列，

其中所述多個(gè)層級(jí)包含第一層級(jí)，其中第一層級(jí)條目是為具有第一長(zhǎng)度的所述參考數(shù)據(jù)的多個(gè)子序列中的每一個(gè)創(chuàng)建的，

其中對(duì)于相應(yīng)層級(jí)n條目，其中n為至少一個(gè)非零正整數(shù)，所述創(chuàng)建包含響應(yīng)于所述相應(yīng)層級(jí)n條目與所述參考數(shù)據(jù)的匹配準(zhǔn)則為大于閾值，創(chuàng)建在所述分級(jí)索引表中用于相應(yīng)層級(jí)n條目的n+1層級(jí)條目，

其中所述創(chuàng)建在所述分級(jí)索引表中的n+1層級(jí)條目包含創(chuàng)建用于具有與所述n+1層級(jí)對(duì)應(yīng)的長(zhǎng)度的所述參考數(shù)據(jù)的多個(gè)子序列中的每一個(gè)的n+1層級(jí)條目；

c)接收指定檢索序列的輸入；和

d)對(duì)所述分級(jí)索引表搜索所述檢索序列與所述參考數(shù)據(jù)的一個(gè)或多個(gè)匹配，其中所述對(duì)所述分級(jí)索引表搜索包含迭代地搜索所述分級(jí)索引表的子序列層級(jí)中檢索序列的子區(qū)段的匹配。

2.根據(jù)權(quán)利要求1所述的方法，

其中具有第一長(zhǎng)度的所述參考數(shù)據(jù)的所述多個(gè)子序列和具有與所述n+1層級(jí)對(duì)應(yīng)的長(zhǎng)度的所述參考數(shù)據(jù)的所述多個(gè)子序列中的每一個(gè)包含其相應(yīng)長(zhǎng)度的子序列的完備集。

3.根據(jù)權(quán)利要求2所述的方法，

其中所述創(chuàng)建在所述分級(jí)索引表的任何相應(yīng)層級(jí)中的相應(yīng)條目通過以下來執(zhí)行：

在所述參考數(shù)據(jù)中搜索與所述相應(yīng)條目對(duì)應(yīng)的所述相應(yīng)長(zhǎng)度的子序列的匹配；和

將信息存儲(chǔ)在所述分級(jí)索引表的相應(yīng)層級(jí)中的所述相應(yīng)條目中，其中所述信息指定在所述參考數(shù)據(jù)中相應(yīng)長(zhǎng)度的所述子序列的匹配的數(shù)量，其中所述信息進(jìn)一步指定所述匹配中的每一個(gè)在所述參考數(shù)據(jù)中的位置。

4.根據(jù)權(quán)利要求3所述的方法，

其中，對(duì)于n+1層級(jí)，在與n層級(jí)中的所述對(duì)應(yīng)條目相關(guān)聯(lián)的位置處執(zhí)行所述搜索所述n+1層級(jí)的所述相應(yīng)子序列的匹配。

5.根據(jù)權(quán)利要求3所述的方法，其中指示與每個(gè)條目相關(guān)聯(lián)的匹配的數(shù)量的數(shù)據(jù)存儲(chǔ)在第一數(shù)據(jù)結(jié)構(gòu)中，并且與每個(gè)條目相關(guān)聯(lián)的所述匹配中的每一個(gè)的數(shù)據(jù)位置存儲(chǔ)在第二數(shù)據(jù)結(jié)構(gòu)中，其中所述第一和第二數(shù)據(jù)結(jié)構(gòu)各自包含在所述分級(jí)索引表內(nèi)。

6.根據(jù)權(quán)利要求1所述的方法，進(jìn)一步包含：

對(duì)于每個(gè)相應(yīng)n層級(jí)條目，將引用對(duì)應(yīng)于所述相應(yīng)n層級(jí)條目的n+1層級(jí)條目的指標(biāo)存儲(chǔ)在存儲(chǔ)器中。

7.根據(jù)權(quán)利要求1所述的方法，其中所述參考數(shù)據(jù)包含參考基因組并且搜索所述參考數(shù)據(jù)包含將短讀數(shù)(SR)與所述參考基因組進(jìn)行比對(duì)。

8.根據(jù)權(quán)利要求1所述的方法，其中所述閾值包含在所述分級(jí)索引表中相應(yīng)層級(jí)n條目與所述參考數(shù)據(jù)的匹配的數(shù)量，其中n+1層級(jí)條目是響應(yīng)于所述相應(yīng)層級(jí)n條目與所述參考數(shù)據(jù)的匹配的數(shù)量大于所述匹配的閾值數(shù)量而為所述相應(yīng)層級(jí)n條目創(chuàng)建的。