Tree Compatibility, Incomplete Directed Perfect Phylogeny, and Dynamic Graph Connectivity: An Experimental Study
Open Access
- 28 February 2019
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 12 (3) , 53
Abstract
We study two problems in computational phylogenetics. The first is tree compatibility. The input is a collection of phylogenetic trees over different partially-overlapping sets of species. The goal is to find a single phylogenetic tree that displays all the evolutionary relationships implied by . The second problem is incomplete directed perfect phylogeny (IDPP). The input is a data matrix describing a collection of species by a set of characters, where some of the information is missing. The question is whether there exists a way to fill in the missing information so that the resulting matrix can be explained by a phylogenetic tree satisfying certain conditions. We explain the connection between tree compatibility and IDPP and show that a recent tree compatibility algorithm is effectively a generalization of an earlier IDPP algorithm. Both algorithms rely heavily on maintaining the connected components of a graph under a sequence of edge and vertex deletions, for which they use the dynamic connectivity data structure of Holm et al., known as HDT. We present a computational study of algorithms for tree compatibility and IDPP. We show experimentally that substituting HDT by a much simpler data structure—essentially, a single-level version of HDT—improves the performance of both of these algorithm in practice. We give partial empirical and theoretical justifications for this observation.
Keywords
Funding Information
- National Science Foundation (1444806)
This publication has 26 references indexed in Scilit:
- Fast Compatibility Testing for Rooted Phylogenetic TreesAlgorithmica, 2017
- An efficient algorithm for testing the compatibility of phylogenies with nested taxaAlgorithms for Molecular Biology, 2017
- Synthesis of phylogeny and taxonomy into a comprehensive tree of lifeProceedings of the National Academy of Sciences of the United States of America, 2015
- Compatibility of unrooted phylogenetic trees is FPTTheoretical Computer Science, 2006
- Incomplete Directed Perfect PhylogenySIAM Journal on Computing, 2004
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivityJournal of the ACM, 2001
- Decremental Dynamic ConnectivityJournal of Algorithms, 1999
- Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary BiologyAlgorithmica, 1999
- The complexity of reconstructing trees from qualitative characters and subtreesJournal of Classification, 1992
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational ExpressionsSIAM Journal on Computing, 1981