Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
Henzinger MH, King V, Warnow T. 1999. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 24, 1–13.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
King, V.;
Warnow, T.
Corresponding author has ISTA affiliation
Abstract
We are given a set T = {T 1 ,T 2 , . . .,T k } of rooted binary trees, each T i leaf-labeled by a subset L(Ti)⊂{1,2,...,n} . If T is a tree on {1,2, . . .,n }, we let T|L denote the minimal subtree of T induced by the nodes of L and all their ancestors. The consensus tree problem asks whether there exists a tree T * such that, for every i , T∗|L(Ti) is homeomorphic to T i .
We present algorithms which test if a given set of trees has a consensus tree and if so, construct one. The deterministic algorithm takes time min{O(N n 1/2 ), O(N+ n 2 log n )}, where N=∑i|Ti| , and uses linear space. The randomized algorithm takes time O(N log3 n) and uses linear space. The previous best for this problem was a 1981 O(Nn) algorithm by Aho et al. Our faster deterministic algorithm uses a new efficient algorithm for the following interesting dynamic graph problem: Given a graph G with n nodes and m edges and a sequence of b batches of one or more edge deletions, then, after each batch, either find a new component that has just been created or determine that there is no such component. For this problem, we have a simple algorithm with running time O(n 2 log n + b 0 min{n 2 , m log n }), where b 0 is the number of batches which do not result in a new component. For our particular application, b0≤1 . If all edges are deleted, then the best previously known deterministic algorithm requires time O(mn−−√) to solve this problem. We also present two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology.
Publishing Year
Date Published
1999-05-01
Journal Title
Algorithmica
Publisher
Springer Nature
Volume
24
Page
1-13
ISSN
eISSN
IST-REx-ID
Cite this
Henzinger MH, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 1999;24:1-13. doi:10.1007/pl00009268
Henzinger, M. H., King, V., & Warnow, T. (1999). Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. Springer Nature. https://doi.org/10.1007/pl00009268
Henzinger, Monika H, V. King, and T. Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” Algorithmica. Springer Nature, 1999. https://doi.org/10.1007/pl00009268.
M. H. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” Algorithmica, vol. 24. Springer Nature, pp. 1–13, 1999.
Henzinger MH, King V, Warnow T. 1999. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 24, 1–13.
Henzinger, Monika H., et al. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” Algorithmica, vol. 24, Springer Nature, 1999, pp. 1–13, doi:10.1007/pl00009268.
Material in ISTA:
Earlier Version