[發(fā)明專利]基因組核酸片段數(shù)量的快速計(jì)數(shù)算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410757812.0
• 申請(qǐng)日: 2014-12-11
• 公開（公告）號(hào): CN104361264A
• 公開（公告）日: 2015-02-18
• 發(fā)明（設(shè)計(jì)）人: 陳科;黃煥舟;厲國(guó)強(qiáng)
• 申請(qǐng)（專利權(quán)）人: 天津工業(yè)大學(xué)
• 主分類號(hào): G06F19/24
• 分類號(hào): G06F19/24
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

技術(shù)領(lǐng)域

本研究主要涉及到生物信息數(shù)據(jù)處理，生物大數(shù)據(jù)挖掘，基因組分析與全基因組拼接。

背景技術(shù)

k-mer，即為kilo?mer，指的是將一條基因序列，連續(xù)切割，挨個(gè)堿基劃動(dòng)得到的一序列長(zhǎng)度為K的核苷酸片段。在生物信息學(xué)項(xiàng)目的研究中，對(duì)k-核酸片段的計(jì)量是解讀基因組信息的重要環(huán)節(jié)，我們可以通過(guò)k-核酸片段了解到基因組的大小，深度，頻率，同時(shí)，k-核酸片段計(jì)量廣泛應(yīng)用于基因組拼裝拼接，評(píng)估基因組測(cè)序覆蓋度，測(cè)序數(shù)據(jù)的糾錯(cuò)，多序列比對(duì)，重復(fù)序列檢測(cè)等研究中。

近年來(lái)，隨著生物信息學(xué)的發(fā)展，國(guó)外研究出了一些此類算法，如Jellyfish，BFCounter等。Jellyfish，一種已有的k-核酸片段計(jì)量算法，采用了并行無(wú)鎖哈希表(lock-free?hash?table)數(shù)據(jù)結(jié)構(gòu)，在速率上比較高效，但需要非常大的內(nèi)存和硬盤空間(在處理160G的人類基因組數(shù)據(jù)需要70G內(nèi)存和211G硬盤)，這嚴(yán)重阻礙了在沒有小型機(jī)等大型計(jì)算設(shè)備的普通實(shí)驗(yàn)室環(huán)境下的數(shù)據(jù)處理。BFCounter，采用概率型數(shù)據(jù)結(jié)構(gòu)Bloom_filter，使其不需要硬盤操作，完全使用內(nèi)存即可實(shí)現(xiàn)計(jì)量。但其消耗內(nèi)存過(guò)大(處理上述數(shù)據(jù)需要56G內(nèi)存)，而且速率過(guò)慢(處理上述數(shù)據(jù)時(shí)間超過(guò)40小時(shí))所以，在有限的內(nèi)存和硬盤空間限制下，尚未有可合理權(quán)衡上述要求的高效算法。同時(shí)，在數(shù)據(jù)處理中，現(xiàn)有方法并沒有深刻發(fā)掘基因組本身信息，如頻率，深度，而這些信息可以幫助我們?nèi)ズ侠硖幚碇貜?fù)基因和錯(cuò)誤基因，從而極大的提升算法效率。

發(fā)明內(nèi)容

本發(fā)明是為了解決現(xiàn)有技術(shù)中的問(wèn)題，而提供了一種快速、低內(nèi)存需求、低硬盤需求的k-核酸片段s計(jì)量算法。

本發(fā)明為解決公知技術(shù)中存在的技術(shù)問(wèn)題所采用的技術(shù)方案包括：合理分配內(nèi)存和硬盤空間，采用合理的數(shù)據(jù)結(jié)構(gòu)來(lái)表示k-核酸片段s，優(yōu)化k-核酸片段s的索引結(jié)構(gòu)和排序。算法具體步驟如下：

1)讀取原始數(shù)據(jù)文件，設(shè)定參數(shù)，包括要統(tǒng)計(jì)k-核酸片段的長(zhǎng)度k，限定硬盤空間D(bits)，內(nèi)存空間M(bits)，數(shù)據(jù)深度(depth)。

2)遍歷數(shù)據(jù)文件一次，將文件利用位運(yùn)算壓縮成二進(jìn)制，并且建立長(zhǎng)度為8-核酸片段的索引index。同時(shí)，獲得k-核酸片段的總個(gè)數(shù)

3)利用參數(shù)劃分迭代次數(shù)和k-核酸片段劃分段。

4)遍歷8-核酸片段索引一次，等量分配每一個(gè)區(qū)段內(nèi)的k-核酸片段個(gè)數(shù)。

5)按照不同的數(shù)據(jù)結(jié)構(gòu)初始化兩種種存儲(chǔ)存儲(chǔ)空間，分配在內(nèi)存，硬盤中，用于存儲(chǔ)和計(jì)算k-核酸片段。

6)根據(jù)迭代順序開始計(jì)量工作。

7)按照索引區(qū)index[i](i∈(劃分段)讀取壓縮文件至內(nèi)存R，直到內(nèi)存R使用量達(dá)到設(shè)定內(nèi)存空間的40％為止。

8)快速排序已存于R的k-核酸片段，并合并相同的k-核酸片段，進(jìn)行計(jì)量，得出的結(jié)果存儲(chǔ)于Lx(x∈1，2，3..)中。

9)迭代7，8操作，直到已使用內(nèi)存超過(guò)60％。合并L1...n中的k-核酸片段，并且建立次數(shù)索引

10)遍歷已統(tǒng)計(jì)的k-核酸片段，根據(jù)基因組的深度劃分正確基因和錯(cuò)誤基因，將重復(fù)次數(shù)少的寫入硬盤，次數(shù)多的保存在內(nèi)存Lx中。每次寫入硬盤的文件必須按照劃分段來(lái)標(biāo)記，同時(shí)，通過(guò)遍歷索引找到相應(yīng)的k-核酸片段寫入的最低次數(shù)，保證寫入k-核酸片段至硬盤必須釋放60％的內(nèi)存。

11)迭代7-10操作，直到所有文件讀完。

12)此時(shí)所有的k-核酸片段都已經(jīng)存儲(chǔ)于內(nèi)存(計(jì)量次數(shù)多的k-核酸片段)和硬盤(次數(shù)少的k-核酸片段)中。根據(jù)劃分段，將內(nèi)存和硬盤中處于同一區(qū)段的k-核酸片段進(jìn)行合并排序，合并排序的順序遵循哈弗曼編碼方法

13)完成所有的迭代次數(shù)，完成計(jì)量工作。

附圖說(shuō)明

圖1：程序運(yùn)行圖1；

圖2：內(nèi)存CPU使用圖1；

圖3：程序運(yùn)行圖2；

圖4：內(nèi)存CPU使用圖2；

圖5：程序運(yùn)行圖3；

圖6：內(nèi)存CPU使用圖3；

具體實(shí)施方式

下面結(jié)合實(shí)施例進(jìn)一步描述本發(fā)明。本發(fā)明的范圍不受這些實(shí)施例的限制，本發(fā)明的范圍在權(quán)利要求書中提出。

本算法中具體的實(shí)施步驟如下：

1.在NCBI上下載的基因組數(shù)據(jù)，利用SRA?Toolkit工具包將其轉(zhuǎn)成fastq和fasta格式的數(shù)據(jù)文件。