### Abstract

We are given a set script T sign = {T_{1}, T2, . . . , T_{k}) of rooted binary trees, each T_{i} leaf-labeled by a subset ℒ(T_{i}] ⊂ {1,2, . . . , n}. If T is a tree on {1, 2, . . . , n}, we let T\ℒ denote the minimal subtree of T induced by the nodes of ℒ and all their ancestors. The consensus tree problem asks whether there exists a tree T* such that, for every i, T*\ℒ(T_{i}) is homeomorphic to T_{i}. We present algorithms which test if a given sel 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} \T_{i}\, and uses linear space. The randomized algorithm takes time O (N log^{3} n) and uses linear space. The previous best for this problem was a 1981 O (N n) 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 b_{0} ≤ 1. If all edges are deleted, then the best previously known deterministic algorithm requires time O (m √n) to solve this problem. We also present two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology.

Original language | English (US) |
---|---|

Pages (from-to) | 1-13 |

Number of pages | 13 |

Journal | Algorithmica (New York) |

Volume | 24 |

Issue number | 1 |

DOIs | |

State | Published - May 1999 |

Externally published | Yes |

### Fingerprint

### Keywords

- Algorithms
- Data structures
- Evolutionary biology
- Theory of databases

### ASJC Scopus subject areas

- Computer Graphics and Computer-Aided Design
- Software
- Safety, Risk, Reliability and Quality
- Applied Mathematics

### Cite this

*Algorithmica (New York)*,

*24*(1), 1-13. https://doi.org/10.1007/PL00009268

**Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology.** / Henzinger, M. R.; King, V.; Warnow, T.

Research output: Contribution to journal › Article

*Algorithmica (New York)*, vol. 24, no. 1, pp. 1-13. https://doi.org/10.1007/PL00009268

}

TY - JOUR

T1 - Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology

AU - Henzinger, M. R.

AU - King, V.

AU - Warnow, T.

PY - 1999/5

Y1 - 1999/5

N2 - We are given a set script T sign = {T1, T2, . . . , Tk) of rooted binary trees, each Ti leaf-labeled by a subset ℒ(Ti] ⊂ {1,2, . . . , n}. If T is a tree on {1, 2, . . . , n}, we let T\ℒ denote the minimal subtree of T induced by the nodes of ℒ and all their ancestors. The consensus tree problem asks whether there exists a tree T* such that, for every i, T*\ℒ(Ti) is homeomorphic to Ti. We present algorithms which test if a given sel of trees has a consensus tree and if so. construct one. The deterministic algorithm takes time min{ O (N n1/2), O (N + n2 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 (N n) 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 + b0 min{n2, m log n}), where b0 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 (m √n) to solve this problem. We also present two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology.

AB - We are given a set script T sign = {T1, T2, . . . , Tk) of rooted binary trees, each Ti leaf-labeled by a subset ℒ(Ti] ⊂ {1,2, . . . , n}. If T is a tree on {1, 2, . . . , n}, we let T\ℒ denote the minimal subtree of T induced by the nodes of ℒ and all their ancestors. The consensus tree problem asks whether there exists a tree T* such that, for every i, T*\ℒ(Ti) is homeomorphic to Ti. We present algorithms which test if a given sel of trees has a consensus tree and if so. construct one. The deterministic algorithm takes time min{ O (N n1/2), O (N + n2 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 (N n) 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 + b0 min{n2, m log n}), where b0 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 (m √n) to solve this problem. We also present two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology.

KW - Algorithms

KW - Data structures

KW - Evolutionary biology

KW - Theory of databases

UR - http://www.scopus.com/inward/record.url?scp=0013290962&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0013290962&partnerID=8YFLogxK

U2 - 10.1007/PL00009268

DO - 10.1007/PL00009268

M3 - Article

AN - SCOPUS:0013290962

VL - 24

SP - 1

EP - 13

JO - Algorithmica (New York)

JF - Algorithmica (New York)

SN - 0178-4617

IS - 1

ER -