On Phylogenetic Encodings and Orchard Networks

On Phylogenetic Encodings and Orchard Networks

Murakami, Yukihiro (TU Delft Discrete Mathematics and Optimization)

van Iersel, L.J.J. (promotor)
Aardal, K.I. (promotor)

Delft University of Technology

2021-11-29

Phylogenetic networks are a type of graph with vertices and edges, used to elucidate the evolutionary history of species. The fundamental goal of phylogenetic research is to infer the true phylogeny of species from raw data such as DNA sequences and morphological data. Most network inference methods require one to solve an NP-hard problem; furthermore, there is generally no guarantee of a unique network. One way of resolving this is to restrict our scope to networks within a certain class and to ask the following question.

What input data guarantees a unique network within this class?

Such a question brings us to the idea of encodings. A network class is encoded by a certain building block, such as displayed trees, splits, or induced inter-taxa distance matrices, if the building block distinguishes one network in the class from another. More precisely, no two networks in the same class may have the same set of building blocks. Often, encoding results give inspiration for polynomial-time algorithms for inferring networks within certain classes. Assuming to have data that corresponds to a network in that class, one may plausibly construct it as the unique network that is consistent with such information.

Phylogenetic Networks
Encodings
Orchard Networks

https://doi.org/10.4233/uuid:049932ab-4124-4639-a7e3-146ac4fd805d

Institutional Repository

doctoral thesis

© 2021 Yukihiro Murakami