牟锦 郭亚茹 黄月月 刘珂

摘 要：目前基因组学领域中染色体三维结构重建是热点研究问题。已有相关文献表明，基因组的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.