基于Hash算法的DNA序列k-mer index問題的數學建模

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

（長春理工大學　理學院，長春　130022）

基于Hash算法的DNA序列k-mer index問題的數學建模

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

（長春理工大學理學院，長春130022）

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

Hash算法；索引問題；數學模型；復雜度分析

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

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

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

1　Hash算法簡述

1.1Hash算法原理

Hash算法的基本原理［1，2］是：以關鍵字key為自變量，構造一個關鍵字與存儲地址之間的函數，稱Hash函數

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

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

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

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

1.2“沖突”的處理

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

所謂鏈地址法［5］，即把所有發生沖突的關鍵字都鏈接在Hash表的同一個地址之后。基于鏈地址法的Hash表實現簡單，在對key的順序信息不重要的應用中（如本問題），它可能是最快也是使用最廣泛的沖突解決方法［2］。如圖2所示，通過鏈地址法解決碰撞。

2　Hash算法在本問題中的應用

2.1該問題的特殊性

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

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

2.2Hash函數的構造

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

其中

表1　不同Hash函數的沖突率

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

2.3數據結構

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

圖3　用于k值較小時順序索引模型的數據結構

圖4　用于k值較大時散列索引模型的數據結構

2.4Hash表的大小

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

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

2.5復雜度分析

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

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

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

當m較小時，可用泊松分布近似表示，即

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

3　實驗結果與分析

本文對100萬條長度為100的DNA序列進行了測試。實驗的硬件平臺為2.6GHz的CPU和8G內存，操作系統為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　索引占用內存

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

4　結論

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

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

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

［3］ 嚴蔚敏，吳偉民.數據結構［M］.北京：清華大學出版社，2014.

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

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

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

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

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

［9］ 趙希奇，柏逢明，呂貴花.基于混沌理論和Hash函數的自適應圖像加密算法［J］.長春理工大學學報：自然科學版，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

國家自然科學基金（NSFC：11326078）

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

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