REU -- Mathematical Phylogenetics and the Space of Trees

Summer 2014

Instructor: Seth Sullivant, office: 3114 SAS Hall, email: smsulli2@ncsu.edu

Graduate Student Mentor: Colby Long, office: 4123 SAS Hall, email: celong2@ncsu.edu

Students: Mercedes Coleman, Cody Fitzgerald, Amber Holmes, Emily Smith

REU Products: Poster Final Project Report

Description: Phylogenetics is the area of biology concerned with inferring ancestral relationships between collections of taxa (e.g. species). An ancestral history of species is usually summarized by a phylogenetic tree. Phylogenetics is a rich area for interactions between mathematics and biology, and mathematical tools in phylogenetics include: discrete math, probability, statistics, algebra and geometry.

This REU will focus on the mathematical study of tree space. Tree space is a geometric object which consists of the set of all metric trees and with a natural distance measure comparing those trees. In many situations, different data sets or different methods for analyzing the same data can yield different trees. Given a collection of inferred trees, how do we compare them? Is there a natural notion of a consensus tree or an average tree? Tree space provides useful ways to address these questions, by phrasing the questions as geometric operations.

After spending a few days developing background on the mathematical aspects of phylogenetics, we will work on reading papers and identifying open problems to tackle.

Basic Reading:

• Semple and Steel, Phylogenetics (Excellent introductory text on mathematical phylogenetics. I will provide two copies of the book.)
• Billera, Louis J., Holmes, Susan P., Vogtmann, Karen. Geometry of the space of phylogenetic trees. Adv. in Appl. Math. 27 (2001), no. 4, 733–767. (This paper introduces the space of phylogenetic trees and proves some main properties about it: especially: it is a CAT(0) space so has unique geodesics.)
• Megan Owen, Scott Provan. A Fast Algorithm for Computing Geodesic Distances in Tree Space, IEEE/ACM Trans. Computational Biology and Bioinformatics, 8: 2-13, 2011 (This paper gives a polynomial time algorithm for compute geodesics in tree space.)

Advanced Reading:

• Ezra Miller, Megan Owen, J. Scott Provan. Polyhedral computational geometry for averaging metric phylogenetic trees 1211.7046 (This paper describes an algorithm for computing averages in tree space. Can it be improved? Can a polynomial time algorithm be obtained?)
• Federico Ardila, Megan Owen, Seth Sullivant. Geodesics in CAT(0) Cubical Complexes Advances in Applied Mathematics, 48: 142-163, 2012 (This paper gives a generalization of the Owen-Provan algorithm to arbitrary CAT(0) cubical complexes. Can the algorithm be improved? Is there a polynomial time algorithm?)
• Moulton, Vincent; Steel, Mike Peeling phylogenetic `oranges'. Adv. in Appl. Math. 33 (2004), no. 4, 710–727. (The "phylogenetic orange" space is a variation on tree space that takes into account probabilistic models of evolution. What do geodesics look like in this space? Can distances be computed quickly?)

LateX Resources: