Pages
- 1
- 2
- 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
-
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
-
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
-
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
- document
-
Gross, Elizabeth (author), van Iersel, L.J.J. (author), Janssen, R. (author), Jones, M.E.L. (author), Long, Colby (author), Murakami, Yukihiro (author)Phylogenetic networks can represent evolutionary events that cannot be described by phylogenetic trees. These networks are able to incorporate reticulate evolutionary events such as hybridization, introgression, and lateral gene transfer. Recently, network-based Markov models of DNA sequence evolution have been introduced along with model...journal article 2021
- document
-
van Iersel, L.J.J. (author), Janssen, R. (author), Jones, M.E.L. (author), Murakami, Yukihiro (author), Zeh, Norbert (author)Phylogenetic networks are used to represent evolutionary relationships between species in biology. Such networks are often categorized into classes by their topological features, which stem from both biological and computational motivations. We study two network classes in this paper: tree-based networks and orchard networks. Tree-based...journal article 2021
- document
-
van Iersel, L.J.J. (author), Moulton, Vincent (author), Murakami, Yukihiro (author)A phylogenetic network is a graph-theoretical tool that is used by biologists to represent the evolutionary history of a collection of species. One potential way of constructing such networks is via a distance-based approach, where one is asked to find a phylogenetic network that in some way represents a given distance matrix, which gives...journal article 2020
- document
-
Döcker, Janosch (author), van Iersel, L.J.J. (author), Kelk, Steven (author), Linz, Simone (author)Here we show that deciding whether two rooted binary phylogenetic trees on the same set of taxa permit a cherry-picking sequence, a special type of elimination order on the taxa, is NP-complete. This improves on an earlier result which proved hardness for eight or more trees. Via a known equivalence between cherry-picking sequences and...journal article 2019
- document
-
Erdős, Péter L. (author), van Iersel, L.J.J. (author), Jones, M.E.L. (author)Unrooted phylogenetic networks are graphs used to represent reticulate evolutionary relationships. Accurately reconstructing such networks is of great relevance for evolutionary biology. It has recently been conjectured that all unrooted phylogenetic networks for at least five taxa can be uniquely reconstructed from their subnetworks obtained...journal article 2019
- document
-
Murakami, Yukihiro (author), van Iersel, L.J.J. (author), Janssen, R. (author), Jones, M.E.L. (author), Moulton, V.L. (author)Network reconstruction lies at the heart of phylogenetic research. Two well-studied classes of phylogenetic networks include tree-child networks and level-k networks. In a tree-child network, every non-leaf node has a child that is a tree node or a leaf. In a level-k network, the maximum number of reticulations contained in a biconnected...journal article 2019
- document
-
van Iersel, L.J.J. (author), Moulton, V.L. (author)An important problem in evolutionary biology is to reconstruct the evolutionary history of a set X of species. This history is often represented as a phylogenetic network, that is, a connected graph with leaves labelled by elements in X (for example, an evolutionary tree), which is usually also binary, i.e., all vertices have degree 1 or 3. A...journal article 2018
- document
-
Jetten, L. (author), van Iersel, L.J.J. (author)Rooted phylogenetic networks are used to describe evolutionary histories that contain non-treelike evolutionary events such as hybridization and horizontal gene transfer. In some cases, such histories can be described by a phylogenetic base-tree with additional linking arcs, which can for example represent gene transfer events. Such phylogenetic...journal article 2018
- document
-
van Iersel, L.J.J. (author), Jones, M.E.L. (author), Scornavacca, Celine (author)Phylogenetic networks arewell suited to represent evolutionary histories comprising reticulate evolution. Several methods aiming at reconstructing explicit phylogenetic networks have been developed in the last two decades. In this article, we propose a new definition of maximum parsimony for phylogenetic networks that permits to model biological...journal article 2018
- document
-
Janssen, R. (author), Jones, M.E.L. (author), Erdős, Péter L. (author), van Iersel, L.J.J. (author), Scornavacca, Celine (author)Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rooted Nearest Neighbour Interchange (rNNI) and rooted Subtree Prune and Regraft (rSPR). Recently, these moves were generalized to rooted phylogenetic networks, which are a more suitable representation of reticulate evolutionary histories, and...journal article 2018
- document
-
Kelk, Steven (author), Pardi, Fabio (author), Scornavacca, Celine (author), van Iersel, L.J.J. (author)Phylogenetic networks are often constructed by merging multiple conflicting phylogenetic signals into a directed acyclic graph. It is interesting to explore whether a network constructed in this way induces biologically-relevant phylogenetic signals that were not present in the input. Here we show that, given a multiple alignment A for a set...journal article 2018
Pages
- 1
- 2