Open AccessComputing Refined Buneman Trees in Cubic Time
Author(s) -
Gerth Stølting Brodal,
Rolf Fagerberg,
Anna Östlin,
Christian N. S. Pedersen,
S. Srinivasa Rao
Publication year - 2002
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v9i51.21766
Subject(s) - mathematics , tree (set theory) , pairwise comparison , measure (data warehouse) , algorithm , set (abstract data type) , combinatorics , binary tree , weight balanced tree , enhanced data rates for gsm evolution , discrete mathematics , running time , computer science , data mining , binary search tree , artificial intelligence , statistics , programming language
Reconstructing the evolutionary tree for a set of n species based on pairwise distances between the species is a fundamental problem in bioinformatics. Neighbour 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(n^5) and a space consumption of O(n^4). In this paper, we present an algorithm with running time O(n^3) and space consumption O(n^2).