---
_id: '11927'
abstract:
- lang: eng
  text: "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\r\ntime 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\r\nproblem, 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\r\nheuristic for constructing the maximum likelihood tree based upon combining
    solutions to small subproblems.\r\nThis is a simple and yet potentially significantly
    interesting approach to the evolutionary tree construction\r\nproblem. "
article_processing_charge: No
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Valerie
  full_name: King, Valerie
  last_name: King
- first_name: Tandy
  full_name: Warnow, Tandy
  last_name: Warnow
citation:
  ama: 'Henzinger MH, King V, Warnow T. Constructing a tree from homeomorphic subtrees,
    with applications to computational evolutionary biology. In: <i>7th Annual ACM-SIAM
    Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics;
    1996:333-340.'
  apa: 'Henzinger, M. H., King, V., &#38; Warnow, T. (1996). Constructing a tree from
    homeomorphic subtrees, with applications to computational evolutionary biology.
    In <i>7th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 333–340).
    Atlanta, GA, United States: Society for Industrial and Applied Mathematics.'
  chicago: Henzinger, Monika H, Valerie King, and Tandy Warnow. “Constructing a Tree
    from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.”
    In <i>7th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 333–40. Society
    for Industrial and Applied Mathematics, 1996.
  ieee: M. H. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic
    subtrees, with applications to computational evolutionary biology,” in <i>7th
    Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Atlanta, GA, United States,
    1996, pp. 333–340.
  ista: '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.'
  mla: Henzinger, Monika H., et al. “Constructing a Tree from Homeomorphic Subtrees,
    with Applications to Computational Evolutionary Biology.” <i>7th Annual ACM-SIAM
    Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics,
    1996, pp. 333–40.
  short: M.H. Henzinger, V. King, T. Warnow, in:, 7th Annual ACM-SIAM Symposium on
    Discrete Algorithms, Society for Industrial and Applied Mathematics, 1996, pp.
    333–340.
conference:
  end_date: 1996-01-30
  location: Atlanta, GA, United States
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 1996-01-28
date_created: 2022-08-19T06:57:47Z
date_published: 1996-01-28T00:00:00Z
date_updated: 2023-02-21T16:24:53Z
day: '28'
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://dl.acm.org/doi/10.5555/313852.314080
month: '01'
oa: 1
oa_version: Published Version
page: 333 -340
publication: 7th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  isbn:
  - '0898713668'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
  record:
  - id: '11679'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Constructing a tree from homeomorphic subtrees, with applications to computational
  evolutionary biology
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1996'
...