染色體三維結構的預測方法研究

牟錦 郭亞茹 黃月月 劉珂

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

關鍵詞：染色體三維結構重建；Hi-C數據集；算法分析

中圖分類號：Q343.2 文獻標志碼：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

引言

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

1 染色體三維結構重建的經典算法原理

1.1 ShRec3D算法原理

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

1.2 Chrome SDE算法原理

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

1.3 基于變參數流形優化方法VMBO原理

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

2 算法比較

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

3 結合幾種經典方法提出新的方法

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

3.1 算法流程

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

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

3.2 性能比較

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

張衛等將Chrome SDE算法中可變參數的思想用在ShRec3D算法上提出了ShRec3D+算法。并針對Hi-C數據集，使用ShRec3D+算法對染色體三維結構進行了實驗預測。

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

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

4 結束語

該綜述對染色體三維結構重建的經典距離算法模型的原理進行了總結介紹，并對Hi-C數據集下方法的預測性能進行了討論。將幾種方法取長補短提出了一種新的預測方法，并對預測性能結果進行討論。使我們能更準確系統的掌握染色體三維結構重建問題的發展方向。為后期染色體三維結構重建研究方向奠定了理論基礎，有利于進一步深入學習和探討。

參考文獻：

[1]陶婧芬，謝婷，鄭覺非，等.基于染色質交互數據的基因組組裝方法[J].生物技術通報，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]胡文橋，侯越，張峰，等.染色質構象解析技術——Hi-C及染色質構象信息提取[J].基因組學與應用生物學，2015，34（11）：002319-2327.

[9]彭城，李國亮，張紅雨，等.染色質三維結構重建及其生物學意義[J].中國科學：生命科學，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].沈陽航空工業大學學報，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]張衛.基于Hi-C數據的預測染色體三維結構的方法研究[D].北京工業大學，2016.

[17]李建更，張衛，李曉丹.基于參數優化的染色體三維結構預測算法VMBO[J].北京工業大學學報，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.