Phylogenies without Branch Bounds: Contracting the Short, Pruning the\n Deep

2008/01/28 by Constantinos Daskalakis, Daskalakis, Constantinos, Elchanan Mossel +3
Biochemistry, Genetics and Molecular Biology · Earth and Planetary Sciences · Agricultural and Biological Sciences · #Genomics and Phylogenetic Studies #Evolution and Paleontology Studies #Plant Taxonomy and Phylogenetics

paper · pdf · doi:10.48550/arxiv.0801.4190

Abstract

We introduce a new phylogenetic reconstruction algorithm which, unlike most\nprevious rigorous inference techniques, does not rely on assumptions regarding\nthe branch lengths or the depth of the tree. The algorithm returns a forest\nwhich is guaranteed to contain all edges that are: 1) sufficiently long and 2)\nsufficiently close to the leaves. How much of the true tree is recovered\ndepends on the sequence length provided. The algorithm is distance-based and\nruns in polynomial time.\n

Related

• Fast phylogeny reconstruction through learning of ancestral sequences
• Fast reconstruction of phylogenetic trees using locality-sensitive hashing
• On the inference of large phylogenies with long branches: How long is too long?
• Sequence-Length Requirement of Distance-Based Phylogeny Reconstruction:\n Breaking the Polynomial Barrier
• The tree reconstruction game: phylogenetic reconstruction using reinforcement learning