On the complexity of comparing evolutionary trees
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 153-169 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 71 |
Issue number | 1-3 |
Publication status | Published - Dec 1996 |
Externally published | Yes |
Link(s)
Abstract
We study the computational complexity and approximation of several problems arising in the comparison of evolutionary trees. It is shown that the maximum agreement subtree (MAST) problem for three trees with unbounded degree cannot be approximated within ratio 2logδ n in polynomial time for any δ <1, unless NP ⊆ DTIME[2polylog n], and MAST with edge contractions for two binary trees is NP-hard. This answers two open questions posed in [1]. For the maximum refinement subtree (MRST) problem involving two trees, we show that it is polynomial-time solvable when both trees have bounded degree and is NP-hard when one of the trees can have an arbitrary degree. Finally, we consider the problem of optimally transforming a tree into another by transferring subtrees around. It is shown that computing the subtree-transfer distance is NP-hard and an approximation algorithm with performance ratio 3 is given.
Research Area(s)
- Approximation algorithm, Compatibility, Computational complexity, Evolutionary tree, Phylogeny, Recombination
Citation Format(s)
On the complexity of comparing evolutionary trees. / Hein, Jotun; Jiang, Tao; Wang, Lusheng et al.
In: Discrete Applied Mathematics, Vol. 71, No. 1-3, 12.1996, p. 153-169.
In: Discrete Applied Mathematics, Vol. 71, No. 1-3, 12.1996, p. 153-169.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review