Earlier Version
Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
Henzinger MH, King V, Warnow T. 1996. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. 7th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 333–340.
Download (ext.)
https://dl.acm.org/doi/10.5555/313852.314080
[Published Version]
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
King, Valerie;
Warnow, Tandy
Abstract
We are given a set 7 = {Tl , Tz, . . . , Tk} of rooted binary trees, each Ti leaf-labeled by a subset L(x) c {1,2 )...) n}. IfT is a tree on {1,2, . . , n}, we let T]L denote the 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’ IC(Ti) is homeomorphic to Ti. 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(mn’/‘), O(m + n2 logn)}, where m = Ci IZl and uses linear space. The randomized algorithm takes
time O(m log3 n) and uses linear space. The previous best for this problem was an 1981 O(mn) 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(n2 log n + be min{ n2, m log n}), where be is the number of batches which do not result in a new component. For our particular application, bc 5 1. If all edges are deleted, then the best previously known deterministic algorithm requires time O(mJ;ii) to solve this problem. computational evolutionary biology. The first application is in the problem of inferring consensus of trees when there can be disagreement[l6]. There have, been several models suggested for this problem[2, 3, 4, 8, ?, 11, 17, 181, of which one is called the Local Consensus Tree[l5]. The local consensus tree model presumes that the user provides a local consensus rule which determines the form of the output tree on (perhaps) each triple of leaves, and the objective is to determine whether a tree exists which is consistent with each of the constraints. We will show that we can construct the local consensus tree of k trees on n species in O(kn3) time, improving on the O(lcn3 + n”) running time if we use the Aho et al algorithm. The second application is a
heuristic for constructing the maximum likelihood tree based upon combining solutions to small subproblems.
This is a simple and yet potentially significantly interesting approach to the evolutionary tree construction
problem.
Publishing Year
Date Published
1996-01-28
Proceedings Title
7th Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher
Society for Industrial and Applied Mathematics
Page
333 -340
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
Atlanta, GA, United States
Conference Date
1996-01-28 – 1996-01-30
ISBN
IST-REx-ID
Cite this
Henzinger MH, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. In: 7th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 1996:333-340.
Henzinger, M. H., King, V., & Warnow, T. (1996). Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. In 7th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 333–340). Atlanta, GA, United States: Society for Industrial and Applied Mathematics.
Henzinger, Monika H, Valerie King, and Tandy Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” In 7th Annual ACM-SIAM Symposium on Discrete Algorithms, 333–40. Society for Industrial and Applied Mathematics, 1996.
M. H. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” in 7th Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, GA, United States, 1996, pp. 333–340.
Henzinger MH, King V, Warnow T. 1996. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. 7th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 333–340.
Henzinger, Monika H., et al. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” 7th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 1996, pp. 333–40.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Material in ISTA:
Later Version