- document
-
Broeders, Theo (author)Reconstructing a minimum reticulation network from phylogenetic trees is used in evolutionary studies. In this thesis, we focus on finding temporal networks using cherry-picking sequences for binary trees with all taxa. Finding such a minimum reticulation temporal network is NP-hard.<br/><br/>We introduce an algorithm to find a minimum...master thesis 2024
- document
-
Huber, Katharina T. (author), van Iersel, L.J.J. (author), Janssen, R. (author), Jones, M.E.L. (author), Moulton, V.L. (author), Murakami, Yukihiro (author), Semple, Charles (author)This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the root and reticulation vertices, can be oriented as a directed nonbinary phylogenetic network....journal article 2024
- document
-
Reichling, C Z (author)This thesis is on the subject of phylogenetic networks. These are schematic<br/>visualisations used mainly to investigate the evolutionary history of species,<br/>but which can be used for any set of distinguishable elements which have diverged from a common ancestor through some evolutionary process. The research specifically focuses on a way...master thesis 2023
- document
-
van Gruijthuijsen, Merel (author)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.<br/>Nonetheless, tree-based phylogenetic...bachelor thesis 2023
- document
-
Holtgrefe, Niels (author)Phylogenetic networks are a specific type of directed acyclic graph (DAG), used to depict evolutionary relationships among, for example, species or other groups of organisms. To solve computationally hard problems, treewidth has been used to parametrize algorithms in phylogenetics. In the hope of simplifying the algorithmic design process, Berry...master thesis 2023
- document
-
Keur, Hans (author)In biology, phylogenetics is the study of the evolutionary history of and relations between e.g. species. Such data are often represented in trees. Remarkably, trees lack the representation of reticulation events, such as hybridization, while such events are believed to be important. One of the reasons why trees are widely used, is the enormous...master thesis 2023
- document
-
Huijsman, Robbert (author)TreeContainment is a well-known problem within phylogenetics, which asks whether a binary phylogenetic tree is embedded in a binary phylogenetic network. For this problem, Jones, Weller and van Iersel (2022) have created an algorithm that uses dynamic programming on tree-decompositions to achieve a running time that is exponential in the tree...master thesis 2023
- document
-
van Iersel, L.J.J. (author), Moulton, Vincent (author), Murakami, Yukihiro (author)Graph invariants are a useful tool in graph theory. Not only do they encode useful information about the graphs to which they are associated, but complete invariants can be used to distinguish between non-isomorphic graphs. Polynomial invariants for graphs such as the well-known Tutte polynomial have been studied for several years, and...journal article 2023
- document
-
Jones, M.E.L. (author), Schestag, J. (author)Phylogenetic Diversity (PD) is a measure of the overall biodiversity of a set of present-day species (taxa) within a phylogenetic tree. We consider an extension of PD to phylogenetic networks. Given a phylogenetic network with weighted edges and a subset S of leaves, the all-paths phylogenetic diversity of S is the summed weight of all edges...conference paper 2023
- document
-
Garvardt, Jaroslav (author), Renken, Malte (author), Schestag, J. (author), Weller, Mathias (author)We consider the problem of orienting a given, undirected graph into a (directed) acyclic graph such that the in-degree of each vertex ν is in a prescribed list λ(ν). Variants of this problem have been studied for a long time and with various applications, but mostly without the requirement for acyclicity. Without this requirement, the problem...conference paper 2023
- document
-
van de Klok, Margot (author)Describing phylogenetic trees or networks with a polynomial is a tool to distinguish between them. In this thesis, a new polynomial for describing rooted binary internally labeled phylogenetic networks and trees is introduced based on the research of P. Liu and J. Pons et al. Two different cases are considered, one where the reticulation nodes...bachelor thesis 2022
- document
-
Nipius, Leonie (author)Phylogenetic networks generalize evolutionary trees and are commonly used to represent evolutionary relationships between species that undergo reticulate evolutionary processes such as hybridization, recombination and lateral gene transfer. In this thesis all quarnets, networks on four species, of a network are assumed to be known. We prove that...master thesis 2022
- document
-
Susanna, Merel (author)Phylogenetic networks are used to represent evolutionary histories of a set of taxa. In this thesis, we look at a certain network class, called orchard networks. <br/>In the beginning of this thesis, definitions concerning phylogenetic networks and specifically orchard networks are introduced. The characterization of orchard networks involves...bachelor thesis 2022
- document
-
Huber, Katharina T. (author), van Iersel, L.J.J. (author), Janssen, R. (author), Jones, M.E.L. (author), Moulton, Vincent (author), Murakami, Yukihiro (author)Recently it was shown that a certain class of phylogenetic networks, called level-2 networks, cannot be reconstructed from their associated distance matrices. In this paper, we show that they can be reconstructed from their induced shortest and longest distance matrices. That is, if two level-2 networks induce the same shortest and longest...journal article 2022
- document
-
van Iersel, L.J.J. (author), Jones, M.E.L. (author), Weller, Mathias (author)Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called Tree Containment, arises when validating networks constructed by phylogenetic inference methods. We present the first algorithm for (rooted) Tree Containment using the treewidth t of the input...conference paper 2022
- document
-
van Iersel, L.J.J. (author), Janssen, R. (author), Jones, M.E.L. (author), Murakami, Yukihiro (author), Zeh, Norbert (author)We present the first fixed-parameter algorithm for constructing a tree-child phylogenetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such networks. The algorithm uses the recently introduced framework of cherry picking sequences and runs in O((8 k) <sup>k</sup>poly (n,...journal article 2022
- document
-
Borst, Sander (author), van Iersel, L.J.J. (author), Jones, M.E.L. (author), Kelk, Steven (author)We study the problem of finding a temporal hybridization network containing at most k reticulations, for an input consisting of a set of phylogenetic trees. First, we introduce an FPT algorithm for the problem on an arbitrary set of m binary trees with n leaves each with a running time of O(5 <sup>k</sup>· n· m). We also present the concept...journal article 2022
- document
-
van Iersel, L.J.J. (author), Janssen, R. (author), Jones, M.E.L. (author), Murakami, Yukihiro (author)Phylogenetic networks are used in biology to represent evolutionary histories. The class of orchard phylogenetic networks was recently introduced for their computational benefits, without any biological justification. Here, we show that orchard networks can be interpreted as trees with additional horizontal arcs. Therefore, they are closely...journal article 2022
- document
-
van Iersel, L.J.J. (author), Kole, Sjors (author), Moulton, Vincent (author), Nipius, L. (author)Evolutionary histories for species that cross with one another or exchange genetic material can be represented by leaf-labelled, directed graphs called phylogenetic networks. A major challenge in the burgeoning area of phylogenetic networks is to develop algorithms for building such networks by amalgamating small networks into a single large...journal article 2022
- document
-
Murakami, Yukihiro (author)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;...doctoral thesis 2021