牟錦 郭亞茹 黃月月 劉珂

摘 要：目前基因組學(xué)領(lǐng)域中染色體三維結(jié)構(gòu)重建是熱點研究問題。已有相關(guān)文獻表明，基因組的DNA突變、復(fù)制、胚胎的發(fā)育和轉(zhuǎn)錄長鏈非編碼RNA的傳播等跟染色質(zhì)的三維結(jié)構(gòu)有著密切的關(guān)聯(lián)。Hi-C實驗提供基因組位點之間的接觸頻率的全基因組圖譜，推測反映其染色體的平均空間組織。文中通過在Hi-C數(shù)據(jù)基礎(chǔ)上對染色體三維結(jié)構(gòu)重建的相關(guān)文獻進行分析，總結(jié)了目前重建染色體三維空間結(jié)構(gòu)的經(jīng)典算法原理和性能，以期能更深入地研究染色體三維結(jié)構(gòu)重建算法，并系統(tǒng)的掌握三維染色體空間結(jié)構(gòu)預(yù)測算法的發(fā)展方向。

關(guān)鍵詞：染色體三維結(jié)構(gòu)重建；Hi-C數(shù)據(jù)集；算法分析

中圖分類號：Q343.2 文獻標(biāo)志碼：A 文章編號：2095-2945（2018）29-0004-03

Abstract： At present， the three-dimensional structure reconstruction of chromosome is a hot research issue in the field of genomics. It has been shown that genomic DNA mutation， replication， embryonic development and transmission of long strand noncoding RNA are closely related to the three-dimensional structure of chromatin. The Hi-C experiment provides a genome-wide map of the contact frequency between genomic sites， presumably reflecting the average spatial organization of its chromosomes. In this paper， based on the analysis of the related literatures on chromosome 3D structure reconstruction based on Hi-C data， the principle and performance of the classical algorithms for chromosome 3D structure reconstruction are summarized. With a view to more in-depth study of chromosome three-dimensional structure reconstruction algorithm， and systematically grasp the development direction of three-dimensional chromosome space structure prediction algorithm.

Keywords： three-dimensional （3D） chromosome structure reconstruction； Hi-C data set； algorithm analysis

引言

重建染色體三維結(jié)構(gòu)即是通過染色質(zhì)的二維交互頻率數(shù)據(jù)來預(yù)測其三維空間的結(jié)構(gòu)。已有相關(guān)文獻表明，基因組的表達，調(diào)控及DNA突變、復(fù)制、胚胎的發(fā)育和轉(zhuǎn)錄長鏈非編碼RNA的傳播以及維護基因組穩(wěn)定性等跟染色質(zhì)的三維結(jié)構(gòu)有著密切的關(guān)聯(lián)[1-6]。目前通過Hi-C技術(shù)[7]，能高通量地獲取多個物種的全基因組的交互作用信息，再對生成的二維接觸矩陣[8]進行處理，并用于預(yù)測染色體的三維結(jié)構(gòu)[9]。目前的預(yù)測算法可根據(jù)模型原理不同分為概率約束和距離約束[10]兩類。這些預(yù)測模型算法有助于人們對染色體三維折疊空間結(jié)構(gòu)有更清晰的認(rèn)識，也為了解其調(diào)控以及對基因組穩(wěn)定性功能和解析相關(guān)的生物過程提供了理論結(jié)構(gòu)依據(jù)。

1 染色體三維結(jié)構(gòu)重建的經(jīng)典算法原理

1.1 ShRec3D算法原理

ShRec3D算法是一種距離約束優(yōu)化模型算法，它通過兩步來建立預(yù)測模型。首先將接觸頻率歸一化并轉(zhuǎn)換為空間距離信息，然后用Shortest distance algorithm[11]重新分配片段間的空間距離并填充距離矩陣中的缺失值，調(diào)整對應(yīng)的不同接觸頻率的距離權(quán)重，將Multidimensional Scaling算法與ShRec3D相結(jié)合來可以有效地重建染色體三維模型[12]，減少時間復(fù)雜度，避免了算法在迭代優(yōu)化過程中遇到的局部收斂問題，在稀疏和噪聲的接觸映射問題中有較強的適用性。

1.2 Chrome SDE算法原理

Chrome SDE（Chromosome semi-definite embedding）也是一種距離約束模型算法。采用semi-define programming約束將空間距離矩陣信息轉(zhuǎn)化為染色體片段的三維空間坐標(biāo)矩陣信息。從理論上證明了semi-define programming[13]算法能夠無噪聲地唯一恢復(fù)三維空間結(jié)構(gòu)。在Chrome SDE中，將變參數(shù)引入到接觸頻率與空間距離轉(zhuǎn)換函數(shù)中[14]，并采用黃金分割算法在一定區(qū)域中尋找最優(yōu)轉(zhuǎn)換參數(shù)。黃金分割算法除要求函數(shù)是單峰外再無限制，因此它有廣泛的應(yīng)用。

1.3 基于變參數(shù)流形優(yōu)化方法VMBO原理

變參數(shù)流行優(yōu)化方法（variable parameter manifold based optimization， VMBO）是在基于流形的優(yōu)化（manifold based optimization， MBO）基礎(chǔ)上引入指數(shù)可變的轉(zhuǎn)換函數(shù)得到的，通過Euclidean distance matrix的低秩特征并利用距離冗余推斷出矩陣中缺失的距離值[15]。再將最短路徑距離與權(quán)重相結(jié)合，在優(yōu)化過程中對估算的距離（即較長的距離）取較小的加權(quán)值，以這種形式解決極小化問題，該方法在三維結(jié)構(gòu)重建中的權(quán)值可以取任意非負(fù)值（不僅僅是0和1）[16]，使得VMBO算法可以預(yù)測不同分辨率下的數(shù)據(jù)集的結(jié)構(gòu)。

2 算法比較

李更建等將VMBO算法與Chrome SDE和ShRec3D對老鼠胚胎干細(xì)胞（mouse embryonic stem cells， mESC）細(xì)胞系和GM06990細(xì)胞系做了實驗預(yù)測并通過斯皮爾曼相關(guān)系數(shù)（即distance spearman correlation coefficient， dSCC數(shù)值越接近1性能越好）進行比較：對于老鼠胚胎干細(xì)胞（mouse embryonic stem cells， mESC）細(xì)胞系，VMBO算法dSCC數(shù)值為0.988相對于ShRec3D算法的0.982和Chrome SDE算法的0.974都高，這些數(shù)值都很高說明三種算法的預(yù)測性能都很好。而對于GM-HicNorm數(shù)據(jù)集，VMBO算法的dSCC為0.874優(yōu)于ShRec3D算法的0.836卻低于Chrome SDE算法的0.952[17]。因此VMBO算法對于GM細(xì)胞系的結(jié)構(gòu)預(yù)測性能優(yōu)于ShRec3D方法，但是低于Chrome SDE方法。兩個數(shù)據(jù)集中Chrome SDE方法的平均dSCC數(shù)值都大于ShRec3D，因此總的來說，Chrome SDE比ShRec3D方法預(yù)測性能更好，而Chrome SDE對GM細(xì)胞系的預(yù)測性能最好。

3 結(jié)合幾種經(jīng)典方法提出新的方法

在Chrome SDE算法中，輸入不一樣的細(xì)胞系或不同分辨率的Hi-C數(shù)據(jù)時通過接觸頻率轉(zhuǎn)化為相對應(yīng)的空間距離值的轉(zhuǎn)換函數(shù)中的參數(shù)是變化的，再用semi-define programming方法準(zhǔn)確的定位每個染色體片段所在的三維空間坐標(biāo)；而ShRec3D方法用了Shortest-distance算法，在距離矩陣中填補了空缺的元素值，調(diào)整染色體片段間的空間距離，并增加接觸頻率值高的染色體片段的權(quán)重值，卻不能對不同的Hi-C數(shù)據(jù)對轉(zhuǎn)化參數(shù)進行變化調(diào)整，降低了ShRec3D算法的適用性，因此將Chrome SDE方法的這一優(yōu)點與ShRec3D算法相結(jié)合提出一種隨不同Hi-C數(shù)據(jù)變化函數(shù)參數(shù)的算法，即ShRec3D+算法，再通過黃金分割算法迭代得到最優(yōu)參數(shù)值。接觸距離矩陣轉(zhuǎn)化為空間距離矩陣的函數(shù)[18]為Dijt=Fij-？琢，F(xiàn)ij>0∞，otherwise，經(jīng)過實驗分析后得出參數(shù)值??？琢∈（0，1.2）最佳[16]。

3.1 算法流程

ShRec3D+算法的流程見圖1所示。

其中函數(shù)error（F，？琢）的計算過程如下：已知某個？琢值，利用（1/F）？琢求出D，再使用Multidimensional Scaling方法將D轉(zhuǎn)化成X，基于X計算出任意片段的歐氏距離D'，再根據(jù)（1-D'）？琢算出F'，再計算|Fij'-Fij|。

3.2 性能比較

3.2.1 準(zhǔn)確性比較。張衛(wèi)等對有噪聲的Helix結(jié)構(gòu)數(shù)據(jù)集進行了實驗?zāi)M，設(shè)置轉(zhuǎn)換參數(shù)為1.0，而采用點數(shù)為100。實驗得出在小于0.3的噪聲值時，Chrome SDE、ShRec3D和ShRec3D+算法都能有效的構(gòu)造Helix模擬結(jié)構(gòu)[16]，并且Chrome SDE的預(yù)測性能要比ShRec3D+算法的性能好，能在無噪音下準(zhǔn)確預(yù)測三維空間結(jié)構(gòu)折疊情況。在Multidimensional Scaling計算過程中，轉(zhuǎn)化為其對應(yīng)的坐標(biāo)值時，只取了最大的三個特征值和相應(yīng)的特征向量，致使ShRec3D+無法預(yù)測出唯一的三維結(jié)構(gòu)。但在噪聲增強的情況下，ShRec3D+算法比Chrome SDE算法的預(yù)測性能要好。這兩種算法都需要迭代尋找最佳的轉(zhuǎn)換參數(shù)，因此可以對兩者的建模效率進行比較。然而在大規(guī)模的問題中，ShRec3D+算法比Chrome SDE算法效率要高，semi-define programming算法在理論上計算時間復(fù)雜度較高，因此不適宜處理大規(guī)模數(shù)據(jù)問題。

張衛(wèi)等將Chrome SDE算法中可變參數(shù)的思想用在ShRec3D算法上提出了ShRec3D+算法。并針對Hi-C數(shù)據(jù)集，使用ShRec3D+算法對染色體三維結(jié)構(gòu)進行了實驗預(yù)測。

實驗得出，ShRec3D+算法在mESC細(xì)胞系中dSCC為0.994較Chrome SDE的Dscc0.974和ShRec3D中的0.982都要高一點，雖三種方法都能有較好的預(yù)測性能，但ShRec3D+算法的結(jié)構(gòu)預(yù)測效果要更好一些，然而在GM細(xì)胞系數(shù)據(jù)中，Chrome SDE算法的dSCC值為0.857比ShRec3D算法的0.687和ShRec3D+算法的0.789都高，其預(yù)測性能是最好的[16]。

3.2.2 時間性能比較。從張衛(wèi)等的實驗結(jié)果得出在1MB分辨率下的mESC細(xì)胞系Hind3和NcoI兩種限制性內(nèi)切酶作用下的Hi-C數(shù)據(jù)集中，ShRec3D+算法所花的時間分別為627s和639s，Chrome SDE方法卻需要4528s和4485s，而ShRec3D算法所需時間僅為105s和109s。ShRec3D+算法的效率遠遠高于Chrome SDE算法，卻不及ShRec3D算法效率高。在GM細(xì)胞系Hind3和NcoI兩種限制性內(nèi)切酶作用下的Hi-C數(shù)據(jù)集中，ShRec3D+算法所需的時間為569s和697s，Chrome SDE方法卻需要4286s和4218s，而ShRec3D算法所需時間僅為64s和66s[16]。其原因是由于semi-define programming算法效率低下，不能直接求解大規(guī)模問題，但ShRec3D算法不需要迭代參數(shù)進行優(yōu)化，效率則高于ShRec3D+算法。

4 結(jié)束語

該綜述對染色體三維結(jié)構(gòu)重建的經(jīng)典距離算法模型的原理進行了總結(jié)介紹，并對Hi-C數(shù)據(jù)集下方法的預(yù)測性能進行了討論。將幾種方法取長補短提出了一種新的預(yù)測方法，并對預(yù)測性能結(jié)果進行討論。使我們能更準(zhǔn)確系統(tǒng)的掌握染色體三維結(jié)構(gòu)重建問題的發(fā)展方向。為后期染色體三維結(jié)構(gòu)重建研究方向奠定了理論基礎(chǔ)，有利于進一步深入學(xué)習(xí)和探討。

參考文獻：

[1]陶婧芬，謝婷，鄭覺非，等.基于染色質(zhì)交互數(shù)據(jù)的基因組組裝方法[J].生物技術(shù)通報，2015，31（11）：43-50.

[2]Misteli T. Spatial positioning； a new dimension in genome function [J]. Cell， 2004，119（2）：153-156.

[3]Frederick W. Alt， Zhang Y， Meng F L， et al. Mechanisms of Programmed DNA Lesions and Genomic Instability in the Immune System[J]. Cell， 2013， 152（3）：417-429.

[4]Fraser P， Bickmore W. Nuclear organization of the genome and the potential for gene regulation.[J]. Nature，2007，447（7143）：413-417.

[5]Miele A， Dekker J. Long-range chromosomal interactions and gene regulation. [J]. Molecular Biosystems， 2008，4（11）：1046-1057.

[6]Dekker J. Gene Regulation in the Third Dimension.[J]. Science， 2008，319（5871）：1793-1794.

[7]Reza Kalhor， Haritanto Tjong， et al， Genome Architectures Revealed by Tethered Chromosome Conformation Capture and Population-based Modeling. [J]. Nature Biotechnology， 2012，30：90-98.

[8]胡文橋，侯越，張峰，等.染色質(zhì)構(gòu)象解析技術(shù)——Hi-C及染色質(zhì)構(gòu)象信息提取[J].基因組學(xué)與應(yīng)用生物學(xué)，2015，34（11）：002319-2327.

[9]彭城，李國亮，張紅雨，等.染色質(zhì)三維結(jié)構(gòu)重建及其生物學(xué)意義[J].中國科學(xué)：生命科學(xué)，2014（8）：794-802.

[10]SERRA F， DI STEFANO M， SPILL Y G， et al. Restraint based three-dimensional modeling of genomes and genomic

domains. [J]. FEBS Letter， 2015，20（589）：2987-2995.

[11]項榮武，劉艷杰，胡忠盛.圖論中最短路徑問題的解法[J].沈陽航空工業(yè)大學(xué)學(xué)報，2004，21（2）：86-88.

[12]Buja A， Swayne D F， Littman M L， et al. XGvis： Interactive Data Visualization with Multidimensional Scaling[J]. Journal of

Computational & Graphical Statistics， 2001，17（2）：444-472.

[13]Leung， N.， and Toh， K. An SDP-based Divide-and-Conquer Algorithm for Large-Scale Noisy Anchor-Free Graph Realization[J]. SIAM Journal on Scientific Computing， 2009，31：4351-4372.

[14]Lesne A， Riposo J， Roger P， et al. 3D genome reconstruction from chromosomal contacts[J].Nature Methods，2014，11（11）：1141.

[15]Paulsen J， Gramstad O， Collas P. Manifold Based Optimization for Single-Cell 3D Genome Reconstruction [J]. Plos Computational Biology， 2015，11（8）：e1004396.

[16]張衛(wèi).基于Hi-C數(shù)據(jù)的預(yù)測染色體三維結(jié)構(gòu)的方法研究[D].北京工業(yè)大學(xué)，2016.

[17]李建更，張衛(wèi)，李曉丹.基于參數(shù)優(yōu)化的染色體三維結(jié)構(gòu)預(yù)測算法VMBO[J].北京工業(yè)大學(xué)學(xué)報，2018，44（2）：207-214.

[18]Zhang Z， Li G， Toh K C， et al. 3D chromosome modeling with semi-definite programming and Hi-C data[J]. Journal of Computational Biology A Journal of Computational Molecular Cell Biology，2013，20（11）：831.