DOI: 10.1101/469130Nov 13, 2018Paper

Statistically consistent divide-and-conquer pipelines for phylogeny estimation using NJMerge

BioRxiv : the Preprint Server for Biology
Erin K Molloy, Tandy Warnow

Abstract

Background Divide-and-conquer methods, which divide the species set into overlapping subsets, construct a tree on each subset, and then combine the subset trees using a supertree method, provide a key algorithmic framework for boosting the scalability of phylogeny estimation methods to large datasets. Yet the use of supertree methods, which typically attempt to solve NP-hard optimization problems, limits the scalability of such approaches. Results In this paper, we introduce a divide-and-conquer approach that does not require supertree estimation: we divide the species set into pairwise disjoint subsets, construct a tree on each subset using a base method, and then combine the subset trees using a distance matrix. For this merger step, we present a new method, called NJMerge, which is a polynomial-time extension of Neighbor Joining (NJ); thus, NJMerge can be viewed either as a method for improving traditional NJ or as a method for scaling the base method to larger datasets. We prove that NJMerge can be used to create divide-and-conquer pipelines that are statistically consistent under some models of evolution. We also report the results of an extensive simulation study evaluating NJMerge on multi-locus datasets with up to 1000...Continue Reading

Related Concepts

Biological Evolution
Extracellular Matrix
Trees (plant)
Proximal
Rhizotomy Procedure
Classical Lissencephaly
Simulation
Research Study
TWISTNB protein, human
Subgroup

Related Feeds

BioRxiv & MedRxiv Preprints

BioRxiv and MedRxiv are the preprint servers for biology and health sciences respectively, operated by Cold Spring Harbor Laboratory. Here are the latest preprint articles (which are not peer-reviewed) from BioRxiv and MedRxiv.

Related Papers

Algorithms for Molecular Biology : AMB
Nam NguyenTandy Warnow
Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
Md Shamsuzzoha Bayzid, Tandy Warnow
© 2021 Meta ULC. All rights reserved