Displaying Phylogenetic Trees in Networks with Integer Linear Programming

A common task in phylogenetics is to deal with a set of topologically different phylogenetic trees. One problem formulation is viewing these trees as displayed in a single underlying directed acyclic graph (or network). Here, we say each given tree is displayed in this network if we can obtain this tree by discarding some edges (while keeping all the leaves) of the network. The most common optimization objective for this problem is finding the most parsimonious network that displays all the given trees. This optimization problem is known to be NP complete even when there are only two trees. In this talk I will present my research on finding optimal network for displaying phylogenetic trees. I will start from a perhaps more well-known problem: computing the rooted subtree prune and regraft distance between two trees (which is in fact closely related to the problem of displaying these two trees in a network). Here I will show that there is a simple ILP formulation for this problem. I will then present ILP-based approaches for finding the optimal networks that display multiple trees.