NETWORK PHYLOGENIES · New Methods to Reconstruct Phylogenetic Networks

Phylogenies are used to describe the history of evolutionarily related biological entities (e.g. genes, individuals, species) and are central in many biological applications, including functional genomics, epidemiology and biodiversity assessment. Many methods for reconstructing and studying phylogenies have been proposed, almost all of which use trees to represent them. Although in many cases this is reasonable, in many others phylogenies should be represented as networks (more precisely directed acyclic graphs). This is due to a number of biological phenomena collectively known as recombination, which are common in viruses (e.g. HIV and influenza), bacteria and sexual populations. Unfortunately recently proposed methods to reconstruct network phylogenies have not yet found many applications in evolutionary biology. I believe that this is due to the fact that many of these methods aim to explain all conflicting signal in the data with recombination, thus inferring far more recombination events than what is actually needed. I therefore propose a number of techniques whose goal is to explore the gap that is left between classical tree reconstruction, where no recombination is allowed, and the new network-based methods, where too many recombinations are allowed. The methods I propose are simple extensions of well-known approaches for tree reconstruction: maximum parsimony and distance methods. The two approaches differ for the optimality criterion used to score networks, but they have in common the fact that they impose a constraint on the number of recombinations allowed. Maximum parsimony scores networks on the basis of the number of sequence changes needed to explain the input sequences. On the other hand, distance methods score networks on the basis of how well they fit a collection of distance matrices given in input. In both cases, the optimization problems involved are likely to be computationally hard and therefore I plan to attack them using heuristics.