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

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

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

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

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

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

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

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

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

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

1　Hash算法簡(jiǎn)述

1.1Hash算法原理

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

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

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

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

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

1.2“沖突”的處理

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

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

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

2.1該問題的特殊性

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

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

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

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

其中

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

對(duì)于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進(jìn)制函數(shù)時(shí)，可以逆向獲得相應(yīng)的k-mer，因此在存儲(chǔ)時(shí)只需存儲(chǔ)位置信息，而不需要存儲(chǔ)相應(yīng)的k-mer，大大減小的內(nèi)存的使用。如圖4所示，用于k值較小時(shí)順序索引模型的數(shù)據(jù)結(jié)構(gòu)，圖5為k值較大時(shí)散列索引模型的數(shù)據(jù)結(jié)構(gòu)。

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

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

2.4Hash表的大小

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

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

2.5復(fù)雜度分析

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

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

由二項(xiàng)分布可知，對(duì)給定鏈含有q個(gè)key的的概率為：

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

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

3　實(shí)驗(yàn)結(jié)果與分析

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

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

圖6　k＞15時(shí)查詢100萬次所需時(shí)間

圖7　建立索引所需時(shí)間

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

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

4　結(jié)論

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

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

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

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

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

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

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

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

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

［9］ 趙希奇，柏逢明，呂貴花.基于混沌理論和Hash函數(shù)的自適應(yīng)圖像加密算法［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(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