Jul 12, 2016

The combinatorics of discrete time-trees: theory and open problems

BioRxiv : the Preprint Server for Biology
Alex GavryushkinFrederick A Matsen

Abstract

A time-tree is a rooted phylogenetic tree such that all internal nodes are equipped with absolute divergence dates and all leaf nodes are equipped with sampling dates. Such time-trees have become a central object of study in phylogenetics. Here we introduce and study a hierarchy of discrete approximations of the space of time-trees from the graph-theoretic and algorithmic point of view. One of the basic and widely used phylogenetic graphs, the NNI graph, is the roughest approximation and bottom level of our hierarchy. More refined approximations discretize the relative timing of evolutionary divergence and sampling dates. We study basic graph-theoretic questions for these graphs including the size of neighborhoods, diameter upper and lower bounds, and the problem of finding shortest paths. We settle many of these questions by applying the concept of graph grammars introduced by Sleator, Tarjan, and Thurston to our graphs. Furthermore, we design an efficient algorithm for constructing these graphs. Our results open up a number of possible directions for theoretical investigation of graph-theoretic and algorithmic properties of the time-tree graphs. We discuss the directions that are most valuable for phylogenetic applications an...Continue Reading

  • References
  • Citations

References

  • We're still populating references for this paper, please check back later.
  • References
  • Citations

Citations

  • This paper may not have been cited yet.

Mentioned in this Paper

Study
Size
Trees (plant)
Phylogenetic Analysis
Theoretical Study
Anatomical Space Structure
Evaluation
Plant Leaves
Anatomic Node

About this Paper

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

Journal of Mathematical Biology
Alex GavryushkinFrederick A Matsen
Bulletin of Mathematical Biology
Sarah BastkowskiTaoyang Wu
Critical Care Medicine
A Boba
Algorithmica
Eleftherios AnastasiadisJinshan Zhang
IEEE/ACM Transactions on Computational Biology and Bioinformatics
Alan Joseph J CaceresKatherine St John
© 2020 Meta ULC. All rights reserved