Computing Refined Buneman Trees in Cubic Time

Gerth Stølting Brodal, Rolf Fagerberg, Anna Östlin, Christian Nørgaard Storm Pedersen, and S. Srinivasa Rao

Technical Report, BRICS-RS-02-51, BRICS, Department of Computer Science, Aarhus University, 14 pages, December 2002.

Abstract

Reconstructing the evolutionary tree for a set of n species based on pairwise distances between the species is a fundamental problem in bioinformatics. Neighbor joining is a popular distance based tree reconstruction method. It always proposes fully resolved binary trees despite missing evidence in the underlying distance data. Distance based methods based on the theory of Buneman trees and refined Buneman trees avoid this problem by only proposing evolutionary trees whose edges satisfy a number of constraints. These trees might not be fully resolved but there is strong combinatorial evidence for each proposed edge. The currently best algorithm for computing the refined Buneman tree from a given distance measure has a running time of O(n5) and a space consumption of O(n4). In this paper, we present an algorithm with running time O(n3) and space consumption O(n2).

Copyright notice

Copyright © 2002, BRICS, Department of Computer Science, Aarhus University. All rights reserved.

Online version

brics-rs-02-51.pdf (157 Kb)

BIBTEX entry

@techreport{brics-rs-02-51,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Anna \"Ostlin and Christian N{\o}rgaard Storm Pedersen and S. Srinivasa Rao",
  institution = "BRICS, Department of Computer Science, Aarhus University",
  issn = "0909-0878",
  month = "December",
  number = "BRICS-RS-02-51",
  pages = "14",
  title = "Computing Refined Buneman Trees in Cubic Time",
  year = "2002"
}