牟錦 郭亞茹 黃月月 劉珂

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

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

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

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

1.1 ShRec3D算法原理

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

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)化過程中對(duì)估算的距離（即較長(zhǎng)的距離）取較小的加權(quán)值，以這種形式解決極小化問題，該方法在三維結(jié)構(gòu)重建中的權(quán)值可以取任意非負(fù)值（不僅僅是0和1）[16]，使得VMBO算法可以預(yù)測(cè)不同分辨率下的數(shù)據(jù)集的結(jié)構(gòu)。

2 算法比較

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

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

在Chrome SDE算法中，輸入不一樣的細(xì)胞系或不同分辨率的Hi-C數(shù)據(jù)時(shí)通過接觸頻率轉(zhuǎn)化為相對(duì)應(yīng)的空間距離值的轉(zhuǎn)換函數(shù)中的參數(shù)是變化的，再用semi-define programming方法準(zhǔn)確的定位每個(gè)染色體片段所在的三維空間坐標(biāo)；而ShRec3D方法用了Shortest-distance算法，在距離矩陣中填補(bǔ)了空缺的元素值，調(diào)整染色體片段間的空間距離，并增加接觸頻率值高的染色體片段的權(quán)重值，卻不能對(duì)不同的Hi-C數(shù)據(jù)對(duì)轉(zhuǎn)化參數(shù)進(jìn)行變化調(diào)整，降低了ShRec3D算法的適用性，因此將Chrome SDE方法的這一優(yōu)點(diǎn)與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í)驗(yàn)分析后得出參數(shù)值取？琢∈（0，1.2）最佳[16]。

3.1 算法流程

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

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

3.2 性能比較

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

[1]陶婧芬，謝婷，鄭覺非，等.基于染色質(zhì)交互數(shù)據(jù)的基因組組裝方法[J].生物技術(shù)通報(bào)，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]彭城，李國(guó)亮，張紅雨，等.染色質(zhì)三維結(jié)構(gòu)重建及其生物學(xué)意義[J].中國(guó)科學(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]項(xiàng)榮武，劉艷杰，胡忠盛.圖論中最短路徑問題的解法[J].沈陽航空工業(yè)大學(xué)學(xué)報(bào)，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ù)測(cè)染色體三維結(jié)構(gòu)的方法研究[D].北京工業(yè)大學(xué)，2016.

[17]李建更，張衛(wèi)，李曉丹.基于參數(shù)優(yōu)化的染色體三維結(jié)構(gòu)預(yù)測(cè)算法VMBO[J].北京工業(yè)大學(xué)學(xué)報(bào)，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.