鬼佬大哥大
  • / 45
  • 下載費用:30 金幣  

數據庫驅動的原始測序數據的初步分析.pdf

摘要
申請專利號:

CN201380065692.1

申請日:

2013.10.11

公開號:

CN104919466A

公開日:

2015.09.16

當前法律狀態:

撤回

有效性:

無權

法律詳情: 發明專利申請公布后的視為撤回IPC(主分類):G06F 19/22申請公布日:20150916|||實質審查的生效IPC(主分類):G06F 19/22申請日:20131011|||公開
IPC分類號: G06F19/22 主分類號: G06F19/22
申請人: 丹麥技術大學
發明人: L·戈蒂埃; O·倫德
地址: 丹麥靈比
優先權: 12188538.8 2012.10.15 EP
專利代理機構: 北京律誠同業知識產權代理有限公司11006 代理人: 徐金國
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201380065692.1

授權公告號:

||||||

法律狀態公告日:

2018.08.28|||2015.11.18|||2015.09.16

法律狀態類型:

發明專利申請公布后的視為撤回|||實質審查的生效|||公開

摘要

本發明涉及一種識別含有原始測序讀段的樣品中的生物序列的來源的方法。該方法可以用于識別未知DNA的來源并且可以用于診斷、生物防御、食品安全和質量以及衛生應用。在另一方面,本發明涉及可以用于本發明方法的參考序列數據庫。

權利要求書

權利要求書
1.  一種識別生物序列,如短讀段,的可能來源的方法,該方法包括:
a)從一來源采樣序列或短讀段的子集,
b)將來自所述子集的序列分段成k-mer,
c)針對包括參考序列的k-mer的第一集合,查詢來自所述子集的一個或多個k-mer,
d)針對包括k-mer在參考序列中的位置的第二集合,查詢來自所述子集的一個或多個k-mer,
e)確定哪個/哪些參考含有所述一個或多個k-mer,和
f)返回對可能的來源參考的描述,
其中所述包括參考序列的k-mer的第一集合與包括k-mer在參考序列中的位置的第二集合是分離的。

2.  如權利要求1的方法,其中所述方法不涉及對序列數據使用比對算法,例如采用評分矩陣的比對算法。

3.  如任一前述權利要求的方法,其中所述查詢進一步包括確定k-mer在所述參考序列中的位置。

4.  如任一前述權利要求的方法,其中存在和位置被用來確定查詢k-mer在參考序列中的的連續性。

5.  如任一前述權利要求的方法,其中所述生物序列是氨基酸序列。

6.  如權利要求1-4的方法,其中所述生物序列是DNA或RNA序列。

7.  如任一前述權利要求的方法,其中k-mer查詢涉及確定查詢k-mer和參考k-mer之間的完全匹配。

8.  如任一前述權利要求的方法,其中查詢涉及從至少一個來源序列或短讀段查詢所有k-mer,優選從至少50,例如從至少100,如從至少150,例如從至少200,如從至少250,例如從至少300,如從至少400,例如從至少500,如從至少750,例如從至少1000,例如從至少1500,如從至少2000,例如從至少2500,如從至少5000或更多個序列。

9.  如任一前述權利要求的方法,其中所述源序列是至少50個堿基的核苷酸序列,優選至少100個堿基,如至少150個堿基,例如至少200個堿基,如至少250個堿基,例如至少300個堿基,如至少400,至少500或更多個堿基。

10.  如任一前述權利要求的方法,其中序列的子集包括至少1%的離散序列,例如至少2%,如至少4%,例如至少5%,如至少6%,例如至少7、5%,例如至少10%,如至少15%,例如至少25%,如至少30%,例如至少35%,如至少40%,例如至少50%。

11.  如任一前述權利要求的方法,進一步包括選擇序列的一個或多個另外的子集并將它們執行權利要求1的步驟a)至步驟f)。

12.  如任一前述權利要求的方法,其中所述子集是隨機的或過濾的。

13.  如任一前述權利要求的方法,其中k-mer的大小為4、8、12、16、20、24、28、32、36、40、44、48、52、56、60、64或更長。

14.  如任一前述權利要求的方法,其中k-mer是連續的。

15.  如任一前述權利要求的方法,其中k-mer是重疊的并且增量為至少一個堿基或氨基酸,例如至少兩個,如至少3個,例如至少4個,如至少5個,例如至少6個或更多。

16.  如任一前述權利要求的方法,其中k-mer是不相交的子序列的串聯。

17.  如任一前述權利要求的方法,其中針對數據庫查詢來自給定序列的k-mer以確定k-mer在一個或多個參考序列中的存在和k-mer在所述一個或多個參考序列中的位置。

18.  如權利要求17的方法,其中只在k-mer存在時才查詢位置。

19.  如任一前述權利要求的方法,其中為返回的參考計算得分。

20.  如任一前述權利要求的方法,其中為識別的參考序列計算得分,所述得分與在給定的參考序列中發現的來自一個或多個序列的k-mer數目相關聯。

21.  如任一前述權利要求的方法,其中為識別的參考計算得分,所述得分通過在參考序列中發現的來自一個或多個序列的k-mer的平均局部集中度與連續性或近似連續性相關聯。

22.  如任一前述權利要求的方法,其中為識別的參考計算得分,所述得分與在參考序列中的k-mer數目相關聯,所述k-mer也存在于來自所述來源的k-mer的子集中。

23.  如任一權利要求19至22的方法,其中根據所述得分對可能來源參考排名。

24.  如任一前述權利要求的方法,其中查詢來自一個來源序列或短讀段的所有k-mer并且為所述來源序列或短讀段計算一個或多個得分。

25.  如任一前述權利要求的方法,其中為參考序列獲得匹配k-mer的計數。

26.  如任一前述權利要求的方法,其中通過將參考序列的匹配k-mer的計數除以被查詢子集中的獨一無二的k-mer的數目來獲得得分。

27.  如權利要求24-26的方法,其中通過將參考序列的匹配k-mer的計數除以參考序列的大小來獲得得分。

28.  如權利要求24-27的方法,其中參考序列的得分被計算為權利要求26和27的得分的加權和。

29.  如任一前述權利要求的方法,還包括查詢來自第二來源序列,優選來自第三來源序列的所有k-mer。

30.  如任一前述權利要求的方法,其中一旦以預定的統計概率識別出參考生物體,就可以停止數據庫查詢。

31.  如任一前述權利要求的方法,其中如果在數據庫中沒找到預定分段的k-mer,就可以停止數據庫查詢。

32.  如任一前述權利要求的方法,其中所述數據庫輸出關于一個或多個可能參考的下列信息中的一個或多個:序列的任何注釋、編碼序列、調控序列、可能參考的分類學名稱、所述可能參考的近親、所述參考的來源、一組另外相關的參考、參考是從哪里獲得的(例如土壤、海洋、內臟或下水道)、參考序列是何時獲得的、分類學分類、近緣物種、關于參考序列是從哪個數據庫(例如NCBI或EBI/Sanger數據庫)下載的信息。

33.  如任一前述權利要求的方法,其中所述數據庫輸出最可能的參考的序列,優選其中所述數據庫輸出最可能的參考物種的全基因組序列。

34.  如任一前述權利要求的方法,其中來自具有非常相似的序列的參考 的結果或者來自另外相關的參考的結果在輸出中分組。

35.  如任一前述權利要求的方法,其中執行該方法的幾次迭代,如在第一次迭代中,識別最豐富的參考并從所述來源序列或短讀數中去除來自所述最豐富的參考的序列。

36.  如權利要求35的方法,還包括在第二次迭代中,識別第二最豐富的參考,去除來自所述第二最豐富的參考的序列等。

37.  如權利要求36的方法,還包括在第二次迭代中,識別插入物的可能參考。

38.  如任一前述權利要求的方法,該方法還包括最初去除與來自預定的參考的序列對準的源序列。

39.  如任一前述權利要求的方法,其中所述方法包括如果數據庫中不存在來自一個來源序列的預定義數目的k-mer,就從所述來源序列忽略k-mer。

40.  如任一前述權利要求的方法,其中查詢涉及忽略來自一個或多個預定的參考的k-mer。

41.  如任一前述權利要求的方法,其中當從核酸測序儀獲得原始序列時查詢這些原始序列。

42.  如任一前述權利要求的方法,其中使用適應采樣。

43.  一種在權利要求1-42所限定的方法中使用的、包括有參考序列的k-mer的數據庫,所述數據庫包括:
a)來自參考序列的k-mer的第一集合,和
b)每個k-mer在參考序列中的位置的第二集合。

44.  如權利要求43的數據庫,其中所述數據庫還包括關于與給定參考相關聯的全長序列的信息,和/或所述參考的來源,和/或所述參考的一個或多個分類學描述符。

45.  如任一權利要求43-44的數據庫,其中在數據庫中的k-mer進行哈希函數運算,向每個獨一無二的k-mer分配唯一密鑰。

46.  如任一權利要求43-45的數據庫,其中在第一集合中的每個唯一k-mer由矢量與關于有k-mer存在的那些參考的信息相關聯。

47.  如任一權利要求43-46的數據庫,其中在第二集合中的每個獨一無二的k-mer由矢量與關于該k-mer存在時,其在每個參考中的位置的信息相關聯。

48.  如任一權利要求43-47的數據庫,還包括第三集合或數據庫,其具有選自下組的參考標識符和信息類型:描述行、數據來源、序列的任何注釋、編碼序列、調控序列、可能參考的分類學名稱、所述可能參考的近親、所述參考的來源、一組另外相關的參考、參考是從哪里獲得的(例如土壤、海洋、內臟或下水道)、參考序列是何時獲得的、分類學分類、近緣物種、關于參考序列是從哪個數據庫(例如NCBI或EBI/Sanger數據庫)下載的信息。

49.  如任一權利要求43-48的數據庫,其中k-mer的長度為4、8、12、16、20、24、28、32、36、40、44、48、52、56、60、64或更長。

50.  如任一權利要求43-49的數據庫,其中k-mer是非重疊的。

51.  如任一權利要求43-50的數據庫,其中k-mer是重疊的并且增量為至少一個堿基或氨基酸,例如至少兩個,如至少3個,例如至少4個,如至少5個,例如至少6個或更多。

52.  如任一權利要求43-51的數據庫,其中所述數據庫包括來自每個參考的完整序列的k-mer。

53.  如任一權利要求43-52的數據庫,其中所述數據庫包括來自人類、動物、哺乳動物、鳥類、魚類、真菌、昆蟲、植物、細菌、古細菌、病毒和/或質粒的序列信息。

54.  如任一權利要求43-53的數據庫,其中所述數據庫被分成被存儲在幾個不同服務器中的子數據庫。

55.  如任一權利要求43-54的數據庫,其中根據選自門、綱、目、科、屬和種的一種或多種分類學描述符,或一種或多種環境描述符,如來源、分布、起源和過去查詢的頻率,使所述數據庫組織成子數據庫。

56.  一種用于識別來源序列的可能來源的數據處理系統,該系統包括輸入裝置、中央處理單元、存儲器和輸出裝置,其中,所述數據處理系統存儲有表示在執行時使得權利要求1-42的方法得以被執行的系列指令的數據,所述存儲器還包括根據任一權利要求43-55的數據庫。

57.  如權利要求56的系統,其中所述數據庫存儲在服務器中,并且輸入裝置和輸出裝置是客戶端,所述客戶端和服務器經由數據通信連接來連接。

58.  如任一權利要求56-57的系統,其中所述客戶端選自個人計算機、臺式PC、便攜式PC、手持式計算裝置如智能電話。

59.  如任一權利要求56-58的系統,其中所述客戶端包括使客戶端能夠采樣來源序列的子集,將這些來源序列分段成k-mer,并將這些來源序列傳送到服務器的一系列指令。

60.  如權利要求56-59的系統,所述客戶端還包括允許其基于從服務器傳送到客戶端的序列將來源序列組裝成一個或多個更大的序列的一系列指令。

61.  如任一權利要求56-60的系統,通過數據連接與測序設備相連接。

62.  一種計算機軟件產品,含有在執行時使得權利要求1-42的方法得以被執行的系列指令。

63.  一種集成電路產品,含有在執行時使得權利要求1-42的方法得以被執行的系列指令。

說明書

說明書數據庫驅動的原始測序數據的初步分析
發明領域
本發明涉及一種用于識別生物序列的可能來源的方法。在進一步的方面,本發明涉及一種適合用于此目的的數據庫。
發明背景
DNA測序是識別堿基(A、T、C或G)順序的實驗過程。截至今天,沒有任何技術能夠測序超過幾千堿基的DNA的完整分子,大多數技術測序100和200個堿基之間。細菌基因組可容易地含有以幾百萬計的堿基。在過去幾年中,測序成本顯著降低從而使以諸如人類健康、食品質量控制或微生物群落研究為目的對樣品中的DNA大規模測序越來越普遍。可以想象的是,全人類基因組測序將更頻繁地用于治療以盡可能地使治療個性化,并且將執行常規測序來控制特定活生物體的存在或不存在。無論是作為最終目的本身或作為更復雜的數據分析或在采取更昂貴的分析之前對測序數據的質量控制步驟的基石,快速識別可能的起源DNA都正在迅速成為一種必然。
初級分析包括使從測序獲得的相對短的序列(稱為短讀段)有意義,該相對短的序列或者是通過將它們與參考基因組比對(這需要參考物種的序列是已知的),或者是通過不使用模型來重構拼圖(所謂的測序標簽的從頭組裝-識別未知樣品的含量將需要補充步驟)來獲得的。與參考比對被認為是比從頭組裝在計算上更容易的任務。
在可負擔非特異性或全基因組測序之前,首先精心地對特定區域測序和組裝,識別感興趣的預測區域。最簡單的方法是通過找到由RNA翻譯成蛋白質的起始密碼子(ATG/AUG)和一個終止翻譯的終止密碼子(TAG/UAG、TAA/UAA、TGA/UGA)所限定的間隔,尋找開放閱讀框架(ORF)。該ORF隨后與所有已知基因名單比對。比對方法包括比對算法和程序如Smith和Waterman算法、BLAST算法和程序、SSAHA和BLAT。它們的目的是要在索引序列的數據庫中找到優化比對,并通過對所有比對的得分排名找到最佳 匹配以及從而找到查詢序列的最可能的功能。為了功能注釋的目的,通過建立“最佳-匹配基因的組”,或直系同源基因(COG)簇,越來越多的具有不同生物學功能的類似匹配導致這一原理的擴張。隨著慢慢地可以利用更多的完整基因組,設計了Mummer算法來比對完整基因組對和可視化如何在遺傳相關的物種之間比較整體的基因組結構。
由于目前在數據庫中可用的序列數目,針對巨大的已知序列池的新序列的比對可能花費相對長的時間,BLAST在這個意義上是個突破,它在找到幾乎最佳結果的同時加速了以前的算法。然而,在基于網絡的搜索引擎可以幾乎立即返回搜索結果的時代,針對所有已知序列的搜索仍相對緩慢。
Ning等,2001,(Genome:11:1725-1729),描述了一種算法SSAHA(通過哈希算法的序列搜索和比對),對含有幾千兆堿基的DNA的數據庫執行快速比對。SSAHA是一個比對器;因此,其任務是向每個全長查詢序列報告它們在何處以及如何匹配參考序列集合中的每個條目。該SSAHA方法是在全長查詢序列上尋找盡可能多的匹配。在數據庫中的序列通過分解為k個連續堿基的連續k-字被預處理,然后使用哈希表來存儲每個k-字每次出現的位置。在數據庫中搜索查詢序列是通過從哈希表取得對查詢序列中每個k-字的“命中”,然后對結果進行分選而完成。該SSAHA算法用于高通量單核苷酸多態性檢測和超大規模序列組裝。在SSAHA中,每個k-字的存在和位置被存儲在同一查找結構中,該結構加載到計算機系統的存儲設備中。
已知的映射或比對算法和程序包括諸如Erland、Corona、BFAST、Bowtie、BWA、NovoAlign的方法。它們的目標是在已知的參考中找到讀段位置。推而廣之,可以將無法找到匹配的讀段標記為并非來自該序列。這些程序和算法也存在搜索時間長的缺點,因為它們都評估查詢集中的每個序列(即每一測序讀段),并且因為它們試圖找到對于它們所有的最佳比對(在用短讀段進行時往往被稱作比對)。有趣的是,因為上面的程序都使用啟發式來以精確性換取速度,因此它們所找到的結果并不相同。
US 2006286566公開了使用k-mer檢測突變的方法。該方法涉及通過比較靶核酸序列的一部分與第二序列節段,檢測與靶核酸序列部分的匹配來檢測靶核酸序列中的明顯突變。
US2012000411中公開了能夠表征樣品內的有機體群體的系統和方法,這 是基于對短序列信息串的匹配以從參考基因組數據庫中識別基因組。該專利申請沒有公開這樣的方法,即其中在一個參考序列中的短串集合中搜索短串的存在和在參考序列中的位置的另一集合中搜索位置。
發明概述
本發明提供了一種用于識別原始序列來源,例如從測序儀獲得的DNA讀段(或短讀段)或者從N-或C-端測序或從質譜獲得的蛋白質序列的新方法。該方法依賴于預先索引的參考序列的集合和對傳入的生物序列(如來自測序儀的讀段)的查詢集評分的系統,和依賴于提交部分查詢集的系統。這可以通過使用基于客戶端-服務器的方法,以服務器實體容納參考的集合并在客戶端提交查詢序列的子集同時進行評分來完成。
由本發明提供的方法,允許快速確定樣品中發現的不同DNA來源,并且不依賴于關于來源序列的給定基因的完整序列以及參考序列的知識。
短讀段,盡管并不代表其起源的完整參考,但帶有該參考的標簽性信號。短讀段可以進一步被分解成子序列(稱為k-mer或k-字(k-tuple))并且那些k-mer搜索索引k-mer的集合,以確定原始測序數據的來源。
在第一方面,本發明涉及識別生物序列的可能來源的方法,該方法包括:
a)從一來源采樣序列或短讀段的子集,
b)將來自該子集的序列分段成k-mer,
c)針對包含參考序列的k-mer的數據庫,查詢來自所述子集的k-mer,
d)確定哪個(哪些)參考包含該k-mer,和
e)返回對可能的來源參考的描述。
該方法比傳統的比對和映射算法具有若干優點,傳統的比對和映射算法關注于比對全部的查詢集并因此需要將來自輸入裝置(如客戶端)的全序列傳輸到可以執行比對的數據庫和評分單元(如服務器)。根據本發明,只有序列的子集進行分段并且查詢從而使數據傳輸的需要最小化。傳輸的子集可以 是例如,但不限于,固定大小的隨機子集、過濾子集、自適應采樣、輸入和評分實體之間的迭代同步或異步對話,或者是它們的任意組合。
相比于基于測序讀段組裝,或基因組構建,隨后搜索的方法或者相比于在參照集合中映射所有讀段的方法,本方法通過不試圖執行全長比對以及通過在數據的子集上工作而對電腦處理能力的需要大大減少,并且因此可以在幾秒鐘內獲得結果。因此,本發明的方法可使用客戶端-服務器的方式運行,例如以具有較小的計算機處理能力(例如移動電話)的平板或手持裝置作為客戶端。因為可以相對快地獲得對一個數據子集的結果,用于搜索另外的數據子集所需的時間大大減少。這樣,相比于基于整個序列比對的常規方法,可以顯著減少的時間段來確定樣品中的不同DNA來源的識別。
在其最廣泛的方面,本發明涉及只查詢在數據庫中的存在。然而,在優選的實施方式中,也查詢數據庫中k-mer在參考序列中的位置,從而允許計算源k-mer的連續性并使評估更加精確。生物體常常彼此遺傳相關,本發明也能在參考序列的集合中找到近緣親本。
在兩個單獨的數據庫或集合中編譯數據允許將在參考中搜索k-mer的存在與搜索位置去關聯(decoupling),并考慮優化,例如將盡可能多的對存在的搜索緩存到存儲器中,在存儲器中的搜索可能比在持久性存儲設備中更快。如果發現存在k-mer,那么可進行位置搜索,并且如果在給定參考中存在足夠的時間,那么在輔助優化步驟中進行,。因此本發明的一個優選實施方式涉及一種識別生物序列的可能來源的方法,該方法包括:
a)從一來源采樣序列的子集,
b)將來自該子集的序列分段成k-mer,
c)針對包括參考序列的k-mer的第一集合,查詢來自所述子集的k-mer,
d)針對包括k-mer在參考序列中的位置的第二集合,查詢來自所述子集的k-mer,
e)確定哪個(哪些)參考包含該k-mer,和
f)返回對可能的來源參考的描述,
其中包括參考序列的k-mer的集合與包括k-mer在參考序列中的位置的集合是分開的。
因此本發明的一個優選實施方式涉及一種識別生物序列的可能來源的方法,該方法包括:
a)從一來源采樣序列或短讀段的子集,
b)將來自該子集的序列分段成k-mer,
c)針對包括參考序列的k-mer的第一集合,查詢來自所述子集的k-mer,
d)針對包括k-mer在參考序列中的位置的第二集合,查詢來自所述子集的k-mer,
e)確定哪個(哪些)參考包含該k-mer,和
f)返回對可能的來源參考的描述,
其中包括參考序列的k-mer的集合與包括k-mer在參考序列中的位置的集合是分離的。
本發明的一個顯著的特點是,一旦識別出可能的參考,那么將關于該可能的參考的信息返回給用戶。返回的信息可以例如是關于可能的物種以及其起源或來源和/或該可能的物種的全長基因組序列的信息。這允許用戶使用現有技術的比對或基因組構建算法將來自未知樣品的其余的原始讀段與參考序列進行比對,以便識別小的變化,如突變和插入。
在進一步的方面,本發明涉及一種包括有參考序列的k-mer的數據庫,所述數據庫包括:
a)來自參考序列的k-mer的第一集合,以及
b)每一k-mer在該參考序列中的位置的第二集合。
編譯兩個單獨的數據庫或集合中的數據允許將搜索k-mer在參考中的存在與搜索位置去關聯,并考慮優化,例如將對存在的搜索盡可能多地緩存到存儲器中,在存儲器中搜索可能比在持久性存儲設備中更快。如果發現存在k-mer,那么可進行位置搜索,并且如果在給定參考中存在足夠的時間,那么 在輔助優化步驟中進行。
在第三個方面,本發明涉及一種用于識別來源序列的可能來源的數據處理系統,該系統優選包括:輸入裝置,中央處理單元,存儲器以及輸出裝置,其中所述數據處理系統中存儲有表示當執行時使得根據本發明的方法得以被執行的系列指令的數據,該存儲器還包括根據本發明的數據庫。
圖3示出本發明的系統的一個實施方式的要點。要點是采樣是在“客戶端”執行,導致最少量的信息被傳輸。在圖中并未示出對最可能的參考的描述符的應用。
裝置(輸入、輸出、存儲器、CPU)可以是手持式、臺式、基于云和/或聯機的。
優選地,數據庫存儲在服務器上,并且輸入和輸出裝置是一個或多個客戶端,客戶端和服務器經由數據通信連接相連并且服務器的共享允許將參考的集合集中并且如果在單獨的處理或者甚至是單獨的機器上運行時,在整個客戶端的服務器中分配計算能力。在這樣的實施方式中,客戶端可以包括使客戶端采樣來源序列的子集,將這些分段成k-mer,并將這些傳輸到服務器的一系列指令。
客戶端可以進一步包括一系列指令,所述指令允許客戶端與服務器對話以適應或中斷采樣程序或基于從服務器傳送到客戶端的序列,執行將來源序列組裝成一個或多個更大的序列。
在一個實施中,系統經由數據連接與測序設備相連接。
在進一步的方面,本發明涉及一種計算機軟件產品,含有一系列在執行時使得本發明的方法得以被執行的指令,以及涉及一種集成電路產品,含有系列在執行時使得本發明的方法得以被執行的指令。
附圖說明
圖1、“存在”和“位置”數據庫的構建。
圖2、評分一組查詢DNA片段,通常是來自測序的原始讀段。
圖3、本發明的系統的構架的一般描述。
圖4、根據改變讀段大小(行)和隨機置換率(列),在數據庫中用作查詢的747個細菌基因組的平均排名(x軸)和排名的標準偏差(y軸)。
圖5、索引和評分程序的具體實例的概述,其也被用于實施例1和2。(A)對參考序列的集合索引過程中,非重疊的k-mer被索引為兩個不同的鍵值對存儲,一個將k-mer與發現有它們('存在')的參考關聯,一個將k-mer與其在發現有該k-mer的參考中的位置('位置')關聯。(B)當處理查詢集中的測序讀段時,重疊的k-mer在“存在”存儲中查找。使用重疊的k-mer允許相對迅速地解決讀段開始和參考序列開始(虛線)之間的錯配。在圖中,只有k-mer的子集與索引步驟同相,因此僅有它們能在“存在”中找到。(C)對于給定的讀段,將閾值僅僅施加到潛在足夠匹配該讀段的保留參考。使用例如在參考中的最小區域內最高集中度的k-mer,在查詢了“位置”存儲的最后步驟中解決了在大量含有不相交的分散k-mer的參考的情況,例如針對哺乳動物基因組的細菌讀段。
圖6、細菌讀段。對于在一組747個基因組中的每一個細菌基因組,模擬了幾個讀段長度(50個核苷酸(nt)、75nt、100nt、150nt、200nt、250nt)和幾個置換錯誤率(0%、1%、5%、10%)。將100個隨機讀段用于每個查詢并記錄列表中的正確參考的排名分布;排名1意味著正確的參考是在列表的最上方。返回的命中的列表被設定為最大長度25并且如果根本不在列表中那么就將該參考算作“未找到”。正確的測試細菌基因組的百分比表示為嵌入每個板的右側的條。該圖表明,正如所料,隨著錯誤率增加,性能下降,同 時也表明,長度為50的讀段似乎具有相對降低的性能。相比于100個核苷酸的讀段,將讀段長度增加至超過100個核苷酸僅帶來小的改進,并且對錯誤率的補償效應有限。
圖7、細菌讀段(讀段數目)。對于在一組747個基因組中的每一個細菌基因組,模擬了幾個讀段長度(50nt、75nt、100nt、150nt、200nt、250nt)和幾個置換錯誤率(0%、1%、5%、10%)。將100、200或300個隨機讀段用于每個查詢并記錄列表中的正確參考的排名分布;排名1意味著正確的參考是在列表的最上方。曲線表示100、200和300個讀段。由此可以看出,隨機樣品中的讀段數目從100個讀段增加到300個讀段使得性能相對較小的增加。錯誤率或讀段長度具有更大的作用。
圖8、細菌讀段,對于747個測試細菌基因組,執行5次識別程序的一次迭代時,真實參考的性能變異性,平均排名(排名,x軸)和排名的標準差(Srank,y軸)。平均排名越接近1,越接近完美的性能,并且排名的標準差越小,采樣效果的敏感性越小。為了提高清晰度,當測試的大量細菌基因組在散點圖上產生等于或接近坐標時,使用六邊形分選并相應地著色該區域。各散點圖的右側豎條表示沒有前25個匹配內的測試基因組的數目,并且與六邊形分選以相同分級著色。嘗試了不同的讀段大小(行)和錯誤率(隨機置換,列),產生散點圖矩陣。
圖9、細菌讀段,同一物種。給出正確物種,也就是在我們的集合中屬于相同物種的細菌的參考,而不是圖7中示出的完全相同的參考的匹配百分比,以及正確物種不在頂部25個匹配的情形下的百分比。對于短讀段(50nt)性能相對較差,噪音進一步降低它(第一行的條線圖),但從100nt變得非常好,并保持對噪聲的穩健性。
本發明的詳細描述
本發明平衡了對來自樣品中發現的蛋白質、DNA或RNA的生物序列信息的可能來源執行識別的速度和精度。
在本發明方法中要使用的序列信息可以例如是來自核酸測序儀或者來自蛋白質的C-或N-端測序或來自質譜蛋白質測序的原始讀段。因此,在本發明的語境中的措詞采樣序列是指這種也被稱為短讀段的原始讀段。
在圖2中描述的本發明一個具體實施方式可以涉及:
·用參考DNA創建數據庫(參見圖1)。該數據庫是兩部分:1)相對于參考來索引的所有參考DNA的k-mer的數據庫和2)來自數據庫1的k-mer與在該參考序列中的位置之間的關聯性的數據庫。因而參考k-mer ID和位置被存儲在兩個不同的數據庫中。
圖1示出了數據庫構建的一個實施方式。用來創建數據庫的輸入是來自公共或專有數據庫的DNA。這些然后都被分成k-mer,其可以優選是不重疊的以節省空間。k-mer還可以是2比特位類型的(2-bit bit packed),這意味著每個堿基只占用存儲器的2個比特。為了加快存儲k-mer,優選在插入數據庫之前對這些k-mer進行分選。此外在該k-mer所來源的參考序列中的名稱和位置可以存儲在單獨的數據庫中。
·針對參考數據庫,搜索來自一來源的查詢序列的分解成k-mer的讀段的選擇。
·由來自該查詢序列的k-mer數計算主要得分,該k-mer可以在數據庫中的給定參考序列中找到。
·將建議的序列返回用戶,并且可以用于更大量且傳統的分析。
本發明的這一實施的特征是:
·在搜索期間,只有完全匹配的k-mer被登記。
·查詢讀段分解成多個k-mer,如長度為16。每個k-mer的起點增量為1。
·不是“傳統”的從頭、比對或映射方法。
圖2示出了用于搜索k-mer數據庫的一個可能的算法。使用具有一個步長的滑動窗將讀段分成k-mer。如果在當前搜索中已經遇到(訪問)k-mer, 那么選擇下一個k-mer。隨后在k-mer數據庫中查找該k-mer。如果它在數據庫中,那么提取在參考序列中的身份和位置。然后計算讀段的近似連續性,并且如果最大連續節段超過閾值,那么命中計數增加。這對于讀段中的所有k-mer進行重復。對于每個讀段,將得分計算為命中數(命中計數)除以查詢序列的長度,并且計算命中計數除以匹配參考序列的長度。這對多個讀段進行重復,這可以依賴于所獲得的得分被先驗或動態定義。得分被分選并且將最佳匹配返回給用戶。
完全匹配不是在讀段水平進行。評分允許沿讀段缺失k-mer匹配(因此確保了對生物樣品中的測序錯誤和突變的穩健性)。
該系統的概述是:
·索引所有已知的參考DNA序列為k-mer,存儲參考(例如物種)和在參考序列中的位置。這一步優選只在參考DNA序列通過增加新序列或通過添加更多的序列信息來更新時進行。
·客戶端,可以通過將DNA的短序列分成k-mer,針對數據庫匹配它們并計數對參考序列的命中數,優選以位置信息精化該匹配,來存儲它們。
獲得的參考隨后可用于:
·過濾掉匹配參考的讀段,并且找到是否存在來自另一不同參考但低豐度的DNA
·針對該參考執行比對,或利用數據庫中的參考反復構建更大的片段,這導致比通過利用預先組裝的參考進行從頭組裝更好的性能;此外,該性能將隨著數據庫大小增大而提高并且加入了更多的組裝好的參考
·識別各種生物體或基因(例如與用于診斷目的相關)的可能存在。
因為只有原始讀段的子樣品是必要的,這可以減少為執行基本的診斷(如識別傳染劑)而被傳輸的數據量。在更小的序列實驗的情況下,這也允許一些分析通過客戶端在商品化硬件上進行。
隨著低通量桌面測序儀(或一次性測序單元)的發展以及更便宜的GPU或FPGA的興起,聯合了允許對測序數據進行實時或接近與實時的初步分析的技術。
算法
在一個方面,本發明涉及識別生物序列的可能來源的方法,該方法包括:
a)從一來源采樣序列或短讀段的子集,
b)將來自該子集的序列分段成k-mer,
b)針對包含參考序列的k-mer的數據庫,查詢來自所述子集的k-mer,
d)確定哪個(哪些)參考包含該k-mer,和
e)返回對可能的來源參考的描述。
術語“從一來源的序列”被用于指定從包含生物序列的樣品中獲得的序列。樣品可以是環境樣品、來自受試者(如患者)的樣品、來自犯罪現場的樣品、食品樣品、水樣品等。樣品進行現有技術的DNA/RNA或蛋白質分離和測序方法。結果是一組表征該樣品的序列(也稱為讀段)。該序列通常是在一定間隔內的隨機長度。該序列也通常是隨機重疊的。來自樣品(稱為來源序列)的每個序列可進行本發明的方法。
根據本發明的術語“參考”包括存儲在數據庫中的序列的描述符。參考的典型例子是特定物種或栽培物,或分離株的全長基因組序列。參考也可以由特定物種或特定條件的物種的轉錄組或蛋白質組組成。物種的轉錄組和蛋白質組可以響應于年齡和環境條件隨時間而改變,而例如物種的基因組序列仍隨時間或多或少恒定。數據庫可存儲關于參考的額外信息。
本發明的方法可以適用于任何生物序列信息,例如氨基酸序列和核苷酸序列如DNA和RNA序列。在優選的實施方式中,序列是DNA序列。
在最廣泛的方面,本發明僅依賴于從查詢或來源序列中識別k-mer的存在。在這種情況下,從算法輸出的是參考列表和在參考中識別的相應命中數 目。然而,由于一些基因組,例如人類基因組并且特別是一些植物基因組的大小,許多k-mer可能偶然存在于這些非常大的基因組中。因此,在優選的實施方式中,查詢還包括確定k-mer在參考序列中的位置。這允許使用存在和位置來確定查詢k-mer在參考序列中的連續性。這使得查詢更精確,因為可使用同時基于k-mer在參考中的存在和位置,或近似連續性的得分。因此本發明的一個優選實施方式涉及一種識別生物序列的可能來源的方法,該方法包括:
a)從一來源采樣序列或短讀段的子集,
b)將來自該子集的序列分段成k-mer,
c)針對包括參考序列的k-mer的第一集合,查詢來自所述子集的一個或多個k-mer,
d)針對包括k-mer在參考序列中的位置的第二集合,查詢來自所述子集的一個或多個k-mer,
e)確定哪個(哪些)參考含有該k-mer,和
f)返回對可能的來源參考的描述,
其中包括參考序列的k-mer的集合與包括k-mer在參考序列中的位置的集合是分離的。
在本發明的一個甚至更優選的實施方式中,針對包括k-mer在參考序列中的位置的第二集合的查詢僅僅是當在包括參考序列的k-mer的第一集合中已經發現(即存在)給定k-mer時才進行(參見圖2)。
在本發明的一個優選實施方式中,當使用上述步驟a)到f)時,在查詢隨后的k-mer之前,確定給定k-mer的存在和位置。因此本發明的一個優選實施方式涉及一種識別生物序列的可能來源的方法,該方法包括:
a)從一來源采樣序列或短讀段的子集,
b)將來自該子集的序列分段成k-mer,
c)針對包括參考序列的k-mer的第一集合,查詢來自所述子集的k-mer,
d)針對包括k-mer在參考序列中的位置的第二集合,查詢來自所述子集的所述k-mer,
e)確定哪個(哪些)參考含有該k-mer,和
f)返回對可能的來源參考的描述,
其中包括參考序列的k-mer的集合與包括k-mer在參考序列中的位置的集合是分離的。
本發明的一個顯著的特點是,只將從測序獲得的序列的子集用于查詢數據庫。這使使得在測序和查詢非常大的基因組時可能是限速步驟的數據傳輸最小化。因此序列的子集可以包括離散序列中的至少1%,例如至少2%,如至少4%,例如至少5%,如至少6%,例如至少7.5%,例如至少10%,如至少15%,例如至少25%,如至少30%,例如至少35%,如至少40%,例如至少50%。
本發明的一個特征在于k-mer查詢涉及確定查詢k-mer和參考k-mer之間的精確匹配。
當查詢來源序列或短讀段時,查詢優選涉及查詢來自至少一個來源序列的所有k-mer。這允許對連續性或近似連續性的最佳計算。優選地,查詢來自至少50個來源序列的所有k-mer,例如來自至少100,如至少150個,例如至少200個,如至少250個,例如至少300個,如至少400個,例如至少500個,如至少750,例如至少1000個,例如至少1500個,如至少2000個,例如至少2500個,如至少5000或更多個序列。所查詢的來源序列的確切數目特別是通過網絡和計算能力、時間限制、統計要求和全長來源序列的大小和與不同參考的源的相關性來確定。
如在實施例中所示,每個來源序列優選是給定的最小長度以得到源生物體、品種、栽培物或分離株的特性指紋。在來源序列是核苷酸序列的情況下,來源序列優選至少50個核苷酸堿基,更優選至少75個核苷酸堿基,例如75至200個核苷酸堿基,如75個核苷酸堿基至100個核苷酸堿基,或100個核苷酸堿基至125個核苷酸堿基,或125個核苷酸堿基至150個核苷酸堿基,或150個核苷酸堿基至175個核苷酸堿基,或175個核苷酸堿基至200個核 苷酸堿基,甚至更優選至少100個核苷酸堿基,例如100-300個核苷酸堿基如,如100個核苷酸堿基至150個核苷酸堿基,或150個核苷酸堿基至200個核苷酸堿基,或200個核苷酸堿基至250個核苷酸堿基,或250個核苷酸堿基至300個核苷酸堿基,如至少100個核苷酸堿基,例如100個核苷酸堿,例如200個核苷酸堿基,如至少250個核苷酸堿基,例如300個核苷酸堿基,如400個核苷酸堿基,至少500或更多個核苷酸堿基。
在許多實際實施中,初始查詢序列的一個子集。如果這還不足以以足夠高的確定性來確定參考,該方法可以進一步包括選擇序列的一個或多個另外的子集并將它們進行本發明方法的步驟a)至f)。
原則上,該方法允許使用任何大小的k-mer或k-字。然而,在一個優選實施方式中,k-mer的大小可以被4整除。因此,k-mer可以是大小為4、8、12、16、20、24、28、32、36、40、44、48、52、56、60、64或更長。更優選地,k-mer的長度為16和64之間,更優選16和32之間。更長的k-mer使該方法對測序錯誤更敏感而更短的k-mer增加隨機命中的數量,從而提供噪聲。
在一個實施方式中,k-mer是連續的,并且優選地,存儲在數據庫中的k-mer是連續的,以便覆蓋整個參考序列。
優選地,來自來源序列的k-mer是重疊的并且增量為至少一個堿基或氨基酸,例如至少兩個,如至少3個,例如至少4個,如至少5個,例如至少6個或更多。這相當于橫跨序列滑動寬度為k的窗口。橫跨序列可以滑動一、二或更多個堿基/氨基酸的窗口。通過從來源序列進行重疊和增量k-mer,該方法對測序錯誤或點突變變得不敏感,因為將在查詢中識別在例如單個堿基突變/錯誤的任一側的k-mer。因此,可以以更高的精度計算連續性。
使用從來源序列的不相交子序列的串聯得到的不相交的k-mer也是可能的。
優選地,根據該方法,針對數據庫查詢來自給定序列的k-mer以確定在一個或多個參考序列中k-mer的存在以及該k-mer在所述一個或多個參考序列中的位置。為了優化數據庫使用,優選僅當k-mer存在于數據庫中時查詢位置。
為了允許定量評價所述查詢,該方法涉及為所識別的參考序列計算得分,所述得分與在給定的參考序列中找到的來自一個或多個序列的k-mer數目相關聯。這個得分可以例如被來源序列的長度整除。可為識別的參考計算進一步的得分,所述進一步的得分與在參考序列中找到的來自一個或多個序列的k-mer的連續性相關聯。例如,該得分可以是來自在數據庫中找到的一個來源序列的k-mer和在該數據庫的一個參考序列中找到的k-mer的最長序列的百分比。
類似地,對于每個識別的參考序列,可以為識別的參考計算得分,所述得分與在參考序列中的k-mer數目相關聯,所述k-mer也存在于來自所述來源的k-mer的子集中。一個實例可以是數據庫中來自來源序列中發現的一個參考的k-mer的百分比。在許多實際應用中,查詢數百個來源序列并評分,以獲得滿意的確定性。這個得分還可以包括基于所識別的k-mer的連續性的得分。
優選地,為每個不同的來源序列計算這些得分,例如其中查詢來自一個來源序列的所有k-mer并且為所述來源序列計算一或多個得分。優選地,該方法還涉及查詢來自第二來源序列,優選來自第三來源序列的所有k-mer等。對于不同的來源序列的得分可例如通過將它們以來源序列的長度加權而合并。
在本發明的一個實施方式中,一旦對為讀段所生成的所有k-mer進行處理,在參考中匹配的連續位置的數目被用來隔離最大的匹配簇,即,在所有匹配參考中源自相同讀段的最大集中度的匹配k-mer。對于每個這樣的簇,計數是通過將在一個簇中的k-mer數量加上給定的參考序列的計數來計算 的。當該方法是對給定樣品的一個以上的讀數迭代時,該計數可通過將在一個簇中的k-mer的數量加上從先前的讀段獲得的參考序列的計數來更新。即,計數可以通過加上用于該參考的k-mer數量來更新并且已經計數的k-mer列表被更新。然后可以處理下一個序列或讀段。獲得與發現匹配的k-mer計數相關聯的參考列表。對于每對<參考,計數>,計數除以查詢集中獨一無二的k-mer的數量,提供了在給定參考匹配的被查詢子集中DNA量的粗略得分。如果被查詢的子集是完全匹配該序列,那么得分將是1,否則會降低;例如,如果所查詢的子集是兩個參考的等比例混合物,那么對兩個參考的得分都將是0.5左右。該計數也可以除以參考的大小(或在參考序列中獨一無二的k-mer的數量),得到由所查詢的子集表示的參考部分的粗略得分;該第二得分有助于對匹配參考進行分選,并避免偏向最大參考。最終的得分是這兩個得分的加權和,例如其中對每個得分使用相等的加權。
在本發明的一個實施方式中,查詢預先選定數目的來源序列并返回結果。然而,在其他實施方式中,一旦以預定義的統計概率識別出參考生物體,那么就可以停止數據庫查詢。同樣,如果在數據庫中沒有找到預定義分數的k-mer或擴展更多的來源序列,或以松弛參數計算的得分,那么可以停止數據庫查詢。這在垃圾序列,具有許多測序錯誤的序列或完全未知序列的情況時可能如此。
來自查詢過程的輸出可以是根據一個或多個所述得分排名的可能的來源參考列表。數據庫輸出的其它實例包括關于一個或多個可能參考的下列信息中的一個或多個:可能參考的分類學名稱、所述可能參考的近親、所述參考的來源、遺傳連鎖信息、關于SNP、基因在序列中的位置和注釋的信息。
在一個具體的實施方式中,數據庫輸出最可能的參考的序列,優選地,其中所述數據庫輸出最可能的參考物種的全基因組序列。這允許用戶使用現有技術的比對算法,針對最可能的物種的全基因組序列比對來源序列,以進一步調查是否有突變或插入或染色體異常(anomaly),異常(abnormality)或畸變。然而,在本發明的一個實施方式中,本發明的方法不涉及對序列數 據使用比對算法,如,例如使用得分矩陣的算法,如,例如Smith-Waterman algorithm[14],BLAST[1],BLAT[5],Bowtie,BWA,SHRiMP[16],或熟練技術人員已知的其他比對算法。
在許多情況下,例如,當查詢微生物的序列時,該數據庫可包括許多密切相關的序列,如來自相同物種的不同分離株的序列。在這樣的情況下,來自具有非常相似的序列的參考的結果可在輸出中被分組。這還可以允許用戶更容易地識別來自以較低量存在的另一物種或不同物種中的小片插入的DNA。
在許多情況下,樣品包含物種的混合種群并且全基因組測序這將導致來自幾個物種的基因組DNA的混合物。在這種情況下,該方法可以涉及執行該方法的幾次迭代,例如在第一次迭代中識別最豐富的參考。在第二迭代中,從來源序列中除去來自最豐富的物種的序列,然后查詢數據庫或者該方法可以涉及忽略來自該物種的進一步的結果。
可替代地,來自本發明的方法的一個迭代的輸出可以包括用于所識別的所有參考的信息和得分。在這種情況下的得分可以包括在不同參考之間的百分比分布。
本實施方式也可以用于識別插入物的參考,例如病毒插入物、轉基因或來自另一細菌物種的插入物。
在許多實施方式中,用戶將最初知曉在樣品中存在來自一個參考的序列或短讀段,并且隨后的任務是識別在該樣品中存在的任何其它序列或短讀段的可能的參考。這在診斷學的情況下會是如此,其中樣品包含人類DNA和來自可能的病原體的DNA兩者。其它實例包括對食物樣品中有害細菌的識別,其中,已知樣品含有來自食物源(如沙拉、番茄、黃瓜、來自特定物種的肉)的DNA并且任務是識別任何污染的DNA的存在和身份。在這樣的方法中,該方法可以包括最初去除與來自預先定義的參考的序列對準的來源序 列。或者,該方法可以涉及忽略來自一個或多個預先定義的參考的k-mer。
在一個實施方式中,該方法涉及在從核酸測序儀獲得原始讀段時采樣并查詢它們。
當為了診斷目的識別DNA數據的查詢集(如來自測序儀的短讀段或原始讀段)時,我們認為包括映射或比對針對于全面的參考數據庫的所有讀段的蠻力方法有兩個主要的缺點:首先是幾百兆或千兆字節的數據的大部分或者從測序設施轉移到計算中心,其次是執行該任務必須的計算資源是至關重要的。假設一個參考集合包含10,000大腸桿菌規模的細菌并且需要30秒優化比對器,如BWA和bowtie2來處理250Mb的原始測序數據(如果基因組是4Mb大小,平均覆蓋為約60x),盡管可以在多個CPU上并行進行處理,但是這樣的CPU處理會花費3天半。可以進行精化使得基因組串聯但代價是需要日益增加的存儲器容量,向初始參考基因組分配映射位置的后處理運算,以及參考接近的基因組時不可避免的多個匹配,這是短讀段比對器往往不適的方面。使用FM-索引在大小為u的參考中定位長度p的串的n個出現次數具有上限O(p+n logεu),這意味著,盡管隨著參考大小(以logε定義的術語)的增加,復雜性增長緩慢,但它與高度相似的基因組的數量呈線性增長。我們的方法包含了巨大的參考數據庫的觀點,并且不試圖在一臺計算機的所有RAM中容納它們。
數據庫
在一個方面,本發明涉及包含參考序列的k-mer的數據庫,所述數據庫包括:
a.來自參考序列的k-mer的第一集合,和
b.每個k-mer在該參考序列中的位置的第二個集合。
數據庫架構允許非常快速地查詢來自來源序列的k-mer,如示于所附實施例中,其證明了結果可在幾秒鐘內被返回。
該數據庫可以進一步包括關于與給定參考相關聯的全長序列,和/或所述參考的來源,和/或所述參考的一種或多種分類學描述符的信息。可以被存儲的附加信息是關于DNA序列中的基因注釋的信息。
當建立該數據庫時,k-mer可以進行哈希函數,向每個獨一無二的k-mer分配唯一的密鑰。其他的可能性包括搜索樹或哈希函數和搜索樹的組合。該唯一的密鑰可以與關于k-mer所在的那些參考的信息相關聯。
在第二集合中,第二集合中的每個獨一無二的k-mer也可以用作密鑰,并通過哈希表、搜索樹或它們的組合與關于在每個參考中k-mer(k-mer在該參考中存在)的位置的信息相關聯。此集合可以包括關于k-mer存在的位置的進一步的信息,例如與序列如編碼序列、調節序列等的任何注解的關聯性。
關于存在給定k-mer的參考序列的一個或多個另外的信息,例如與序列的任何注釋的關聯性、編碼序列、調控序列、可能參考的分類學名稱、所述可能參考的近親、所述參考的來源、一組另外相關的參考、參考是從哪里獲得的(例如土壤、海洋、內臟、下水道等)、參考序列是何時獲得的、分類學分類、近緣物種、關于參考序列是從哪個數據庫(例如NCBI、EBI/Sanger)下載的信息,或者其他信息都可存儲在單獨的數據庫中,例如SQL數據庫,其可以另外用于提取關于根據本發明的參考序列的信息。
術語“一組另外相關的序列”是指來自取自諸如土壤、海洋、內臟、下水道等的相似環境的樣品的序列。
因此,在本發明的一個實施方式中,包括參考序列的k-mer的數據庫包括:
a)來自參考序列的k-mer的第一集合,和
b)每一k-mer在該參考序列中的位置的第二集合。
c)第三集合或數據庫,其具有選自下組的參考標識符和一或多個信息:描述行、數據來源、可能參考的分類學名稱、所述可能參考的近親、所述參 考的來源、一組另外相關的參考的信息、參考是從哪里獲得的(例如土壤、海洋、內臟、下水道等)、參考序列是何時獲得的、分類學分類、近緣物種、關于參考序列是從哪個數據庫(例如NCBI、EBI/Sanger或其他數據庫)下載的信息。
在一個優選的實施方式中,k-mer的第一集合是關聯到每個k-mer(數據庫中的密鑰)的鍵值對存儲或NoSQL數據庫,例如KyotoCabinet,對應于具有該k-mer的參考的標識符列表如圖1中所示。k-mer在參考序列中的位置的第二集合也可以被存儲在鍵值對存儲或NoSQL數據庫,例如KyotoCabinet中(參見圖1)。參考標識符和信息條(例如描述行和數據來源)之間的關聯性被存儲在單獨的SQL數據庫中。
雖然假定有足夠的查找表,但k-mer在數據庫中的長度優選匹配k-mer在來源序列中的長度。然而,k-mer在數據庫中優選不重疊。使用重疊的k-mer將增加數據處理時間。
根據本發明,在數據庫中參考序列的索引的k-mer可以是重疊或非重疊的。在優選實施方式中,索引的參考序列的k-mer是非重疊的。本領域技術人員可以理解,相似的評分原則可以用于參考序列中的非重疊或重疊的k-mer的索引數據庫。
如果將樹或哈希用于k個索引和查找,在以k-mer索引的大小為u的參考中定位長度p的串的n個出現的時間復雜度具有O(p+n log u)或O(p+n)的復雜度。
這并不排除這樣的實施方式,其中k-mer是重疊的并且增量為至少一個堿基或氨基酸,例如至少兩個,如至少3個,例如至少4個,如至少5,例如至少6個或更多。
在優選的實施方式中,給定參考的完整基因組序列被分段成k-mer并上 傳到數據庫中。還可以設想僅基于給定參考的轉錄組或給定參考的蛋白質組建立數據庫。
如果目的只是為了識別來源序列的可能的參考,該數據庫不必是完整的。提供對來自特定參考的基因組DNA的隨機選擇可能就足夠。該選擇也可以是非隨機的,例如排除重復DNA以及所謂的垃圾DNA的拉伸。
對于生物序列、蛋白質、RNA、DNA每種類型,可以構建一個包含所有可用信息的數據庫。在其他實施方式中,可以構建用于專門目的的專門的數據庫,例如目的僅僅是為了從來源序列識別給定參考序列的存在或不存在。例如,該數據庫可以包括來自人類、動物、哺乳動物、鳥類、魚類、真菌、昆蟲、植物、細菌、古細菌、病毒和/或質粒的序列信息。如果沒有找到具有足夠高的得分的匹配參考,也可以通過一個服務器向一個或幾個其他服務器轉發的關于讀段的請求來建立數據庫網絡。
為了不損害速度而最佳利用硬件資源,該數據庫可以被劃分成存儲在幾個不同的服務器中的子數據庫。
在其他實施方式中,根據選自門、綱、目、科、屬和種的一種或多種分類學描述符,或一種或多種環境描述符,如來源、分布、起源和通常的搜索頻率,使所述數據庫組織成子數據庫。
該數據庫可以按照在圖1中的描述來構建并使用被稱為鍵值對存儲的數據庫引擎(例如BSDDB、KyotoCabinet、LevelDB、MongoDB和其他)存儲。因此,在本發明的一個實施方式中,使用選自BSDDB、KyotoCabinet、LevelDB、MongoDB的組中的鍵值對存儲來存儲數據庫。
算法的應用
本發明的方法和系統可以在需要識別在樣品中發現的DNA的可能來源的多種應用中使用。
診斷
在藥物治療中,需要快速識別感染的可能來源。這可以使用根據本發明的方法來完成。由此可以選擇將以最有效的方式和最少的副作用治療感染的合適的治療。
進一步的診斷應用涉及識別癌細胞中的病毒插入物。在本申請中,有利的是從獲自原始讀段的序列過濾全長人類序列或者簡單地忽略在數據庫中識別的所有人類命中。這將允許識別人基因組中的相對小的病毒插入物。
生物防御
在生物防御應用中,有必要進行快速可靠地識別所遇到的傳染性物種或致病劑。本發明提供了對該來源沒有先驗知識時快速識別該來源的可能性。本發明的方法允許沒有對病原體物種的先驗知識時區別物種。
生物防御的其它應用包括識別轉基因病原體,其中已經插入了例如有毒的轉基因。該數據庫有利也包含來自現有技術的質粒的序列信息。這將允許容易地識別插入物的側翼區。如果轉基因是來自在數據庫中發現的生物體,它也將可能識別轉基因的來源。在這種情況下,數據庫可以返回病原體的名稱、該轉基因來源的生物體的名稱、該轉基因編碼的基因以及用于插入該轉基因的質粒。
食品安全和質量
目前用于鑒定食品中潛在的有害傳染的方法緩慢(基于傳染性生物體的分離和生長)或需要傳染源的以前的知識(基于PCR的方法)。本方法不需要如此,并允許當局和制造商簡單地分離基因組DNA,測序DNA并上傳原始讀段到能夠操作本發明的方法的系統。
當在食物樣品中尋找細菌、真菌或病毒時,有利的可能是查詢只包含來自細菌、真菌或病毒的序列的數據庫的一小部分。以這種方式,來自食物(蔬菜、水果、肉)的任何基因組序列都將被識別為在數據庫中不存在,從而提高了該方法的性能。
其他應用包括質量控制。一種可能的應用是識別肉的種類,如肉末、肉醬、即食餐、方便食品。有許多企圖詐騙的實例,其中昂貴的肉,如牛或羊 肉被用更便宜的肉類,如豬肉替換或“稀釋”。
其他可能的質量控制應用包括確定植物的品種,如葡萄、蘋果、土豆等。
再其他的可能性包括水質的控制。
衛生和預防
本發明提供了通過能夠快速鑒定取自與清潔程序相連的樣品中的DNA來源來進行衛生控制的可能性。進一步的應用包括識別污染的可能來源從而能夠應用最適于消除特定傳染原的衛生技術。
項目
現在,本發明描述為任意編號的項目1到56,這將被視為本發明的實施方式。進一步參照所附的權利要求定義本發明。
1.一種識別生物序列的可能來源的方法,該方法包括:
a)從一來源采樣序列或短讀段的子集,
b)將來自該子集的序列分段成k-mer,
c)針對包括參考序列的k-mer的數據庫,查詢來自所述子集的k-mer,
d)確定哪個(哪些)參考含有該k-mer,和
e)返回對可能的來源參考的描述。
2.項目1的方法,其中生物序列或短讀段是氨基酸序列。
3.項目1的方法,其中所述生物序列或短讀段是DNA或RNA序列。
4.任一前述項目的方法,其中k-mer查詢涉及確定查詢k-mer和參考k-mer之間的完全匹配。
5.任一前述項目的方法,其中所述查詢進一步包括確定k-mer在參考序列中的位置。
6.任一前述項目的方法,其中存在和位置被用來確定在參考序列中的查詢k-mer的連續性。
7.任一前述項目的方法,其中查詢涉及從至少一個來源序列或短讀段查詢所有的k-mer,優選從至少50,例如從至少100,如從至少150,例如從至少200,如從至少250,例如從至少300,如從至少400,例如從至少500,如從至少750,例如從至少1000,例如從至少1500,如從至少2000,例如從 至少2500,如從至少5000或更多個序列。
8.任一前述項目的方法,其中所述來源序列是至少50個堿基的核苷酸序列,優選至少100個堿基,如至少150個堿基,例如至少200個堿基,如至少250個堿基,例如至少300個堿基,如至少400,至少500或更多個堿基。
9.任一前述項目的方法,其中序列的子集包括至少1%的離散序列,例如至少2%,如至少4%,例如至少5%,如至少6%,例如至少7、5%,例如至少10%,如至少15%,例如至少25%,如至少30%,例如至少35%,如至少40%,例如至少50%。
10.任一前述項目的方法,進一步包括選擇序列的一個或多個另外的子集并將它們進行項目1的步驟a)至步驟e))。
11.任一前述項目的方法,其中所述子集是隨機的或過濾的。
12.任一前述項目的方法,其中k-mer的大小為4、8、12、16、20、24、28、32、36、40、44、48、52、56、60、64或更長。
13.任一前述項目的方法,其中k-mer是連續的。
14.任一前述項目的方法,其中k-mer是重疊的并且增量為至少一個堿基或氨基酸,例如至少兩個,如至少3個,例如至少4個,如至少5個,例如至少6個或更多。
15.任一前述項目的方法,其中k-mer是不相交的子序列的串聯。
16.任一前述項目的方法,其中針對數據庫查詢來自給定序列的k-mer以確定k-mer在一個或多個參考序列中的存在和k-mer在所述一個或多個參考序列中的位置。
17.項目16的方法,其中只在k-mer存在時才查詢位置。
18.任一前述項目的方法,其中為返回的參考計算得分。
19.任一前述項目的方法,其中為識別的參考序列計算得分,所述得分與在給定的參考序列中發現的來自一個或多個序列的k-mer數目相關聯。
20.任一前述項目的方法,其中為識別的參考計算得分,所述得分通過在參考序列中發現的來自一個或多個序列的k-mer的平均局部集中度與連續性或近似連續性相關聯。
21.任一前述項目的方法,其中為識別的參考計算得分,所述得分與在參考序列中的k-mer數目相關聯,所述k-mer也存在于來自所述來源的k-mer 的子集中。
22.任一項目18至21的方法,其中根據所述得分對可能的來源參考排名。
23.任一前述項目的方法,其中查詢來自一個來源序列或短讀段的所有k-mer并且為所述來源序列或短讀段計算一個或多個得分。
24.項目23的方法,還包括:查詢來自第二來源序列或短讀段,優選來自第三來源序列或短讀段的所有k-mer等。
25.任一前述項目的方法,其中一旦以預定義的統計概率識別出一參考生物體,那么可以停止數據庫查詢。
26.任一前述項目的方法,其中如果在數據庫中沒找到預定分段的k-mer,那么可以停止數據庫查詢。
27.任一前述項目的方法,其中數據庫輸出關于一個或多個可能參考的下列信息中的一個或多個:可能參考的分類學名稱、所述可能參考的近親、所述參考的來源、一組另外相關的參考。
28.任一前述項目的方法,其中所述數據庫輸出最可能的參考的序列,優選其中所述數據庫輸出最可能的參考物種的全基因組序列。
29.任一前述項目的方法,其中來自具有非常相似的序列的參考的結果或者來自另外相關的參考的結果在輸出中分組。
30.任一前述項目的方法,其中執行該方法的幾次迭代,如在第一次迭代中,識別最豐富的參考并從所述來源序列或短讀數中去除來自所述最豐富的參考的序列。
31.項目30的方法,還包括在第二次迭代中,識別第二最豐富的參考,去除來自所述第二最豐富的參考的序列等。
32.項目30的方法,還包括在第二次迭代中,識別插入物的可能參考。
33.任一前述項目所述的方法,該方法還包括最初去除與來自預定義的參考的序列對準的來源序列。
34.任一前述項目的方法,其中所述方法包括如果數據庫中不存在來自一個來源序列或短讀段的預定義數目的k-mer,那么從所述來源序列或短讀段忽略k-mer。
35.任一前述項目的方法,其中查詢涉及忽略來自一個或多個預定義的參考的k-mer。
36.任一前述項目的方法,其中當從核酸測序儀獲得原始序列時查詢所述原始序列。
37.一種包括有參考序列的k-mer的數據庫,所述數據庫包括:
a)來自參考序列的k-mer的第一集合,和
b)每個k-mer在參考序列中的位置的第二集合。
38.項目37的數據庫,其中所述數據庫還包括關于與給定參考相關聯的全長序列的信息,和/或所述參考的來源,和/或所述參考的一個或多個分類學描述符。
39.項目37-38的數據庫,其中在數據庫中的k-mer進行哈希函數運算,向每個獨一無二的k-mer分配唯一密鑰。
40.任一項目37-39的數據庫,其中在第一集合中的每個獨一無二的k-mer由矢量與關于有k-mer存在的那些參考的信息相關聯。
41.任一項目37-40的數據庫,其中在第二集合中的每個獨一無二的k-mer由矢量與關于該k-mer存在時,其在每個參考中的位置信息相關聯。
42.項目37-41的數據庫,其中k-mer的長度為4、8、12、16、20、24、28、32、36、40、44、48、52、56、60、64或更長。
43.任一項目37-42的數據庫,其中k-mer是非重疊的。
44.任一項目37-43的數據庫,其中k-mer是重疊的并且增量為至少一個堿基或氨基酸,例如至少兩個,如至少3個,例如至少4個,如至少5個,例如至少6個或更多。
45.任一項目37-44的數據庫,其中數據庫包括來自每個參考的完整序列的k-mer。
46.任一項目37-46的數據庫,其中所述數據庫包括來自人類、動物、哺乳動物、鳥類、魚類、真菌、昆蟲、植物、細菌、古細菌、病毒和/或質粒的序列信息。
47.任一項目37-46的數據庫,其中所述數據庫被分成存儲在幾個不同服務器中的子數據庫。
48.任一項目37-47的數據庫,其中根據選自門、綱、目、科、屬和種的一種或多種分類學描述符,或一種或多種環境描述符,如來源、分布、起源和過去查詢的頻率,使所述數據庫組織成子數據庫。
49.一種用于識別來源序列的可能來源的數據處理系統,該系統包括輸入裝置、中央處理單元、存儲器和輸出裝置,其中,所述數據處理系統中存儲有表示在執行時使得項目1-36的方法得以被執行的系列指令的數據,所述存儲器還包括根據任一項目37-49的數據庫。
50.項目49的系統,其中所述數據庫存儲在服務器中,并且輸入和輸出裝置是客戶端,所述客戶端和服務器經由數據通信連接來連接。
51.任一項目49-50的系統,其中所述客戶端選自個人計算機、臺式PC、便攜式PC、手持式計算裝置,如智能電話。
52.任一項目49-51的系統,其中所述客戶端包括使客戶端采樣來源序列的子集,將這些來源序列分段成k-mer,并將這些來源序列傳送到服務器的一系列指令。
53.項目49-52的系統,所述客戶端還包括允許其基于從服務器傳送到客戶端的序列,執行將來源序列組裝成一個或多個更大的序列的一系列指令。
54.任一項目49-53的系統,通過數據連接與測序設備相連接。
55.一種計算機軟件產品,含有在執行時使得項目1-36的方法得以被執行的系列指令。
56.一種集成電路產品,含有在執行時使得項目1-36的方法得以被執行的系列指令。
實施例
具有k-mer的序列的快速識別
這里,我們提出了新方法,Tapir,即能夠迅速地指向DNA或RNA的可能來源并能夠直接在從DNA測序儀獲得的原始讀段上工作。我們的系統包括參照已知DNA的服務器,以及具有待量化的DNA數據的客戶端。為了說明如何使用,我們已參考了數千細菌基因組、噬菌體基因組、噬菌體和質粒,以及人類基因組、小鼠基因組、擬南芥和來自真菌、古細菌的各種序列。我們也已經在Web瀏覽器上實施了客戶端運行,并能夠處理來自便攜式計算裝置的數據中的數億個堿基的數據。該方法依賴于索引k-mer,以及向服務器傳輸有限量的數據。它能夠在幾秒鐘內從Android智能手機完成其任務,消 耗適度數量的帶寬與服務器通信,并且盡我們的知識提供了一種不同于任何現有工具的使用簡便性。它在我們的核心設施上使用,以測序運行來進行常規的即時質量檢查,并且可獲自http://tapir.cbs.dtu.dk
介紹
DNA測序在過去十年已經越來越實惠[13],扼要的講對DNA測序進行敘述再次成為絕對平常化。今天的高端測序儀具有處理相當于幾個人類基因組或幾百個細菌的能力,并且下一代測序儀已經開始變得可用,因此需要低得多的初始投資,并提供靈活的測序量。完整細菌分離株的測序是一天的事,并且很快就是幾小時的事。最近發布的納米孔測序[12]呈現了一個USB供電的裝置,能夠直接測序DNA,以及因為測序裝置將是一次性的,故而資本投資水平前所未有的低。Oxford Nanopore,在該未來產品背后的公司已經在2012年發布新款[8]。提取DNA是相對簡單的過程,并且可以預見,DNA測序將很快在分子生物學中成為常規和廉價的過程。患者將被常規測序,通過他們的DNA追蹤傳染原的暴發,水和食品的質量也通過DNA測序監測。
在分析方面,利用如Smith-Waterman算法[14]的開拓性的工具進行序列的局部比對已經成為生物信息學的基石。一旦將它應用到查詢集合和參考集合之間,將允許對比對排名,使研究者對新測序的DNA或RNA從它與現有序列的相似性來推斷其起源和功能。雖然有批評該方法有時是不準確的[2,11],但其受歡迎程度仍然是不爭的,公共數據庫中有大量的功能注釋提到“通過序列同源性”。然而,在數據庫中實現將新獲得的DNA與存檔的現有數據庫比對仍是相對苛刻的計算任務。BLAST[1]和隨后的BLAT[5]提高了速度,但在網絡搜索引擎幾乎立即返回結果的時代,用目前可用的序列數量針對已知序列的池搜索新序列可能需要相當長的時間。設計用于短讀段測序的新工具自從被開發出來也僅僅命名了兩個,如Bowtie[6]和BWA[7],但這些工具是被設計成針對給定參考來比對所有測序讀段。為了實現速度,這樣的工具將參考的索引加載到存儲器中,并以此限定可以被處理的參考DNA的量。
我們注意到在找到查詢序列和參考的集合之間的絕對最佳比對的計算需 求任務與從一組查詢序列快速識別與它們最匹配的參考之間的距離。據我們所知,沒有任何一種工具采用短DNA或RNA序列集,如來自DNA測序儀的讀段,并返回該集所代表的參考的列表,無論是全基因組或個體基因。要做到這一點,我們提出了與在BLAT和SSAHA[9,10]兩者中使用來自比對種子以及在MUSCLE[3]中的k-mer計數不同的方式使用k-mer,以幾秒或者更短時間相當準確地識別DNA序列的來源。
材料和方法
將獲自EBI和NCBI的公眾可得的基因組、重疊群、質粒和個體基因下載作為參考DNA。每個參考序列被分成重疊k-mer(on-overlapping k-mer)并且對于遍布所有參考的所有k-mer,創建鍵值對存儲或NoSQL數據庫(使用KyotoCabinet[4]),關聯到每個k-mer體(數據庫中的密鑰),對應于具有該k-mer的參考的標識符列表(圖1)。稱它為存在數據庫。同樣地,在參考中發現該k-mer的位置存儲在被稱為位置數據庫的地方(圖1)。參考標識符和信息,如描述行和數據源之間的關聯性,儲存在單獨的SQL數據庫中。
為了對一組短查詢序列或讀段評分,對它們的隨機樣品進行迭代(圖2)。對于每個序列,對通過在整個序列上滑動寬度k的窗口所獲得的連續k-mer進行迭代。對于每個k-mer,如果它之前并未被計數并且在存在數據庫中發現它,那么將查詢參考的位置。一旦對讀段的所有k-mer進行處理,查找在參考中匹配的連續位置的數目并且只考慮最大匹配簇,即,在所有匹配參考中源自相同讀段的匹配k-mer的最大集中度。對于每個這樣的簇,將k-mer數加上可能之前用于該參考的加數并且更新已經計數的k-mer列表。然后處理下一個序列或讀段。獲得與發現匹配的k-mer計數相關聯的參考列表。對于每對<參考,計數>,計數除以查詢集中獨一無二的k-mer的數量,提供了在給定參考匹配的被查詢子集中DNA量的粗略得分。如果查詢集完全匹配該序列,那么得分將是1,否則會降低;例如,如果查詢集是兩個參考的等比例混合物,那么對兩個參考的得分都將是0.5左右。該計數也可以除以參考的大小(參考序列中的獨一無二的k-mer數目),得到由該查詢表示的參考部分的粗略得分;該第二得分有助于對匹配參考進行分選,并避免偏向最大 參考。最終的得分被計算為這兩個得分的加權和,默認是相等的加權。如果查詢集很大,例如,如果考慮來自一輪DNA測序的所有讀段,那么僅使用該集的隨機樣品。
為了方便該服務使用,實施作為在Web瀏覽器中的網頁運行的HTML5/JavaScript客戶端。在編寫時,Firefox 15.0是實現所有需要的功能的唯一瀏覽器,并測試在Linux、Mac OS X、微軟的Windows和Android 4.0上的工作。
為了基準化該原本設計為識別測序數據中的細菌的系統,反復取得在2012年可從EBI獲得的細菌的所有序列,也就是747個細菌基因組。對于每一個基因組,從基因組序列產生隨機可能重疊的子序列,以模擬從DNA測序儀獲得的讀段;使用長度為50、100、150、200和250個堿基的子序列。還以0%(沒有錯誤)、1%、5%和10%的比率引入了堿基的均勻的隨機置換,以模擬一類測序錯誤和在實際樣品中的準時突變的存在。對于每個基因組,長度和置換率,取100個子序列或讀段的隨機樣品并且該采樣重復十次。
結果
對于每一種細菌基因組,采取了100個隨機模擬讀段,并使用我們的方法,在參考中,針對于包括那些細菌基因組的數據庫對它們評分,記錄該查詢基因組在25個最佳得分列表中的排名。平均排名和排名的標準差如圖4所示。
平均排名越接近1,評分越好,而排名的標準差越小,對采樣影響越不敏感。寫入每個單個面板的丟失的排名數,對應于沒有在25個最高得分的基因組數量。
讀段在長度為50個堿基時性能低于最佳,但在100個堿基的讀段時已經有顯著的改善,所查詢基因組在97%和99%的時間具有低置換率,在前5位具有較低置換率而在前15位時具有更高的置換率。讀段長度增加至250 個堿基有助于補償更高置換率對平均排名的負面影響。
使用的長度范圍和置換率與從新一代測序平臺,例如lllumina(100個堿基,具有約0.1-1%的錯誤率),Life Technologies的SOLiD 5500(75nt讀段,具有0.01%的錯誤率),Ion Torrent PGM(200-300個堿基,具有1%的錯誤率),或Pacific Bioscience(3,000個堿基,具有15%的錯誤率)獲得的范圍是可比的。我們的方法在這些范圍內執行良好,并且我們預期因增加對雙末端測序(一種用于提供替代較長讀段的技術)的支持而實現了性能進一步提高。我們的方法似乎對于測序錯誤(例如堿基置換)相對不敏感,并且對于我們的測試查詢的預期較低的排名隨置換率增加而使影響最小。
得益于NoSQL數據庫的使用,隨著基因組數據越來越豐富,預計規模會擴大,并且不斷能夠在比較實惠的電腦系統上索引和查詢越來越大的參考集合。
為了便于使用我們的方法,開發了一種基于瀏覽器的客戶端。我們用高達2GB的原始FASTQ文件測試,并監控到其在RAM中只用了稍微超過200MB并在20秒內返回結果。
結論
基于TAPIR的概念相當簡單。已經宣布了DNA數據庫規模的增長,并至少觀察了十多年,但最近在DNA測序技術的發展使得快速且經濟實惠的數據生成成為現實。我們主張對所有已知的DNA的匹配實驗獲得的DNA序列是生物信息學中最重要的挑戰之一。我們在這里表明,這可以用與互聯網網絡搜索巨頭已經讓公眾使用相匹配的速度和易用性完成。當考慮用桌面DNA測序儀進行諸如實時監控、患者感染、生物防御或食品安全的任務時,我們的方法提供了一種立即早期步驟,在此期間搜索空間可以縮小并且此后可以執行更先進的分析方法。
實施例2
在本實施例中,參考了來自細菌、病毒、噬菌體、質粒、以及人類、小鼠、植物、真菌和古細菌的數以萬計的基因組和基因組區域。還實施了在Web瀏覽器上運行的客戶端,并且證明采用該客戶端在幾秒鐘內處理并識別來自商品化便攜式計算裝置的千兆字節的原始測序數據,同時消耗適度量的帶寬與服務器通信。因此,在本實施例中,示出了來自原始讀段的DNA的識別可以與查詢搜索引擎一樣簡單。
查詢DNA序列針對參考的全面集合的匹配集
查找比對程序的主觀方式是將它們分成兩個主要類別:一類試圖針對已知參考的集合映射一個查詢序列(如BLAST),和一類試圖盡可能快地映射針對一種指定參考的大量短序列(例如,Bowtie或BWA)。我們提出了一個可對大量短序列識別很好的參考的折衷辦法;我們匹配了針對于參考序列的集合的若干序列并且選出了哪些參考在查詢集中得到最好的體現。
在本實施例中提出的方法不涉及在索引k-mer期間的任何選擇步驟,該功能從序列的集合構建時極大地簡化了復雜性。這以空間為代價而得到,有潛在的較少信息的k-mer被索引,但是這通過以下好處得到彌補:該過程對于參考集合的總大小是線性的,并且可以平行進行。這使得索引所有已知的DNA最終似是可信的(類似于在互聯網上的所有文件的網絡搜索引擎的索引。)
在這個例子中,我們的算法并不僅僅是計數k-mer,并且它不執行完整的映射或比對。該算法考慮了在每個讀段內的匹配k-mer,以及彼此接近的匹配k-mer的簇。
在本實施例中,使用非重疊的k-mer進行索引,同時在查詢中使用重疊的k-mer,如圖5所示,但我們認為這是一個實施細節并且可以很容易地使用重疊的k-mer進行索引和在查詢中的不重疊的k-mer同時對給定分數保持相同的指導原則以匹配參考。
如果將樹或哈希用于k索引和查找,那么在使用k-mer索引的大小為u 的參考中確定長度為p的串n次出現的位置的時間復雜度為O(p+n log u)或O(p+n)復雜度。
當為了診斷目的要識別DNA數據的查詢集,如來自測序儀的原始讀段時,我們認為包括針對于全面的參考數據庫映射所有讀段的蠻力方法有兩個主要的缺點:成百兆或千兆字節的數據的大部分或者從測序設施傳送到計算中心,并且執行該任務必須的計算資源是至關重要的。假設一個參考集合包含10,000大腸桿菌規模的細菌并且需要30秒優化比對器,如BWA和bowtie2來處理250Mb的原始測序數據(如果基因組是4Mb大小,平均覆蓋為約60x),盡管這可以在多個CPU上并行進行處理,但是這樣的CPU處理會花費3天半。
除了時間復雜度,數據傳輸將是250Mbases的DNA,將測序數據傳送到存放有參考的數據中心。我們基于k-mer的方法減少了對小的參考集的詳細的調查,如映射讀段或SNP判讀,甚至基于模板的從頭組裝。當評估性能時,隨意選擇,如果正確的答案是在5個建議的匹配集中,那么最初只是考慮搜索成功。針對那些參考映射所有讀段的以準確識別哪個是最佳匹配這項任務可以在12分鐘內在相同的CPU上完成,或者如果在規定的3天半的時間內獲得了強大的多核體系結構,那么任務可以在更短時間內完成。傳輸全部的基因組將代表約20 Mbases的DNA,它可以很容易地通過3G移動互聯網連接來完成。我們的方法使得移動測序設施,如Ion總線[15]能夠在現場的偏遠位置執行關鍵的診斷和科學任務。如果有未映射的讀段,因為存在較小的區域,如質粒、毒力基因、病毒或細菌的混合物,這些讀段可以被類似地處理,并且全部內容通過幾次迭代來識別。
建立基準
為了基準化該原本設計為識別測序數據中的細菌的系統,反復取得在2012年可從EBI獲得的細菌的所有序列,也就是747個細菌基因組。除了這些以外,所含的所有的參考數據庫為:來自NCBI的細菌參考、噬菌體和病毒、質粒以及人類基因組(見下文表1)。表1示出在2012年開始的基因組 參考(參考的來源和數目)的快照。參考是完整基因組或質粒的混合物,和諸如重疊群或基因的基因組片段的混合物。
表1.基因組參考
數據庫參考數大小(DNA堿基)HIV405336471153噬菌體基因組(Sanger)107859538128病毒基因組(Sanger)346464859892細菌基因組(Sanger)7472418028337細菌基因(NCBI)52180774963568551細菌基因組(NCBI)46932418028337病毒基因組(NCBI)175060637755真菌202270298736207人類微生物組16537001490442185質粒159705132800479病毒(Virii)7863065110952智人(Hg19)31342844000504小鼠(Mus musculus)3052745142291植物(RefSeq)5582678622349159無脊椎動物(Genbank)112381318429666992原生動物(Genbank)472751997449553真菌(Genbank)200242402709
對于每種基因組,從基因組序列產生隨機可能的重疊子序列,以模擬從DNA測序儀獲得的讀段;使用長度為50、100、150、200和250個堿基的子序列。還以0%(沒有錯誤)、1%、5%和10%的比率引入了均勻的堿基隨機置換,以便模擬一類測序錯誤和實際樣品中的準時突變的存在。對于每種基因組、長度和置換率,執行100個子序列或讀段的隨機樣品,并且采樣重復5次。
目的是評估當考慮到諸如測序錯誤或突變的不確定性時,在樣品或足夠接近的基因組中是否可以找到有哪種已知的DNA。
預測性能
對每個細菌基因組,采取100個隨機模擬的讀段,并使用我們的方法,針對包括那些細菌基因組的數據庫,從其他細菌、噬菌體、植物、真菌、病毒和哺乳動物序列和基因組的較大集合中,對它們評分,記錄查詢基因組中25個最佳匹配的參考列表中的排名。為了評估對每種測試細菌基因組的結果的變異性,這對每個基因組重復5次并且平均排名和對該排名的標準偏差如圖9所示。
讀段在長度為50個核苷酸時性能相對較差,但讀段長度增加時觀察到了顯著提高,在測序堿基中的長度為100的讀段已經接近最大性能。最好的結果是示出了正確的基因組在97%的時間是在低錯誤率的結果列表中,在前5位具有較低置換率,并且在前15位具有較高置換率。增加讀段長度達250個堿基幫助補償錯誤率增加帶來的負面影響。增加被發送用于識別的隨機樣品中的讀段數并沒有產生太大的影響,參見圖7中的隨機樣品中:100個讀段是少量的數據,但它在大量情形下似乎足以識別DNA。
如前面所詳述,我們的方法旨在返回在提出的匹配集中的正確參考并且通過如此做,簡化了粗苯的方法需要利用計算指令程序來探索的搜索空間。將我們限制為在前五個結果中找到查詢序列很可能比需要的還要嚴格,因為運行所有25個分析相比于窮舉搜索仍將是至關重要的,但是指出該方法已經能夠返回在非常小的候選答案集中的正確答案。
在迭代搜索和識別的情況下,可以考慮指出正確的細菌物種,即使不是正確的精確株或基因組參考,已經是比較成功的答案。圖6示出了以超過個核苷酸的讀段進行的識別過程執行得很好。
使用的長度范圍和置換率與從新一代測序平臺,例如lllumina(150個堿基,具有約0.1-1%的錯誤率),Life Technologies的SOLiD 5500(最大75nt讀段,具有0.01%的錯誤率),Ion Torrent PGM(最大200-300個堿基,具有 1%的錯誤率),或Pacific Bioscience(3,000個堿基,具有15%的錯誤率)獲得的范圍是可比的。我們的方法在這些范圍內執行良好,并且我們預期因增加對雙末端測序(一種用于提供替代較長讀段的技術)的支持而實現了性能進一步提高。我們的方法似乎對于測序錯誤(例如堿基置換)相對不敏感,并且對于我們的測試查詢的預期較低的排名隨置換率增加而使影響最小。
我們也嘗試基于來自Ion Torrent PGM的、從病毒和細菌分離株到宏基因組學混合物的范圍的測序數據的方法。索引的參考的集合中的非常相似的基因組,如幾株同一物種,通過增加密切相關的基因組比正確參考的基因組有更低的排名的概率可以有助于性能的劣化。這是通過考慮物種增加的性能而不是精確的參考所確認的,并且這是中度不便的,即可以在第二迭代期間消除歧義。最后,因為我們已經考慮讀段范圍內的k-mer,而不是孤立的實體,我們從來自不同哺乳動物的樣品測序獲得了非常令人鼓舞的結果,并預測能夠在不久的將來可靠地識別它們。
計算性能
服務器:
在服務器上的存儲器使用量可以保持最低限度使用基于磁盤的鍵值存儲和調優的性能可以通過這些緩存到存儲器中運行可在計算機上實現。由于使用的NoSQL數據庫,我們也期望能規模達的基因組數據得到越來越豐富,并不斷能夠引用索引和查詢越來越大集合比較實惠的電腦系統上。與當前的實現既索引系統和服務器在Python中實現,在使用8芯(英特爾至強,2.93GHz的)幾個小時來執行的參照DNA 44Gbases的索引,和一個輸入樣品的處理以幾秒鐘。甲顯著加速可與優化的努力來實現,例如移動到C的瓶頸,但它也可以由專更多內核增加的更多的請求的處理全球演出,在需要變得顯而易見。
客戶:
為了方便使用我們的方法,開發了使用JavaScript和HTML5特征的基于瀏覽器的客戶端,其可以在http://tapir.cbs.dtu.dk訪問。該客戶端目前正在最 新的Firefox版本(版本15或更高)上運行。
隨著具有在主頻為2.53GHz的Intel Core i5CPU的相對普通的筆記本電腦上Firefox,可在30秒內處理大小高達2Gb的FASTQ文件的原始讀段,文件越小越快,使用在RAM中稍小于300Mb,并且與服務器通信幾秒。
還實施了基于控制臺的命令行工具來執行我們的算法和隨后的比對。該實施可獲自流行的軟件庫https://bitbucket.org/lgautier/dnasnout-client。該實施使用我們的算法以抓取參考基因組,并用bowtie2進行所有讀段的索引和映射。當考慮前10個讀段時,完整的迭代花費不到一分鐘并且在98%的情況下一次迭代就足夠了。隨著瀏覽器的快速發展,預計很快就能僅使用網絡瀏覽器開展與流行病學實驗室用臺式測序所作相似的工作流程。
討論
我們主張針對所有已知的DNA匹配實驗獲得的DNA序列是生物信息學中最重要的挑戰之一。我們在這里表明,這可以用與互聯網網絡搜索巨頭已經使公眾習慣相匹配的速度和易用性來完成。當考慮諸如實時監控,患者感染、生物防御或食品安全的任務時,今天的桌面DNA測序如Ion Torrent PGM或lllumina MiSeq已經不能勝任此任務并且我們的方法提供了一種立即早期步驟,在此期間搜索空間可以縮小而且可以事后在本地執行更先進的分析方法,而不需要在執行DNA測序的實驗室和計算設施之間傳輸大量的原始數據。
方法
基因組參考的來源:
下載公眾可獲得的基因組、重疊群、質粒和可從EBI和NCBI獲得的個體基因作為參考DNA。參考的確切組成將隨著時間擴大,但在表1中列出了用于本實施例的快照。
參考索引:
每個參考序列被分成不重疊的k-mer并且對于所有參考的所有k-mer,創建鍵值對存儲或NoSQL的數據庫(使用KyotoCabinet[4]),關聯每個k-mer(在數據庫中的密鑰),對應于具有該k-mer的參考的標識符列表。稱這為存在數據庫。同樣地,在該參考中發現該k-mer的位置被存儲在稱作位置數據庫的地方。k被選擇為等于16,因為它給出了滿意的結果,并且作為4的倍數很好地適用于位包裝。參考標識符和信息,如描述行和數據源之間的關聯,儲存在單獨的SQL數據庫。
評分:
為了對短查詢序列或讀段集評分,對它們的隨機樣品迭代。樣品大小越大,可靠的準確性越大。對于每個序列,對在通過在序列上滑動寬度k的窗口所獲得的連續k-mer迭代。對于每個k-mer,如果它之前并未被計數并且在存在數據庫中發現它,那么將查詢參考的位置。一旦對讀段的所有k-mer進行處理,查找在參考中匹配的連續位置的數目并且只考慮最大匹配簇,即,在所有匹配參考中源自相同讀段的匹配k-mer的最大集中度。對于每個這樣的簇,將k-mer數加上可能之前用于該參考的加數并且更新已經計數的k-mer列表。然后處理下一個序列或讀段。當處理了所有讀段后,獲得與發現匹配的k-mer計數相關聯的參考列表。對于每對<參考,計數>,計數除以查詢集中獨一無二的k-mer的數量,提供了在給定參考匹配的被查詢子集中DNA量的粗略得分。利用示出的評分原則,如果查詢集完全匹配該序列,那么得分將是1,否則會降低;例如,如果查詢集是兩個參考的等比例混合物,那么對兩個參考的得分都將是0.5左右。該計數也可以除以參考的大小,得到由該查詢表示的參考部分的粗略得分;該第二得分有助于對匹配參考進行分選,并避免偏向最大參考。最終的得分被計算為這兩個得分的加權和,其中使用相等的加權。如果查詢集很大,例如,如果考慮來自一輪DNA測序的所有讀段,那么僅使用該集的隨機樣品。
客戶端的實施:
為了方便使用該服務,實施在Web瀏覽器的頁面運行的HTML5/JavaScript客戶端。對于目前的研究,使用Firefox 15版本,并且測試它在 Linux、Mac OS X、微軟Windows(各種筆記本和臺式機)以及在Android 4.0(平板ASUS TF101-預計它也將在高端智能手機上工作)的運行。然而,本領域技術人員將理解,其他合適的瀏覽器也可以是有用的。該客戶端也被實施為Python庫和命令行工具以便于在現有的工作流程和管線中評估和整合。
其它技術規格:
除了結合到諸如KyotoCabinet庫以外的所有實施是在服務器端利用Python版本2.7.3進行。網絡應用是使用微框架Flask并由lighttp服務。為Python版本3.3開發客戶端庫和命令行工具。
本領域技術人員將理解,算法或部分算法的實施可以由其它合適的和一般公知的編程語言來實現,例如C編程語言,其可以通過降低用于查詢的時間,提高該方法的性能。
參考文獻
[1]Stephen F.Altschul,Warren Gish,Webb Miller,Eugene W.Myers,and David J.Lipman.Basic local alignment search tool.Journal of Molecular Biology,215(3):403-410,October 1990.
[2]Damien Devos and Alfonso Valencia.Practical limits of function prediction.Proteins:Structure,Function,and Genetics,41(1):98-107,October 2000.
[3]R.C.Edgar.MUSCLE:multiple sequence alignment with high accuracy and high throughput.Nucleic Acids Research,32(5):1792-1797,March 2004.
[4]Mikio Hirabayashi.Kyoto cabinet:a straightforward implementation of DBM.
http://fallabs.com/kyotocabinet/
[5]W.J.Kent.BLAT—The BLAST-Like alignment tool.Genome Research,12(4):656-664,March 2002.
[6]Ben Langmead,Cole Trapnell,Mihai Pop,and Steven L Salzberg.Ultrafast and memory-efficient alignment of short DNA sequences to the human  genome.Genome Biology,10(3):R25,2009.
[7]H.Li and R.Durbin.Fast and accurate short read alignment with burrows-wheeler transform.Bioinformatics,25(14):1754-1760,May 2009.
[8]Christopher E Mason and Olivier Elemento.Faster sequencers,larger datasets,new challenges.Genome Biology,13(3):314,2012.
[9]Z.Ning.SSAHA:a fast search method for large DNA databases.Genome Research,11(10):1725-1729,October 2001.
[10]Zemin Ning,W.Spooner,A.Spargo,S.Leonard,M.Rae,and A.Cox.The SSAHA trace server,pages 519-520.IEEE.
[11]Burkhard Rost.Enzyme function less conserved than anticipated.Journal of Molecular Biology,318(2):595-608,April 2002.
[12]Nicole Rusk.Cheap third-generation sequencing.Nature Methods,6(4):244-244,April 2009.
[13]Jay Shendure and Hanlee Ji.Next-generation DNA sequencing.Nature Biotechnology,26(10):1135-1145,October 2008.
[14]T.F.Smith and M.S.Waterman.Identification of common molecular subsequences.Journal of Molecular Biology,147(1):195-197,March 1981.
[16].Rumble SM,Lacroute P,Dalca AV,Fiume M,Sidow A,et al.(2009)SHRiMP:accurate mapping of short color-space reads.PLoS Computational Biology 5:e1000386.
[17].Li H,Homer N(2010)A survey of sequence alignment algorithms for next-generation sequencing.Briefings in Bioinformatics 11:473-483.
[18].Babraham bioinformatics-FastQ screen.
http://www.bioinformatics.babraham.ac.uk/projects/fastq screen/.URL
http://www.bioinformatics.babraham.ac.uk/projects/fastq_screen/.

關 鍵 詞:
數據庫 驅動 原始 序數 初步 分析
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:數據庫驅動的原始測序數據的初步分析.pdf
鏈接地址:http://www.wwszu.club/p-6373731.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大