基于ChIP—seq測序數(shù)據(jù)的二維快速檢索技術(shù)

摘要：ChIP-seq技術(shù)是研究全基因組范圍內(nèi)轉(zhuǎn)錄因子結(jié)合位點的重要技術(shù)。ChIP-seq測序數(shù)據(jù)晦澀難懂，2009年Simon Anders發(fā)明了Hilbert曲線方法，將一維測序數(shù)據(jù)以二維圖像形式呈現(xiàn)。本文在前人工作基礎(chǔ)上，研究使用三種圖像相似性檢索的技術(shù)，對測序數(shù)據(jù)進行快速檢索。通過模擬數(shù)據(jù)測試，證明了圖像相似性檢索方法在操作性和計算速度方面比傳統(tǒng)的序列比對（Blast）檢索技術(shù)有顯著優(yōu)勢。本研究對高通量測序數(shù)據(jù)的醫(yī)學(xué)診斷或有裨益。

關(guān)鍵詞：ChIP-seq；Hilbert曲線；圖像檢索；感知哈希算法；顏色直方圖；顏色相關(guān)圖

中圖分類號：R857.3 文獻標(biāo)識碼：B

Two-Dimensional Fast Retrieval Technologies for ChIP-seq Data

LI Da，SONG Xin-rui，JIN Rong-xia，ZHAO Yong，ZHOU Jia-peng

（Beijing Computing Center， Beijing 100094，China）

Abstract：ChIP-seq technology is an important technology for researching transcript factor binding sites in the whole genome. ChIP-seq data is obscure， so Simon Anders developed the HilbertVis method to show it two-dimensionally. In the present study， three image similarity retrieval technologies were used in order to rapid retrieval for sequencing data. Via simulation data， the operability and calculation speed of image similarity retrieval method showed a significant advantage over the conventional sequence alignment （Blast）. This study may be helpful for application of high-throughput sequencing data in medical diagnosis.

Key words：ChIP-seq；HilbertVis；Image retrieval；pHash；Color histogram；Color correlograms

1引言

近年來越來越多的研究發(fā)現(xiàn)，基因的轉(zhuǎn)錄調(diào)控與人類疾病存在密切關(guān)系。轉(zhuǎn)錄因子結(jié)合位點（TFBS）是轉(zhuǎn)錄調(diào)控研究中的核心內(nèi)容。ChIP是研究體內(nèi)蛋白質(zhì)與DNA相互作用的有力工具，通常用于轉(zhuǎn)錄因子結(jié)合位點或組蛋白特異性修飾位點的研究。將ChIP與高通量測序相結(jié)合的ChIP-seq技術(shù)，充分發(fā)揮了二者的優(yōu)勢，能夠高效地在全基因組范圍內(nèi)研究目的蛋白的結(jié)合位點。ChIP-seq技術(shù)可以產(chǎn)生高分辨率的數(shù)據(jù)來精確定位轉(zhuǎn)錄因子結(jié)合位點，使得醫(yī)學(xué)科研工作者可以更加深入細致地研究轉(zhuǎn)錄調(diào)控水平的疾病發(fā)生機理。

1.1二維化理念 現(xiàn)實生活中最常見也是最成功的二維化應(yīng)用就是二維碼的普及， 二維碼較一維碼有如下優(yōu)點：信息密度高、存儲容量大、錯誤糾正能力強、保密性好、譯碼率低和識讀速度快等[1，2]。

在感官層面，二維數(shù)據(jù)的展現(xiàn)形式比一維數(shù)據(jù)更加直觀、生動和形象。在技術(shù)層面，數(shù)據(jù)存儲、保密性、容災(zāi)性、譯碼率及識別速度上，二維數(shù)據(jù)也具有先天優(yōu)勢。

1.2 ChIP-seq測序數(shù)據(jù)二維化轉(zhuǎn)換 將ChIP-seq的一維測序數(shù)據(jù)轉(zhuǎn)換為二維化的數(shù)據(jù)格式，在前人的研究中，已經(jīng)有比較成熟的技術(shù)。Simon Anders[3]在2009年發(fā)表的文章中實現(xiàn)了使用Hilbert曲線將ChIP-seq數(shù)據(jù)進行二維轉(zhuǎn)換，通過可視化技術(shù)對數(shù)據(jù)進行直觀展示，并表述了其顏色分布的物理意義。

1.3圖像檢索技術(shù) 所謂圖像檢索技術(shù)就是專門處理并提供能夠快速且準(zhǔn)確地查找數(shù)字圖像資源的信息檢索技術(shù)。當(dāng)前業(yè)內(nèi)主要通過數(shù)據(jù)庫和計算機視覺兩個不同的角度來區(qū)分并研究圖像檢索技術(shù)。前者是基于文本的圖像檢索技術(shù)（簡稱TBIR），而后者是基于內(nèi)容的圖像檢索技術(shù) （簡稱CBIR）[4]。本文所用的三種檢索方法，均采用CBIR類技術(shù)。

1.3.1感知哈希函數(shù) 感知哈希是多媒體數(shù)據(jù)集到感知摘要集的一類單向映射，即將具有相同感知內(nèi)容的多媒體數(shù)字表示唯一的映射為一段數(shù)字摘要，并滿足感知魯棒性和安全性[5]。

傳統(tǒng)的圖像感知哈希的構(gòu)造，主要步驟有：圖像預(yù)處理、圖像感知特征提取、加密、量化和編碼[6]?；诒疚牡膽?yīng)用場景及算法要求，主要介紹提取圖像感知特征的過程：①縮小尺寸：去除高頻和細節(jié)的最快方法是縮小圖片，將圖片縮小到8x8的尺寸；②簡化色彩：將8*8的小圖片轉(zhuǎn)換成灰度圖像；③計算平均值：計算所有64個像素的灰度平均值；④比較像素的灰度：將每個像素的灰度，與平均值進行比較，大于或等于平均值記的為1，小于平均值的記為0；⑤計算hash值：將上一步的比較結(jié)果，組合在一起，就構(gòu)成了一個64位的二進制數(shù)，這就是圖片的指紋。

1.3.2顏色直方圖 顏色直方圖是常用的圖像顏色特征表示方法，反映圖像顏色的統(tǒng)計分布，描述的是圖像的整體顏色特征。對于一幅圖像I，其顏色由L級組成，每一種顏色值為Ci（i=1，2，…，L）。在整幅圖像中，具有Ci值的像素個數(shù)為hi，則一組像素的統(tǒng)計值hl，h2，？，hf，就稱為該圖像的顏色直方圖[7]。

顏色直方圖特征的改進算法有很多，比如扇形顏色模型[8]、空間熵結(jié)合[9]和九分塊[10]等等。我們采用的方法是業(yè)界比較成熟的提取算法，主要步驟如下：①將整幅圖像分成4×4塊，計算每一塊中所有象素RGB三個顏色通道的顏色平均值，并以此作為該塊的代表顏色；②將各塊的顏色平均值進行離散余弦變換（DCT），得到DCT系數(shù)矩陣；③對DCT系數(shù)矩陣進行之字形掃描和量化，得到DCT系數(shù)；④對于R、G、B三個通道，分別從DCT系數(shù)中取出4個低頻分量，形成12個參數(shù)，共同構(gòu)成該圖像的顏色特征向量。

1.3.3顏色相關(guān)圖 顏色相關(guān)圖[11]是Huang J博士1997年提出一種新的圖像特征值，它表達了顏色隨距離變換的空間關(guān)系，也就是說顏色相關(guān)圖不僅包含圖像顏色統(tǒng)計信息，同時包括顏色之間的空間關(guān)系。

2方法

2.1生成模擬數(shù)據(jù) 使用R的HilbertVis軟件包[12]生成1000例模擬數(shù)據(jù)，轉(zhuǎn)化為Hilbert曲線并存儲為圖片，見圖1。

圖1 Hilbert曲線圖

2.2生成圖像特征庫 ①預(yù)處理：切割掉圖片的色度標(biāo)注和圖片區(qū)黑框，只保留能真實反映圖片特征的區(qū)域。②將預(yù)處理后的1000張Hilbert圖片分別采用介紹的三種算法提取特征值，并導(dǎo)入MongoDB數(shù)據(jù)庫。

2.3圖像檢索測試 通過比較在1000張圖片中找出10張幾近相同的Hilbert圖片，并抽取1張用于檢索測試，比較三種算法的速度、穩(wěn)健性和一致性。

3結(jié)果

經(jīng)過在1000張圖片中多次檢索測試，計算出感知哈希算法檢索耗時平均約1s，顏色直方圖算法耗時約平均4s，顏色相關(guān)圖耗時平均6s。

取測試結(jié)果排序的前20條數(shù)據(jù)計算整理得到相應(yīng)的查全率和查準(zhǔn)率見表1。

4討論

感知哈希算法考慮的是圖片的概貌，所以速度顯著，但是其計算結(jié)果的查準(zhǔn)率和查全率遠不如顏色直方圖和相關(guān)圖。顏色直方圖刻畫各種顏色的像素數(shù)目占像素總數(shù)目的比例，對顏色的空間分布情況沒有考慮。基于兩種算法的不足，提出了先用感知哈希算法在圖片的概貌上進行篩選然后再使用顏色直方圖進行檢索，提高速度兼顧整體概貌的同時考慮顏色特征，實驗表明，在此測試場景，檢索的效果不理想。如何有效利用兩種算法各自的優(yōu)點，從實驗中可以看出，基于顏色相關(guān)圖的檢索算法是一個比較不錯的選擇，下一步的工作是針對顏色相關(guān)圖調(diào)優(yōu)算法的參數(shù)，提高檢索速度和查全率等。

將一維數(shù)據(jù)進行二維化轉(zhuǎn)換的過程會有數(shù)據(jù)的損失，同時圖片的相似度檢索過程，也是基于圖像主要特征值的計算，會丟失一些不顯著的細節(jié)，這一系列操作必然導(dǎo)致檢索的結(jié)果不夠精細。但是可以確定的是，相關(guān)圖片必定處于檢索的相似結(jié)果集當(dāng)中，通過調(diào)整結(jié)果集的閾值，就可以獲取粗粒度相似范圍的原始數(shù)據(jù)集。在二維檢索的初篩基礎(chǔ)上，再結(jié)合特征識別等技術(shù)在一維序列水平進行局部序列比對的精篩，可大大提升高通量測序數(shù)據(jù)的檢索效率；而單獨使用Blast方法則效率低下，因為全基因組水平的全局序列比對幾無可操作性，分割后的局部序列比對耗時、難以識別關(guān)鍵特征和分配權(quán)重/合理評分，導(dǎo)致結(jié)果缺乏穩(wěn)健性。

本研究可能對醫(yī)學(xué)影像的快速檢索、健康或病理圖片的識別等發(fā)揮發(fā)作用。

參考文獻：

[1]李志鵬.集成化微光學(xué)標(biāo)簽系統(tǒng)的設(shè)計與制作[D].南京：南京郵電大學(xué)，2013.

[2]張瑜.PDF417二維條形碼編解碼的設(shè)計與實現(xiàn)[D].武漢：武漢理工大學(xué)，2012.

[3]Simon Anders. Visualization of genomic data with the Hilbert curve[J]. BIOINFORMATICS， 2009， 25（10）： 1231-1235.

[4]陳劍雄，張蓓.簡析圖像檢索系統(tǒng)中的CBIR技術(shù)[J]. 情報探索， 2010（7）： 98-100

[5]牛夏牧，焦玉華.感知哈希綜述[J].電子學(xué)報，2008，7（7）：1406-1401.

[6]曾勇. 圖形感知哈希算法及應(yīng)用[D].杭州：浙江理工大學(xué)，2012.

[7]魏寶剛，李向陽，魯東明.彩色圖像分割研究進展[J].計算機科學(xué)，1999，26（4）：59-62.

[8]李太君，康耀紅，溫小斌，等.基于改進的顏色直方圖模型的圖像檢索[J].計算機科學(xué)，2006， 33（11）：108-110.

[9]高美真，申艷梅.基于顏色直方圖的圖像檢索技術(shù)[J].微電子學(xué)與計算機，2008，25（4）：25-27.

[10]何亞犇，冀小平.基于九分塊的顏色直方圖圖像檢索算法[J].軟件，2011，32（11）：29-31.

[11]HUANG J， KUMAR R， MITRA M， et al. Image Indexing Using Color Correlograms[C]//Computer Vision and Pattern Recognition， 1997： 762-768.

[12]Simon Anders. Visualising very long data vectors with the Hilbert curve[J].Bioinformatics 2009，25（10）：1231-1235.

編輯/申磊