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

M. R. Henzinger, V. King, T. Warnow

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1-13
Number of pages13
JournalAlgorithmica (New York)
Volume24
Issue number1
DOIs
StatePublished - May 1999
Externally publishedYes

Fingerprint

Homeomorphic
Biology
Deterministic Algorithm
Batch
Linear Space
Dynamic Graphs
Rooted Trees
Tree Algorithms
Binary Tree
Randomized Algorithms
Vertex of a graph
Deletion
Fast Algorithm
Leaves
Binary trees
Efficient Algorithms
Denote
Subset
Graph in graph theory

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

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

In: Algorithmica (New York), Vol. 24, No. 1, 05.1999, p. 1-13.

Research output: Contribution to journalArticle

@article{c146c9257da147809dd697f8185a5757,
title = "Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology",
abstract = "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.",
keywords = "Algorithms, Data structures, Evolutionary biology, Theory of databases",
author = "Henzinger, {M. R.} and V. King and T. Warnow",
year = "1999",
month = "5",
doi = "10.1007/PL00009268",
language = "English (US)",
volume = "24",
pages = "1--13",
journal = "Algorithmica (New York)",
issn = "0178-4617",
publisher = "Springer New York",
number = "1",

}

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 -