Fast error-tolerant quartet phylogeny algorithms

DOI10.1007/978-3-642-21458-5_14zbMATH Open1339.92057arXiv1010.1866OpenAlexW2567739102MaRDI QIDQ3011850FDOQ3011850

Authors: Daniel G. Brown, Jakub Truszkowski 

Publication date: 29 June 2011

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

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.

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

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

zbMATH Keywords

taxaphylogeny algorithms

Mathematics Subject Classification ID

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

Cites Work

• Computing with Noisy Information
• Title not available (Why is that?)
• Concentration of Measure for the Analysis of Randomized Algorithms
• Computing the quartet distance between evolutionary trees in time \(O(n\,\log n)\)
• Title not available (Why is that?)
• Determining the Evolutionary Tree Using Experiments
• A few logs suffice to build (almost) all trees. II
• Noisy binary search and its applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

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

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)