基于Hash算法的DNA序列k-mer index問題的數(shù)學(xué)建模

郭方舟，華陽，董修偉，蔡志丹

（長春理工大學(xué)　理學(xué)院，長春　130022）

基于Hash算法的DNA序列k-mer index問題的數(shù)學(xué)建模

郭方舟，華陽，董修偉，蔡志丹

（長春理工大學(xué)理學(xué)院，長春130022）

針對查找DNA序列的相似序列問題，給出了建立索引和查找索引的數(shù)學(xué)模型，基于Hash算法，建立了依賴于k值大小的順序索引模型和散列索引模型，特別對較大k值選用了DJBHash函數(shù)，有效的避免了Hash沖突問題。最后在硬件平臺CPU為2.6GHz、內(nèi)存為8G、操作系統(tǒng)為64位Windows 7的條件下，對100萬條長度為100的DNA序列進行了測試，給出了不同k值下建立和查詢索引的用時和占用內(nèi)存情況，有效的解決了DNA序列的k-mer index問題。

Hash算法；索引問題；數(shù)學(xué)模型；復(fù)雜度分析

從大量的DNA序列中查詢相似序列是當(dāng)前研究的熱點問題。

所謂DNA序列的k-mer，指的是一條長度為k 的DNA子序列，由A、T、C、G四種字符組成。使用長度為k的窗口在一條DNA序列上依次滑動，可以得到該DNA序列的k-mer集合。而k-mer index問題就是對這些k-mer構(gòu)建一種數(shù)據(jù)索引方法，以便之后可以對某條k-mer進行快速訪問，獲取其頻次、位置等信息。

理想的索引方法是不經(jīng)過比較，直接從字典中得到檢索的關(guān)鍵字法。Hash算法的基本思想就是在元素的關(guān)鍵字與元素的存儲位置之間確立一種函數(shù)關(guān)系，查找時直接得到元素的存儲位置。所有元素的存儲位置構(gòu)成Hash表。在理想情況下，使用Hash表查找能達到O（1）的性能。

1　Hash算法簡述

1.1Hash算法原理

Hash算法的基本原理［1，2］是：以關(guān)鍵字key為自變量，構(gòu)造一個關(guān)鍵字與存儲地址之間的函數(shù)，稱Hash函數(shù)

H（x）為關(guān)鍵字key的存儲地址，或稱索引值。所有索引值構(gòu)成一張Hash表，也稱索引。實際情況中，可以直接將k-mer作為關(guān)鍵字，也可以先對其處理后再作為關(guān)鍵字。

理想情況下，不同關(guān)鍵字的索引值都不相同。但實際情況中，很難找到這樣一個Hash函數(shù)。由此存在一個問題：兩個關(guān)鍵字可能映射到同一個地址上。這種情形稱為發(fā)生了“沖突（Collision）”，如圖1所示，用1個Hash函數(shù)將key映射到Hash表中：k3和k4發(fā)生了沖突。

Hash表是算法為了在查找時間上更高效，而在空間上做出讓步的一種存儲的經(jīng)典算法。如果沒有時間限制，那么直接將關(guān)鍵字順序存儲，查找時遍歷即可。顯然，當(dāng)數(shù)據(jù)量極大時，時間上是不允許的。另一方面，使用Hash函數(shù)生成的往往是一個相對隨機的索引值，于是為了盡量減小沖突，需要構(gòu)造一個龐大的空間來存儲Hash表，因為不知道哪些位置會被使用。此時，難免出現(xiàn)無效的索引位置。

圖1　用一個Hash函數(shù)將key映射到Hash表中：k3和k4發(fā)生了沖突

1.2“沖突”的處理

處理Hash沖突的方法很多［3］，如線性探測法、二次探測法、偽隨機探測法、鏈地址法等方法。而這些方法中或處理復(fù)雜、或可能發(fā)生“二次沖突”。鏈地址法更適合解決本問題引起的Hash沖突。

所謂鏈地址法［5］，即把所有發(fā)生沖突的關(guān)鍵字都鏈接在Hash表的同一個地址之后?；阪湹刂贩ǖ腍ash表實現(xiàn)簡單，在對key的順序信息不重要的應(yīng)用中（如本問題），它可能是最快也是使用最廣泛的沖突解決方法［2］。如圖2所示，通過鏈地址法解決碰撞。

2　Hash算法在本問題中的應(yīng)用

2.1該問題的特殊性

DNA序列有其特殊性，它僅由A、T、C、G四種字符構(gòu)成。對k-mer而言，其總組合數(shù)為4k種。當(dāng)k值較小時，大小的數(shù)組空間是可以接受的。此時可以不再使用傳統(tǒng)的Hash函數(shù)，轉(zhuǎn)而構(gòu)造一個新的映射關(guān)系，將k-mer映射為連續(xù)的索引值，可以大幅度提升空間利用率，減小內(nèi)存的使用。

另一方面，對于k值較大的情況，特定DNA序列的k-mer集合只是所有k-mer組合的一個小子集。此時，可以使用傳統(tǒng)的Hash函數(shù)，只對出現(xiàn)過的k-mer計算其索引值。

2.2Hash函數(shù)的構(gòu)造

一個優(yōu)秀的Hash函數(shù)應(yīng)該易于計算并能跟盡可能的減小沖突［6］。基于這個要求，加之這個問題的特殊性，最簡單易行的方法就是將k-mer轉(zhuǎn)化為一個4進制數(shù)，相應(yīng)的函數(shù)表達式如下：

其中

表1　不同Hash函數(shù)的沖突率

對于k值較大的情況，我們比較了常見的用于轉(zhuǎn)換字符串的Hash函數(shù)［4］，選擇了效果最好的DJB Hash函數(shù)。如表1所示，記錄了不同Hash函數(shù)的沖突率。

2.3數(shù)據(jù)結(jié)構(gòu)

兩種情況所使用的數(shù)據(jù)結(jié)構(gòu)有些不同，由于使用4進制函數(shù)時，可以逆向獲得相應(yīng)的k-mer，因此在存儲時只需存儲位置信息，而不需要存儲相應(yīng)的k-mer，大大減小的內(nèi)存的使用。如圖4所示，用于k值較小時順序索引模型的數(shù)據(jù)結(jié)構(gòu)，圖5為k值較大時散列索引模型的數(shù)據(jù)結(jié)構(gòu)。

圖3　用于k值較小時順序索引模型的數(shù)據(jù)結(jié)構(gòu)

圖4　用于k值較大時散列索引模型的數(shù)據(jù)結(jié)構(gòu)

2.4Hash表的大小

選擇適當(dāng)?shù)臄?shù)組大小，既不會因空位置過多而浪費內(nèi)存空間，也不會因鏈表太長而降低查詢效率［7］。如果存入的key多于預(yù)期，查找的時間會稍長；如果少于預(yù)期，雖然浪費了部分空間，但查找很快。

對該問題，k值較小時，數(shù)組大小即4k；當(dāng)k較大時，如果事先知道待建索引的DNA序列的總長和k的大小，可以計算出k-mer的總數(shù)（包括重復(fù)）［8］。那么可以建立一個比該值稍小的數(shù)組。如果內(nèi)存有限，則可以動態(tài)調(diào)整數(shù)組的大小以保持較短的鏈表，而且無需重寫代碼，適當(dāng)調(diào)整參數(shù)即可。

2.5復(fù)雜度分析

建立索引的過程就是掃描一遍DNA序列的過程，時間復(fù)雜度為O（n）［9］。

如果使用的Hash函數(shù)能夠大致均勻的將key分布于［0，M-1］，則查詢的時間復(fù)雜度為O（m）=O （1），其中m＜N/M，N為key的數(shù)量，M為鏈的數(shù)量，簡單證明如下：

由二項分布可知，對給定鏈含有q個key的的概率為：

當(dāng)m較小時，可用泊松分布近似表示，即

說明任意一條鏈中key的數(shù)量小于m的概率趨向于1。

3　實驗結(jié)果與分析

本文對100萬條長度為100的DNA序列進行了測試。實驗的硬件平臺為2.6GHz的CPU和8G內(nèi)存，操作系統(tǒng)為64位Windows7，軟件平臺為Dec-C++Version5.7.1，編譯器為TDM-GCC 4.8.1 64-bit Release。

圖5　0＜k≤15時查詢100萬次所需時間

圖6　k＞15時查詢100萬次所需時間

圖7　建立索引所需時間

圖8　索引占用內(nèi)存

實驗結(jié)果如圖5（0＜k≤15時查詢100萬次所需時間）、圖6（k＞15時查詢100萬次所需時間）、圖7（建立索引所需時間）、圖8（索引占用內(nèi)存）所示，根據(jù)結(jié)果分析可知：在0＜k≤15時適用于順序索引模型的數(shù)據(jù)結(jié)構(gòu)，k＞15時適用于散列索引模型的數(shù)據(jù)結(jié)構(gòu)。

4　結(jié)論

本文針對不同長度的k-mer分別應(yīng)用了兩種Hash映射關(guān)系。從實驗結(jié)果可以看出，兩者相互結(jié)合，互為補充，可以有效的解決DNA序列的k-mer索引問題。

［1］ Cormen T H.算法導(dǎo)論（第2版）［M］.北京：機械工業(yè)出版社，2006.

［2］ Robert Sedgewick.算法（第4版）［M］.北京：人民郵電出版社，2015.

［3］ 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京：清華大學(xué)出版社，2014.

［4］ 成麗波，蔡志丹，周蕊，等.大學(xué)數(shù)學(xué)實驗教程（第2版）［M］，北京：北京理工大學(xué)出版社，2015.

［5］ 趙國峰，閆亮.用于快速流分類的關(guān)鍵字分解Hash算法［J］.計算機工程，2010，36（16）：79-81.

［6］ 林勇.面向下一代測序技術(shù)的de novo序列拼接工具綜述［J］.小型微型計算機系統(tǒng)，2013，34（3）：627-631.

［7］ 鄭瑩，歐陽丹彤，何麗莉，等.基于Hash函數(shù)的抵御失去同步RFID安全認證協(xié)議［J］.吉林大學(xué)學(xué)報：理學(xué)版，2015，53（3）：499-504.

［8］ 李錦青，柏逢明，底曉強.基于Hopfield混沌神經(jīng)網(wǎng)絡(luò)的彩色圖像加密算法研究［J］.長春理工大學(xué)學(xué)報：自然科學(xué)版，2012，35（4）：117-121.

［9］ 趙希奇，柏逢明，呂貴花.基于混沌理論和Hash函數(shù)的自適應(yīng)圖像加密算法［J］.長春理工大學(xué)學(xué)報：自然科學(xué)版，2014，37（4）：117-120.

The Mathematical Model of k-mer Index for DNA Sequence Problem Based on Hash Algorithm

GUO Fangzhou，HUA Yang，DONG Xiuwei，CAI Zhidan
（School of Science，Changchun University of Science and Technology，Changchun 130022）

In this paper，we give the mode of building and searching index for DNA similar sequences.Based on the Hash algorithm，we establishthe order index model and Hash indexing model which depend on the size of the k value.In orter to avoid Hash-Clash，we chose DJBhash fuction under the larger k value.Finally，we give the time of buliding and searching index and the memory occupation with different k value which CPU is 2.6GHz，memory is 8G，operation system is window 7 at 64 bit，at the same time，we test 1 million of DNAsequencewiththe length of 100，solve the k-mer index problem of DNA sequence effectively.

Hash algorithm；index problem；mathematical model；complexity analysis

O244

A

1672-9870（2015）05-0116-04

2015-07-01

國家自然科學(xué)基金（NSFC：11326078）

郭方舟（1993-），男，本科，E-mail：940481517@qq.com

蔡志丹（1979-），女，副教授，E-mail：1261046008@qq.com