DNA序列的k-merindex問題-基于Hash算法快速檢索

1、2015山東科技大學數(shù)學建模競賽承 諾 書我們仔細閱讀了山東科技大學數(shù)學建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從A/B/C中選擇一項填寫）： 我們的參賽序號為： 所屬學院（請?zhí)顚懲暾娜?參賽隊員

2、 (打印并簽名) ：1. 2. 3. 日期： 年 月 日基于Hash表在大量DNA序列中快速索引查找k-mer 的算法摘要：為了解決在大量DNA數(shù)據中快速查找到k-mer所在位置，我們基于Hash算法思想建立適合此題的快速索引方法（桶式定址法），利用四進制轉十進制的方式（）取得關鍵碼值建立哈希表進行索引查詢，8G內存限制下在codeblocks集成開發(fā)環(huán)境中，借助C語言進行編寫使k支持114。針對問題將依次進行下列敘述：對建立索引的算法進行敘述和沖突分析；對建立索引算法的計算復雜度和空間復雜度進行分析；對索引查詢進行敘述及性能分析；分析整套算法程序在不同k值下內存占用及極限分析。總結分析整套索

3、引算法性能，對算法進行缺陷分析及改進方案。關鍵詞：索引算法、Hash表、k-mer快速索引、數(shù)據結構一、問題重述1.1背景 給定一個DNA序列，這個系列只含有4個字母ATCG，如 S =“CTGTACTGTAT”。給定一個整數(shù)值k，從S的第一個位置開始，取一連續(xù)k個字母的短串，稱之為k-mer（如k= 5，則此短串為CTGTA）， 然后從S的第二個位置， 取另一k-mer（如k= 5，則此短串為TGTAC），這樣直至S的末端，就得一個集合，包含全部k-mer 。 如對序列S來說，所有5-mer為CTGTA，TGTAC，GTACT，TACTG，ACTGT，TGTAT通常這些k-mer需一種數(shù)據索

4、引方法，可被后面的操作快速訪問。例如，對5-mer來說，當查詢CTGTA，通過這種數(shù)據索引方法，可返回其在DNA序列S中的位置為1，6。1.2問題現(xiàn)在以文件形式給定 100萬個 DNA序列，序列編號為1-，每個基因序列長度為100 。（1）要求對給定k， 給出并實現(xiàn)一種數(shù)據索引方法，可返回任意一個k-mer所在的DNA序列編號和相應序列中出現(xiàn)的位置。每次建立索引，只需支持一個k值即可，不需要支持全部k值。（2）要求索引一旦建立，查詢速度盡量快，所用內存盡量小。（3）給出建立索引所用的計算復雜度，和空間復雜度分析。 （4）給出使用索引查詢的計算復雜度，和空間復雜度分析。（5）假設內存限制為8G，

5、分析所設計索引方法所能支持的最大k值和相應數(shù)據查詢效率。（6）按重要性由高到低排列，將依據以下幾點，來評價索引方法性能 索引查詢速度 索引內存使用 8G內存下，所能支持的k值范圍 建立索引時間二、問題分析在生物技術快速發(fā)展的今天，人類分析人類自身編碼的需求也越來越高，人們利用計算機來處理分析大量DNA序列，k-mer快速查找也是處理大量數(shù)據的問題，所以必須依賴數(shù)據結構原理，建立模型構造算法，從而利用有限的資源解決復雜問題。針對問題一：按照給定k值，將所有數(shù)據按題目要求分組，求出每組數(shù)據的關鍵碼值，并將關鍵碼值與此組k-mer所在位置建立對應關系并存儲到表中，從而建立哈希表。針對問題二：將要查找

6、的k-mer序列求出其關鍵碼值，直接輸出其關鍵碼值在表中對應位置信息，大大加快了索引查詢速度。針對問題三：詳見四-（二）-2，3。針對問題四：詳見四-（三）-2，3。針對問題五：根據k值大小動態(tài)分配內存建立哈希表，最終實現(xiàn)k支持114的范圍，因為直接關鍵碼值尋址輸出，所以索引查詢速度非?？臁ａ槍栴}六：按照重要性首先考慮索引查詢速度，其次動態(tài)內存分配盡量減少索引對內存的消耗，在8G內存限制下，使k值支持114，最后優(yōu)化添加計數(shù)器記錄已經存在地址的k-mer個數(shù)，倘若達到所有k-mer種類數(shù)，則停止建立索引，索引成功建立。三、符號說明符號符號說明H(x)關鍵碼值生成函數(shù)，其中x代表一個k-mer

7、Ci代表A，T，C，G中的任意一個Ii與Ci相對應的四進制數(shù)k一個k-mer的長度M內存空間占用（單位：GB）四、算法設計思路及性能分析（代碼見附錄一）(一) 哈希表設計：1、k-mer關鍵碼值生成函數(shù)H(x)由于DNA序列由4個字母排列而成，所以每個k-mer都是一個四進制數(shù)，H(x)函數(shù)根據這個特征將四進制數(shù)轉為十進制數(shù)作為哈希表關鍵碼值。 x= “CTGTA”如上圖為每個字母代表的四進制數(shù)字，例如一個5-mer “CTGTA” 可以表示為四進制數(shù)21310，其十進制表示為628，628即為5-mer “CTGTA”在哈希表中的關鍵碼值。關鍵碼值計算的一般公式為: （1）2、哈希表結構將k

8、-mer通過公式（1）轉換為十進制的關鍵碼值存入哈希表中的關鍵碼值一列，并將關鍵碼值與此k-mer所在位置建立對應關系，從而便于索引尋址。這里采用的方法是：桶定址法。桶：一片足夠大的存儲空間。桶定址：為表中的每個地址關聯(lián)一個桶。如果桶已經滿了，可以使用開放定址法來處理。如圖。3、沖突處理方法開放地址法有一個公式：Hi=(H(key)+di) MOD m i=1,2,.,k(k=m-1）其中，m為哈希表的表長。di 是產生沖突的時候的增量序列。如果di值可能為1,2,3,.m-1，稱線性探測再散列。如果di取1，則每次沖突之后，向后移動1個位置.如果di取值可能為1,-1,4,-4,9,-9,1

9、6,-16,.k*k,-k*k(k=m/2）稱二次探測再散列。(二) 建立索引的算法、計算復雜度及空間復雜度分析1、 算法分析hash表初始化時，根據用戶輸入的k值， 計算出存儲哈希表需要的空間，利用內存動態(tài)分配函數(shù)動態(tài)分配內存，k-mer所在行數(shù)為100 0000以內所以我們采用int型（占用4字節(jié)）存儲，而其在行的第幾個位置數(shù)在100以內，我們則采用char（占用1字節(jié)）型存儲，充分減少空間損耗。哈希表初始化代碼：求關鍵碼值如上敘述采用四進制轉十進制數(shù)作為關鍵碼值存入哈希表用于位置索引。求關鍵碼值代碼：建立哈希表過程中先將傳入的長度為100的字符串分成每k個字符一段的串，每分好一個就求一個

10、關鍵碼值存儲哈希表，為了提高建立索引的速度，每個關鍵碼值只對應一個位置信息，也就是說索引查詢時只返回k-mer的一個位置信息。倘若每個關鍵碼值都有其對應的位置信息了，就退出索引建立，索引建立完成。建立哈希表代碼：2、計算復雜度分析不考慮8G空間限制，k在150的范圍內每條DNA序列分段的循環(huán)不斷增加，計算復雜度也隨之增加，而50100范圍內循環(huán)則又開始減少。根據計算復雜度定義1，建立索引的計算復雜度為O(-k2+100k)3、空間復雜度分析邏輯上哈希表空間占用計算公式：M=(54k)/(102410241024)（每條索引信息邏輯空間占用為5Byte）k值建立索引后空間占用（GB）10. 20

11、. 30. 40. 50. 60. 70. 80. 90. 100. 110. 120. 130. 141. 155. 1620. 由以上圖表可以清晰的看到，索引建立的內存消耗隨著k的增長冪指數(shù)增長，與k-mer排列組合種類數(shù)（4k）相對應，所以減少每條索引數(shù)據的存儲空間，可大大增加k的取值范圍，k-mer所在行數(shù)為100 0000以內所以我們采用int型（占用4字節(jié)）存儲，而其在行的第幾個位置數(shù)在100以內，我們則采用char（占用1字節(jié)）型存儲，盡可能的縮小了每條索引數(shù)據的存儲空間，最終使k支持114。但由上表可以看出，邏輯上k=15也能支持，但設備資源有限，未能實際測試。k=14時，索引

12、建立實際內存消耗為KB=1.GB，與邏輯分析基本一致。如下圖：(三) 索引查詢的算法、計算復雜度及空間復雜度分析1、算法分析索引查詢需要將要查找的k-mer的關鍵碼值求出來，然后直接從哈希表中輸出對應關鍵碼值的位置信息，求關鍵碼值的函數(shù)同建立索引過程的函數(shù)，不再重復給出。索引查詢代碼如下：2、計算復雜度分析索引查詢的過程中只有求關鍵碼值時需要進行計算，其計算復雜度為：O(k)3、空間復雜度分析索引查詢過程用到只一個存關鍵碼值的中間變量，根據空間復雜度定義2（臨時占用存儲空間大小的量度）可知，索引查詢過程中空間復雜度為：O(1)(四) 整套索引算法程序在不同k值下內存占用及極限分析k值k-mer

13、種類數(shù)建立索引耗時（秒）索引查詢耗時（秒）1400216003640042560.0010510240.0010640960.00807163840.03108655360.17091.0680108.2901133.55801236.08301339.31601443.9470測量上表耗時數(shù)據設備參數(shù)：CPU：Intel 酷睿i3 3110M 2.4GHz 雙核心/四線程內存（RAM）：DDR3 1600MHz 8G硬盤：500G 5400轉比對以上兩折線圖不難發(fā)現(xiàn)建立索引耗時與k-mer種類數(shù)目變化趨勢并不是一致的，原因有兩點，第一點建立索引用事在9秒前幾乎為零因為此算法在確認所有種類k-

14、mer都有對應位置后索引就建立完成不管是否將所有數(shù)據都遍歷過，9秒前k-mer種類較少，所以沒有檢索所有數(shù)據就已經完成了索引建立；第二點建立索引耗時并沒有跟著k-mer種類指數(shù)上升而是放緩，原因是k-mer種類太多，將所有數(shù)據都遍歷結束后，有的k-mer也沒有找到與其匹配的位置，所以耗時基本就是遍歷所有數(shù)據的時間。(五) 缺陷分析及改進方案1、 缺陷分析建立索引過程中會有一個k-mer與多個位置對應，由于hash表存儲限制發(fā)生了沖突，只能返回k-mer的一個位置信息，不能將k-mer的所有位置信息都返回。2、 改進方案 針對這個缺陷，可以采取hash算法沖突處理方法開放定址法，或采用hash的改進算法tri-樹（字典樹）算法，在這里我們采用沖突處理的方案對此算法進行改進，在內存有限制的情況下，放棄一點k值的范圍，騰出部分空間來存儲更多k-mer位置信息，從而彌補之前的缺陷，代碼見附錄二。五、參考文獻1創(chuàng)建者：flyingmyself時間復雜度/link?url=4RJO-qHmJs867JEK