Skip to content

What is an elementary modification of a discrete time-tree? Exploring the geometry and Ricci-Ollivier curvature of discrete phylogenetic time-trees.

Notifications You must be signed in to change notification settings

gavryushkin/curvatureNNI

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

Alex Gavryushkin, Chris Whidden, and Frederick A Matsen IV

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 and give a list of open problems of prominent importance for those applications.

About

What is an elementary modification of a discrete time-tree? Exploring the geometry and Ricci-Ollivier curvature of discrete phylogenetic time-trees.

Resources

Stars

Watchers

Forks

Packages

No packages published

Contributors 4

  •  
  •  
  •  
  •  

Languages