哈希方法在生物信息學研究中的應用探討

耿彧 白濤

[摘 要]哈希表由于能夠實現高效的數據存儲和查找，操作時間可達到O（1）級，所以其被廣泛應用于信息安全、操作系統、數據挖掘和生物信息等領域。本文對哈希方法在生物信息中的應用進行了探討，同時介紹了其他特殊的哈希方法在生物信息相關問題中的解決策略。哈希方法的引入能更好地提高生物信息大數據的存儲與檢索性能。

[關鍵詞]生物信息計算；哈希方法；最小哈希；相似哈希

doi：10.3969/j.issn.1673 - 0194.2018.12.064

[中圖分類號]TP312；R28 [文獻標識碼]A [文章編號]1673-0194（2018）12-0-02

1 哈希方法在組裝技術中的應用

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

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

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

一次哈希方法和二次哈希方法中所用哈希表長度均為227，k值越大k-mer數目越少。裝填因子與k值成正比，沖突率、平均查找長度與k值成反比，即k取值越大哈希效果越好。通過分析可見，二次哈希方法性能更優。

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

2 其他Hash方法

2.1 最小哈希（Minhash）

Minhash可以用來快速估算兩個集合的相似度。Yang將Minhash用于DNA序列的聚類；VICUNA引入Minhash解決片段重疊群（Contig）中的讀段聚類問題。Jaccard Index是距離的一種度量標準，用來計算集合的相似性。對于集合A和B，當A∪B中具有最小哈希值的元素也在A∩B中，則hmin（A）=hmin（B）。其中，hmin（S）表示集合S中的元素經過哈希函數后，具有最小哈希值的元素。集合A和B的相似度為集合A和B經過哈希函數運算后取得最小哈希值相等的概率，即J（A，B）=Pr[hmin（A）=hmin（B）]。根據Minhash思想計算兩個集合的相似度時，可采用單哈希函數和多哈希函數的解決策略。使用多哈希函數時，如哈希函數個數為k，用k個哈希函數分別對集合A和B求哈希值。每種哈希函數都會得到一個相應的最小哈希值，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）

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

3 結 語

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

主要參考文獻

[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）.