Measuring how far a nonbinary phylogenetic network is from being tree-based

Bachelor Thesis (2018)
Author(s)

F.J.A. Janisse (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Contributor(s)

Leo van Iersel – Mentor

Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright
© 2018 Frank Janisse
More Info
expand_more
Publication Year
2018
Language
English
Copyright
© 2018 Frank Janisse
Graduation Date
29-01-2018
Awarding Institution
Delft University of Technology
Faculty
Electrical Engineering, Mathematics and Computer Science
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.

Abstract

In computational biology, phylogenetic trees are used to describe evolutionary history. This can be done more generally using phylogenetic networks, which can also describe nontreelike events such as hybridization. Some phylogenetic networks can be obtained from a base tree, a rooted spanning tree with the same leaf set, by adding linking edges. Such networks are called tree-based. In recent articles, characterizations of binary tree-based networks are given. They are linked to maximum-sized matchings in bipartite graphs, path partitions and antichains. However, in many real-life applications, phylogenetic networks are not binary. Therefore, we will prove that some characterizations are extendable to all (nonbinary) phylogenetic networks while some others are not. We will discuss five proximity measures of how close an arbitrarily (nonbinary) phylogenetic network is to being tree-based. Three of the measures turn out to be equal and at least three of them are computable in polynomial time. We show that this is also true in the nonbinary case. Lastly, we prove two inequalities comparing the other measures.

Files

BEP_final_Frank_Janisse.pdf
(pdf | 0.329 Mb)
License info not available