A polynomial time algorithm for constructing the refined Buneman tree

DOI10.1016/S0893-9659(98)00148-7MaRDI QIDQ1808975zbMATH OpenOpenAlexFDO

Authors David Bryant, Vincent Moulton

Publication date 16 February 2000

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0893-9659(98)00148-7

zbMATH Keywords

Buneman treedistance-based tree reconstructionphylogeneticsrefined Buneman treeweighted tree

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Problems related to evolution (92D15)

Review text

Let \(X\) be a finite set, and let \({\mathcal D}(X)\) denote the set of distance functions on \(X\). An important problem in phylogenetic analysis is to approximate distances (such as those arising from biomolecular data) by tree metrics. In this paper this problem is investigated by looking for a tree construction map, that is, a map \(f:{\mathcal D}(X)\rightarrow {\mathcal D}(X)\), with \(f({\mathcal D}(X))\subseteq {\mathcal T}(X)\), where \({\mathcal T}(X)\) denotes the set of all tree metrics on \(X\), which satisfies four requirements that are desirable in biological applications. Buneman gave a method for tree construction that satisfies these requirements [Mathematics in the Archaeological and Historical Sciences (edited by F. Hodson, D. Kendall and P. Tautu), Edinburgh University Press, Edinburgh, 387-395 (1971)]. However, the price paid for continuity of the map \(f\) is that the resulting tree is often highly unresolved. The Buneman construction was modified in an attempt to address this problem by \textit{V. Moulton} and \textit{M. Steel} [Discrete Appl. Math. 91, No. 1-3, 215-233 (1999; Zbl 0914.05016)]. The resulting construction is called the refined Buneman tree. However, it is not shown whether the property: ``if \(d\in {\mathcal D}(X)\), then \(f(d)\) can be computed in time that is polynomial in \(|X |\) holds for this construction or not. Note that the algorithm currently used for computing the refined Buneman tree in the phylogenetic analysis (program SplitsTree) has exponential time complexity. In this paper an algorithm for computing the refined Buneman tree in polynomial time (in at most \(O(n^{6})\) time for every \(n\geq 4\), where \(n=|X |\)) is presented.

Recommendations

• A fast algorithm for constructing trees from distance matrices
• Retractions of finite distance functions onto tree metrics
• An optimal algorithm to reconstruct trees from additive distance data
• Constructing optimal trees from quartets

Cites work

• Efficient algorithms for inferring evolutionary trees
• From copair hypergraphs to median graphs with latent vertices
• scientific article; zbMATH DE number 4201445 (Why is no real title available?)
• scientific article; zbMATH DE number 1088266 (Why is no real title available?)
• scientific article; zbMATH DE number 1113973 (Why is no real title available?)
• Retractions of finite distance functions onto tree metrics
• Trees, taxonomy, and strongly compatible multi-state characters
• Weak hierarchies associated with similarity measures - An additive clustering technique

Cited in

(7)

• A fast algorithm for constructing trees from distance matrices
• Retractions of finite distance functions onto tree metrics
• Inferring evolutionary trees with strong combinatorial evidence
• A structured family of clustering and tree construction methods
• Combining polynomial running time and fast convergence for the disk-covering method.
• The triangles method to build X-trees from incomplete distance matrices
• Lagged couplings diagnose Markov chain Monte Carlo phylogenetic inference

Describes a project that uses

Uses Software

• SplitsTree

This page was built for publication: A polynomial time algorithm for constructing the refined Buneman tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1808975)