ALCOMFT-TR-03-73
|
![ALCOM-FT](../Main/logo_160x41.gif)
|
Gerth Stølting Brodal, Rolf Fagerberg, Anna Östlin, Christian N. S. Pedersen and S. Srinivasa Rao
Computing Refined Buneman Trees in Cubic Time
Århus.
Work package 4.
November 2003.
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). The
improved complexity of our algorithm makes the method of refined
Buneman trees computational competitive to methods based on neighbor
joining.
Postscript file: ALCOMFT-TR-03-73.ps.gz (171 kb).
System maintainer Gerth Stølting Brodal <gerth@cs.au.dk>