鹼基序列對準裝置及其方法
2023-05-03 21:08:34
鹼基序列對準裝置及其方法
【專利摘要】本發明公開一種鹼基序列對準裝置及其方法，用於從參考序列中尋找與作為短片段序列的一部分的基準片段一致的基準位置，並以基準位置為基準而將參考序列與所述短片段序列相互映射。據此，可實現允許短片段序列中可能存在的所有變異和誤差的對準，並能夠在短片段序列的整個區域中尋找變異和誤差，而且，與現有技術中的鹼基序列對準技術不同而不允許反向跟蹤(back?tracking)，且可以用更少的計算量執行對準。
【專利說明】鹼基序列對準裝置及其方法
【技術領域】
[0001]本發明涉及一種鹼基序列對準裝置及其方法，尤其涉及一種可實現允許短片段序列中可能存在的所有變異和誤差的對準，並能夠在短片段序列的整個區域中尋找變異和誤差，還能夠在不允許反向跟蹤(back tracking)的條件下用更少的計算量執行對準的鹼基序列對準裝置及其方法。
【背景技術】
[0002]鹼基序列對準技術為整個生物學領域中最為廣泛使用的技術之一。例如，可通過利用參考配位(Reference assembly)方法而將短片段序列映射於已知的參考序列的過程而完成針對各對象(individual)的基因組序列，進而可以分析各對象之間的鹼基序列差異(variation)。目前1，OOOgenome pro ject之類的大型測序項目正在執行,如果這種發展持續下去，則最終有望實現個人基因組分析以及基於遺傳信息的量身型醫療系統等服務。
【發明內容】
[0003]技術問題
[0004]根據本發明概念的一個以上的示例性實施例，提供一種可實現允許短片段序列中可能存在的所有變異和誤差的對準，且可以在短片段序列的整個區域中尋找變異和誤差的鹼基序列對準裝置及其方法和 記錄有程序的記錄介質。
[0005]並且，根據本發明概念的一個以上的示例性實施例，提供一種與現有技術中的鹼基序列對準技術不同而不允許反向跟蹤(back tracking)並能夠用更少的計算量執行對準的鹼基序列對準裝置及其方法和記錄有程序的記錄介質。
[0006]技術方案
[0007]根據本發明概念的一個以上的示例性實施例，提供一種鹼基序列對準方法，用於將短片段序列對準於參考序列，包括如下步驟:基準位置選擇步驟，在參考序列上找出與作為短片段序列的一部分的基準片段一致的位置；以所述基準位置為基準而將所述參考序列與所述短片段序列相互映射。
[0008]基準片段可從短片段序列的任意位置開始而由預定長度的序列構成。
[0009]基準片段的預定長度可基於在所述參考序列中出現所述基準片段的平均頻率值而確定。
[0010]平均頻率值可根據所述參考序列的長度和鹼基序列的數量而確定。
[0011]基準位置選擇步驟可以是從所述參考序列中與基準片段完全一致的位置、以及在所述參考序列中在已設定的誤差允許值E範圍內使基準片段與參考序列一致的位置中選擇至少一種位置的步驟。
[0012]基準位置選擇步驟可包括如下步驟中的至少一個步驟:在所述參考序列中找出一個以上的與基準片段完全一致的位置；在已設定的誤差允許值E範圍內針對構成所述基準片段的序列進行插入、刪除和/或置換之後找出一個以上的與所述參考序列一致的位置。[0013]以基準位置為基準而將所述參考序列與所述短片段序列相互映射的步驟可以是將所述短片段序列中的基準片段之後的殘餘序列與所述參考序列中的所述基準位置之後的序列進行映射的步驟。
[0014]本鹼基序列對準方法還可以包括如下步驟:判斷在已設定的誤差允許值E範圍內，針對構成所述短片段序列中除了基準片段以外的殘餘序列的序列進行了插入、刪除和/或置換的序列與所述參考序列是否一致。
[0015]所述誤差允許值E可以是針對所述基準序列而設定的誤差允許值。
[0016]當基準位置之後的參考序列與所述短片段序列中基準片段之後的殘餘序列存在不相一致的部分時，可將始於在已設定的誤差允許值E範圍內進行跳躍的位置的參考序列與所述基準片段之後的殘餘序列進行映射。
[0017]本序列對準方法還可以包括如下步驟:當所述基準片段與所述參考序列一致時，將所述基準片段作為映射片段進行存儲；當所述基準片段之後的殘餘序列中具有在已設定的誤差允許值E內與所述基準位置之後的參考序列一致的部分時，將該一致的部分作為映射片段進行存儲。
[0018]本鹼基序列對準方法還可以包括在映射片段滿足數學式Dr(M1, M2)-De(M1, M2) <E-E0時予以相互連接的步驟，其中，M1, M2為需要相互連接的映射片
段，DJM1, M2)為短片段序列上的映射片段M1J2之間的距離,DJM1, M2)為參考序列上的映射片段W、M2之間的距離，E是對短片段序列允許的誤差允許值，E0為包含於映射片段中的誤差值的總和，IDr(M11M2)-D li(MDM2)I是對Dr (M1, M2)與Dk(M1, M2)的距離差的絕對值。
[0019]根據本發明概念的另一示例性實施例，提供一種記錄有用於在計算機上執行根據權利要求1~12中的任意一項的方法的程序的計算機可讀介質。
[0020]根據本發明概念的另一示例性實施例，可包括:基準位置選擇單元，在參考序列中找出與作為短片段序列的一部分的基準片段一致的位置；映射單元，以所述基準位置為基準而將所述參考序列與所述短片段序列相互映射；對準單元，當以所述基準位置為基準而使所述參考序列與所述短片段序列相互一致時，將所述短片段序列對準於所述基準位置。
[0021]基準位置選擇單元可從所述參考序列中與基準片段完全一致的位置、以及在所述參考序列中在已設定的誤差允許值E範圍內使基準片段與參考序列一致的位置中選擇至少一種位置。
[0022]映射單元可將所述短片段序列中的基準片段之後的殘餘序列與所述參考序列中的所述基準位置之後的序列進行映射，或者可將所述短片段序列中的基準片段前後的殘餘序列與所述參考序列中的基準位置前後的序列進行映射。
[0023]誤差允許值E可以是針對所述基準序列而定的誤差允許值。
[0024]映射單元還可以判斷所述基準位置之後的參考序列與所述短片段序列中的基準片段之後的殘餘序列是否相互一致，且可以在所述基準位置之後的參考序列與所述短片段序列中基準片段之後的殘餘序列存在不相一致的部分時，將始於在已設定的誤差允許值E範圍內進行跳躍的位置的參考序列與所述基準片段之後的殘餘序列進行映射。
[0025]本鹼基序列對準裝置還可以包括存儲單元，且所述映射單元可在所述基準片段與所述參考序列一致時，將所述基準片段作為映射片段存儲於所述存儲單元，而在所述基準片段之後的殘餘序列中具有在已設定的誤差允許值E內與所述基準位置之後的參考序列一致的部分時，可將該一致的部分作為映射片段存儲於所述存儲單元。
[0026]對準單元在所述映射片段滿足數學式IDr(MnM2)-Dli(MDM2) <E-E0時予以相互連接，其中，M1J2S需要相互連接的映射片段，DJM1, M2)為短片段序列上的映射片段M1J2之間的距離，De(M1, M2)為參考序列上的映射片段MpM2之間的距離，E是對短片段序列允許的誤差允許值，Etl為包含於映射片段中的誤差值的總和，Dr (M1, M2)-De(M1, M2) |是對Dr (M1, M2)與DJM1, M2)的距離差的絕對值。
[0027]有益效果
[0028]根據本發明概念的一個以上的示例性實施例，可實現允許短片段序列中可能存在的所有變異和誤差的對準，並能夠在短片段序列的整個區域中尋找變異和誤差。
[0029]而且，根據本發明概念的一個以上的示例性實施例，與現有技術中的鹼基序列對準技術不同，其不允許反向跟蹤(back tracking)，且能夠用更少的計算量執行對準，因此對準速度可以加快。
【專利附圖】
【附圖說明】
[0030]圖1為用於說明記錄有用於執行根據本發明概念的示例性實施例的鹼基序列對準方法的程序的計算機可讀記錄介質的圖，。
[0031]圖2為根據本發明 概念的示例性實施例的鹼基序列對準裝置的構成圖，
[0032]圖3為用於說明根據本發明概念的示例性實施例的鹼基序列對準方法的流程圖，以及
[0033]圖4和圖5是為了說明根據本發明概念的示例性實施例的基準片段映射方法而提供的圖。
[0034]符號說明:
[0035]10:測序儀100、200:鹼基序列對準裝置
[0036]201:基準位置選擇單元 203:映射單元
[0037]205:對準單元207:存儲單元
【具體實施方式】
[0038]通過附圖和相關的以下優選實施例而使以上的本發明的目的、其他目的、特徵以及優點容易被理解。然而本發明並不局限於在此說明的實施例而也可以具體化為其他形態。在此介紹的實施例只是為了能夠徹底而完全地公開內容，並為了將本發明的思想充分地傳遞給本領域技術人員而提供的。在本說明書中，所謂的某一構成要素在另一構成要素上，表示該構成要素可以直接形成於另一構成要素上，或者它們之間也可以夾設有第三個構成要素。
[0039]並且，所謂的某一元素(或構成要素)在另一元素(或構成要素)上(ON)操作或執行，應當理解為該元素(或構成要素)在另一元素(或構成要素)操作或執行的環境中操作或執行，或者通過與其他元素(或構成要素)的直接或間接的相互作用而操作或執行。
[0040]所謂的某一元素、構成要素、裝置或系統包括由程序或軟體構成的構成要素，即使沒有明確的說明也應當理解為該元素、構成要素、裝置或系統包括該程序或軟體的執行或操作所需的硬體(例如，存儲器、CPU等)或者其他程序或軟體(例如，驅動作業系統或硬體所需的驅動器等)。
[0041]而且，在實現某一元素(或構成要素)時如果沒有特別說明，則應當理解為該元素(或構成要素)可以由軟體、硬體、或者軟體和硬體中的任何形態實現。
[0042]在本說明書中使用的術語是用於說明實施例，而不是用於限定本發明。在本說明書中，只要沒有在文中特別說明，則單數型也包括複數型。在說明書中使用的「包括(comprises) 」和/或「包含(comprising)的」並不排除所述的構成要素中存在或者還有一個以上其他構成要素的可能。
[0043]以下，參照附圖詳細說明本發明。在對以下的特定實施例進行敘述時，各種特定內容是為了有助於更加具體地說明本發明和理解本發明而編入的。然而具備足以理解本發明的程度的本領域知識的人員應當能夠明白即使沒有這些多種特定內容也可以使用本發明。在有些情況下，在記載本發明時對公知的與本發明沒有太大關係的部分則為了防止對說明本發明帶來不必要的混亂而不予記載。
[0044]圖1為用於說明記錄有用於執行根據本發明概念的示例性實施例的鹼基序列對準方法的程序的計算機可讀記錄介質的圖。
[0045]參照圖1，鹼基序列對準裝置100包括記錄有用於執行根據本發明概念的示例性實施例的鹼基序列對準方法的程序的計算機可讀記錄介質110。另外，出於為了說明本發明概念的目的，額外圖示了測序儀10。
[0046]測序儀10從樣品中生成短片段序列(Read Sequence)，鹼基序列對準裝置100將測序儀10所生成的短片段序 列映射於已知的參考序列(Reference Sequence)而進行對準。
[0047]包含記錄有用於執行根據本實施例的鹼基序列對準方法的程序的計算機可讀記錄介質110的喊基序列對準裝置100 (以下稱為喊基序列裝置100)不僅執行基於喊基序列的同源性(homology)的精確匹配(exact matching),而且還可以執行允許與誤差允許值(E) 一樣多的不匹配的非精確匹配。
[0048]根據本實施例的鹼基序列對準裝置100針對短片段序列的一部分區間(以下稱為「基準片段」)考慮可能組合的所有變異(刪除、置換或者增加)而在參考序列中檢索可映射的所有位置並確定為基準位置。在此，鹼基序列對準裝置100可使用現有技術中公知的映射方法(例如，利用BWT和Suffix排列的方法)而檢索與基準片段相一致的位置。
[0049]根據本發明概念的示例性實施例，基準片段的起始位置可確定為短片段序列的第一個位置。與此不同，基準片段的起始位置可以確定為短片段序列的第二個位置。還可以不同地，基準片段的起始位置可以確定為短片段序列的第三個位置。又可以不同地，基準片段的起始位置可以確定為從短片段序列的第一個位置到短片段序列長度的50%處的位置中的任意位置。其中，基準片段的位置是在確定為從短片段序列的第一個序列開始的預定長度的區間時準確率較高，然而要知道本發明概念並不僅僅局限於這樣的位置。
[0050]參照圖4說明，基準片段的位置選定為從短片段序列的第一位開始，且示例性地圖示出三處(M1、M2、M3)與基準片段精確匹配或者在誤差允許值以內非精確匹配的基準位置。
[0051]鹼基序列對準裝置100以基準位置為基準而將短片段序列的殘餘序列與參考序列進行比較。例如，鹼基序列對準裝置100將緊跟基準位置Ml之後的參考序列Rl與短片段序列的殘餘序列相互映射，並將緊跟基準位置M2之後的參考序列R2與短片段序列的殘餘序列相互映射，並將緊跟基準位置R3之後的參考序列R3與短片段序列的殘餘序列相互映射。
[0052]另外，如果基準片段不是從短片段序列的第一個位置開始選擇而是從接下來的位置中的某一位置開始選擇，則殘餘序列將位於基準片段的前後。在這種情況下，鹼基序列對準裝置100不僅將緊跟基準位置之後的參考序列與殘餘序列進行映射，而且還會將基準位置之前的參考序列與殘餘序列進行映射。
[0053]鹼基序列對準裝置100在執行短片段序列的殘餘序列與基準位置Ml、M2、M3的參考序列之間的映射操作的過程中如果不能進行匹配(例如，無法完成誤差允許值以內的非精確匹配的情況)，則可以跳躍預定距離之後繼續執行映射。在此，跳躍距離可以成為對短片段序列給定的最大誤差允許值E以下的值。例如，如果將已經選定的基準位置的誤差允許值之和記為「k」，則所述跳躍距離可以是(E-k)以下。
[0054]或者(alternatively)，鹼基序列對準裝置100在執行短片段序列的殘餘序列與基準位置的參考序列之間的映射操作的過程中如果不能進行匹配，則並不直接跳躍，而是只有在先前映射的結果滿足最小匹配距離的情況下才跳躍。參照圖5說明，假設鹼基序列對準裝置100將短片段序列的殘餘序列與參考序列Rl進行映射，當鹼基序列對準裝置100在判斷為參考序列位置E上不能進行匹配的情況下，只有在先前映射的區域SI的長度大於最小匹配距離時才會跳躍位置E而繼續執行映射操作。如果區域SI的長度小於最小匹配距離，則鹼基序列對準裝置100將Rl區域從短片段序列的對準位置中除外。
[0055]鹼基序列對準裝置100在短片段序列的殘餘序列與基準位置Ml之間映射的結果如果有最小匹配長度mS以上的一致，便將該一致部分作為映射片段進行存儲(在圖5中S1、S2、S3可以成為映射片段，而基準位置的序列也可以成為映射片段)。
[0056]如果一直到短片段序列末尾，映射片段全部得到存儲，則鹼基序列對準裝置100嘗試存儲的映射片段的連接。例如，鹼基序列對準裝置100將映射片段在短片段序列與參考序列上的位置信息、作為參數值而接收的最大誤差允許值作為基準而判斷映射片段的連接與否。
[0057]例如，鹼基序列對準裝置100在滿足如下數學式I的情況下連接映射片段。
[0058][數學式I]
[0059]I Dr (M1, M2) -De (M1, M2) | <E_E0
[0060]其中，MpM2為需要相互連接的映射片段；
[0061]Dr(M11M2)為短片段序列上的映射片段Mp M2之間的距離；
[0062]De(M1, M2)為參考序列上的映射片段Mp M2之間的距離；
[0063]E是對短片段序列允許的誤差允許值；
[0064]Etl為包含於映射片段中的誤差值的總和；
[0065]I Dr (M1, M2) -De(M1, M2) | 是對 Dr (M1, M2)與 De (M1, M2)的距離差的絕對值。
[0066]鹼基序列對準裝置100對映射片段的可連接的組合應用現有技術中公知的技術手段(例如，內德勒曼-文施(Needleman-Wunsch)算法)或將來會被發現的技術手段而將映射片段之間予以連接。
[0067] 另外，基準片段的長度可基於基準片段出現於參考序列的平均頻率值而確定，其中，平均頻率值可根據參考序列的長度和鹼基序列(即A、G、C、T)的數量而確定。而且，映射片段的最小匹配長度也可以確定為等於基準片段的長度。
[0068]雖然沒有圖示，然而本鹼基序列對準裝置100可以額外地包括用於執行根據本發明概念的示例性實施例的鹼基序列對準方法的程序運行所需的H/W和S/W資源。例如，作為硬體資源可以舉出CPU (Central Processing Unit)、存儲器(MEMORY)、硬碟、網卡等,作為軟體資源可以舉出作業系統(OS:0perating System)、用於驅動硬體的驅動器(driver)。例如，基準位置的選擇或映射操作的執行等是在CPU的控制下被加載於存儲器而進行操作。似此，為了執行存儲於記錄介質210的程序，需要硬體資源和/或軟體資源，關於這些資源與存儲於記錄介質210中的程序之間的相互作用，只要是本發明概念所屬的【技術領域】的人員就會輕易地理解。
[0069]圖2為根據本發明概念的示例性實施例的鹼基序列對準裝置的構成圖。
[0070]參照圖2，本鹼基序列對準裝置200包括:基準位置選擇單元201、映射單元203、對準單元205、以及存儲單元207。在圖2中，為了說明的目的而額外圖示了測序儀10。
[0071]鹼基序列對準裝置200的基準位置選擇單元201、映射單元203、對準單元205、以及存儲單元207可相互有機地操作而執行與圖1中說明的鹼基序列對準裝置100相同或類似的操作。只要是本發明概念所屬【技術領域】的人員就能夠將基準位置選擇單元201、映射單元203、以及對準單元205通過軟體和/或硬體來實現。
[0072]測序儀10從樣品中生成短片段序列(Read Sequence)，鹼基序列對準裝置200將測序儀10所生成的短片段序列映射於已知的參考序列(Reference Sequence)而進行對準。
[0073]基準位置選擇單元201針對基準片段考慮可能組合的所有變異(刪除、置換、或者增加)而在參考序列中檢索可映射的所有位置並確定為基準位置。
[0074]如上所述，基準片段的位置是在確定為從短片段序列的第一個序列開始的預定長度的區間時準確率較高，然而本發明概念並不僅僅局限於這樣的位置。並且，與在圖1的實施例中說明的一樣，基準片段的長度可基於基準片段出現於參考序列的平均頻率值而確定，其中，平均頻率值可根據參考序列的長度和鹼基序列(即A、G、C、T)的數量而確定。
[0075]映射單元203以基準位置作為基準而將短片段序列的殘餘序列與參考序列進行映射。參照圖4的示例進行說明，映射單元203將緊跟基準位置Ml之後的參考序列Rl與短片段序列的殘餘序列相互映射，並將緊跟基準位置M2之後的參考序列R2與短片段序列的殘餘序列相互映射，並將緊跟基準位置R3之後的參考序列R3與短片段序列的殘餘序列相互映射。
[0076]映射單元203在執行短片段序列的殘餘序列與基準位置Ml、M2、M3的參考序列之間的映射操作的過程中如果不能進行匹配(例如，無法完成誤差允許值以內的非精確匹配的情況)，則可以跳躍預定距離之後繼續執行映射。在此，跳躍距離可以成為對短片段序列給定的最大誤差允許值E以下的值。例如，如果將已經選定的基準位置的誤差允許值之和記為「k」，則所述跳躍距離可以是(E-k)以下。
[0077]或者(alternatively)，映射單元203在執行短片段序列的殘餘序列與基準位置的參考序列之間的映射操作的過程中如果不能進行匹配，則並不直接跳躍，而是只有在先前映射的結果滿足最小匹配距離的情況下才跳躍。參照圖5說明，假設將短片段序列的殘餘序列與參考序列Rl進行映射，則映射單元203在判斷為參考序列位置E上不能進行匹配的情況下，只有在先前映射的區域SI的長度大於最小匹配距離時才會跳躍位置E而繼續執行映射操作。如果區域SI的長度小於最小匹配距離，則映射單元103對Rl區域不再執行映射操作。
[0078]映射單元203在短片段序列的殘餘序列與基準位置Ml之間映射的結果如果有最小匹配長度mS以上的一致，便將該一致部分作為映射片段存儲於存儲單元207(在圖5中S1、S2、S3可以成為映射片段，而基準位置的序列也可以成為映射片段)。
[0079]如果一直到短片段序列末尾，映射片段全部得到存儲，則對準單元205將存儲的映射片段予以連接。例如，對準單元205將映射片段在短片段序列與參考序列上的位置信息、作為參數值而接收的最大誤差允許值作為基準而判斷映射片段的連接與否。
[0080]例如，對準單元205可在滿足上述數學式I的情況下連接映射片段，且對映射片段的可連接的組合可應用現有技術中公知的技術手段(例如，內德勒曼-文施(Needleman-Wunsch)算法)或將來會被發現的技術手段而將映射片段之間予以連接。
[0081]圖3為用於說明根據本發明概念的示例性實施例的鹼基序列對準方法的流程圖。
[0082]參照圖3，鹼基序列對準裝置100或200從由測序儀10生成的短片段序列中選擇基準片段(SlOl)。
[0083]關於基準片段的位置，雖然短片段序列的第一個位置的準確率較高，然而沒有必要非要局限於第一個位置。而且，關於基準片段的長度雖然也是基於基準片段出現於參考序列的平均頻率值進行確定會進一步提高鹼基序列的對準速度，然而也沒有必要非要局限於此。
[0084]鹼基序列對準裝置100或200將在步驟SlOl中選擇的基準片段與參考序列進行映射(S103)，並選擇精確匹配或者在誤差允許值以內匹配的基準位置(S105)。
[0085]鹼基序列對準裝置100或200以步驟S105中選擇的基準位置作為基準而將短片段序列的殘餘序列與參考序列進行映射(S107)。
[0086]在步驟S107中，鹼基序列對準裝置100或200在無法映射的情況下，可在最大誤差允許值以內跳躍。
[0087]鹼基序列對準裝置100或200連接滿足上述數學式I的映射片段(S109)。在S109中，鹼基序列對準裝置100或200可使用現有技術中公知的技術手段或將來會開發出的技術手段而填充映射片段的空白空間。
[0088]如上所述的根據本發明概念的鹼基序列裝置及方法可利用於SNP(SingleNucleotide Polymorphism,單核苷酸多態性)、MNP (Multiple Nucleotide Polymorphism,多核苷酸多態性)、結構多樣性(Structural variations)、CNV (Copy Number Variation,拷貝數變異)等的探索，並可以跨越轉錄組(transcriptome)分析、用於開發新藥物的蛋白質結合位點(binding site)掌握等整個生物學領域而得到應用。
[0089]雖然已通過有限的實施例和【專利附圖】
【附圖說明】了如上所述的本發明概念，然而本發明概念並不局限於所述的實施例，只要是本發明概念所屬的領域中具有普通知識的人員就能夠通過這樣的記載實現多種多樣的修改和變形。因此，本發明概念的範圍不應局限於所述的實施例而確定，而是要根據權利要求書及其等價內容來確定。
【權利要求】
1.一種鹼基序列對準方法，用於將短片段序列對準於參考序列，包括如下步驟: 基準位置選擇步驟，在參考序列上找出與作為短片段序列的一部分的基準片段一致的位置； 以所述基準位置為基準而將所述參考序列與所述短片段序列相互映射。
2.如權利要求1所述的鹼基序列對準方法，其特徵在於，所述基準片段從短片段序列的任意位置開始而由預定長度的序列構成。
3.如權利要求1所述的鹼基序列對準方法，其特徵在於，所述基準片段的預定長度為基於在所述參考序列中出現所述基準片段的平均頻率值而確定。
4.如權利要求3所述的鹼基序列對準方法，其特徵在於，所述平均頻率值為根據所述參考序列的長度和鹼基序列的數量而確定。
5.如權利要求1所述的鹼基序列對準方法，其特徵在於，所述基準位置選擇步驟為從所述參考序列中與基準片段完全一致的位置、以及在所述參考序列中在已設定的誤差允許值E範圍內使基準片段與參考序列一致的位置中選擇至少一種位置的步驟。
6.如權利要求1所述的鹼基序列對準方法，其特徵在於，所述基準位置選擇步驟包括如下步驟中的至少一個步驟: 在所述參考序列中找出一個以上的與基準片段完全一致的位置； 在已設定的誤差允許值E範圍內針對構成所述基準片段的序列進行插入、刪除和/或置換之後找出一個以上的與所述參考序列一致的位置。
7.如權利要求6所述的鹼基序列對準方法，其特徵在於，以所述基準位置為基準而將所述參考序列與所述短片段序列相互映射的步驟為將所述短片段序列中的基準片段之後的殘餘序列與所述參考序列中的所述基準位置之後的序列進行映射的步驟。
8.如權利要求7所述的鹼基序列對準方法，其特徵在於，還包括如下步驟: 判斷在已設定的誤差允許值E範圍內，針對構成所述短片段序列中除了基準片段以外的殘餘序列的序列進行了插入、刪除和/或置換的序列與所述參考序列是否一致。
9.如權利要求8所述的鹼基序列對準方法，其特徵在於，所述誤差允許值E為針對所述基準序列而設定的誤差允許值。
10.如權利要求9所述的鹼基序列對準方法，其特徵在於，當所述基準位置之後的參考序列與所述短片段序列中基準片段之後的殘餘序列存在不相一致的部分時，將始於在已設定的誤差允許值E範圍內進行跳躍的位置的參考序列與所述基準片段之後的殘餘序列進行映射。
11.如權利要求9所述的鹼基序列對準方法，其特徵在於，還包括如下步驟: 當所述基準片段與所述參考序列一致時，將所述基準片段作為映射片段進行存儲； 當所述基準片段之後的殘餘序列中具有在已設定的誤差允許值E內與所述基準位置之後的參考序列一致的部分時，將該一致的部分作為映射片段進行存儲。
12.如權利要求11所述的鹼基序列對準方法，其特徵在於，還包括當所述映射片段滿足數學式IW(MpM2)-Dk(MpM2) <E-E0時予以相互連接的步驟，其中，MpM2為需要相互連接的映射片段，Dr(M11M2)為短片段序列 上的映射片段Μ」 M2之間的距離，Dk(MdM2)為參考序列上的映射片段札、M2之間的距離，E是對短片段序列允許的誤差允許值，E0為包含於映射片段中的誤差值的總和，Dr(M1, M2)-De(M1, M2) I是對Dr (M1, M2)與Dk(M1, M2)的距離差的絕對值。
13.—種記錄有用於在計算機上執行根據權利要求1~12中的任意一項的方法的程序的計算機可讀介質。
14.一種鹼基序列對準裝置，用於將短片段序列對準於參考序列，包括: 基準位置選擇單元，在參考序列中找出與作為短片段序列的一部分的基準片段一致的位置； 映射單元，以所述基準位置為基準而將所述參考序列與所述短片段序列相互映射； 對準單元，當以所述基準位置為基準而使所述參考序列與所述短片段序列相互一致時，將所述短片段序列對準於所述基準位置。
15.如權利要求14所述的鹼基序列對準裝置，其特徵在於，所述基準片段從短片段序列的任意位置開始而由預定長度的序列構成。
16.如權利要求14所述的鹼基序列對準裝置，其特徵在於，所述基準片段的預定長度為基於在所述參考序列中出現所述基準片段的平均頻率值而確定，而所述平均頻率值為根據所述參考序列的長度和鹼基序列的數量而確定。
17.如權利要求14所述的鹼基序列對準裝置，其特徵在於，所述基準位置選擇單元從所述參考序列中與基準片段完全一致的位置、以及在所述參考序列中在已設定的誤差允許值E範圍內使基準片段與參考序列一致的位置中選擇至少一種位置。
18.如權利要求14所述的鹼基序列對準裝置，其特徵在於，所述映射單元將所述短片段序列中的基準片段之後的殘餘序列與所述參考序列中的所述基準位置之後的序列進行映射，或者將所述短片段序列中的基準片段前後的殘餘序列與所述參考序列中的基準位置前後的序列進行映射。
19.如權利要求17所述的鹼基序列對準裝置，其特徵在於，所述誤差允許值E為針對所述基準序列而設定的誤差允許值。
20.如權利要求19所述的鹼基序列對準裝置，其特徵在於，所述映射單元還判斷所述基準位置之後的參考序列與所述短片段序列中的基準片段之後的殘餘序列是否相互一致，且在所述基準位置之後的參考序列與所述短片段序列中基準片段之後的殘餘序列存在不相一致的部分時，將始於在已設定的誤差允許值E範圍內進行跳躍的位置的參考序列與所述基準片段之後的殘餘序列進行映射。
21.如權利要求14所述的鹼基序列對準裝置，其特徵在於，還包括存儲單元，且所述映射單元在所述基準片段與所述參考序列一致時，將所述基準片段作為映射片段存儲於所述存儲單元，而在所述基準片段之後的殘餘序列中具有在已設定的誤差允許值E內與所述基準位置之後的參考序列一致的部分時，將該一致的部分作為映射片段存儲於所述存儲單J Li ο
22.如權利要求21所述的鹼基序列對準裝置，其特徵在於，所述對準單元在所述映射片段滿足數學式IW(MdM2)-Dk(MpM2) <E-E0時予以相互連接，其中，MpM2為需要相互連接的映射片段，Dr(M11M2)為短片段序列上的映射片段Μ」 M2之間的距離，Dk(MdM2)為參考序列上的映射片段札、M2之間的距離，E是對短片段序列允許的誤差允許值，E0為包含於映射片段中的誤差值的總和，Dr(M1, M2)-De(M1, M2) I是對Dr (M1, M2)與Dk(M1, M2)的距離差的絕對值。
【文檔編號】C12Q1/68GK103930569SQ201280055343
【公開日】2014年7月16日 申請日期:2012年11月23日 優先權日:2011年11月30日
【發明者】樸旻壻, 呂潤九, 樸商賢 申請人:三星Sds株式會社, 延世大學校產學協力團