- 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
-
Deen, Elise (author), van Iersel, L.J.J. (author), Janssen, Remie (author), Jones, M.E.L. (author), Murakami, Yukihiro (author), Zeh, Norbert (author)The maximum parsimony distance d<sub>MP</sub>(T<sub>1</sub>,T<sub>2</sub>) and the bounded-state maximum parsimony distance d<sub>MP</sub><sup>t</sup>(T<sub>1</sub>,T<sub>2</sub>) measure the difference between two phylogenetic trees T<sub>1</sub>,T<sub>2</sub> in terms of the maximum difference between their parsimony scores for any...journal article 2024
- 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
-
Bernardini, Giulia (author), van Iersel, L.J.J. (author), Julien, E.A.T. (author), Stougie, Leen (author)Background: Combining a set of phylogenetic trees into a single phylogenetic network that explains all of them is a fundamental challenge in evolutionary studies. Existing methods are computationally expensive and can either handle only small numbers of phylogenetic trees or are limited to severely restricted classes of networks. Results: In...journal article 2023
- document
-
van Iersel, L.J.J. (author), Jones, M.E.L. (author), Julien, E.A.T. (author), Murakami, Yukihiro (author)Phylogenetic networks are used to represent the evolutionary history of species. Recently, the new class of orchard networks was introduced, which were later shown to be interpretable as trees with additional horizontal arcs. This makes the network class ideal for capturing evolutionary histories that involve horizontal gene transfers. Here,...conference paper 2023
- 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
-
Bernardini, Giulia (author), van Iersel, L.J.J. (author), Julien, E.A.T. (author), Stougie, Leen (author)Combining a set of phylogenetic trees into a single phylogenetic network that explains all of them is a fundamental challenge in evolutionary studies. In this paper, we apply the recently-introduced theoretical framework of cherry picking to design a class of heuristics that are guaranteed to produce a network containing each of the input...conference paper 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
- document
- Janssen, R. (author) doctoral thesis 2021
- document
-
Janssen, R. (author), Liu, Pengyu (author)Phylogenetic networks represent evolutionary history of species and can record natural reticulate evolutionary processes such as horizontal gene transfer and gene recombination. This makes phylogenetic networks a more comprehensive representation of evolutionary history compared to phylogenetic trees. Stochastic processes for generating...journal article 2021
- document
-
Janssen, R. (author)Head moves are a type of rearrangement moves for phylogenetic net-works. They have primarily been studied as part of other types of moves, such as rSPR moves. Here, we study head moves as a type of moves on themselves. We show that the tiers (k > 0) of phylogenetic network space are connected by local head moves. Then, we show tail moves...journal article 2021
- document
-
Jones, M.E.L. (author), Kelk, Steven (author), Stougie, Leen (author)Maximum parsimony distance is a measure used to quantify the dissimilarity of two unrooted phylogenetic trees. It is NP-hard to compute, and very few positive algorithmic results are known due to its complex combinatorial structure. Here we address this shortcoming by showing that the problem is fixed parameter tractable. We do this by...journal article 2021
- document
-
Wallin, Rosanne (author), van Iersel, L.J.J. (author), Kelk, Steven (author), Stougie, Leen (author)Background: Rooted phylogenetic networks are used to display complex evolutionary history involving so-called reticulation events, such as genetic recombination. Various methods have been developed to construct such networks, using for example a multiple sequence alignment or multiple phylogenetic trees as input data. Coronaviruses are known...journal article 2021