Detailed project information

The traditional model for representing evolution is the phylogenetic tree. This provides an adequate model for mutation and speciation events but not for reticulate phenomena such as hybridization, horizontal gene transfer and recombination. These are better modelled by phylogenetic networks, essentially a generalisation of phylogenetic trees to directed acyclic graphs. The central algorithmic challenge is constructive: how does one efficiently and accurately infer phylogenetic etworks given noisy and incomplete biological data? The problem for trees has been very well studied but for networks the problem is far from solved: optimizing over directed acyclic graphs is in general much harder than optimizing over trees. Despite recent attention the field is still algorithmically immature. Many existing algorithms fail to strike the necessary balance between flexibility and optimality. For example, several well-known packages will produce a network, without any guarantees on its quality, and over-fitting is commonplace i.e. the solution complexity is too high. On the other hand, many other algorithms will generate optimal solutions but with infeasibly long execution times; here the running-time complexity is too high. Proof techniques are often long and based on case-analysis: proof complexity is too high. We propose to reduce these three complexities by applying advanced techniques from combinatorial optimization. The goal is to design and implement novel, fast algorithms that produce networks that are verifiably close to optimality with respect to explaining the input data and minimizing network complexity.