A Reduction Algorithm for Computing The Hybridization Number of Two Trees
A Reduction Algorithm for Computing The Hybridization Number of Two Trees
复制标题
DOI：
10.1177/117693430700300017
复制
发表时间：
2007-05
期刊：
影响因子：
--
通讯作者：
M. Bordewich;S. Linz;Katherine St. John;C. Semple
中科院分区：
文献类型：
--
作者：
M. Bordewich;S. Linz;Katherine St. John;C. Semple
对于许多物种群体来说，杂交是一个重要的进化过程。因此，数据集中的冲突信号可能不是采样或建模错误的结果，而是由于杂交在所考虑的物种的进化历史中发挥了重要作用的事实。假设最初的基因树集是正确的，生物学家的一个基本问题是计算杂交事件的最小数量来解释该集。在本文中，我们描述了一种新的基于约简的算法，用于在初始数据集由两棵树组成时计算最小数。尽管二树问题是 NP 难问题，但我们的算法总是给出精确的解，并且在许多实际的生物问题上运行高效。以前的二树问题算法要么解决问题的受限版本，要么给出不保证与精确解接近的答案。我们在草地数据集上说明我们的算法。这种新算法可在 http://www.bi.uni-duesseldorf.de/~linz 或 http://www.math.canterbury.ac.nz/~cas83 上免费使用。
Hybridization is an important evolutionary process for many groups of species. Thus, conflicting signals in a data set may not be the result of sampling or modeling errors, but due to the fact that hybridization has played a significant role in the evolutionary history of the species under consideration. Assuming that the initial set of gene trees is correct, a basic problem for biologists is to compute this minimum number of hybridization events to explain this set. In this paper, we describe a new reduction-based algorithm for computing the minimum number, when the initial data set consists of two trees. Although the two-tree problem is NP-hard, our algorithm always gives the exact solution and runs efficiently on many real biological problems. Previous algorithms for the two-tree problem either solve a restricted version of the problem or give an answer with no guarantee of the closeness to the exact solution. We illustrate our algorithm on a grass data set. This new algorithm is freely available for application at either http://www.bi.uni-duesseldorf.de/~linz or http://www.math.canterbury.ac.nz/~cas83.