一種基因組短序列映射的快速處理方法及系統的製作方法
2023-10-17 12:56:09
專利名稱：一種基因組短序列映射的快速處理方法及系統的製作方法
技術領域：
本發明屬於基因工程技術領域，尤其涉及一種基因組短序列映射的快速處理方法
及系統。
背景技術：
對大基因組的短序列進行組裝面臨內存的挑戰，為了降低構建deBruijn圖的內 存使用，組裝軟體可以不在內存中記錄測序序列和序列片段重疊群(contig)之間的對應 關係，而只在contig組裝完畢後，將正確的測序序列映射到contig上。現有的短序列比對 多採用計算機軟體實現，主要分兩類，一類使用了固定短串(kmer)的組合索引結構，另一 類使用的是後綴樹類樣的索引結構。現有短序列對比軟體可以在兩個錯配之內將短序列映 射到contig上，但是在處理contig和短序列之間的比對時，處理時間長、效率低，不能很好 地滿足短序列組裝中的需求。
發明內容
本發明一個目的在於提供一種基因組短序列映射的快速處理方法和系統，旨在減 少contig和短序列之間的比對過程的處理時間、提高效率。 基於上述目的，本發明提供的一種基因組短序列的快速處理映射方法，所述方法 包括下述步驟 將測序序列按預設長度短串的鹼基值排序； 將序列片段重疊群逐個鹼基切割成所述預設長度的短串； 依次根據所述序列片段重疊群中所切割成的短串的鹼基值在排序後的測序序列 中查找相應的測序序列，建立映射關係。
基於上述目的，本發明提供的基因組短序列的快速處理映射系統，所述系統包括
排序單元，用於將測序序列按預設長度短串的鹼基值排序； 切割單元，用於將序列片段重疊群逐個鹼基切割成所述預設長度的短串；以及
映射單元，用於依次根據所述序列片段重疊群中所切割成的短串的鹼基值在排序 後的測序序列中查找相應的測序序列，建立映射關係。 在本發明實施例中，通過將測序序列按預設長度短串的鹼基值排序，並將contig 逐個鹼基切割成預設長度的短串，依次根據contig中所切割成的短串的鹼基值在排序後 的測序序列中查找相應的測序序列，建立映射關係，本發明技術方案從contig和參與拼接 的序列之間的比對出發，利用基於de Bruijn圖組裝出contig所具有的在定長的短串上不 存在重複的特點，實現了用於短序列組裝中的短序列映射，所需處理時間明顯縮短、效率大 幅提高。
圖1是本發明實施例提供的基因組短序列映射的快速處理方法的實現流程4
圖2是本發明實施例提供的基因組短序列映射的快速處理系統的結構圖；
圖3是本發明另一實施例提供的基因組短序列映射的快速處理系統的結構圖。
具體實施例方式
為了使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖及實施例，對 本發明進行進一步詳細說明。應當理解，此處所描述的具體實施例僅僅用以解釋本發明，並 不用於限定本發明。 在本發明實施例中，通過將測序序列按預設長度短串的鹼基值排序，並將contig 逐個鹼基切割成預設長度的短串，依次根據contig中所切割成的短串的鹼基值在排序後 的測序序列中查找相應的測序序列，建立映射關係。 圖1示出了本發明實施例提供的基因組短序列映射的快速處理方法的實現流程， 詳述如下 在步驟S101中，將測序序列按預設長度短串的鹼基值排序。 在本發明實施例中，短串長度的選取嚴格等於在構建de Bruijn圖時短串的長度， 即上述預設長度為構建de Bruijn圖時短串的長度。將測序序列按短串的鹼基值排序，可 以降低排序的複雜性。按預設長度切割各測序序列的短串，並從小到大按短串的鹼基值排 序，生成一個短串數組，這個短串數組和各測序序列是一一對應的。其中，所述按預設長度 切割各測序序列的短串的步驟可以採用如下方式在當前被切割的測序序列上滑動截取短 串，滑動的步長為l個鹼基，截取的窗口為所述預設長度，即構建de Bruiin圖時短串的長 度。 另外，本步驟中，優選可以建立一個索引數組，用於記錄短串數組中短串與contig 的對應關係。 在對短串進行排序時，可以使用桶排序方式對短串的鹼基值進行排序。其中，每個
桶子存放短串上的4個鹼基，這樣按4個鹼基逐步完成排序。另外，在排序中使用另 一個前
綴數組記錄相鄰短串間共有前綴的鹼基個數，對前綴鹼基個數的記錄可以在桶排序內部完
成。當然，也可以採用其他方法對短串的鹼基值進行排序。 在步驟S102中，將contig逐個鹼基切割成所述預設長度的短串。 在本發明實施例中，本步驟可採用如下方式提取contig保存在內存中，在
contig上滑動截取短串，滑動的步長為1個鹼基，截取的窗口為所述預設長度，即構建de
Bruijn圖時短串的長度。 由於構建de Bruijn圖時短串是唯一的，所以按照構建de Bruijn圖時短串的長 度將contig逐個鹼基切割成的各個短串是唯一的。 在步驟S103中，依次根據contig中所切割成的短串的鹼基值在排序後的測序序
列中查找相應的測序序列，建立contig與測序序列的映射關係。 上述步驟S103具體包括 步驟Sl.依次取contig切割得到的短串； 步驟S2.在排序後的測序序列中查找短串的鹼基值與contig中所取短串的鹼基 值相等的所有測序序列； 步驟S3.通過查詢所述索引數組，在步驟S2查找到的測序序列與contig間建立映射關係。 在本發明實施例中，步驟S3具體包括利用索引數組保存的短串數組中短串與 contig的對應關係，根據步驟S2中查找到的測序序列中的短串在所述索引數組中查詢對 應的contig，建立短串對應的測序序列與contig之間的映射關係。 在本發明實施例中，步驟S2中採用二分法在短串數組中查找與contig中所取短 串的鹼基值相等的短串，實現短串間的比較，算法詳述如下 初始化將起始位置L置為0，結束位置R設為N-l，最小共有前綴數1、最大共有 前綴數r都置為0 ; 步驟1.判斷contig中所取短串W是否小於短串數組的短串A[O]，如果是返回不 匹配的響應，否則進入步驟2 ; 步驟2.判斷contig中所取短串W是否大於短串數組的第N個短串A[N-1]，如果 是則返回不匹配的響應，否則進入步驟3 ; 步驟3.判斷L+l是否小於結束位置R，如果是則進入步驟4，否則進入步驟8 ; 步驟4.查找中間位置M取為~^^鹼基判斷位置m取最小共有前綴數1和最大
共有前綴數r 二者中的最小值；其中，m是L和R之間的最大共有前綴數。 步驟5.判斷短串W的第m個鹼基值Wm是否小於或等於查找中間位置短序的第m
個鹼基值A[M]m，如果是則進入步驟6，否則進入步驟7 ; 步驟6.結束位置R向前移動到查找中間位置M，用短串W與短序A[M]的共有前綴 數更新最大共有前綴數r，進入步驟3 ; 步驟7.起始位置L向後移動到查找中間位置M，用短串W與短序A[M]的共有前綴
數更新最大共有前綴數l，進入步驟3 ; 步驟8.將起始位置L賦值為結束位置R。 A[R]即為查找到的短串，結合已經建立的前綴數組，找出A[R]前後鹼基值均與其 相等的短串。再根據索引數組即可以得到這些短串對應的測序序列，進一步建立得到的這 些測序序列與contig的映射。當然，也可以根據其他查詢方法在短串數組中查找與contig 中所取短串的鹼基值相等的短串。 由於在生物學上，互補序列上的映射關係也是構成該contig的序列的正確關係， 為了同時得到contig的互補序列與測序序列的映射，作為本發明的一個優選實施例，在步 驟S101前進一步包括根據測序序列得到其互補測序序列的步驟。 此時，步驟S101改為將測序序列和得到的互補測序序列按預設長度短串的鹼基 值排序；步驟S103改為依次根據contig中所切割成的短串的鹼基值在排序後的測序序列 及其互補測序序列中查找相應的測序序列和/或互補測序序列，建立映射關係。將測序序 列及其互補測序序列按短串的鹼基值排序，實現contig與測序序列間的正、反相映射，減 少了比較搜索的次數，處理速度加快。 為了同時得到互補contig與測序序列的映射，作為本發明的另一個優選實施例， 在上述步驟S102之前進一步根據contig得到其互補contig。此時，步驟S102為將contig 和得到的互補contig逐個鹼基切割成預設長度的短串，步驟S103為依次根據contig和 得到的互補contig中所切割成的短串的鹼基值在排序後的測序序列中查找相應的測序序
6
對比上述通過對contig逐個鹼基在排序後的測序序列及其互補測序序列中查 找，實現contig與測序序列的正、反相映射的方式，這裡通過對contig及其互補contig逐 個鹼基執行兩次切割、查找操作實現。 本發明上面兩個優選實施例中所採取的這種正反向截取的方式，雖然使用了更多
的內存，但是測序序列查詢時，只查詢一個方向就可以找出雙向的比對結果，速度得到了提
高。如果截取單向的話，在查詢時需要將測序序列正方向都查詢，才能得到結果。 本領域普通技術人員可以理解，實現上述實施例方法中的全部或部分步驟是可以
通過程序來指令相關的硬體來完成，所述的程序可以在存儲於一計算機可讀取存儲介質
中，所述的存儲介質，如ROM/RAM、磁碟、光碟等，該程序用來執行如下步驟 1.將測序序列按預設長度短串的鹼基值排序； 2.將contig逐個鹼基切割成預設長度的短串； 3.依次根據contig中所切割成的短串的鹼基值在排序後的測序序列中查找相應 的測序序列，建立映射關係。 圖2示出了本發明實施例提供的基因組短序列映射的快速處理系統的結構，為了 便於說明僅示出了與本發明實施例相關的部分，該系統可以用於短序列組裝中，其中
排序單元201，用於將測序序列按預設長度短串的鹼基值排序，其實現方式可參見 上述步驟S101的內容，不再贅述。 切割單元202，用於將contig逐個鹼基切割成預設長度的短串，其實現方式可參 見上述步驟S102的內容，不再贅述。 映射單元203，依次根據contig中所切割成的短串的鹼基值在排序後的測序序列
中查找相應的測序序列，建立映射關係。 其中，映射單元203包括 短串獲取模塊2031，用於依次取contig切割得到的短串。 查找模塊2032，在排序後的測序序列中查找短串的鹼基值與短串獲取模塊2031
所取短串的鹼基值相等的所有測序序列，其實現方式參見上述步驟S2，不再贅述。 關聯模塊2033，在查找到的測序序列與contig間建立映射關係，其實現方式參見
上述步驟S3，不再贅述。 為了同時得到contig與測序序列的反相映射，作為本發明的一個優選實施例，短 序列映射系統還包括 第一互補計算單元204，根據測序序列得到其互補測序序列。 此時，排序單元201將測序序列和得到的互補測序序列按預設長度短串的鹼基值 排序，映射單元203依次根據contig中所切割成的短串的鹼基值在排序後的測序序列及其 互補測序序列中查找相應的測序序列和/或互補測序序列，在查找到的測序序列和/或互 補測序序列與所述序列片段重疊群間建立映射關係。即查找相應的測序序列，在查找到的 測序序列與所述contig間建立映射關係；或者查找相應的互補測序序列，在查找到的互補 測序序列與所述contig間建立映射關係；或者查找相應的測序序列，並查找相應的互補測 序序列，查找到的測序序列與所述contig間建立映射關係，並同時在查找到的互補測序序 列與所述contig間建立映射關係。
為了同時得到互補contig與測序序列的映射，作為本發明的另一個優選實施例， 如圖3所示，短序列映射系統還包括 第二互補計算單元205，根據contig得到其互補contig。 此時，切割單元202將contig和得到的互補contig逐個鹼基切割成預設長度的 短串，映射單元203依次根據contig和得到的互補contig中所切割成的短串的鹼基值在 排序後的測序序列中查找相應的測序序列，建立映射關係。 在本發明實施例中，通過將測序序列按預設長度短串的鹼基值排序，並將contig 逐個鹼基切割成預設長度的短串，依次根據contig中所切割成的短串的鹼基值在排序後 的測序序列中查找相應的測序序列，建立映射關係，實現了用於短序組裝中的一種短序列 映射方法，處理時間短、效率高。 以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發明的精 神和原則之內所作的任何修改、等同替換和改進等，均應包含在本發明的保護範圍之內。
權利要求
一種基因組短序列映射的快速處理方法，其特徵在於，所述方法包括下述步驟將測序序列按預設長度短串的鹼基值排序；將序列片段重疊群逐個鹼基切割成所述預設長度的短串；依次根據所述序列片段重疊群中所切割成的短串的鹼基值在排序後的測序序列中查找相應的測序序列，在查找到的測序序列與所述序列片段重疊群間建立映射關係。
2. 如權利要求l所述的方法，其特徵在於，所述預設長度為構建de Bruijn圖時短串的長度。
3. 如權利要求2所述的方法，其特徵在於，所述依次根據所述序列片段重疊群中所切 割成的短串的鹼基值在排序後的測序序列中查找相應的測序序列，在查找到的測序序列與 所述序列片段重疊群間建立映射關係的步驟具體為依次取所述序列片段重疊群切割得到的短串；在排序後的測序序列中查找短串的鹼基值與序列片段重疊群中所取短串的鹼基值相 等的所有測序序列；在查找到的測序序列與所述序列片段重疊群間建立映射關係。
4. 如權利要求3所述的方法，其特徵在於，採用二分法在所述排序後的測序序列中查 找短串的鹼基值與所述序列片段重疊群中所取短串的鹼基值相等的測序序列。
5. 如權利要求1所述的方法，其特徵在於，在所述將測序序列按預設長度短串的鹼基 值排序的步驟前，所述方法還包括根據所述測序序列得到其互補測序序列； 所述將測序序列按預設長度短串的鹼基值排序的步驟為 將測序序列和得到的互補測序序列按所述預設長度短串的鹼基值排序； 所述依次根據所述序列片段重疊群中所切割成的短串的鹼基值在排序後的測序序列中查找相應的測序序列，在查找到的測序序列與所述序列片段重疊群間建立映射關係的步驟為依次根據所述序列片段重疊群中所切割成的短串的鹼基值在排序後的測序序列及其 互補測序序列中查找相應的測序序列和/或互補測序序列，在查找到的測序序列和/或互 補測序序列與所述序列片段重疊群間建立映射關係。
6. 如權利要求1所述的方法，其特徵在於，在所述將序列片段重疊群逐個鹼基切割成 所述預設長度的短串的步驟前，所述方法還包括根據所述序列片段重疊群得到其互補序列片段重疊群； 所述將序列片段重疊群逐個鹼基切割成所述預設長度的短串的步驟為 將序列片段重疊群和得到的互補序列片段重疊群逐個鹼基切割成所述預設長度的短串；所述依次根據所述序列片段重疊群中所切割成的短串的鹼基值在排序後的測序序列 中查找相應的測序序列，建立映射關係的步驟為依次根據所述序列片段重疊群和得到的互補序列片段重疊群中所切割成的短串的鹼 基值在排序後的測序序列中查找相應的測序序列，在查找到的測序序列與所述序列片段重 疊群間建立映射關係。
7. 如權利要求1所述的方法，其特徵在於，所述將測序序列按預設長度短串的鹼基值排序步驟為使用桶排序方式對短串的鹼基值進行排序。
8. 如權利要求1所述的方法，其特徵在於，所述將測序序列按預設長度短串的鹼基值 排序過程中進一步包括建立一個索引數組，用於記錄短串數組中短串與所述序列片段重 疊群的對應關係；在查找到的測序序列與所述序列片段重疊群間建立映射關係的步驟包括通過查詢所 述索引數組，在查找到的測序序列與所述序列片段重疊群間建立映射關係。
9. 一種基因組短序列映射的快速處理系統，其特徵在於，所述系統包括 排序單元，用於將測序序列按預設長度短串的鹼基值排序；切割單元，用於將序列片段重疊群逐個鹼基切割成所述預設長度的短串；以及 映射單元，用於依次根據所述序列片段重疊群中所切割成的短串的鹼基值在排序後的測序序列中查找相應的測序序列，在查找到的測序序列與所述序列片段重疊群間建立映射關係。
10. 如權利要求9所述的系統，其特徵在於，所述映射單元包括 短串獲取模塊，用於依次取所述序列片段重疊群切割得到的短串；查找模塊，用於在排序後的測序序列中查找短串的鹼基值與所述短串獲取模塊所取短 串的鹼基值相等的所有測序序列；以及關聯模塊，用於在查找到的測序序列與所述序列片段重疊群間建立映射關係。
11. 如權利要求9所述的系統，其特徵在於，所述短序列映射系統還包括 第一互補計算單元，用於根據所述測序序列得到其互補測序序列； 所述排序單元具體是用於將測序序列和得到的互補測序序列按所述預設長度短串的鹼基值排序，所述映射單元具體是用於依次根據所述序列片段重疊群中所切割成的短串的 鹼基值在排序後的測序序列及其互補測序序列中查找相應的測序序列和/或互補測序序 列，在查找到的測序序列和/或互補測序序列與所述序列片段重疊群間建立映射關係。
12. 如權利要求9所述的系統，其特徵在於，所述短序列映射系統還包括 第二互補計算單元，用於根據所述序列片段重疊群得到其互補序列片段重疊群； 所述切割單元具體是用於將序列片段重疊群和得到的互補序列片段重疊群逐個鹼基切割成所述預設長度的短串，所述映射單元具體是用於依次根據所述序列片段重疊群和得 到的互補序列片段重疊群中所切割成的短串的鹼基值在排序後的測序序列中查找相應的 測序序列，在查找到的測序序列與所述序列片段重疊群間建立映射關係。
全文摘要
本發明適用於基因工程技術領域，提供了一種基因組短序列映射的快速處理方法及系統，所述方法包括下述步驟將測序序列按預設長度短串的鹼基值排序；將序列片段重疊群逐個鹼基切割成所述預設長度的短串；依次根據所述序列片段重疊群中所切割成的短串的鹼基值在排序後的測序序列中查找相應的測序序列，建立映射關係。在本發明中，通過將測序序列按預設長度短串的鹼基值排序，並將序列片段重疊群逐個鹼基切割成預設長度的短串，依次根據序列片段重疊群中所切割成的短串的鹼基值在排序後的測序序列中查找相應的測序序列，建立映射關係，實現了用於短序組裝中的一種短序列映射，處理時間短、效率高。
文檔編號C12Q1/68GK101751517SQ20091025246
公開日2010年6月23日 申請日期2009年12月11日 優先權日2009年12月11日
發明者朱紅梅, 李瑞強, 楊煥明, 汪建, 王俊 申請人:深圳華大基因研究院