[發明專利]使用分級反向索引表的DNA比對

有效

• 申請號: 201680061446.2
• 申請日: 2016-10-21
• 公開（公告）號: CN108140071B
• 公開（公告）日: 2022-04-29
• 發明（設計）人: M·B·多爾;J·D·加瑪尼;S·V·伍德;D·G·阿拉斯塔斯;M·A·亨特
• 申請（專利權）人: 相干邏輯公司
• 主分類號: G16B40/00
• 分類號: G16B40/00;G16B20/20
• 代理公司: 中國貿促會專利商標事務所有限公司 11038
• 代理人: 鮑進

用于構建可用于將檢索序列與參考數據匹配的分級索引表的系統和方法。所述索引表可經構建以含有與給定長度的所有子序列的窮盡性列表相關聯的條目，其中每個條目含有在所述參考數據中的每個子序列的匹配的數量和位置。可以迭代方式構建所述分級索引表，其中基于匹配的數量大于一組相應閾值中的每一個，選擇性地和迭代地構建用于每個延長子序列的條目。所述分級索引表可用于搜索在檢索序列和參考數據之間的匹配，并且對每個相應候選匹配執行錯配鑒別和表征。

技術領域

本申請大體上涉及將數據模式映射到參考數據組上，且更具體地說，涉及在DNA測序和DNA比對應用中執行這類數據比對或模式匹配。

背景技術

現代技術涉及越來越大量數據的收集和處理。其中，所謂的“大數據”的應用和使用情況范圍是數據挖掘、播發、機器學習和DNA測序。在許多情況下，有必要搜索在少量樣品數據和大得多的參考數據組之間的匹配。隨著參考數據組的尺寸增加，樣本數據與此參考數據組的比對(模式匹配)變成以指數方式更為計算密集型任務。

數據比對的示例性案例在DNA比對領域中進行。活生物體由細胞構成并且細胞的操作和繁殖受從一代細胞傳送到下一代的基因信息控制。

物種和個體生物體的基因信息的詳細知識對于更精確生命科學的保持巨大希望，從而支持改善的健康護理、農業、環境管理和犯罪解析。

實現這些益處的障礙中的一個為對生物體的基因信息進行測序的成本。為了做到這一點的技術已經在數十年的最后十年內顯著改善，使得將成本減少到小于US $1000/人表現為可實現的。然而，仍然存在數據的完整性、精確度、解釋的問題，和可靠診斷疾病的問題。從生物樣品獲取基因信息的天數也是需要快速響應的用途的障礙，如已知供急救室患者使用的對于敏感個體具有嚴重副作用的醫藥適合性。

因此，期望用于數據比對并且具體來說DNA測序的改善的技術和工具。

發明內容

公開用于將數據模式映射到顯著地較大數據組上的系統和方法的各種實施例。在一些實施例中，較大數據組可為參考數據組。在一些實施例中，較大數據組可為從頭測序的結果，其中多個數據模式用于構建與多個數據模式自一致的大數據組。本文中呈現的許多實施例涉及DNA比對的具體使用案例，其中參考數據組為參考基因組并且數據模式為衍生自DNA鏈的短讀數(SR)的一串DNA堿基。然而，本文中詳述的方法通常適用于將任何數據模式映射到較大數據組上的問題。本文關于DNA比對所描述的方法的說明旨在有助于解釋，并且不意指以任何方式限制本發明的范圍。本領域中技術人員將容易地參看本文所描述的方法可如何應用于除DNA比對以外的數據比對或模式匹配方法。

在一個實施例中，可生成基于參考數據的分級索引表。分級索引表可包含其中多個數據段中的每一個所在的在參考數據中的位置。在計算機科學中，此形式的索引表可被稱作反向索引表。分級索引表可用于將檢索序列與參考數據匹配。索引表可經構建以含有與給定長度的所有子序列的窮盡性列表相關聯的條目，其中每個條目含有在參考數據中的每個子序列的匹配的數量和位置。可以迭代的方式構建分級索引表，其中基于匹配的數量大于一組相應閾值中的每一個，選擇性地和迭代地構建用于每個延長子序列(層次的更深層級)的條目。對于一些子序列，匹配的數量將相等或小于當前閾值，為此方法生成在表中的末端條目。有限長度的參考數據意指，可發現足夠長子序列的匹配的數量將低于給定正閾值。然而，據了解，存在大于1000bp長并且出現數千次的基因組的子序列。對于完全地索引，這些序列可為或不為所感興趣的；并且在后一種情況下，某些序列可排除掉，而非包括于分級索引表中。

用于在參考基因組中對SR執行候選位置選擇(鑒別匹配模式)的方法可包括通過以迭代方式執行以下來檢索對應分級索引表。可基于一段SR，生成“印跡”(由一串DNA堿基組成)，并且其用于從與參考基因組相關聯的索引表選擇SR的至少一個候選位置。印跡的長度可延長以便移動到分級索引表的更深層級。一旦達到分級索引表的末端條目，就可停止迭代，并且可輸出候選位置。使用分級索引表可操作以大大地增加可出現候選選擇的速度。