×

Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms. (English) Zbl 0885.68071

Summary: The maximum agreement subtree approach is one method of reconciling different evolutionary trees for the same set of species. An agreement subtree enables a subset of the species for whom the restricted subtree is equivalent (under a suitable definition) in all given evolutionary trees.
Recently, dynamic programming ideas were used to provide polynomial time algorithms for finding a maximum homeomorphic agreement subtree of two trees. Generalizing these methods to sets of more than two trees yields algorithms that are exponential in the number of trees. Unfortunately, it turns out that in reality one is usually presented with more than two trees, sometimes as many as thousands of trees.
In this paper, we prove that the maximum homeomorphic agreement subtree problem is NP-complete for three trees with unbounded degrees. We then show an approximation algorithm of time \(O(kn^5)\) for choosing the species that are not in a maximum agreement subtree of a set of \(k\) trees. Our approximation is guaranteed to provide a set that is no more than 4 times the optimum solution.
While the set of evolutionary trees may be large in practice, the trees usually have very small degrees, typically no larger than three. We develop a new method for finding a maximum agreement subtree of \(k\) trees, of which one has degree bounded by \(d\). This new method enables us to find a maximum agreement subtree in time \(O(kn^d+ 1+ n^{2d})\).

MSC:

68W10 Parallel algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI