未来智讯 > 科技创新与应用 > 染色体三维布局的展望要领切磋

染色体三维布局的展望要领切磋

发布时间:2019-01-24 01:07:00 文章来源:威客论坛    

牟锦 郭亚茹 黄月月 刘珂

摘 要:今朝基因组学范畴中染色体三维布局重修是热门切磋问题。已有有关文献证明,基因组的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.

科技立异与应用 2018年29期

科技立异与应用的其它文章 海底管道修复用三通联贯器的设计 球阀壳体的有限元剖析
转载请注明来源。原文地址:https://www.7428.cn/tech/2019/0124/11901/
 与本篇相关的热门内容: