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

在審

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

1.一種快速統(tǒng)計基因組核酸片段數(shù)量的算法，該方法可在有限內(nèi)存的限制條件下完成核酸片段數(shù)量的統(tǒng)計。本發(fā)明總是優(yōu)先將高倍數(shù)的核酸片段放置于內(nèi)存，而將低倍數(shù)的核酸不斷移除到硬盤中。通過不斷排序與迭代上述過程，盡可能地提高在內(nèi)存中計算的比例。其期特征在于，

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

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

(3)劃分迭代次數(shù)和k-核酸片段區(qū)段。

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

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

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

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

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

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

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

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

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

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