Computing the Diameter of the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model
Computing the Diameter of the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model
复制标题
DOI：
10.1109/tcbb.2018.2849732
复制
发表时间：
2019-01-01
影响因子：
4.5
通讯作者：
Libeskind-Hadas, Ran
中科院分区：
文献类型：
--
作者：
Haack, Jordan;Zupke, Eli;Libeskind-Hadas, Ran
系统发育树和解被广泛应用于分子进化、共同进化、寄生虫学和生物地理学等领域，用于研究实体对的进化史。在这些上下文中，在重复-传输-丢失（DTL）事件模型下，调和通常使用最大限度的节约来执行。一般来说，最大简约调节（mpr）的数量会随着树的大小呈指数增长。虽然之前已经做了许多努力来计算MPR的数量，找到具有代表性的MPR，并计算跨MPR空间的事件频率，但对MPR空间的结构知之甚少。特别是，mpr在它们所包含的事件方面有何不同？解决这个问题的一种方法是计算MPR空间的直径，定义为区分解空间中任意两个MPR的DTL事件的最大数量。我们展示了如何在多项式时间内计算MPR空间的直径，然后将该算法应用于大型生物数据集来研究事件的可变性。
Phylogenetic tree reconciliation is widely used in the fields of molecular evolution, cophylogenetics, parasitology, and biogeography to study the evolutionary histories of pairs of entities. In these contexts, reconciliation is often performed using maximum parsimony under the Duplication-Transfer-Loss (DTL) event model. In general, the number of maximum parsimony reconciliations (MPRs) can grow exponentially with the size of the trees. While a number of previous efforts have been made to count the number of MPRs, find representative MPRs, and compute the frequencies of events across the space of MPRs, little is known about the structure of MPR space. In particular, how different are MPRs in terms of the events that they comprise? One way to address this question is to compute the diameter of MPR space, defined to be the maximum number of DTL events that distinguish any two MPRs in the solution space. We show how to compute the diameter of MPR space in polynomial time and then apply this algorithm to a large biological dataset to study the variability of events.