用於下一代測序的序列重組方法及裝置製造方法
2023-04-30 01:29:21 3
用於下一代測序的序列重組方法及裝置製造方法
【專利摘要】本發明涉及一種用於下一代測序(NGS)的序列重組方法及裝置。在本發明的一優選實施例中是將序列長度為n的短序列六等分之後只將前3個片段利用為種子，並檢索以參考序列為基礎生成的哈希表而檢索映射候選位置。
【專利說明】用於下一代測序的序列重組方法及裝置
【技術領域】
[0001]本發明涉及一種用於完成生物個體的整個遺傳序列的測序領域，具體而言涉及一種為用於NGS(Next Generation Sequencing,下一代測序)而重組短序列的標引和檢索技術。
【背景技術】
[0002]DNA鹼 基序列信息的解讀即基因組測序(genome sequencing)的核心為掌握個人差異以及民族特性，或者是探明與基因異常有關的疾患中包含染色體異常在內的先天性原因以及尋找糖尿病、高血壓之類複合疾病的基因缺陷。
[0003]並且,序列數據(Sequencing Data)可將基因表達、基因多樣性、遺傳性變異、遺傳性疾病原因及其相互作用等信息廣泛地應用於分子診斷及治療領域，因此非常重要。
[0004]在遺傳研究中傳統使用的用於生產長序列的桑格(Sanger)測序方法正在被實驗過程中所需的時間或費用及其應用性方面優良的用於生產短序列的NGS(Next GenerationSequencing,下一代測序)技術迅速地取代。而且還開發出著眼於準確率的多種NGS序列重組程序。
[0005]近來由於NGS費用相比以往的HGP降低為1/1，520, 000左右，因此可以使用為短序列的數據的量增加。作為用於處理大量數據的方法已開發出S0AP2之類的方法，然而對於S0AP2而言，存在著針對特定長度時雖能表現出較快的速度卻無法保證品質的問題。因此，對於保證短小的大容量短序列的品質的同時又能快速處理的方案的需求正在高漲。
【發明內容】
[0006]技術問題
[0007]本發明用於解決以上技術問題，其目的在於提供一種在保證從序列中獲取的短小的短序列的品質的同時進行重組而生成一個完整的鹼基序列的標引技術方法和搜索技術方法。
[0008]技術方案
[0009]作為本發明的一種優選實施例，用於下一代測序(NGS)的序列重組方法包括如下步驟:將序列長度為η的短序列六等分；針對參考序列以η/6大小的子序列(sub-string)單位生成哈希值而構成哈希表；在將所述短序列六等分的片段中，將位於所述短序列的前部的3個片段分別利用為種子；計算所述3個種子的哈希值；從所述哈希表中檢索與所述3個種子的哈希值一致的哈希值而檢索映射候選位置。
[0010]作為本發明的另一種優選實施例，包括:分割部，將序列長度為η的短序列六等分；種子生成部，將六等分所述短序列的片段當中位於所述短序列前部的3個片段分別使用為種子；哈希值生成部，計算所述3個種子的哈希值；哈希表生成部，針對參考序列以η/6大小的子序列(sub-string)單位生成哈希值而構成哈希表；檢索部，從所述哈希表中檢索與所述3個種子的哈希值一致的哈希值而檢索映射候選位置。[0011]有益效果
[0012]本發明在將從序列中獲得的短小的短序列進行重組而製作一個鹼基序列時，具有保證品質的同時改善速度的效果。
[0013]通過本發明所公開的用於下一代測序(NGS)的序列重組方法及裝置，可以縮短從驗血到完成整個基因組序列的時間，且在診斷疾病時能夠快速地分析基因組，從而可以縮短解明遺傳性疾病原因的時間。
【專利附圖】
【附圖說明】
[0014]圖1表示重組序列數據而完成基因組序列的流程圖。
[0015]圖2表示基因組分析方案的一般構成圖。
[0016]圖3表不現有的MAQ的標引方法的一實施例。
[0017]圖4表示在本發明的一優選實施例中以基因組參考序列為基礎而生成哈希表的示例。
[0018]圖5為本發明的一優選實施例，其表示用於下一代測序的序列重組方法。
[0019]圖6為本發明的一優選實施例，其表示用於下一代測序的序列重組裝置的構成圖。
[0020]最優實施方式
[0021]用於下一代測序(NGS)的序列重組裝置包括:分割部，將序列長度為η的短序列六等分；種子生成部，將六等分所述短序列的片段當中位於所述短序列前部的3個片段分別使用為種子；哈希值生成部，計算所述3個種子的哈希值；哈希表生成部，針對參考序列以η/6大小的子序列(sub-string)單位生成哈希值而構成哈希表；檢索部,從所述哈希表中檢索與所述3個種子的哈希值一致的哈希值而檢索映射候選位置。
【具體實施方式】
[0022]以下，參照附圖詳細說明本發明的實施例。需要注意的是在附圖中同一構成要素雖然可能出現於其他圖中，然而已儘量用同一附圖標記及符號進行了表示。
[0023]下面在對本發明進行說明時，如果認為對相關公知功能或構成部分的具體說明可能使本發明的主旨不清楚，則省略其詳細說明。
[0024]而且，為了進一步忠實於本發明，需要提醒在不脫離本發明主旨的範圍內可存在本領域技術人員層次的變更或變形。
[0025]圖1表示重組序列數據而完成基因組序列的流程圖。
[0026]製作關於基因組參考序列的索引(SllO)。為了製作索弓丨，在本發明的優選實施例中，針對基因組參考序列以η/6大小的子序列(sub-string)單位生成哈希值而構成哈希表。在此，η表示輸入的序列數據100的長度。針對基因組參考序列以η/6大小的子序列(sub-string)單位生成哈希值的例將參考圖4。
[0027]在本發明的一種優選實施例中，序列數據100表示作為IOObp長度以內的A、G、C、
T所構成的字符串的序列集合。
[0028]然後，將序列數據100六等分之後將六等分的片段當中位於序列數據100的前部的3個片段利用為種子，並針對3個種子(Seed)生成哈希值。如果生成了種子的哈希值，則在哈希表內檢索匹配的哈希值而檢索候選映射的位置(SllO)。生成哈希值的方法以及生成哈希表的實施例將參考圖4。
[0029]如果檢索出候選映射的位置，便將序列數據100與參考序列的對應位置排列為沒有空隙(gap)並測定相似度(S120)。針對檢索到的所有候選映射的位置執行此項作業之後將相似度最高的位置選擇為最優位置(S130)。然後尋找成對的兩個序列的序列對，並執行錯誤檢查以及位置校正而完成基因組序列(S140、S150)。
[0030]圖2表示基因組分析方案的一般構成圖。
[0031]基因組分析方案是所有生物/醫療信息學(Bio/Medical informatics)的所有研究以及執行中所必要的過程，被應用於得知生物個體的整個遺傳序列的測序領域、分析遺傳性變異(Variation)之間的關係的領域、解明遺傳性疾病原因的遺傳序列的醫療領域、解明生命現象原因的遺傳序列的醫療領域、以及解明特定化學物質起反應的蛋白質和遺傳序列的醫療領域。 [0032]在本發明的一種優選實施例中，在相當於基因組分析方案的前處理過程的映射步驟(210)和配對步驟(220)中將現有的MAQ的標引(indexing)方法改善而利用。
[0033]現有的MAQ(Mapping and Assembly with Quality,高品質映射與配位)為不僅可以利用基因組分析儀(Genome Analyzer)而且還可以處理SOLiD短序列的工具(Tools),其以短序列單位執行了映射。而且，在映射時使用6個種子，並將2個種子配對而執行了映射。
[0034]圖3表不現有的MAQ的標引方法的一實施例。
[0035]參考圖3，如果現有的MAQ中允許k個失配(Mismatch)，則MAQ將各短序列分為k個以上的短片段(fragment)。例如，如果對於長度為28的短序列允許2個失配，則分為4 Ok = 2)個短片段之後將種子兩兩組合而生成組合種子(Combination Seed)，並以此為基礎而對每一個短片段生成6個哈希值來製作哈希表。依次掃描參考序列而哪怕只是從6個種子中發現一個就將計算準確的排列分數而確定是否映射。
[0036]然而在本發明中可以利用MAQ而以種子單位執行映射，並且可以將使用的種子個數減少為3個，從而與現有的MAQ方法相比至少可以縮短50%以上的時間。
[0037]在現有的MAQ中為了種子的組合而使用規格化圖案，並使用6個非連續(Non-continuous)種子,從而造成速度緩慢。然而作為本發明中公開的一種實施例,其使用3個種子，且各種子被獨立使用，從而可以實現並行處理(Parallel Processing)，且速度得到提聞。
[0038]圖4表不在本發明的一優選實施例中以基因組參考序列為基礎生成哈希表的不例。
[0039]當輸入序列長度為η的短序列時，可如圖4所示地生成基因組參考序列的哈希表。使長度為η/6的窗口(window) 410從參考序列的起始位置開始以一個序列為單位朝右側方向移動而生成由ACGACG、CGACGT、GACGTC…之類的子序列(sub-string)構成的種子序列欄位420。然後生成關於各子序列的哈希值欄位430，並生成包含記錄有各種子序列的起始位置的起始位置欄位440的哈希表。
[0040]在本發明的一種優選實施例中，哈希值生成為對應於種子序列欄位420內的各子序列的一個值。生成哈希值的方法是將鹼基序列A、C、G、T分別置換成2比特(bit)的二進位數00、01、10、11而變換。例如，CGACGT被變換為二進位數011000011011的哈希值。[0041 ] 對於CGACGT子序列而言，哈希表內的哈希值欄位為011000011011，而起始位置欄位中生成 82 (411)、88 (412)...(450)。
[0042]圖5為本發明的一優選實施例，其表示用於下一代測序(NextGenerationSequencing, NGS)的序列重組方法。
[0043]將序列長度為η的短序列510六等分。將六等分的片段中的前三個片段利用為種子(520)。在本發明的一種優選實施例中，之所以只將位於短序列510的前部的3個片段利用為種子，是因為短序列是在一個序列內越往後走準確率越低，而越是處於前方的鹼基序列準確率就越高。
[0044]針對如此生成的3個種子分別存儲起始位置(偏移(Offset)) (530)。在本發明的一優選實施例中，種子的起始位置是以短序列510的起始位置為基準而設定，且第一個種子(種子I)的位置被存儲為0，第二個種子(種子2)的位置被存儲為n/6，而第三個種子(種子3)的位置被存儲為2n/6。
[0045]另外，針對生成的3個種子生成哈希值。然後，在如圖4的一實施例所示的哈希表內，在0(1)的檢索時 間之內尋找具有與各種子相同的序列的映射候選位置。
[0046]如果利用本發明的一優選實施例中揭示的以上方式執行檢索，則由於只對3個種子執行檢索，因此與現有的方式相比可以使檢索時間縮短到一半以下。
[0047]如果檢索到映射候選位置，則在各映射候選位置上利用史密斯-沃特曼(Smith-Waterman)算法而將輸入的整個短序列與參考序列的對應位置進行排列而測定相似度。在檢索到的所有映射候選位置上測定相似度之後，將相似度最高的位置分配為最優位置而進行配置。
[0048]圖6為本發明的一優選實施例，其表示用於下一代測序的序列重組裝置的構成圖。
[0049]用於下一代測序(NGS)的序列重組裝置600包括分割部610、種子生成部620、哈希值生成部630、哈希表生成部640、以及檢索部。
[0050]分割部610將序列長度為η的短序列六等分。在本發明的一優選實施例中，在將短序列六等分的情況下可以確保品質的同時支持最優的速度。
[0051]對於將短序列五等分的情形與六等分的情形進行如下比較。
[0052](I)將短序列五等分的情形
[0053]在短序列的長度最大為IOObp的情況下，每一個種子所需的存儲空間為10位元組(bytes)；
[0054]種子序列:0位元組(逆變換為哈希值)；
[0055]哈希值:5位元組(4~20 個=2~ (8*5)個)；
[0056]起始位置:5位元組；
[0057]染色體#:1位元組(23個〈2~8)；
[0058]偏移(Offset):4 字節(2 億 4 千萬 <2~ (8*4))；
[0059]哈希表大小:10TB;
[0060]10 字節 *4~20 = 10*(2~30)*2~10 = 10GB*2~10 = IOTB ；
[0061]當把短序列五等分時，如上所述，需要IOTB以用於哈希表。[0062](2)將短序列六等分的情形
[0063]在短序列的長度最大為IOObp的情況下，每一個種子所需的存儲空間為9位元組(bytes)；
[0064]種子序列:0位元組(逆變換為哈希值)；
[0065]哈希值:4位元組(4'15 個=2' (8*4)個)；
[0066]起始位置:5位元組；
[0067]染色體#:1位元組(23個〈2~8)；
[0068]偏移(offset):4 字節(2 億 4 千萬 <2~ (8*4))；
[0069]哈希表大小:9Gbytes ；
[0070]9bytes*4~15 = 9*(2~30) = 9GB ；
[0071]當把短序列六等分時，如上所述，需要9GB以用於哈希表。
[0072]檢索部從哈希表中檢索與3個種子的哈希值一致的哈希值而檢索映射候選位置。哈希表包含由n/6大小的子序列構成的種子序列欄位、記錄有分別對應於各子序列的哈希值的哈希值欄位、以及記錄有子序列的起始位置的起始位置欄位。
[0073]本發明還可以 通過計算機可讀記錄介質中的計算機可讀代碼實現。計算機可讀記錄介質中包括用於存儲可被計算機系統讀取的數據的所有類型的記錄裝置。
[0074]計算機可讀記錄介質的例中有ROM、RAM、⑶-ROM、磁帶、軟盤、光數據存儲裝置等。並且，計算機可讀記錄介質可分散於通過網絡連接的計算機系統中，從而可以用分散方式存儲並執行計算機可讀代碼。
[0075]以上已在附圖和說明書中公開了最優實施例。在此雖然使用了特定的術語，然而這僅僅是為了說明本發明而使用的，而不是要用來限定含義或者限制權利要求書中記載的本發明的範圍。
[0076]因此，只要是本【技術領域】中具有普通知識的人員就會明白可以由此獲得多種變形例及其他等價實施例。所以本發明的真正的技術保護範圍應當是由權利要求書的技術思想來確定。
【權利要求】
1.一種用於下一代測序的序列重組方法，其特徵在於，包括如下步驟: 將序列長度為η的短序列六等分； 針對參考序列以η/6大小的子序列單位生成哈希值而構成哈希表； 在將所述短序列六等分的片段中，將位於所述短序列的前部的3個片段分別利用為種子; 計算所述3個種子的哈希值； 從所述哈希表中檢索與所述3個種子的哈希值一致的哈希值而檢索映射候選位置。
2.如權利要求1所述的用於下一代測序的序列重組方法，其特徵在於，所述3個種子的起始位置是以所述短序列的起始位置為基準而設定，且第一個種子的位置為O，第二個種子的位置為η/6,而第三個種子的位置為2η/6。
3.如權利要求1所述的用於下一代測序的序列重組方法，其特徵在於，所述哈希值是將鹼基序列A、G、C、T分別置換成二進位數00、01、10、11而生成的值。
4.如權利要求1所述的用於下一代測序的序列重組方法，其特徵在於，在進行所述檢索的步驟中，針對所述3個種子每一個的檢索時間為O (I)以內。
5.如權利要求1所述的用於下一代測序的序列重組方法，其特徵在於，在進行所述檢索的步驟中，對所述3個種子可同時並行檢索。
6.如權利要求1所述的用於下一代測序的序列重組方法，其特徵在於，所述哈希表包括: 種子序列欄位，由η/6大小的所述子序列構成； 哈希值欄位，記錄有分別對應於所述子序列的哈希值； 起始位置欄位，記錄有所述子序列的起始位置。
7.如權利要求1所述的用於下一代測序的序列重組方法，其特徵在於，還包括如下步驟: 在各映射候選位置上將輸入的整個短序列與參考序列的對應位置進行排列而測定相似度。
8.一種用於下一代測序的序列重組裝置，其特徵在於，包括: 分割部，將序列長度為η的短序列六等分； 種子生成部，將六等分所述短序列的片段當中位於所述短序列前部的3個片段分別使用為種子； 哈希值生成部，計算所述3個種子的哈希值； 哈希表生成部，針對參考序列以η/6大小的子序列單位生成哈希值而構成哈希表； 檢索部，從所述哈希表中檢索與所述3個種子的哈希值一致的哈希值而檢索映射候選位置。
9.如權利要求8所述的用於下一代測序的序列重組裝置，其特徵在於，所述3個種子的起始位置是以所述短序列的起始位置為基準而設定，且第一個種子的位置為O，第二個種子的位置為η/6,而第三個種子的位置為2η/6。
10.如權利要求8所述的用於下一代測序的序列重組裝置，其特徵在於，所述哈希值是將鹼基序列A、G、C、T分別置換成二進位數00、01、10、11而生成的值。
11.如權利要求8所述的用於下一代測序的序列重組裝置，其特徵在於，在進行所述檢索時，針對所述3個種子每一個的檢索時間為0(1)以內。
12.如權利要求8所述的用於下一代測序的序列重組裝置，其特徵在於，在進行所述檢索時，對所述3個種子可同時並行檢索。
13.如權利要求8所述的用於下一代測序的序列重組裝置，其特徵在於，所述哈希表包括: 種子序列欄位，由n/6大小的所述子序列構成； 哈希值欄位，記錄有分別對應於所述子序列的哈希值； 起始位置欄位，記錄有所述子序列的起始位置。
14.如權利要求8所述的用於下一代測序的序列重組裝置，其特徵在於，還在各映射候選位置上將輸入的整個短序列與參考序列的對應位置進行排列而測定相似度。
【文檔編號】C12Q1/68GK103946396SQ201280053889
【公開日】2014年7月23日 申請日期:2012年9月11日 優先權日:2011年10月31日
【發明者】樸旻胥, 金判奎 申請人:三星Sds株式會社