Encoding level-k phylogenetic networks

Encoding level-k phylogenetic networks

Janisse, Frank (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Delft Institute of Applied Mathematics)

van Iersel, L.J.J. (mentor)
Jones, M.E.L. (mentor)
Groenevelt, W.G.M. (graduation committee)

Delft University of Technology

Applied Mathematics | Optimization

2021-08-17

Phylogenetic networks are used to describe evolutionary histories and are a generalisation of evolutionary trees. They can contain so called reticulations, representing reticulate evolution, such as hybridization, lateral gene transfer and recombination. Methods are being developed to construct certain rooted phylogenetic networks from their subnetworks. A constructed network is encoded by their subnetworks if it is uniquely determined by that set. It has been shown that phylogenetic trees are encoded by their set of triplets, which are rooted trees on three species. However, triplets do not encode phylogenetic networks. Huber and Moulton introduced trinets, rooted networks on three species, which do encode level-1 phylogenetic networks, which are networks containing at most one reticulation in each biconnected component. Van Iersel and Moulton proved that level-2 phylogenetic networks are encoded by their set of trinets and Nipius proved that level-3 phylogenetic networks are encoded by their set of quarnets, which are rooted networks on four species. In this thesis we prove that for all k>1, level-k networks without symmetry in their biconnected components are encoded by their set of (k+1)-nets, which are rooted networks on k+1 leaves. This result provides some evidence for the conjecture that all level-k phylogenetic networks are encoded by their set of (k+1)-nets. Thereafter, we generalise encoding results for level-2 and level-3 networks, where the underlying structure, called generator, and its sides play an important role. A generator is a directed acyclic biconnected multigraph, containing only vertices with indegree 2 and outdegree at most 1, indegree 1 and outdegree 2, and indegree 0 and outdegree 2. The sides of a generator are the arcs and outdegree-0 vertices of a generator. We have not been able to prove that level-k networks with symmetry in the generators of their biconnected components are in general encoded by k+1-nets. For the networks with symmetry, we prove encoding results for networks with leaves on at most p sides of the underlying generators of their biconnected components. We further prove that level-4 networks are encoded by 6-nets. Although Nipius gave a counterexample showing that not all (level-3) phylogenetic networks are encoded by their set of trinets, it is useful to know which networks are encoded by their set of trinets or k-nets. In this thesis, we provide an algorithm which can serve as tool for proving that certain level-k networks are encoded by their set of k-nets. Our presented algorithm is a first step to generalise encoding results to level-k networks with k>3 by using trinets. Furthermore, we are a step closer to proving the conjecture that all level-k networks are encoded by (k+1)-nets, including networks with symmetry in the generators of their biconnected components.

Phylogenetic networks
Encoding
Optimization
Evolution
Graph theory
Phylogenetic trees

http://resolver.tudelft.nl/uuid:11939b58-b834-4073-8de8-b61d9a5f9a81

Student theses

master thesis

© 2021 Frank Janisse