DLS-trees:: A model of evolutionary scenarios
DLS-trees:: A model of evolutionary scenarios
复制标题
DOI：
10.1016/j.tcs.2006.05.019
复制
发表时间：
2006-08-14
影响因子：
1.1
通讯作者：
Tiuryn, Jerzy
中科院分区：
文献类型：
--
作者：
Gorecki, Pawel;Tiuryn, Jerzy
我们提出了一个物种进化背景下的基因树进化模型。其概念类似于和解模式。我们假设基因进化是由复制和丢失来模拟的。物种的进化是由物种形成事件来模拟的。我们定义了一个进化的场景（称为DLS树），它可以代表物种中的基因进化。我们感兴趣的是一个给定的物种树和一个给定的基因树的所有方案，而不仅仅是吝啬的。我们提出了一个重写系统，用于转换的场景。我们证明了该系统是融合的，健全的和强正规化的。我们证明了一个正常形式的场景（即，不可约的）是唯一的，并且在作为基因复制和丢失的总数计算的成本（突变成本）的意义上是最小的。我们提出了一个分类的情况下，并分析其层次结构。最后，我们证明了协调树可以很容易地转化为标准形式的DLS-树。这解决了和解树的一些开放问题。(C)2006 Elsevier B. V.保留所有权利。
We present a model of evolution of gene trees in the context of species evolution. Its concept is similar to reconciliation models. We assume that the gene evolution is modelled by duplications and losses. Evolution of species is modelled by speciation events. We define an evolutionary scenario (called a DLS-tree) which can represent an evolution of genes in species. We are interested in all scenarios for a given species tree and a given gene tree-not only parsimonious ones. We propose a rewrite system for transforming the scenarios. We prove that the system is confluent, sound and strongly normalizing. We show that a scenario in normal form (i.e., non-reducible) is unique and minimal in the sense of the cost computed as the total number of gene duplications and losses (mutation cost). We present a classification of the scenarios and analyze their hierarchy. Finally, we prove that the reconciled tree can be easily transformed into DLS-tree in normal form. This solves some open problems for reconciled trees. (C) 2006 Elsevier B.V. All rights reserved.