Degree, Curvature, and Mixing of Random Walks on the Phylogenetic Subtree-Prune-Regraft Graph and What It Tells Us About Phylogenetic Inference via MCMC

• Activity Number: 450
• Type: Contributed
• Date/Time: Tuesday, August 11, 2015 : 3:05 PM to 3:50 PM
• Sponsor: Section on Bayesian Statistical Science
• Author(s): Frederick Matsen* and Chris Whidden
• Companies: Fred Hutchinson Cancer Research Center and Fred Hutchinson Cancer Research Center
• Keywords: MCMC ; phylogenetics ; mixing time ; graphical model ; Ollivier-Ricci curvature

Abstract

Statistical phylogenetics is the inference of a tree structure representing evolutionary history using biological sequence data (e.g. DNA) under a likelihood model of sequence evolution. All such inferences perform either heuristic search or Markov chain Monte Carlo (MCMC) on a graph built with the various trees as vertices and edges representing tree modifications. Because this graph is connected with nonzero transition probabilities, MCMC is guaranteed to work in the large time limit, although inference using a finite number of steps is determined by mixing properties of MCMC on the graph. However, little is known about the large-scale structure of, or properties of MCMC on, the graphs actually used for inference. In this talk, I will first demonstrate significant graph effects on phylogenetic inference for the subtree-prune-regraft (rSPR) graph, which is a popular such graph involving reconnection of subtrees of a tree in a different location. I will then recap what is known about the rSPR graph and describe our work on Ricci-Ollivier curvature of the SPR graph, then describe consequences for random walks on the SPR graph and phylogenetic MCMC.