《一種短序列組裝中構建圖的方法及系統》是深圳華大基因研究院於2008年12月12日申請的專利，該專利的申請號為2008102183389，公布號為CN101430742，授權公布日為2009年5月13日，發明人是李瑞強、阮珏、朱紅梅、李松崗、王俊、楊煥明、汪建。
《一種短序列組裝中構建圖的方法及系統》適用於基因工程技術領域，提供了一種短序列組裝中構建圖的方法及系統，所述方法包括下述步驟：接收測序序列；分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串，並得到所述短串的左、右連線關係；將得到的各所述短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點。在該發明中，通過分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串及短串的左、右連線關係，將得到的各短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點，實現了一種短序列組裝中構建圖的方法，能對大基因組進行組裝，占用記憶體小、速度快。
2016年12月7日，《一種短序列組裝中構建圖的方法及系統》獲得第十八屆中國專利優秀獎。
（概述圖為《一種短序列組裝中構建圖的方法及系統》摘要附圖）
基本介紹
- 中文名：一種短序列組裝中構建圖的方法及系統
- 公布號：CN101430742
- 授權日：2009年5月13日
- 申請號：2008102183389
- 申請日：2008年12月12日
- 申請人：深圳華大基因研究院
- 地址：廣東省深圳市鹽田區北山工業區綜合樓
- 發明人：李瑞強、阮珏、朱紅梅、李松崗、王俊、楊煥明、汪建
- Int.Cl.：G06F19/00(2006.01)I、C12Q1/68(2006.01)I
- 代理機構：深圳中一專利商標事務所
- 代理人：張全文
- 類別：發明專利
專利背景,發明內容,專利目的,技術方案,改善效果,附圖說明,技術領域,權利要求,實施方式,榮譽表彰,
專利背景
新測序技術產生的短序列有兩個特點：
1.序列長度短；
2.數據量大。
長序列組裝常用的phrap等軟體均基於序列間的交疊（overlap）來拼接，在短序列上的運算量太大，沒有實際套用價值。新興的短序列組裝軟體中成功處理短序列的，例如velvet等，基於de Bruijn圖。但是，由於受記憶體、時間等的限制，2008年12月前短序列組裝軟體只能組裝較小的原核生物基因組，對於大基因組，例如真核生物基因組，特別是哺乳動物基因組數據，均不能組裝。
發明內容
專利目的
《一種短序列組裝中構建圖的方法及系統》實施例的目的在於提供一種短序列組裝中構建圖的方法，旨在解決2008年12月前短序列組裝軟體不能組裝大基因組的問題。
技術方案
《一種短序列組裝中構建圖的方法及系統》實施例是這樣實現的，一種短序列組裝中構建圖的方法，所述方法包括下述步驟：
接收測序序列；分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串，並得到所述短串的左、右連線關係；將得到的各所述短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點。
《一種短序列組裝中構建圖的方法及系統》實施例的另一目的在於提供一種短序列組裝中構建圖的系統，所述系統包括：
接收單元，用於接收測序序列；序列切割單元，用於分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串，並得到所述短串的左、右連線關係；以及構圖單元，用於將得到的各所述短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點。
改善效果
在《一種短序列組裝中構建圖的方法及系統》實施例中，通過分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串，並得到短串的左、右連線關係，將得到的各短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點，實現了一種短序列組裝中構建圖的方法，能對大基因組進行組裝，占用記憶體小、速度快。
附圖說明
圖1是《一種短序列組裝中構建圖的方法及系統》實施例提供的短序列組裝中構建圖的方法的實現流程圖；
圖2是《一種短序列組裝中構建圖的方法及系統》實施例提供的節點存儲內容的示意圖；
圖3《一種短序列組裝中構建圖的方法及系統》實施例提供的短序列組裝中構建圖的系統的結構圖。
技術領域
《一種短序列組裝中構建圖的方法及系統》屬於基因工程技術領域，尤其涉及一種短序列組裝中構建圖的方法及系統。
權利要求
1、一種短序列組裝中構建圖的方法，其特徵在於，所述方法包括下述步驟：
接收測序序列；分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串，並得到所述短串的左、右連線關係；將得到的各所述短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點。
2、如權利要求1所述的方法，其特徵在於，所述de Bruijn圖的節點使用相應位存儲所述短串的序列值、存在左連線的各鹼基的連線數量和存在右連線的各鹼基的連線數量。
3、如權利要求1所述的方法，其特徵在於，所述將得到的各短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點的步驟具體為：
根據得到的短串的序列值在已存儲的節點中查詢是否已存有相應節點；如果沒有查詢到相應節點，則添加節點；如果查詢到相應節點，則更新所述相應節點的連線關係。
4、如權利要求1所述的方法，其特徵在於，所述de Bruijn圖的一個節點中存儲互補的兩短串。
5、如權利要求1所述的方法，其特徵在於，採用哈希表存儲所述de Bruijn圖的各節點，其中哈希鍵為所述序列值，值為所述節點。
6、如權利要求5所述的方法，其特徵在於，採用多個哈希表唯一存儲所述de Bruijn圖的不同節點，並採用不同執行緒訪問不同的哈希表。
7、一種短序列組裝中構建圖的系統，其特徵在於，所述系統包括：
接收單元，用於接收測序序列；序列切割單元，用於分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串，並得到所述短串的左、右連線關係；以及構圖單元，用於將得到的各所述短串的序列值，左、右連線關係及其連線 數量存儲為de Bruijn圖的一個節點。
8、如權利要求7所述的系統，其特徵在於，所述構圖單元在de Bruijn圖的節點中使用相應位存儲所述短串的序列值、存在左連線的各鹼基的連線數量和存在右連線的各鹼基的連線數量。
9、如權利要求8所述的系統，其特徵在於，所述構圖單元包括：
查詢模組，用於根據得到的短串的序列值在已存儲的節點中查詢是否已存有相應節點；節點添加模組，用於在所述查詢模組沒有查詢到相應節點時，添加節點；連線更新模組，用於在所述查詢模組查詢到相應節點時，更新所述相應節點的連線關係。
10、如權利要求7所述的系統，其特徵在於，所述構圖單元採用哈希表存儲所述de Bruijn圖中的不同節點，其中哈希鍵為所述序列值，值為所述節點。
實施方式
在《一種短序列組裝中構建圖的方法及系統》實施例中，通過分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串，並得到短串的左、右連線關係，將得到的各短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點。
圖1示出了《一種短序列組裝中構建圖的方法及系統》實施例提供的短序列組裝中構建圖的方法的實現流程，詳述如下：
在步驟S101中，接收測序序列；
在步驟S102中，分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串（kmer），並得到短串的左、右連線關係；
在步驟S103中，將得到的各短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點。
在《一種短序列組裝中構建圖的方法及系統》實施例中，測序序列的鹼基長度為25-75，切割成固定鹼基長度為21-31的短串。當然，切割得到的短串的長度小於測序序列的長度，其長度可以根據測序序列的長度和實際情況設定。de Bruijn圖中每個節點使用相應位存儲其序列值、存在左連線的各鹼基的連線數量和存在右連線的各鹼基的連線數量。這裡，用16位元組存儲de Bruijn圖上的各節點，其存儲格式如下：
[seq：64，left_links：24，right_links：24，...]；
其中，seq存儲短串的序列值，序列值的計算方法是使用2位存儲一個核苷序列，A用00表示，G用01表示，C用10表示，T用11表示，順序編碼下去生成一個占64位的整數值，並且，考慮到對於偶數長度的短串，其互補短串可能為它自己，例如短串GATC的互補短串為GATC自己。為了防止這種混淆，短串的長度均為奇數，由於《一種短序列組裝中構建圖的方法及系統》實施例中數據結構的限制，短串的長度不大於31；left_links用24位存儲其左連線關係及數量，將24位分割成4個6位，即A：6，T：6，G：6，C：6，分別用6位存儲與該短串存在左連線的鹼基A、T、G或C的連線數量，每種連線數量的取值範圍為[0，63]；right_links用24位存儲其右連線關係及數量，將24位分割成4個6位，即A：6，T：6，G：6，C：6，分別用6位存儲與該短串存在右連線的鹼基A、T、G或C的連線數量，每種連線數量的取值範圍為[0，63]；其後面的8位可以用於存儲其他值，例如，可以存儲刪除標記closed，以標識該短串是否被刪除；也可以存儲使用標記in_use，以標識該短串是否被使用過，還可以存儲其他標識。這樣，根據節點中存儲的短串序列值、存在左連線的各鹼基的連線數量和存在右連線的各鹼基的連線數量即可構建de Bruijn圖中各節點的連線關係。
例如，短串甲為AAAAAAAA存在右連線的鹼基T的連線數量為19，與其右連線鹼基T的短串乙為AAAAAAAT，等於短串甲左移一個鹼基並加上與其連線的鹼基T，並且與短串甲連線的短串乙有19個，節點中存儲右連線鹼基T的連線數量的存儲內容如圖2所示。
上述步驟S103具體為：
步驟1.根據得到的短串的序列值在已存儲的節點中查詢是否已存有相應節點；
步驟2.如果沒有查詢到相應節點，則添加節點；
步驟3.如果查詢到相應節點，則更新該相應節點的連線關係。
在《一種短序列組裝中構建圖的方法及系統》實施例中，使用哈希表存儲de Bruijn圖的各節點，哈希鍵為序列值，值為節點。例如取一短串為AAAAAAAA，其序列值為0x0000，將其序列值0x0000作為鍵在哈希表中查詢是否已存有相應節點，如果沒有查詢到相應節點，則添加節點存儲到哈希表中，其值中的seq為該短串的序列值0x0000，並根據該短串相鄰的短串將該節點中相應左、右相連鹼基的連線數量置為1；如果查詢到已存有相應節點，則更新相應節點的連線關係，即根據與該短串相鄰的短串更新該節點中相應左、右相連鹼基的連線數量，將與該短串有連線的鹼基的相應連線數量加1。完成後，執行步驟1，查找下一個短串，直至完成全部短串的查找。
在《一種短序列組裝中構建圖的方法及系統》實施例中，使用哈希表可以在O（1）的時間內完成查找節點、插入節點（即存儲節點）和更新節點連線關係。更新節點連線關係等同於查找節點，並更新查找到的節點的左、右相連鹼基的連線數量，所以時間複雜度依然為O（1）。
為了降低存儲de Bruijn圖中節點所需的空間，作為《一種短序列組裝中構建圖的方法及系統》的一個優選實施例，只用de Bruijn圖中的一個節點存儲互補的兩短串，節點的序列值取互補的兩短串中較小的序列值。如果一個的短串的序列值小於其互補短串的序列值， 則de Bruijn圖中的節點存儲該短串的序列值，seq存儲該短串的序列值，與其左連線鹼基的相應連線數量更新到left_links，與其右連線鹼基的相應連線數量更新到right_links；如果一個的短串的序列值大於其互補短串的序列值，則de Bruijn圖中的節點存儲其互補短串的序列值，seq存儲其互補短串的序列值，與其右連線鹼基的相應連線數量更新到left_links，與其左連線鹼基的相應連線數量更新到right_links。操作圖時，可以在程式中使用一個附加的變數來標記我們使用的是互補的兩短串的哪一個。並且，在沿圖遍歷時，只需要程式維持一個這樣的變數，就可以正確地得到路徑中所有節點的正方向。當然，de Bruijn圖中節點的序列值也可以存儲互補的兩短串中較大的序列值。
為了加快構建圖的速度，作為《一種短序列組裝中構建圖的方法及系統》的另一個優選實施例，使用多個哈希表唯一存儲de Bruijn圖中的不同節點，並採用不同執行緒訪問不同的哈希表。
在《一種短序列組裝中構建圖的方法及系統》實施例中，建立8個哈希表，讀入一定數目的原始序列，採用8個執行緒對讀入的原始測序列進行多執行緒切割、短串求互補，在數據收集完畢後，採用8個執行緒進行插入更新節點，其中每個執行緒只處理固定前綴的序列值。每個哈希表存儲指定前綴的序列值，並且一個哈希表只有一個執行緒訪問，以保證節點存儲的唯一性。
採用上述《一種短序列組裝中構建圖的方法及系統》實施例提供的壓縮的數據結構，可以將節點信息（即序列值）和節點的連線信息（即邊）組合在一起，從一個節點的值可以得到該節點上的短串、與該短串相鄰的短串的序列值及其數量。
當然，也可以用其他結構來存儲de Bruijn圖的各節點，例如可以用數結構來存儲，使用哈希表存儲各節點在記憶體和使用上與用樹狀結構存儲近似，但是使用哈希表存儲各節點在訪問和修改速度上都明顯優於樹的存儲結構。
選取非洲人基因組重測序數據，經糾錯處理後，序列數據量254G鹼基，切割成25鹼基長度的定長短串後，短串的總數目（包括正反向序列）為7G條，採用《一種短序列組裝中構建圖的方法及系統》實施例提供的方法構建de Bruijn圖，記憶體最大使用值為110G，共消耗23CPU小時，其中，CPU的參數為Quad-Core AMD Opteron（tm）Processor 83562.2吉赫。
該領域普通技術人員可以理解，實現上述實施例方法中的全部或部分步驟是可以通過程式來指令相關的硬體來完成，所述的程式可以在存儲於一計算機可讀取存儲介質中，所述的存儲介質，如ROM/RAM、磁碟、光碟等，該程式用來執行如下步驟：
1.接收測序序列；
2.分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串，並得到短串的左、右連線關係；
3.將得到的各短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點。
圖3示出了《一種短序列組裝中構建圖的方法及系統》實施例提供的短序列組裝中構建圖的系統的結構，為了便於說明僅示出了與《一種短序列組裝中構建圖的方法及系統》實施例相關的部分。
該系統可以用於短序列組裝中，其中：接收單元301，接收測序序列。
序列切割單元302，分別將接收到的測序序列逐個鹼基滑動切割得到固定鹼基長度的短串，並得到短串的左、右連線關係，其實現方式如上所述，不再贅述。
構圖單元303，將得到的各短串的序列值，左、右連線關係及其連線數量存儲為de Bruijn圖的一個節點。在《一種短序列組裝中構建圖的方法及系統》實施例中，構圖單元303在de Bruijn圖的節點中使用相應位存儲其序列值、存在左連線的各鹼基的連線數量和存在右連線的各鹼基的連線數量，採用哈希表存儲de Bruijn圖的節點，其中哈希鍵為序列值，值為節點。
其中，構圖單元303包括：查詢模組3031，根據得到的短串的序列值在已存儲的節點中查詢是否已存有相應節點。
節點添加模組3032，在查詢模組3031沒有查詢到相應節點時，添加節點， 其實現方式如上所述，不再贅述。
連線更新模組3033，在查詢模組3031查詢到相應節點時，更新該相應節點的連線關係，其實現方式如上所述，不再贅述。
為了降低存儲de Bruijn圖中節點所需空間，作為《一種短序列組裝中構建圖的方法及系統》的一個優選實施例，構圖單元303使用de Bruijn圖中的一個節點存儲互補的兩短串，節點的序列值取互補的兩短串中較小的序列值，其實現方式如上所述，不再贅述。
為了加快構建圖的速度，作為《一種短序列組裝中構建圖的方法及系統》的另一個優選實施例，構圖單元303採用多個哈希表唯一存儲de Bruijn圖中的不同節點，並採用不同執行緒訪問不同的哈希表。
榮譽表彰
2016年12月7日，《一種短序列組裝中構建圖的方法及系統》獲得第十八屆中國專利優秀獎。
