The Importance of Agreement Forests (14:25–15:10)

Steven Kelk ( Maastricht University )

A phylogenetic tree is a tree in which the leaves are bijectively labelled by a set X, where X represents a set of contemporary species. Such trees are used to model the evolutionary history of X: internal nodes represent points at which a lineage diversified into two or more sublineages. A natural question within phylogenetics is to quantify the extent to which two or more phylogenetic trees on the same (or overlapping) set of species X differ topologically. This goal - to succinctly quantify the dissimilarity of phylogenetic trees - has given rise to a line of algorithmic research in which one particular data structure, the agreement forest, occurs time and time again. These forests, which partition the input trees into isomorphic subtrees, are often used as an intermediate abstraction to reduce complex phylogenetic models into a clean, combinatorial framework. Here I will give an overview of recent positive (fixed parameter tractability, approximability) and negative (inapproximability) results concerning their use. I will also show how the core agreement forest abstraction can be extended to model more complex phylogenetic optimization problems. This flexibility and ubiquity is intriguing and hints at the possibility of developing a structural basis for phylogenetics, analogous to the shift towards structural approaches in graph theory.

This is based on joint work with various authors.