在一定近似下，可以采用以下简化格式:DNA被认为是{中的一个很长的序列一个，C，T，G}字母表。序列中具有特定位置的某些区域具有特定的作用，称为基因。部分有序的dna基因集可以认为是基因组。邻近基因之间的区域(基因间区)也可以通过触发后续基因的活动来发挥功能，并且被认为含有a监管的信号，起到开关的作用。调控信号也可以包含在基因组中。

进化是任何在时间上发展的过程。基因、调控信号和基因组的进化是进化的特殊案例。为简单起见，只考虑演化对象的一个属性，而忽略所有其他属性。在这里，我们忽略基因的文本内容;在这种情况下，DNA由一组常规片段(例如单位长度)表示，每个片段代表一个基因，而基因之间的距离和基因间区域的内容也被忽略。我们可以方便地认为这些区域的长度为零，即相邻基因的端点被合并在一起。每个基因都可以读(他们的阅读是生命的基本过程之一)有两个方向:从左到右和从右到左。因此，每个线段都是有向的，因此是一个矢量。在这种情况下，基因组是由有向路径和圆组成的图。分析这类图具有数学意义。这样的图称为aCC-graph繁殖的染色体结构的基因组。

在这里，进化包括基因的重新定位;对应的事件称为进化。汇编一个进化事件的简短列表是可能的。它们可以分为具有特定成本的正数类型。一个基因组可以通过一系列进化事件转化为另一个基因组。就cc -图而言，一个cc -图可以通过对cc -图的一系列确定的操作转换为另一个cc -图，每个操作对应于一个自然事件。

第一个问题给定两个cc图，找出一系列进化事件(操作)，将第一个图转换为第二个最小值图总成本。这个最小成本将被称为距离在这些cc图之间。重要的是不仅要找到距离，而且要找到最低(或最短的）进化事件的顺序。因此，第一个问题的解决方案描述了一个基因组在染色体结构水平上向另一个基因组的可能进化。

第二个问题:给定一组cc图;让它们对应于某一棵树的叶子年代这是我们还不知道的。假设树的所有内部节点(即除叶子节点外的所有节点)年代任意分配给任意cc图。这棵树年代这样的作业将被称为安排。每个排列都有一个成本，对于树的所有边，在一条边的两端cc图之间的距离之和年代。找一棵树年代用最小的成本来安排。因此，第二个问题的解决方案描述了一组基因组(例如，在给定物种中)在染色体结构水平上的可能进化。解决方案排列称为重建在整棵树的叶子中定义的染色体结构。这两个问题及其公式的扩展都是非常有趣的。这棵树年代被称为系统发育。上面对树的所有边求和年代(或类似的值)称为功能。

系统基因组学的主要目标之一是沿着整个系统发育树重建在叶子中定义的对象，以最小化指定成本(功能)，这也可能包括系统发育树生成本身。这些对象可以包括核苷酸和氨基酸序列、染色体结构等。这种结构可以有任何一组线性和圆形染色体，可变的基因组成，包括任何数量的类似物，以及任何权重的个体进化操作来改变染色体结构。为此提出了许多启发式算法，但只有少数几种精确算法其中多项式计算复杂度较高。这些算法自然是从计算两个结构之间的距离和将一个结构转换为另一个结构的最短操作序列开始的。这样的计算本身就是一个np困难问题。

考虑了染色体结构重排的一般模型。具有几乎线性或三次多项式复杂度的精确算法已经被开发出来，用于解决任何染色体结构的问题，但在运算权值上有一定的限制。针对线粒体或质体染色体结构重建问题，对计算机程序进行了生物学数据测试。据我们所知，这种型号没有可用的计算机程序。

证明了所提算法的准确性和较低的多项式复杂度。重建的线粒体和质体染色体结构的进化树以及这些结构的祖先状态似乎是合理的。

瓦西里Lyubetsky
俄罗斯科学院信息传输问题研究所
(Kharkevich研究所),
罗蒙诺索夫莫斯科国立大学

出版

染色体结构重建算法。
吕贝茨基V，格什戈林R, Seliverstov A, Gorbunov K
BMC生物信息学。2016年1月19日

离线阅读:

相关文章:

	4亿年前视紫红质基因的逆转录动物利用环境中的光作为重要的信息来源。我们可以通过视觉系统来辨别物体的颜色、亮度和形状。此外，动物还能探测到日常和季节性……
	表观遗传表型多样化有助于动物适应…越来越多的证据表明，表观遗传表型变异有助于环境适应、物种形成和进化。表型的表观遗传变化是由基因表达差异引起的，而不是由基因表达差异引起的。
	miRNA，一个不起眼但在发育过程中的关键角色…在一些国家，宫颈癌是影响45岁以下妇女的三大癌症之一。脱氧核糖核酸(DNA)序列的改变和修饰都起着关键作用。
	快速监测多种微生物感染的影响……细菌感染的发展是一项重大挑战，因为致病菌在医疗机构中传播，患者可能接触到在医院大量定植的复杂细菌群落。
	ACTN3基因真的是马的“速度基因”吗?人类编码α-肌动蛋白-3的ACTN3基因被认为是决定短期或长期运动(短跑或耐力)倾向的关键因素。此外，在…
	预测传感:运动信号在传感中的作用。大脑接收感官信息，并利用它来构建我们环境的表征，并指导我们的行为。然而，这些自愿行为反过来也会刺激……