哈希方法在生物信息學(xué)研究中的應(yīng)用探討

耿彧 白濤

[摘 要]哈希表由于能夠?qū)崿F(xiàn)高效的數(shù)據(jù)存儲(chǔ)和查找，操作時(shí)間可達(dá)到O（1）級(jí)，所以其被廣泛應(yīng)用于信息安全、操作系統(tǒng)、數(shù)據(jù)挖掘和生物信息等領(lǐng)域。本文對(duì)哈希方法在生物信息中的應(yīng)用進(jìn)行了探討，同時(shí)介紹了其他特殊的哈希方法在生物信息相關(guān)問(wèn)題中的解決策略。哈希方法的引入能更好地提高生物信息大數(shù)據(jù)的存儲(chǔ)與檢索性能。

[關(guān)鍵詞]生物信息計(jì)算；哈希方法；最小哈希；相似哈希

doi：10.3969/j.issn.1673 - 0194.2018.12.064

[中圖分類號(hào)]TP312；R28 [文獻(xiàn)標(biāo)識(shí)碼]A [文章編號(hào)]1673-0194（2018）12-0-02

1 哈希方法在組裝技術(shù)中的應(yīng)用

哈希函數(shù)可把任意長(zhǎng)度的輸入通過(guò)一定的算法轉(zhuǎn)換成固定長(zhǎng)度的哈希值，將某種類型的數(shù)據(jù)元素盡量均勻隨機(jī)地映射到一個(gè)整數(shù)空間。哈希表根據(jù)設(shè)定的哈希函數(shù)和處理沖突方法將一組關(guān)鍵字映射到一個(gè)有限的地址區(qū)間上，在實(shí)際中不可避免地產(chǎn)生哈希沖突，一個(gè)良好的哈希函數(shù)應(yīng)保證散列均勻、沖突少。在基因序列組裝技術(shù)中，通常采用不同的哈希方法對(duì)k-mers實(shí)現(xiàn)快速存儲(chǔ)與查找。如Meta-IDBA采用一次哈希方法實(shí)現(xiàn)宏基因組序列組裝，將k-mers存儲(chǔ)于一個(gè)數(shù)組中，按數(shù)組類型的位數(shù)對(duì)k-mer進(jìn)行分段，再對(duì)每段進(jìn)行異或運(yùn)算。然而，一次哈希函數(shù)建立的哈希表策略可能產(chǎn)生較高的沖突率，因此考慮采用多次哈希和多級(jí)哈希方法保證裝填因子在更合理的情況下減少?zèng)_突率。多次哈希方法先采用一種哈希函數(shù)對(duì)關(guān)鍵字進(jìn)行散列，然后對(duì)發(fā)生沖突的關(guān)鍵字采用不同哈希函數(shù)再次散列。多級(jí)哈希方法根據(jù)關(guān)鍵字的哈希值對(duì)數(shù)據(jù)元素進(jìn)行“分類”，如SOAPdenovo采用二級(jí)哈希方法實(shí)現(xiàn)組裝，第一級(jí)哈希函數(shù)將k-mer進(jìn)行循環(huán)冗余程序計(jì)算，按照所得哈希值查找已確定的循環(huán)冗余校驗(yàn)表，得到對(duì)應(yīng)的桶號(hào)（0～255），然后對(duì)每個(gè)桶再次建立第二級(jí)哈希表。

以染色體chr19為參考序列，分別采用一次哈希、二次哈希和二級(jí)哈希方法，從裝填因子、沖突率和平均查找長(zhǎng)度幾個(gè)性能指標(biāo)對(duì)不同長(zhǎng)度的k-mer進(jìn)行分析，為基因組序列組裝中哈希方法的選擇提供參考依據(jù)。輸入數(shù)據(jù)為雙末端讀段，插入距離服從正態(tài)分布N（500 bp，49 bp），讀段長(zhǎng)度為100 bp。一次哈希方法中哈希函數(shù)采用分段疊加法，每段長(zhǎng)度取27 bp；二次哈希方法中第一次哈希函數(shù)采用分段異或法，第二次哈希函數(shù)采用分段疊加法；二級(jí)哈希方法中第一級(jí)哈希函數(shù)采用低八位與255進(jìn)行按位與運(yùn)算，產(chǎn)生256個(gè)桶，再用第二級(jí)哈希函數(shù)分段疊加法實(shí)現(xiàn)桶內(nèi)的哈希存儲(chǔ)。對(duì)于生物信息中涉及的大數(shù)據(jù)，用公共溢出區(qū)的方法按順序查找空位，其效率相對(duì)較低，所以通常采用鏈地址法解決沖突。

（1）在無(wú)變異的情況下。k值分別取23 bp、45 bp和63 bp，覆蓋度為100×。裝填因子、沖突率和平均查找長(zhǎng)度的比較如圖1所示。

一次哈希方法和二次哈希方法中所用哈希表長(zhǎng)度均為227，k值越大k-mer數(shù)目越少。裝填因子與k值成正比，沖突率、平均查找長(zhǎng)度與k值成反比，即k取值越大哈希效果越好。通過(guò)分析可見(jiàn)，二次哈希方法性能更優(yōu)。

（2）對(duì)性能較優(yōu)的二次哈希方法，覆蓋度取值為30×，k-mer取值為63 bp，實(shí)現(xiàn)不同變異率下的比較分析，變異率分別為0、10-4和10-5。從圖2可見(jiàn)，隨著變異率的增大，裝填因子、沖突率及平均查找長(zhǎng)度均有所增加。

2 其他Hash方法

2.1 最小哈希（Minhash）

Minhash可以用來(lái)快速估算兩個(gè)集合的相似度。Yang將Minhash用于DNA序列的聚類；VICUNA引入Minhash解決片段重疊群（Contig）中的讀段聚類問(wèn)題。Jaccard Index是距離的一種度量標(biāo)準(zhǔn)，用來(lái)計(jì)算集合的相似性。對(duì)于集合A和B，當(dāng)A∪B中具有最小哈希值的元素也在A∩B中，則hmin（A）=hmin（B）。其中，hmin（S）表示集合S中的元素經(jīng)過(guò)哈希函數(shù)后，具有最小哈希值的元素。集合A和B的相似度為集合A和B經(jīng)過(guò)哈希函數(shù)運(yùn)算后取得最小哈希值相等的概率，即J（A，B）=Pr[hmin（A）=hmin（B）]。根據(jù)Minhash思想計(jì)算兩個(gè)集合的相似度時(shí)，可采用單哈希函數(shù)和多哈希函數(shù)的解決策略。使用多哈希函數(shù)時(shí)，如哈希函數(shù)個(gè)數(shù)為k，用k個(gè)哈希函數(shù)分別對(duì)集合A和B求哈希值。每種哈希函數(shù)都會(huì)得到一個(gè)相應(yīng)的最小哈希值，min（A）={a1，…，ak}，min（B）={b1，…，bk}那么A和B的相似度為：J（A，B）=（min（A）k∩min（B）k）/（min（A）k∪min（B）k）。

2.2 相似哈希（Similarity Hash）

相似哈希是一種局部敏感哈希函數(shù)，不僅能定性地判斷同類型數(shù)據(jù)元素是否相同，還能進(jìn)一步定量分析同類數(shù)據(jù)元素之間的相似度，即越相似的元素相似哈希值越相近，反之，哈希值相差越遠(yuǎn)。將相似哈希的思想引入比對(duì)技術(shù)中，將讀段拆分為不覆蓋的k段，每一段轉(zhuǎn)換為一個(gè)特征集合，該集合是一個(gè)n維的向量V，給特征集合中的每個(gè)特征都賦予一個(gè)權(quán)重，由于讀段中每個(gè)位點(diǎn)的地位是均等的，所以每個(gè)特征的權(quán)值都置為1。由于MD5函數(shù)產(chǎn)生的哈希值具有隨機(jī)性強(qiáng)的特點(diǎn)，所以對(duì)讀段中的k段可采用MD5作為哈希函數(shù)進(jìn)行散列，得到一個(gè)n位的哈希值h；如果h的第i位為1，則向量V的第i位加上權(quán)值；如果h的第i位為0，則向量V的第i位減去權(quán)值；將讀段的k段按位統(tǒng)計(jì)，進(jìn)行累加，如果第i維的累加值大于0，則將相似哈希值中該位置為1，否則置為0，所得結(jié)果即為此序列的相似哈希值。

3 結(jié) 語(yǔ)

哈希函數(shù)可以實(shí)現(xiàn)快速索引功能，具有O（1）級(jí)的時(shí)間復(fù)雜度，使其得到了廣泛應(yīng)用。然而哈希表是基于數(shù)組創(chuàng)建的，很難再次拓展，而且裝填因子的大小會(huì)影響哈希函數(shù)的性能。目前衍生出了許多哈希方法，但不同的應(yīng)用對(duì)哈希函數(shù)有著不同的要求。

主要參考文獻(xiàn)

[1]Peng Y，Leung H C M， Yiu S M.Meta-IDBA：a De Novo Assembler for Metagenomic Data[J].Bioinformatics，2011（13）.

[2]Li R，Zhu H，Ruan J.De novo Assembly of Human Genomes with Massively Parallel Short Read Sequencing[J].Genome Research，2010（2）.

[3]Yang X，Charlebois P，Gnerre S.De Novo Assembly of Highly Diverse Viral Populations[J].Bmc Genomics，2012（1）.