Forest-Based Binary Phylogenetic Networks

Finding Optimal Base Forests with Integer Linear Programming

Bachelor thesis (2023)

Authors

M.A. van Gruijthuijsen Electrical Engineering, Mathematics and Computer Science

Contributors

L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS (mentor)
W.T. van Horssen Mathematical Physics - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 Merel van Gruijthuijsen
More Info
expand_more

Published Date

14-07-2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Phylogenetic trees are commonly utilised in evolutionary biology. These trees represent the evolution of a set of species. In case of gene transfer however, a phylogenetic tree is insufficient. In such cases, tree-based phylogenetic networks are more suitable as they can depict reticulate evolution.
Nonetheless, tree-based phylogenetic networks have their limitations as they are unable to represent reticulate events occurring between different environments, families, or lineages of species. To address this, forest-based networks offer a solution.
A forest-based network is a collection of leaf-disjoint phylogenetic trees with arcs added between different trees in case of reticulate evolution.
In this thesis, an integer linear programme (ILP) is created to determine whether a binary phylogenetic network is forest-based. It is important to note that this thesis exclusively focuses on binary phylogenetic networks.
This ILP model is expected to be valuable in the development of new models and algorithms for both binary and non-binary phylogenetic networks, thereby enhancing the understanding of reticulate evolution. Additionally, the ILP may lead to time-related challenges when processing bigger phylogenetic networks.