[發明專利]一種短序列映射方法及系統

無效

• 申請號: 200810218337.4
• 申請日: 2008-12-12
• 公開（公告）號: CN101430741A
• 公開（公告）日: 2009-05-13
• 發明（設計）人: 阮玨;朱紅梅;李瑞強;王俊;楊煥明;汪建
• 申請（專利權）人: 深圳華大基因研究院
• 主分類號: G06F19/00
• 分類號: G06F19/00;C12Q1/68
• 代理公司: 深圳中一專利商標事務所
• 代理人: 張全文

技術領域

本發明屬于基因工程技術領域，尤其涉及一種短序列映射方法及系統。

背景技術

對大基因組的短序列進行組裝面臨內存的挑戰，為了降低構建de?Bruijn圖的內存使用，組裝軟件可以不在內存中記錄測序序列和序列片段重疊群(contig)之間的對應關系，而只在contig組裝完畢后，將正確的測序序列映射到contig上?，F有的短序列比對軟件分兩類，一類使用了固定短串的組合索引結構，另一類使用的是后綴樹類樣的索引結構?，F有短序列對比軟件可以在兩個錯配之內將短序列映射到contig上，但是由于這些比對軟件的出發點不是contig和參與拼接的序列之間的比對，特別是沒有考慮使用de?Bruijn圖組裝出的contig的特點，在這種情況下，其處理時間長、效率低。

綜上所述，現有短序列對比軟件在處理contig和短序列之間的比對時，處理時間長、效率低，不能很好地滿足短序列組裝中的需求。

發明內容

本發明實施例的目的在于提供一種短序列映射方法，旨在解決現有短序列對比軟件在處理contig和短序列之間的比對時，處理時間長、效率低，不能很好地滿足短序列組裝中需求的問題。

本發明實施例是這樣實現的，一種短序列映射方法，所述方法包括下述步驟：

將測序序列按預設長度前綴短串的堿基值排序；

將序列片段重疊群逐個堿基切割成所述預設長度的短串；

依次根據所述序列片段重疊群中所切割成的短串的堿基值在排序后的測序序列中查找相應的測序序列，建立映射關系。

本發明實施例的另一目的在于提供短序列映射系統，所述系統包括：

排序單元，用于將測序序列按預設長度前綴短串的堿基值排序；

切割單元，用于將序列片段重疊群逐個堿基切割成所述預設長度的短串；以及

映射單元，用于依次根據所述序列片段重疊群中所切割成的短串的堿基值在排序后的測序序列中查找相應的測序序列，建立映射關系。

在本發明實施例中，通過將測序序列按預設長度前綴短串的堿基值排序，并將contig逐個堿基切割成預設長度的短串，依次根據contig中所切割成的短串的堿基值在排序后的測序序列中查找相應的測序序列，建立映射關系，實現了用于短序列組裝中的一種短序列映射方法，處理時間短、效率高。

附圖說明

圖1是本發明實施例提供的短序列映射方法的實現流程圖；

圖2是本發明實施例提供的短序列映射系統的結構圖；

圖3是本發明另一實施例提供的短序列映射系統的結構圖。

具體實施方式

為了使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖及實施例，對本發明進行進一步詳細說明。應當理解，此處所描述的具體實施例僅僅用以解釋本發明，并不用于限定本發明。

在本發明實施例中，通過將測序序列按預設長度前綴短串的堿基值排序，并將contig逐個堿基切割成預設長度的短串，依次根據contig中所切割成的短串的堿基值在排序后的測序序列中查找相應的測序序列，建立映射關系。

圖1示出了本發明實施例提供的短序列映射方法的實現流程，詳述如下：

在步驟S101中，將測序序列按預設長度前綴短串的堿基值排序；

在步驟S102中，將contig逐個堿基切割成預設長度的短串；

在步驟S103中，依次根據contig中所切割成的短串的堿基值在排序后的測序序列中查找相應的測序序列，建立映射關系。

在本發明實施例中，短串長度的選取嚴格等于在構建de?Bruijn圖時短串的長度，即上述預設長度為構建de?Bruijn圖時短串的長度。將測序序列按前綴短串的堿基值排序，可以降低排序的復雜性。按預設長度切割各測序序列的前綴短串，并從小到大按短串的堿基值排序，生成一個短串數組，這個短串數組和各測序序列是一一對應的。建立一個索引數組用于記錄短串數組中短串與測序序列的對應關系。在對短串進行排序時，可以使用桶排序對短串的堿基值進行排序。其中，每個桶子存放短串上的4個堿基，這樣按4個堿基逐步完成排序。另外，在排序中使用另一個前綴數組記錄相鄰短串間共同的前綴堿基個數，對前綴堿基個數的記錄可以在桶排序內部完成。當然，也可以采用其他方法對短串的堿基值進行排序。

然后，由于構建de?Bruijn圖時短串是唯一的，所以按照構建de?Bruijn圖時短串的長度將contig逐個堿基切割成的各個短串是唯一的。

接著，依次根據contig中切割成的短串的堿基值建立contig與測序序列的映射關系，上述步驟S103具體為：