Fast error-tolerant quartet phylogeny algorithms

DOI10.1007/978-3-642-21458-5_14MaRDI QIDQ3011850zbMATH OpenOpenAlexFDO

Authors Daniel G. Brown, Jakub Truszkowski

Publication date 29 June 2011

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.1866

zbMATH Keywords

taxaphylogeny algorithms

Mathematics Subject Classification ID

Problems related to evolution (92D15) Computational methods for problems pertaining to biology (92-08)

Abstract: We present an algorithm for phylogenetic reconstruction using quartets that returns the correct topology for $n$ taxa in $O(nlogn)$ time with high probability, in a probabilistic model where a quartet is not consistent with the true topology of the tree with constant probability, independent of other quartets. Our incremental algorithm relies upon a search tree structure for the phylogeny that is balanced, with high probability, no matter what the true topology is. Our experimental results show that our method is comparable in runtime to the fastest heuristics, while still offering consistency guarantees.

Recommendations

• Fast error-tolerant quartet phylogeny algorithms
• Constructing optimal trees from quartets
• scientific article; zbMATH DE number 1305402
• Publication:4938781
• scientific article; zbMATH DE number 6297767

Cites work

• scientific article; zbMATH DE number 5764888 (Why is no real title available?)
• scientific article; zbMATH DE number 1304319 (Why is no real title available?)
• scientific article; zbMATH DE number 2079368 (Why is no real title available?)
• scientific article; zbMATH DE number 1541304 (Why is no real title available?)
• scientific article; zbMATH DE number 1405796 (Why is no real title available?)
• A few logs suffice to build (almost) all trees. II
• Computing the quartet distance between evolutionary trees in time \(O(n\,\log n)\)
• Computing with Noisy Information
• Concentration of Measure for the Analysis of Randomized Algorithms
• Determining the Evolutionary Tree Using Experiments
• Noisy binary search and its applications

Cited in

(8)

• A polynomial time algorithm for the minimum quartet inconsistency problem with \(O(n)\) quartet errors
• Fast error-tolerant quartet phylogeny algorithms
• New absolute fast converging phylogeny estimation methods with improved scalability and accuracy
• Maximal Accurate Forests from Distance Matrices
• Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining
• scientific article; zbMATH DE number 1405796 (Why is no real title available?)
• Using \textsc{INC} within divide-and-conquer phylogeny estimation
• scientific article; zbMATH DE number 7626718 (Why is no real title available?)

Describes a project that uses

Uses Software

• Pfam
• FastTree
• Scoredist

This page was built for publication: Fast error-tolerant quartet phylogeny algorithms

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