Publications
2026
[95]
journal article
Metrics for classes of semi-binary phylogenetic networks using μ-representations
Advances in Applied Mathematics, 172:102953, 2026.
Develops mathematically rigorous ways to measure how similar or different two evolutionary networks are, for two common types of network, filling a gap since comparing networks (rather than trees) has generally been much harder.
Phylogenetic networks are useful in representing the evolutionary history of taxa. In certain scenarios, one requires a way to compare different networks. In practice, this can be rather difficult, except within specific classes of networks. In this paper, we derive metrics for the class of \emph{orchard networks} and the class of \emph{strongly reticulation-visible} networks, from variants of so-called \emph{$μ$-representations}, which are vector representations of networks. For both network classes, we impose degree constraints on the vertices, by considering \emph{semi-binary} networks.
@article{reichling2026metrics,
author = {Reichling, Christopher and van Iersel, Leo and Murakami, Yukihiro},
title = {{Metrics for classes of semi-binary phylogenetic networks using μ-representations}},
journal = {Advances in Applied Mathematics},
year = {2026},
volume = {172},
pages = {102953}
}
[94]
journal article
Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
Journal of Computer and System Sciences, 160:103802, 2026.
Gives the first practical algorithm for exactly computing scanwidth, a measure of how tree-like a directed graph is, plus a fast heuristic approximation, enabling this measure to actually be computed and used on realistically sized evolutionary networks.
To measure the tree-likeness of a directed acyclic graph (DAG), a new width parameter that considers the directions of the arcs was recently introduced: scanwidth. We present the first algorithm that efficiently computes the exact scanwidth of general DAGs. For DAGs with one root and scanwidth $k$ it runs in $O(k \cdot n^k \cdot m)$ time. The algorithm also functions as an FPT algorithm with complexity $O(2^{4 \ell - 1} \cdot \ell \cdot n + n^2)$ for phylogenetic networks of level-$\ell$, a type of DAG used to depict evolutionary relationships among species. Our algorithm performs well in practice, being able to compute the scanwidth of synthetic networks up to 30 reticulations and 100 leaves within 500 seconds. Furthermore, we propose a heuristic that obtains an average practical approximation ratio of 1.5 on these networks. While we prove that the scanwidth is bounded from below by the treewidth of the underlying undirected graph, experiments suggest that for networks the parameters are close in practice.
@article{holtgrefe2026exact,
author = {Holtgrefe, Niels and van Iersel, Leo and Jones, Mark},
title = {Exact and heuristic computation of the scanwidth of directed acyclic graphs},
journal={Journal of Computer and System Sciences},
doi={10.1016/j.jcss.2026.103802},
volume = {160},
pages = {103802},
year = {2026}
}
[93]
journal article
Characterizing semi-directed phylogenetic networks and their multi-rootable variants
Theory in Biosciences, 145(1):4, 2026.
Provides precise mathematical criteria for recognizing a type of evolutionary network in which the direction of some evolutionary relationships is known and others are not, replacing an informal working definition with one that can actually be checked.
In evolutionary biology, phylogenetic networks are graphs that provide a flexible framework for representing complex evolutionary histories that involve reticulate evolutionary events. Recently phylogenetic studies have started to focus on a special class of such networks called semi-directed networks. These graphs are defined as mixed graphs that can be obtained by de-orienting some of the arcs in some rooted phylogenetic network, that is, a directed acyclic graph whose leaves correspond to a collection of species and that has a single source or root vertex. However, this definition of semi-directed networks is implicit in nature since it is not clear when a mixed-graph enjoys this property or not. In this paper, we introduce novel, explicit mathematical characterizations of semi-directed networks, and also multi-semi-directed networks, that is, mixed graphs that can be obtained from directed phylogenetic networks that may have more than one root. In addition, through extending foundational tools from the theory of rooted networks into the semi-directed setting - such as cherry picking sequences, omnians, and path partitions - we characterize when a (multi-)semi-directed network can be obtained by de-orienting some rooted network that is contained in one of the well-known classes of tree-child, orchard, tree-based or forest-based networks. These results address structural aspects of (multi-)semi-directed networks and pave the way to improved theoretical and computational analyses of such networks, for example, within the development of algebraic evolutionary models that are based on such networks.
@article{holtgrefe2025charachterizing,
author = {Holtgrefe, Niels and Huber, Katharina T and van Iersel, Leo and Jones, Mark and Moulton, Vincent},
title = {Characterizing semi-directed phylogenetic networks and their multi-rootable variants},
journal={Theory in Biosciences},
doi={10.1007/s12064-025-00453-8},
volume = {145},
pages = {4},
number = {1},
year = {2026}
}
[92]
preprint
A kernel for the maximum agreement forest problem on multiple binary phylogenetic trees
arXiv:2602.22281, 2026.
Improves the theoretical guarantees behind algorithms that measure how much several evolutionary trees (for example, built from different genes) disagree with each other, by proving a tighter limit on how far such problems can be simplified before they must be solved directly.
The maximum agreement forest (MAF) problem in phylogenetics takes as input a set t >= 2 of binary phylogenetic trees T on the same set of taxa X. It asks for a partition of X into the smallest number of blocks such that the subtrees induced by these blocks are disjoint and have common topology across all the trees in T. We produce a modified version of the well-known chain reduction rule in order to prove that after exhaustive application of reduction rules each tree has O( t * r * k ) leaves, where k is the natural parameter (the number of blocks) and r=min{max{k,3},t+1}}. We prove this bound for both the unrooted and rooted version of the problem, and demonstrate that the bound r, the length to which common chains are truncated, is tight. Our results constitute the first kernels for MAF in the t>2 regime.
@misc{kelk2026kernel,
author = {Kelk, Steven and Meuwese, Ruben and van Iersel, Leo},
title = {{A kernel for the maximum agreement forest problem on multiple binary phylogenetic trees}},
year = {2026},
archivePrefix = {arXiv},
eprint = {2602.22281},
doi = {10.48550/arXiv.2602.22281},
url = {https://doi.org/10.48550/arXiv.2602.22281}
}
[91]
preprint
A Class of Unrooted Phylogenetic Networks Inspired by the Properties of Rooted Tree-Child Networks
arXiv:2603.07000, 2026.
Identifies a new class of evolutionary networks that stay computationally manageable even when the direction of evolutionary time is unknown, after showing that the most obvious such class is actually intractable to recognize.
A directed phylogenetic network is tree-child if every non-leaf vertex has a child that is not a reticulation. As a class of directed phylogenetic networks, tree-child networks are very useful from a computational perspective. For example, several computationally difficult problems in phylogenetics become tractable when restricted to tree-child networks. At the same time, the class itself is rich enough to contain quite complex networks. Furthermore, checking whether a directed network is tree-child can be done in polynomial time. In this paper, we seek a class of undirected phylogenetic networks that is rich and computationally useful in a similar way to the class tree-child directed networks. A natural class to consider for this role is the class of tree-child-orientable networks which contains all those undirected phylogenetic networks whose edges can be oriented to create a tree-child network. However, we show here that recognizing such networks is NP-hard, even for binary networks, and as such this class is inappropriate for this role. Towards finding a class of undirected networks that fills a similar role to directed tree-child networks, we propose new classes called $q$-cuttable networks, for any integer $q\geq 1$. We show that these classes have many of the desirable properties, similar to tree-child networks in the rooted case, including being recognizable in polynomial time, for all $q\geq 1$. Towards showing the computational usefulness of the class, we show that the NP-hard problem Tree Containment is polynomial-time solvable when restricted to $q$-cuttable networks with $q\geq 3$.
@misc{iersel2026class,
author = {van Iersel, Leo and Jones, Mark and Linz, Simone and Zeh, Norbert},
title = {{A Class of Unrooted Phylogenetic Networks Inspired by the Properties of Rooted Tree-Child Networks}},
year = {2026},
archivePrefix = {arXiv},
eprint = {2603.07000},
doi = {10.48550/arXiv.2603.07000},
url = {https://doi.org/10.48550/arXiv.2603.07000}
}
[90]
journal article
Bounds on the sequence length sufficient to reconstruct binary level-1 phylogenetic networks under the CFN model
Annals of Combinatorics, 2026.
Determines how much genetic sequence data is actually needed to reconstruct a common type of evolutionary network with high confidence, showing that the required amount of data scales predictably with the number of species involved.
Phylogenetic trees and networks are graphs used to model evolutionary relationships, with trees representing strictly branching histories and networks allowing for events in which lineages merge, called reticulation events. While the question of data sufficiency has been studied extensively in the context of trees, it remains largely unexplored for networks. In this work we take a first step in this direction by establishing bounds on the amount of genomic data required to reconstruct binary level-$1$ semi-directed phylogenetic networks, which are binary networks in which reticulation events are indicated by directed edges, all other edges are undirected, and cycles are vertex-disjoint. For this class, methods have been developed recently that are statistically consistent. Roughly speaking, such methods are guaranteed to reconstruct the correct network assuming infinitely long genomic sequences. Here we consider the question whether networks from this class can be uniquely and correctly reconstructed from finite sequences. Specifically, we present an inference algorithm that takes as input genetic sequence data, and demonstrate that the sequence length sufficient to reconstruct the correct network with high probability, under the CFN model of evolution, scales logarithmically, polynomially, or polylogarithmically with the number of taxa, depending on the parameter regime. As part of our contribution, we also present novel inference rules for quartet data in the semi-directed phylogenetic network setting.
@article{frohn2026bounds,
author = {Frohn, Martin and Holtgrefe, Niels and van Iersel, Leo and Jones, Mark and Kelk, Steven},
title = {Bounds on the sequence length sufficient to reconstruct binary level-1 phylogenetic networks under the {CFN} model},
journal = {Annals of Combinatorics},
doi = {10.1007/s00026-026-00830-0},
year = {2026}
}
[89]
preprint
Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
arXiv:2604.27745, 2026.
Studies how to efficiently select the species that best preserve evolutionary diversity when the underlying history is an evolutionary network rather than a simple tree, showing this can be done quickly for networks that are not too tangled but becomes computationally hard beyond a certain point.
We investigate parameterized algorithms for computing the average-tree phylogenetic diversity (APD) in rooted phylogenetic networks, studying the problem under different structural parameters that capture the deviation of a network from a tree. Our primary parameter is the scanwidth, a measure of the tree-likeness of a given directed acyclic graph. We show that a subset of taxa with maximum APD can be found in polynomial time in phylogenetic networks of scanwidth at most 2, but becomes NP-hard in networks of scanwidth 3. Further, we design an algorithm that computes the APD of a given set of taxa in O(2^sw n) time, where sw denotes the scanwidth and n the number of taxa in the input network. Finally, we give a linear-time algorithm for computing the APD of a given set of taxa if the network induced by these taxa is reticulation-visible. We generalize this algorithm to still run in polynomial time if each biconnected component of the induced network has only constantly many invisible reticulations.
@misc{iersel2026averagetree,
author = {van Iersel, Leo and Jones, Mark and Schestag, Jannik and Scornavacca, Celine and Weller, Mathias},
title = {{Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility}},
year = {2026},
archivePrefix = {arXiv},
eprint = {2604.27745},
doi = {10.48550/arXiv.2604.27745},
url = {https://doi.org/10.48550/arXiv.2604.27745}
}
[88]
preprint
Tree Containment Parameterized by Scanwidth
arXiv:2605.31071, 2026.
Gives a fast algorithm for checking whether a proposed evolutionary tree is consistent with a more complex network, whenever the network is not too tangled, and proves that this speed cannot be substantially improved once the network becomes more complex.
TREE CONTAINMENT is a central decision problem in mathematical phylogenetics, asking whether a given rooted phylogenetic tree is embeddable in ("displayed by") a given rooted phylogenetic network. While the problem is NP-complete for general networks, many algorithmic advances have relied on structural parameters that capture how "tree-like" a network is. In this paper we investigate TREE CONTAINMENT under the structural parameter scanwidth, a directed width measure generalizing popular parameters measuring tree-likeness of phylogenetic networks. We first present a parameterized algorithm that solves the problem in $O(4^{k + k\log{k}} n + nm^2)$ time, where $n$ and $m$ are the numbers of nodes and arcs in the network and $k$ is the width of a given tree-extension. Complementing this upper bound, we prove a matching lower bound under the Exponential-Time Hypothesis (ETH), showing that there is no algorithm for TREE CONTAINMENT that runs in $2^{o(c\log{c})} n^{O(1)}$ time, even on binary inputs, where $c$ is the directed cutwidth of the input network, which upper-bounds the scanwidth $k$.
@misc{iersel2026tree,
author = {van Iersel, Leo and Jones, Mark and Weller, Mathias},
title = {{Tree Containment Parameterized by Scanwidth}},
year = {2026},
archivePrefix = {arXiv},
eprint = {2605.31071},
doi = {10.48550/arXiv.2605.31071},
url = {https://doi.org/10.48550/arXiv.2605.31071}
}
[87]
preprint
Proximity Measures for Classes of Phylogenetic Networks
arXiv:2607.11325, 2026.
Introduces ways to measure how far a complex evolutionary network is from simpler, easier-to-analyze shapes, by counting the minimum number of edits needed to reshape it, and compares these different distance measures and how hard each is to compute.
Phylogenetic networks are used to represent the evolutionary history of species. Due to biological interpretations and computational advantages, researchers have focused on restricted classes of phylogenetic networks, such as tree-child, orchard, and tree-based. These classes capture different notions of tree-likeness: tree-child networks require every internal vertex to have a taxon reachable by a tree path, orchard networks are trees with horizontal arcs (for modelling histories rife with horizontal gene transfers), and tree-based networks are trees with additional (not-necessarily horizontal) arcs. A natural question to ask is 'how far is a given network from belonging to a particular class?' This motivates the study of proximity measures, which measure the minimum number of graph modifications required to transform a network into one belonging to a particular class. In this paper, we consider three proximity measures based on leaf addition, valid arc deletion, and arc deletion. We study pairwise comparability of the proximity measures, prove complexity results, and derive extremal bounds for the classes of tree, tree-child, orchard, and tree-based networks.
@misc{iersel2026proximity,
author = {van Iersel, Leo and Jones, Mark and Julien, Esther and Long, Yangjing and Murakami, Yukihiro},
title = {{Proximity Measures for Classes of Phylogenetic Networks}},
year = {2026},
archivePrefix = {arXiv},
eprint = {2607.11325},
doi = {10.48550/arXiv.2607.11325},
url = {https://doi.org/10.48550/arXiv.2607.11325}
}
[86]
preprint
On Tree-Network Distinguishability and Full Identifiability of Phylogenetic Networks
arXiv:2607.12919, 2026.
Proves that genetic data can reliably distinguish a straightforward evolutionary tree from a more tangled history involving hybridization, and shows that in a wide range of realistic cases such a network can be fully and uniquely reconstructed from the data rather than only narrowed down to a few possibilities.
Phylogenetic networks generalize phylogenetic trees to evolutionary histories that include reticulate events such as recombination, horizontal gene transfer, and hybridization. Under a Markov model of nucleotide substitution, a phylogenetic network determines a distribution of leaf-patterns. Here, we study the identifiability of the network topology from this distribution under the Jukes-Cantor (JC), Kimura 2-parameter (K2P), and Kimura 3-parameter (K3P) models. Our first result is that the semi-directed network parameter of a level-1 phylogenetic network (modulo redirecting triangles) is fully identifiable under all three models, on a biologically reasonable parameter space in which substitution rates are probabilistic and mixing parameters are non-trivial (i.e., not 0 or 1). In contrast to the generic identifiability established in prior work, this holds at every point of the parameter space, not merely off of a measure-zero subset. Our second result distinguishes phylogenetic networks from phylogenetic trees, on the same parameter space, under JC and K2P. We prove that no phylogenetic network and phylogenetic tree can induce the same leaf-pattern distribution unless the network is a tree, possibly augmented with certain substructures called 2-blobs. This means the presence of reticulate evolution creates, in most cases, a detectable signature in the leaf-pattern distribution. More broadly, these results have consequences for identifiability beyond the models and network classes studied here, including for several coalescent-based models.
@misc{brits2026treenetwork,
author = {Brits, Jari and Holtgrefe, Niels and van Iersel, Leo and Martin, Samuel},
title = {{On Tree-Network Distinguishability and Full Identifiability of Phylogenetic Networks}},
year = {2026},
archivePrefix = {arXiv},
eprint = {2607.12919},
doi = {10.48550/arXiv.2607.12919},
url = {https://doi.org/10.48550/arXiv.2607.12919}
}
2025
[85]
journal article
Fence decompositions and cherry covers in non-binary phylogenetic networks
IEEE Transactions on Computational Biology and Bioinformatics (2025), 2025.
Extends key mathematical tools for understanding evolutionary networks built on top of an underlying tree structure from the simplified case where every hybridization event involves exactly two ancestors to the more general and realistic case of more, connecting two previously separate ways of analyzing such networks.
Reticulate evolution can be modelled using phylogenetic networks. Tree-based networks, which are one of the more general classes of phylogenetic networks, have recently gained eminence for its ability to represent evolutionary histories with an underlying tree structure. To better understand tree-based networks, numerous characterizations have been proposed, based on tree embeddings, matchings, and arc partitions. Here, we build a bridge between two arc partition characterizations, namely maximal fence decompositions and cherry covers. Results on cherry covers have been found for general phylogenetic networks. We first show that the number of cherry covers is the same as the number of support trees (underlying tree structure of tree-based networks) for a given semibinary network. Maximal fence decompositions have only been defined thus far for binary networks (constraints on vertex degrees). We remedy this by generalizing fence decompositions to non-binary networks, and using this, we characterize semi-binary tree-based networks in terms of forbidden structures. Furthermore, we give an explicit enumeration of cherry covers of semi-binary networks, by studying its fence decomposition. Finally, we prove that it is possible to characterize semi-binary tree-child networks, a subclass of tree-based networks, in terms of the number of their cherry covers.
@article{carlespons2025fence,
author = {Carles Pons, Joan and Vives López, Pau and Murakami, Yukihiro and van Iersel, Leo},
title = {{Fence decompositions and cherry covers in non-binary phylogenetic networks}},
journal = {IEEE Transactions on Computational Biology and Bioinformatics (2025)},
year = {2025}
}
[84]
journal article
When are quarnets sufficient to reconstruct semi-directed phylogenetic networks?
Bulletin of Mathematical Biology, 87:136, 2025.
Determines how complex an evolutionary network can get before the information in all its four-species sub-networks is no longer enough to pin it down exactly, showing this holds up to a certain complexity level but breaks down beyond it, while the network's coarse overall structure remains always recoverable — results that underpin the reliability of practical reconstruction software such as Squirrel.
Phylogenetic networks are graphs that are used to represent evolutionary relationships between different taxa. They generalize phylogenetic trees since for example, unlike trees, they permit lineages to combine. Recently, there has been rising interest in semi-directed phylogenetic networks, which are mixed graphs in which certain lineage combination events are represented by directed edges coming together, whereas the remaining edges are left undirected. One reason to consider such networks is that it can be difficult to root a network using real data. In this paper, we consider the problem of when a semi-directed phylogenetic network is defined or encoded by the smaller networks that it induces on the 4-leaf subsets of its leaf set. These smaller networks are called quarnets. We prove that semi-directed binary level-2 phylogenetic networks are encoded by their quarnets, but that this is not the case for level-3. In addition, we prove that the so-called blob tree of a semi-directed binary network, a tree that give the coarse-grained structure of the network, is always encoded by the quarnets of the network. These results are relevant for proving the statistical consistency of programs that are currently being developed for reconstructing phylogenetic networks from practical data, such as the recently developed Squirrel software tool.
@article{huber2025when,
author = {Huber, Katharina T and van Iersel, Leo and Jones, Mark and Moulton, Vincent and Veenema-Nipius, Leonie},
title = {{When are quarnets sufficient to reconstruct semi-directed phylogenetic networks?}},
journal = {Bulletin of Mathematical Biology},
year = {2025},
volume = {87},
pages = {136}
}
[83]
journal article
Reconstructing semi-directed level-1 networks using few quarnets
Journal of Computer and System Sciences, 152:103655, 2025.
Shows that an evolutionary network can be accurately reconstructed from far fewer small four-species building blocks than previously thought needed, giving a fast algorithm that uses close to the minimum possible amount of such information, and extending the approach to recover the coarse overall shape of even more complex networks.
Semi-directed networks are partially directed graphs that model evolution where the directed edges represent reticulate evolutionary events. We present an algorithm that reconstructs binary $n$-leaf semi-directed level-1 networks in $O( n^2)$ time from its quarnets (4-leaf subnetworks). Our method assumes we have direct access to all quarnets, yet uses only an asymptotically optimal number of $O(n \log n)$ quarnets. When the network is assumed to contain no triangles, our method instead relies only on four-cycle quarnets and the splits of the other quarnets. A variant of our algorithm works with quartets rather than quarnets and we show that it reconstructs most of a semi-directed level-1 network from an asymptotically optimal $O(n \log n)$ of the quartets it displays. Additionally, we provide an $O(n^3)$ time algorithm that reconstructs the tree-of-blobs of any binary $n$-leaf semi-directed network with unbounded level from $O(n^3)$ splits of its quarnets.
@article{frohn2025reconstructing,
title={Reconstructing semi-directed level-1 networks using few quarnets},
author={Frohn, Martin and Holtgrefe, Niels and van Iersel, Leo and Jones, Mark and Kelk, Steven},
journal={Journal of Computer and System Sciences},
doi={10.1016/j.jcss.2025.103655},
volume = {152},
pages = {103655},
year = {2025}
}
[82]
journal article
A Simple 4-Approximation Algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees
Information Processing Letters, 190:106572, 2025.
Gives a much simpler algorithm that comes within a factor of 4 of the best possible score for measuring how much several evolutionary trees disagree with each other, matching the best known guarantee with a far more straightforward method, and proves that this particular approach cannot be improved any further.
We present a simple 4-approximation algorithm for computing a maximum agreement forest of multiple unrooted binary trees. This algorithm applies LP rounding to an extension of a recent ILP formulation of the maximum agreement forest problem on two trees by Van Wersch al. We achieve the same approximation ratio as the algorithm of Chen et al. but our algorithm is extremely simple. We also prove that no algorithm based on the ILP formulation by Van Wersch et al. can achieve an approximation ratio of $4 - \varepsilon$, for any $\varepsilon > 0$, even on two trees. To this end, we prove that the integrality gap of the ILP approaches 4 as the size of the two input trees grows.
@article{dempsey2025simple,
author = {Dempsey, Jordan and van Iersel, Leo and Jones, Mark and Zeh, Norbert},
title = {{A Simple 4-Approximation Algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees}},
journal = {Information Processing Letters},
year = {2025},
volume = {190},
pages = {106572},
archivePrefix = {arXiv},
eprint = {2409.08440},
doi = {10.1016/j.ipl.2025.106572},
url = {https://doi.org/10.1016/j.ipl.2025.106572}
}
[81]
conference paper
Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond
RECOMB-CG 2025, pp. 107--130 (2025).
Gives an efficient algorithm for selecting the most diverse subset of species from an evolutionary network whenever the network has a manageable number of hybridization events, and shows that a natural attempt to broaden this efficiency to more tangled networks is impossible unless a major unsolved problem in computer science (P=NP) turns out to be false.
Network Phylogenetic Diversity (Network-PD) is a measure for the diversity of a set of species based on a rooted phylogenetic network (with branch lengths and inheritance probabilities on the reticulation edges) describing the evolution of those species. We consider the Max-Network-PD problem: Given such a network, find k species with maximum Network-PD score. We show that this problem is fixed-parameter tractable (FPT) for binary networks, by describing an optimal algorithm running in O(2r log(k)(n + r)) time, with n the total number of species in the network and r its reticulation number. Furthermore, we show that Max-Network-PD is NP-hard for level-1 networks, proving that, unless P=NP, the FPT approach cannot be extended by using the level as parameter instead of the reticulation number.
@inproceedings{DBLP:conf/recombcg/IerselJSSW25,
author = {Leo van Iersel and Mark Jones and Jannik Schestag and Céline Scornavacca and Mathias Weller},
title = {Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond},
booktitle = {Comparative Genomics - 22nd RECOMB International Workshop, RECOMB-CG 2025, Seoul, South Korea, April 24-25, 2025, Proceedings},
pages = {107--130},
year = {2025},
crossref = {DBLP:conf/recombcg/2025},
url = {https://doi.org/10.1007/978-3-031-94928-9_7},
doi = {10.1007/978-3-031-94928-9_7},
biburl = {https://dblp.org/rec/conf/recombcg/IerselJSSW25.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
[80]
journal article
Is this network proper forest-based?
Information Processing Letters, 187:106500, 2025.
Settles the computational difficulty of testing whether an evolutionary network with multiple root points can be built by connecting a set of ordinary evolutionary trees, showing this check is easy for two roots but becomes computationally hard for three or more.
In evolutionary biology, networks are becoming increasingly used to represent evolutionary histories for species that have undergone non-treelike or reticulate evolution. Such networks are essentially directed acyclic graphs with a leaf set that corresponds to a collection of species, and in which non-leaf vertices with indegree 1 correspond to speciation events and vertices with indegree greater than 1 correspond to reticulate events such as gene transfer. Recently forest-based networks have been introduced, which are essentially (multi-rooted) networks that can be formed by adding some arcs to a collection of phylogenetic trees (or phylogenetic forest), where each arc is added in such a way that its ends always lie in two different trees in the forest. In this paper, we consider the complexity of deciding whether or not a given network is proper forest-based, that is, whether it can be formed by adding arcs to some underlying phylogenetic forest which contains the same number of trees as there are roots in the network. More specifically, we show that it can be decided in polynomial time whether or not a binary, tree-child network with $m \ge 2$ roots is proper forest-based in case $m=2$, but that this problem is NP-complete for $m\ge 3$. We also give a fixed parameter tractable (FPT) algorithm for deciding whether or not a network in which every vertex has indegree at most 2 is proper forest-based. A key element in proving our results is a new characterization for when a network with $m$ roots is proper forest-based which is given in terms of the existence of certain $m$-colorings of the vertices of the network.
@article{huber2025is,
author = {Huber, Katharina and van Iersel, Leo and Moulton, Vincent and Scholz, Guillaume},
title = {{Is this network proper forest-based?}},
journal = {Information Processing Letters},
year = {2025},
volume = {187},
pages = {106500}
}
[79]
journal article
Squirrel: Reconstructing semi-directed phylogenetic level-1 networks from four-leaved networks or sequence alignments
Molecular Biology and Evolution, 42(4):msaf067, 2025.
Presents Squirrel, free software that reconstructs evolutionary networks directly from DNA sequence alignments by piecing together many small four-species sub-networks, shown to run in minutes on real datasets and guaranteed to reconstruct the correct network when its assumptions hold.
With the increasing availability of genomic data, biologists aim to find more accurate descriptions of evolutionary histories influenced by secondary contact, where diverging lineages reconnect before diverging again. Such reticulate evolutionary events can be more accurately represented in phylogenetic networks than in phylogenetic trees. Since the root location of phylogenetic networks can not be inferred from biological data under several evolutionary models, we consider semi-directed (phylogenetic) networks: partially directed graphs without a root in which the directed edges represent reticulate evolutionary events. By specifying a known outgroup, the rooted topology can be recovered from such networks. We introduce the algorithm SO_SCPLOWQUIRRELC_SCPLOW (Semi-directed Quarnet-based Inference to Reconstruct Level-1 Networks) which constructs a semi-directed level-1 network from a full set of quarnets (four-leaf semi-directed networks). Our method also includes a heuristic to construct such a quarnet set directly from sequence alignments. We demonstrate SO_SCPLOWQUIRRELC_SCPLOWs performance through simulations and on real sequence data sets, the largest of which contains 29 aligned sequences close to 1.7 Mbp long. The resulting networks are obtained on a standard laptop within a few minutes. Lastly, we prove that SO_SCPLOWQUIRRELC_SCPLOW is combinatorially consistent: given a full set of quarnets coming from a triangle-free semi-directed level-1 network, it is guaranteed to reconstruct the original network. SO_SCPLOWQUIRRELC_SCPLOW is implemented in Python, has an easy-to-use graphical user-interface that takes sequence alignments or quarnets as input, and is freely available at https://github.com/nholtgrefe/squirrel.
@article{holtgrefe2025squirrel,
title={Squirrel: Reconstructing semi-directed phylogenetic level-1 networks from four-leaved networks or sequence alignments},
author={Holtgrefe, Niels and Huber, Katharina T and van Iersel, Leo and Jones, Mark and Martin, Samuel and Moulton, Vincent},
journal={Molecular Biology and Evolution},
doi={10.1093/molbev/msaf067},
volume = {42},
number = {4},
pages = {msaf067},
year = {2025}
}
[78]
preprint
Identifiability of Phylogenetic Level-2 Networks under the Jukes-Cantor Model
bioRxiv:10.1101/2025.04.18.649493, 2025.
Extends prior guarantees that an evolutionary network can be uniquely recovered from enough genetic data to a wider and more realistic class of networks, including cases with two closely linked hybridization events, and shows that key large-scale features of any such network are always recoverable.
AO_SCPLOWBSTRACTC_SCPLOWWe investigate which evolutionary histories can potentially be reconstructed from sufficiently long DNA sequences by studying the identifiability of phylogenetic networks from sequence data generated under site independent models of molecular evolution. While previous work in the field has established the identifiability of phylogenetic trees and level-1 networks, networks with non-overlapping reticulation cycles, less is known about more complex network structures. In this work, we extend identifiability results to network classes that include pairs of tangled reticulations.
Our main result shows that binary semi-directed level-2 phylogenetic networks are generically identifiable under the Jukes-Cantor model, provided they are triangle-free and strongly tree-child. We also strengthen existing identifiability results for level-1 networks, showing that the number of reticulation nodes is generically identifiable under the Jukes-Cantor model.
In addition, we present more general identifiability results that do not restrict the network level at all and hold for the Jukes-Cantor as well as for the Kimura-2-parameter model. Specifically, we demonstrate that any two binary semi-directed networks that display different sets of 4-leaf subtrees (quartets) are distinguishable. This has direct implications for the identifiability of a networks reticulated components (blobs). We show that the tree-of-blobs of a network, the global branching structure of the network, is identifiable, as well as the circular ordering of the subnetworks around each blob, for networks in which edges do not cross and taxa are on the outside.
@misc{englander2025identifiability,
author = {Englander, Aviva K and Frohn, Martin and Gross, Elizabeth and Holtgrefe, Niels and van Iersel, Leo and Jones, Mark and Sullivant, Seth},
title = {Identifiability of Phylogenetic Level-2 Networks under the {Jukes-Cantor} Model},
year={2025},
archivePrefix={bioRxiv},
eprint={10.1101/2025.04.18.649493}
}
[77]
journal article
Distinguishing Phylogenetic Level-2 Networks with Quartets and Inter-Taxon Quartet Distances
Bulletin of Mathematical Biology, 87(12):168, 2025.
Lays the mathematical groundwork for reliably inferring a broader class of evolutionary networks (allowing more complex, overlapping hybridization events) from genetic data, by working out precisely which features of such networks can be recovered from small four-species comparisons.
The inference of phylogenetic networks, which model complex evolutionary processes including hybridization and gene flow, remains a central challenge in evolutionary biology. Until now, statistically consistent inference methods have been limited to phylogenetic level-1 networks, which allow no interdependence between reticulate events. In this work, we establish the theoretical foundations for a statistically consistent inference method for a much broader class: semi-directed level-2 networks that are outer-labeled planar and galled. We precisely characterize the features of these networks that are distinguishable from the topologies of their displayed quartet trees. Moreover, we prove that an inter-taxon distance derived from these quartets is circular decomposable, enabling future robust inference of these networks from quartet data, such as concordance factors obtained from gene tree distributions under the Network Multispecies Coalescent model. Our results also have novel identifiability implications across different data types and evolutionary models, applying to any setting in which displayed quartets can be distinguished.
@article{holtgrefe2025distinguishing,
author = {Holtgrefe, Niels and Allman, Elizabeth S and Baños, Hector and van Iersel, Leo and Moulton, Vincent and Rhodes, John A and Wicke, Kristina},
title = {Distinguishing Phylogenetic Level-2 Networks with Quartets and Inter-Taxon Quartet Distances},
journal={Bulletin of Mathematical Biology},
doi={10.1007/s11538-025-01549-4},
volume = {87},
pages = {168},
number = {12},
year = {2025}
}
[76]
conference paper
Average-Tree Phylogenetic Diversity of Networks
WABI 2025, vol. 344, pp. 15:1--15:20 (2025).
Introduces a way to measure phylogenetic diversity that accounts for uncertainty about which branches of an evolutionary network were actually used, shows that computing it is hard in general but tractable when a network has only a few hybridization events, and validates the approach experimentally.
@InProceedings{vaniersel_et_al:LIPIcs.WABI.2025.15,
author = {van Iersel, Leo and Jones, Mark and Schestag, Jannik and Scornavacca, Celine and Weller, Mathias},
title = {{Average-Tree Phylogenetic Diversity of Networks}},
booktitle = {25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
pages = {15:1--15:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-386-7},
ISSN = {1868-8969},
year = {2025},
volume = {344},
editor = {Brejová, Broňa and Patro, Rob},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.15},
URN = {urn:nbn:de:0030-drops-239405},
doi = {10.4230/LIPIcs.WABI.2025.15},
annote = {Keywords: phylogenetic diversity, phylogenetic networks, network phylogenetic diversity, algorithms, computational complexity}
}
[75]
conference paper
PaNDA: Efficient Optimization of Phylogenetic Diversity in Networks
RECOMB 2026 (2025).
Presents PaNDA, free software for selecting the most evolutionarily diverse subset of species from a phylogenetic network — useful for conservation prioritization — including a fast algorithm that scales to large real-world datasets and a graphical interface for non-specialists.
Phylogenetic diversity plays an important role in biodiversity, conservation, and evolutionary studies by measuring the diversity of a set of taxa based on their phylogenetic relationships. In phylogenetic trees, a subset of k taxa with maximum phylogenetic diversity can be found by a simple and efficient greedy algorithm. However, this algorithmic tractability is lost when considering phylogenetic networks, which incorporate reticulate evolutionary events such as hybridization and horizontal gene transfer. To address this challenge, we introduce PaNDA (Phylogenetic Network Diversity Algorithms), the first software package and interactive graphical user-interface for exploring, visualizing and maximizing diversity in phylogenetic networks. PaNDA includes a novel algorithm to find a subset of k taxa with maximum diversity, running in polynomial time for networks of bounded scanwidth, a measure of tree-likeness of a network that grows slower than the well-known level measure. This algorithm considers the variant of phylogenetic diversity on networks in which the branch lengths of all paths from the root to the selected taxa contribute towards their diversity. We demonstrate the scalability of this algorithm on simulated networks, successfully analyzing level-15 networks with up to 200 taxa in seconds. We also provide a proof-of-concept analysis using a phylogenetic network on Xiphophorus species, illustrating how the tool can support diversity studies based on real genomic data. The software is easily installable and freely available at https://github.com/nholtgrefe/panda. Additionally, we extend the definition of phylogenetic diversity to semi-directed phylogenetic networks, which are mixed graphs increasingly used in phylogenetic analysis to model uncertainty of the root location. We prove that finding a subset of k taxa with maximum diversity remains NP-hard on semi-directed networks, but do present a polynomial-time algorithm for networks with bounded level.
@misc{holtgrefe2025panda,
author = {Holtgrefe, Niels and van Iersel, Leo and Meuwese, Ruben and Murakami, Yukihiro and Schestag, Jannik},
title = {{PaNDA}: Efficient Optimization of Phylogenetic Diversity in Networks},
year={2025},
archivePrefix={bioRxiv},
eprint={10.1101/2025.11.14.688467}
}
[74]
preprint
Computational support for case-heavy proofs in mathematical phylogenetics
arXiv:2512.16691, 2025.
Shows that computer-assisted checking can shorten and simplify many long, case-heavy mathematical proofs in phylogenetics, and uses the same approach to establish new results that would otherwise have taken considerable effort to prove by hand.
In this note we demonstrate that a number of case-heavy combinatorial proofs in the mathematical phylogenetics literature can be proven more compactly using computational support. We use these techniques to also prove several new combinatorial lemmas that would have taken considerable effort to prove by hand. We are optimistic that similar approaches can be deployed more widely in phylogenetics.
@misc{forte2025computational,
author = {Forte, Luca and van Iersel, Leo and Kelk, Steven and Meuwese, Ruben},
title = {{Computational support for case-heavy proofs in mathematical phylogenetics}},
year = {2025},
archivePrefix = {arXiv},
eprint = {2512.16691},
doi = {10.48550/arXiv.2512.16691},
url = {https://doi.org/10.48550/arXiv.2512.16691}
}
2024
[73]
journal article
When Three Trees Go to War
Peer Community Journal, 4:e54, 2024.
Shows that reconciling three or more conflicting evolutionary trees into a single network can require substantially more hybridization events than reconciling just two — at least 50% more relative to the number of species — settling the simplest case where the previous best combinatorial tools stop applying.
How many reticulations are needed for a phylogenetic network to display a given set of k phylogenetic trees on n leaves? For k = 2, Baroni et al. [Ann. Comb. 8, 391-408 (2005)] showed that the answer is n − 2. Here, we show that, for k ≥ 3 the answer is at least (3 /2 − ε )n. Concretely, we prove that, for each ε > 0, there is some n ∈ N such that three n-leaf caterpillar trees can be constructed in such a way that any network displaying these caterpillars contains at least (3 /2 − ε )n reticulations. The case of three trees is interesting since it is the easiest case that cannot be equivalently formulated in terms of agreement forests. Instead, we base the result on a surprising lower bound for multilabelled trees (MUL-trees) displaying the caterpillars. Indeed, we show that one cannot do (more than an ε ) better than the trivial MUL-tree resulting from a simple concatenation of the given caterpillars. The results are relevant for the development of methods for the Hybridization Number problem on more than two trees. This fundamental problem asks to construct a binary phylogenetic network with a minimum number of reticulations displaying a given set of phylogenetic trees
@article{iersel2024when,
author = {van Iersel, Leo and Jones, Mark and Weller, Mathias},
title = {{When Three Trees Go to War}},
journal = {Peer Community Journal},
year = {2024},
volume = {4},
pages = {e54}
}
[72]
journal article
Orienting undirected phylogenetic networks
Journal of Computer and System Sciences, 140:103480, 2024.
Studies when an evolutionary network drawn without any indication of the direction of time can be consistently assigned a direction, giving efficient algorithms for this task both when some of the necessary information is already known and, more generally, when it must be inferred from the network's shape alone, for networks that are not too tangled.
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. Moreover, we characterize when this is possible and show that, in such instances, the resulting directed nonbinary phylogenetic network is unique. In addition, without being given the location of the root and the reticulation vertices, we describe an algorithm for deciding whether an undirected binary phylogenetic network $N$ can be oriented as a directed binary phylogenetic network of a certain class. The algorithm is fixed-parameter tractable (FPT) when the parameter is the level of $N$ and is applicable to classes of directed phylogenetic networks that satisfy certain conditions. As an example, we show that the well-studied class of binary tree-child networks satisfies these conditions.
@article{huber2024orienting,
author = {Huber, Katharina T and van Iersel, Leo and Janssen, Remie and Jones, Mark and Moulton, Vincent and Murakami, Yukihiro and Semple, Charles},
title = {{Orienting undirected phylogenetic networks}},
journal = {Journal of Computer and System Sciences},
year = {2024},
volume = {140},
pages = {103480}
}
[71]
journal article
A near-linear kernel for bounded-state parsimony distance
Journal of Computer and System Sciences, 140:103477, 2024.
Proves that a natural measure of how much two evolutionary trees disagree, based on a limited number of possible character states, can always be efficiently simplified to a near-minimal instance before solving, extending an efficiency guarantee that was previously known only for a related, less restrictive version of the measure.
The maximum parsimony distance $d_{\textrm{MP}}(T_1,T_2)$ and the bounded-state maximum parsimony distance $d_{\textrm{MP}}^t(T_1,T_2)$ measure the difference between two phylogenetic trees $T_1,T_2$ in terms of the maximum difference between their parsimony scores for any character (with $t$ a bound on the number of states in the character, in the case of $d_{\textrm{MP}}^t(T_1,T_2)$). While computing $d_{\textrm{MP}}(T_1, T_2)$ was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for $d_{\textrm{MP}}^t(T_1,T_2)$. In this paper, we prove that computing $d_{\textrm{MP}}^t(T_1, T_2)$ is fixed-parameter tractable for all~$t$. Specifically, we prove that this problem has a kernel of size $O(k \lg k)$, where $k = d_{\textrm{MP}}^t(T_1, T_2)$. As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest.
@article{deen2024nearlinear,
author = {Deen, Elise and van Iersel, Leo and Janssen, Remie and Jones, Mark and Murakami, Yukihiro and Zeh, Norbert},
title = {{A near-linear kernel for bounded-state parsimony distance}},
journal = {Journal of Computer and System Sciences},
year = {2024},
volume = {140},
pages = {103477}
}
[70]
journal article
Solving the Tree Containment Problem Using Graph Neural Networks
Transactions on Machine Learning Research (2024), 2024.
Uses machine learning, specifically graph neural networks, to quickly and approximately check whether a proposed evolutionary tree is consistent with a larger network — a problem that is computationally hard to solve exactly — achieving over 95% accuracy and generalizing to larger species sets than it was trained on.
Tree Containment is a fundamental problem in phylogenetics useful for verifying a proposed phylogenetic network, representing the evolutionary history of certain species. Tree Containment asks whether the given phylogenetic tree (for instance, constructed from a DNA fragment showing tree-like evolution) is contained in the given phylogenetic network. In the general case, this is an NP-complete problem. We propose to solve it approximately using Graph Neural Networks. In particular, we propose to combine the given network and the tree and apply a Graph Neural Network to this network-tree graph. This way, we achieve the capability of solving the tree containment instances representing a larger number of species than the instances contained in the training dataset (i.e., our algorithm has the inductive learning ability). Our algorithm demonstrates an accuracy of over $95\%$ in solving the tree containment problem on instances with up to 100 leaves.
@article{dushatskiy2024solving,
author = {Dushatskiy, Arkadiy and Julien, Esther and van Iersel, Leo and Stougie, Leen},
title = {{Solving the Tree Containment Problem Using Graph Neural Networks}},
journal = {Transactions on Machine Learning Research (2024)},
year = {2024}
}
[69]
preprint
Invariants for level-1 phylogenetic networks under the random walk 4-state Markov model
arXiv:2407.11720, 2024.
Develops new algebraic tools for detecting the correct evolutionary network from DNA sequence data under a general statistical model of mutation, and provides a faster and more reliable way to find these tools than previous methods, while also showing that this particular set of tools is not by itself enough to guarantee that small networks can always be told apart.
Phylogenetic networks can represent evolutionary events that cannot be described by phylogenetic trees, such as hybridization, introgression, and lateral gene transfer. Studying phylogenetic networks under a statistical model of DNA sequence evolution can aid the inference of phylogenetic networks. Most notably Markov models like the Jukes-Cantor or Kimura-3 model can been employed to infer a phylogenetic network using phylogenetic invariants. In this article we determine all quadratic invariants for sunlet networks under the random walk 4-state Markov model, which includes the aforementioned models. Taking toric fiber products of trees and sunlet networks, we obtain a new class of invariants for level-1 phylogenetic networks under the same model. Furthermore, we apply our results to the identifiability problem of a network parameter. In particular, we prove that our new class of invariants of the studied model is not sufficient to derive identifiability of quarnets (4-leaf networks). Moreover, we provide an efficient method that is faster and more reliable than the state-of-the-art in finding a significant number of invariants for many level-1 phylogenetic networks.
@misc{frohn2024invariants,
author = {Frohn, Martin and Holtgrefe, Niels and van Iersel, Leo and Jones, Mark and Kelk, Steven},
title = {Invariants for level-1 phylogenetic networks under the random walk 4-state {Markov} model},
year={2024},
archivePrefix={arXiv},
eprint={2407.11720}
}
[68]
journal article
Inferring Phylogenetic Networks from Multifurcating Trees via Cherry Picking and Machine Learning
Molecular Phylogenetics and Evolution, 199:108137, 2024.
Presents FHyNCH, software that combines a tree-simplification technique with machine learning to reconstruct evolutionary networks from large collections of trees, even when those trees are only partially resolved and cover different, overlapping sets of species — a scale and flexibility beyond what earlier methods could handle.
The Hybridization problem asks to reconcile a set of conflicting phylogenetic trees into a single phylogenetic network with the smallest possible number of reticulation nodes. This problem is computationally hard and previous solutions are restricted to small and/or severely restricted data sets, for example, a set of binary trees with the same taxon set or only two non-binary trees with non-equal taxon sets. Building on our previous work on binary trees, we present FHyNCH, the first algorithmic framework to heuristically solve the Hybridization problem for large sets of multifurcating trees whose sets of taxa may differ. Our heuristics combine the cherry-picking technique, recently proposed to solve the same problem for binary trees, with two carefully designed machine-learning models. We demonstrate that our methods are practical and produce qualitatively good solutions through experiments on both synthetic and real data sets.
@article{bernardini2024inferring,
author = {Bernardini, Giulia and van Iersel, Leo and Julien, Esther and Stougie, Leen},
title = {{Inferring Phylogenetic Networks from Multifurcating Trees via Cherry Picking and Machine Learning}},
journal = {Molecular Phylogenetics and Evolution},
year = {2024},
volume = {199},
pages = {108137},
doi = {10.1016/j.ympev.2024.108137},
url = {https://doi.org/10.1016/j.ympev.2024.108137}
}
[67]
preprint
A Wild Sheep Chase Through an Orchard
arXiv:2408.10769, 2024.
Shows that determining whether an evolutionary network — considered without knowing the direction of time — could have arisen from a tree-like history augmented by horizontal gene transfer is computationally hard, and introduces a new mathematical description of such networks that may help future research make progress despite this hardness.
Orchards are a biologically relevant class of phylogenetic networks as they can describe treelike evolutionary histories augmented with horizontal transfer events. Moreover, the class has attractive mathematical characterizations that can be exploited algorithmically. On the other hand, undirected orchard networks have hardly been studied yet. Here, we prove that deciding whether an undirected, binary phylogenetic network is an orchard -- or equivalently, whether it has an orientation that makes it a rooted orchard -- is NP-hard. For this, we introduce a new characterization of undirected orchards which could be useful for proving positive results.
@misc{dempsey2024wild,
author = {Dempsey, Jordan and van Iersel, Leo and Jones, Mark and Murakami, Yukihiro and Zeh, Norbert},
title = {{A Wild Sheep Chase Through an Orchard}},
year = {2024},
archivePrefix = {arXiv},
eprint = {2408.10769},
doi = {10.48550/arXiv.2408.10769},
url = {https://doi.org/10.48550/arXiv.2408.10769}
}
2023
[66]
journal article
Constructing Phylogenetic Networks via Cherry Picking and Machine Learning
Algorithms for Molecular Biology, 18:13, 2023.
Preliminary version in WABI 2022, LIPIcs 242:16.
Introduces fast heuristic methods, including some guided by a trained machine-learning model, for combining many evolutionary trees into a single explanatory network — a problem existing exact methods could only handle for a handful of trees — and shows the results are reliably close to the best possible solution on both simulated and real data.
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. In this paper, we apply the recently-introduced theoretical framework of cherry picking to design a class of efficient heuristics that are guaranteed to produce a network containing each of the input trees, for datasets consisting of binary trees. Some of the heuristics in this framework are based on the design and training of a machine learning model that captures essential information on the structure of the input trees and guides the algorithms towards better solutions. We also propose simple and fast randomised heuristics that prove to be very effective when run multiple times. Unlike the existing exact methods, our heuristics are applicable to datasets of practical size, and the experimental study we conducted on both simulated and real data shows that these solutions are qualitatively good, always within some small constant factor from the optimum. Moreover, our machine-learned heuristics are one of the first applications of machine learning to phylogenetics and show its promise.
@article{bernardini2023constructing,
author = {Bernardini, Giulia and van Iersel, Leo and Julien, Esther and Stougie, Leen},
title = {{Constructing Phylogenetic Networks via Cherry Picking and Machine Learning}},
journal = {Algorithms for Molecular Biology},
year = {2023},
volume = {18},
pages = {13},
doi = {10.1186/s13015-023-00233-3},
url = {https://doi.org/10.1186/s13015-023-00233-3}
}
[65]
journal article
Embedding phylogenetic trees in networks of low treewidth
Discrete Mathematics & Theoretical Computer Science, 25(2):2, 2023.
Preliminary version in ESA 2022, LIPIcs 244:69.
Gives the first efficient algorithm for checking whether a proposed evolutionary tree is consistent with a network, based on a general measure of how tree-like the network's underlying structure is, extending fast verification to a broader range of networks than earlier specialized methods could handle.
Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called \textsc{Tree Containment}, arises when validating networks constructed by phylogenetic inference methods.We present the first algorithm for (rooted) \textsc{Tree Containment} using the treewidth $t$ of the input network $N$ as parameter, showing that the problem can be solved in $2^{O(t^2)}\cdot|N|$ time and space.
@article{jones2023embedding,
author = {Jones, Mark and Weller, Mathias and van Iersel, Leo},
title = {{Embedding phylogenetic trees in networks of low treewidth}},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2023},
volume = {25},
number = {2},
pages = {2},
archivePrefix = {arXiv},
eprint = {2207.00574},
url = {https://arxiv.org/abs/2207.00574}
}
[64]
journal article
Polynomial invariants for cactuses
Information Processing Letters, 182:106394, 2023.
Develops a more compact and practical mathematical fingerprint for telling different evolutionary networks apart, focusing on a common category of network that includes ordinary trees and simple hybridization networks, improving on earlier such fingerprints that were unwieldy to compute or use.
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 recently there has been interest to also define such invariants for phylogenetic networks, a special type of graph that arises in the area of evolutionary biology. Recently Liu gave a complete invariant for (phylogenetic) trees. However, the polynomial invariants defined thus far for phylogenetic networks that are not trees require vertex labels and either contain a large number of variables, or they have exponentially many terms in the number of reticulations. This can make it difficult to compute these polynomials and to use them to analyse unlabelled networks. In this paper, we shall show how to circumvent some of these difficulties for rooted cactuses and cactuses. As well as being important in other areas such as operations research, rooted cactuses contain some common classes of phylogenetic networks such phylogenetic trees and level-1 networks. More specifically, we define a polynomial $F$ that is a complete invariant for the class of rooted cactuses without vertices of indegree 1 and outdegree 1 that has 5 variables, and a polynomial $Q$ that is a complete invariant for the class of rooted cactuses that has 6 variables \vince{whose degree can be bounded linearly in terms of the size of the rooted cactus}. We also explain how to extend the $Q$ polynomial to define a complete invariant for leaf-labelled rooted cactuses as well as (unrooted) cactuses.
@article{iersel2023polynomial,
author = {van Iersel, Leo and Moulton, Vincent and Murakami, Yukihiro},
title = {{Polynomial invariants for cactuses}},
journal = {Information Processing Letters},
year = {2023},
volume = {182},
pages = {106394},
doi = {10.1016/j.ipl.2023.106394},
url = {https://doi.org/10.1016/j.ipl.2023.106394}
}
[63]
conference paper
Making a Network Orchard by Adding Leaves
WABI 2023, vol. 273, pp. 7:1--7:20 (2023).
Studies how many extra species would need to be added to an evolutionary network to bring it into a well-behaved, easy-to-analyze form, proves that computing this minimum number exactly is computationally hard, and develops a practical optimization method that works well in experiments on both real and simulated data.
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, we study the minimum number of additional leaves needed to make a network orchard. We demonstrate that computing this proximity measure for a given network is NP-hard and describe a tight upper bound. We also give an equivalent measure based on vertex labellings to construct a mixed integer linear programming formulation. Our experimental results, which include both real-world and synthetic data, illustrate the effectiveness of our implementation.
@InProceedings{vaniersel_et_al:LIPIcs.WABI.2023.7,
author = {van Iersel, Leo and Jones, Mark and Julien, Esther and Murakami, Yukihiro},
title = {{Making a Network Orchard by Adding Leaves}},
booktitle = {23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
pages = {7:1--7:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-294-5},
ISSN = {1868-8969},
year = {2023},
volume = {273},
editor = {Belazzougui, Djamal and Ouangraoua, Aïda},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.7},
URN = {urn:nbn:de:0030-drops-186333},
doi = {10.4230/LIPIcs.WABI.2023.7},
annote = {Keywords: Phylogenetics, Network, Orchard Networks, Proximity Measures, NP-hardness}
}
2022
[62]
journal article
An algorithm for reconstructing level-2 phylogenetic networks from trinets
Information Processing Letters, 178:106300, 2022.
Gives an efficient, provably correct method for piecing together a moderately complex evolutionary network from information about every possible triplet of species, extending earlier techniques that only worked for simpler, more tree-like networks, while showing that this building-block approach cannot be pushed further to even more complex networks without fundamentally new ideas.
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 network. The level of a phylogenetic network is a measure of its deviation from being a tree; the higher the level of network, the less treelike it becomes. Various algorithms have been developed for building level-1 networks from small networks. However, level-1 networks may not be able to capture the complexity of some data sets. In this paper, we present a polynomial-time algorithm for constructing a rooted binary level-2 phylogenetic network from a collection of 3-leaf networks or trinets. Moreover, we prove that the algorithm will correctly reconstruct such a network if it is given all of the trinets in the network as input. The algorithm runs in time $O(t\cdot n+n^4)$ with $t$ the number of input trinets and $n$ the number of leaves. We also show that there is a fundamental obstruction to constructing level-3 networks from trinets, and so new approaches will need to be developed for constructing level-3 and higher level-networks.
@article{iersel2022algorithm,
author = {van Iersel, Leo and Kole, Sjors and Moulton, Vincent and Nipius, Leonie},
title = {{An algorithm for reconstructing level-2 phylogenetic networks from trinets}},
journal = {Information Processing Letters},
year = {2022},
volume = {178},
pages = {106300},
doi = {10.1016/j.ipl.2022.106300},
url = {https://doi.org/10.1016/j.ipl.2022.106300}
}
[61]
journal article
A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees
Algorithmica, 84:917--960, 2022.
Presents the first efficient algorithm guaranteed to find the simplest possible well-behaved evolutionary network consistent with any number of given trees, together with a parallelized implementation that, unlike earlier approaches, can handle up to 100 input trees on an ordinary desktop computer.
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((8k)^k \mathrm{poly}(n, t))$ time, where $n$ is the number of leaves of every tree, $t$ is the number of trees, and $k$ is the reticulation number of the constructed network. Moreover, we provide an efficient parallel implementation of the algorithm and show that it can deal with up to $100$ input trees on a standard desktop computer, thereby providing a major improvement over previous phylogenetic network construction methods.
@article{iersel2022practical,
author = {van Iersel, Leo and Janssen, Remie and Jones, Mark and Murakami, Yukihiro and Zeh, Norbert},
title = {{A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees}},
journal = {Algorithmica},
year = {2022},
volume = {84},
pages = {917--960}
}
[60]
journal article
New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
Algorithmica, 84:2050--2087, 2022.
Gives efficient algorithms for finding the smallest possible network, consistent with a biologically motivated timing constraint, that reconciles a set of conflicting evolutionary trees, including a new way to measure how close an arbitrary network comes to satisfying that timing constraint, all backed by a working implementation tested experimentally.
We study the problem of finding a temporal hybridization network for a set of phylogenetic trees that minimizes the number of reticulations. First, we introduce an FPT algorithm for this problem on an arbitrary set of $m$ binary trees with $n$ leaves each with a running time of $O(5^k\cdot n\cdot m)$, where $k$ is the minimum temporal hybridization number. We also present the concept of temporal distance, which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most $d$ and at most $k$ reticulations in $O((8k)^d5^ k\cdot n\cdot m)$ time. Lastly, we introduce a $O(6^kk!\cdot k\cdot n^2)$ time algorithm for computing a minimum temporal hybridization network for a set of two nonbinary trees. We also provide an implementation of all algorithms and an experimental analysis on their performance.
@article{borst2022new,
author = {Borst, Sander and van Iersel, Leo and Jones, Mark and Kelk, Steven},
title = {{New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees}},
journal = {Algorithmica},
year = {2022},
volume = {84},
pages = {2050--2087}
}
[59]
journal article
Level-2 networks from shortest and longest distances
Discrete Applied Mathematics, 306:138--165, 2022.
Shows that although a common type of evolutionary network cannot always be reconstructed from typical genetic distance data alone, it can be reconstructed reliably by combining two complementary kinds of distance information, and identifies exactly which such networks can already be recovered from the simpler kind of distance data by itself.
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 distance matrices, then they must be isomorphic. We further show that level-$2$ networks are reconstructible from their shortest distance matrices if and only if they do not contain a subgraph from a family of graphs. A generator of a network is the graph obtained by deleting all pendant subtrees and suppressing degree-$2$ vertices. We also show that networks with a leaf on every generator side is reconstructible from their induced shortest distance matrix, regardless of level.
@article{huber2022level2,
author = {Huber, Katharina T and van Iersel, Leo and Janssen, Remie and Jones, Mark and Moulton, Vincent and Murakami, Yukihiro},
title = {{Level-2 networks from shortest and longest distances}},
journal = {Discrete Applied Mathematics},
year = {2022},
volume = {306},
pages = {138--165}
}
[58]
journal article
Orchard Networks are Trees with Additional Horizontal Arcs
Bulletin of Mathematical Biology, 84:76, 2022.
Shows that a class of evolutionary networks introduced purely for its computational advantages actually corresponds to a natural and biologically meaningful picture — an ordinary tree with extra sideways connections representing horizontal gene transfer — and proves that one can always move between any two such networks via a bounded number of small rearrangement steps.
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 \emph{horizontal} arcs. Therefore, they are closely related to tree-based networks, where the difference is that in tree-based networks the additional arcs do not need to be horizontal. Then, we use this new characterization to show that the space of orchard networks is connected under the rNNI rearrangement move, with a diameter of at most $4kn+n\lceil \log_2(n) \rceil +2k+6n-8$.
@article{iersel2022orchard,
author = {van Iersel, Leo and Janssen, Remie and Jones, Mark and Murakami, Yukihiro},
title = {{Orchard Networks are Trees with Additional Horizontal Arcs}},
journal = {Bulletin of Mathematical Biology},
year = {2022},
volume = {84},
pages = {76}
}
2021
[57]
journal article
Distinguishing level-1 phylogenetic networks on the basis of data generated by Markov processes
Journal of Mathematical Biology, 83:32, 2021.
Proves that, under standard statistical models of DNA mutation, a fairly broad and biologically relevant class of evolutionary networks can, in principle, always be uniquely recovered from sufficiently long genetic sequences — an essential prerequisite for trusting network-based reconstruction methods built on these models.
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-based methods for reconstructing phylogenetic networks. For these methods to be consistent, the network parameter needs to be identifiable from data generated under the model. Here, we show that the semi-directed network parameter of a triangle-free, level-1 network model with any fixed number of reticulation vertices is generically identifiable under the Jukes-Cantor, Kimura 2-parameter, or Kimura 3-parameter constraints.
@article{gross2021distinguishing,
author = {Gross, Elizabeth and van Iersel, Leo and Janssen, Remie and Jones, Mark and Long, Colby and Murakami, Yukihiro},
title = {{Distinguishing level-1 phylogenetic networks on the basis of data generated by Markov processes}},
journal = {Journal of Mathematical Biology},
year = {2021},
volume = {83},
pages = {32}
}
[56]
journal article
A Unifying Characterization of Tree-based Networks and Orchard Networks using Cherry Covers
Advances in Applied Mathematics, 129:102222, 2021.
Introduces a single unifying mathematical framework, based on decomposing a network's structure into simple building blocks, that explains two previously separate families of easy-to-analyze evolutionary networks, and extends the approach beyond the simplest case where every hybridization event involves exactly two ancestors.
Phylogenetic networks are used to study 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 networks are those that can be obtained by inserting edges between the edges of an underlying tree. Orchard networks are a recently introduced generalization of the class of tree-child networks. Structural characterizations have already been discovered for tree-based networks; this is not the case for orchard networks. In this paper, we introduce cherry covers---a unifying characterization of both network classes---in which we decompose the edges of the networks into so-called cherry shapes and reticulated cherry shapes. We show that cherry covers can be used to characterize the class of tree-based networks as well as the class of orchard networks. Moreover, we also generalize these results to non-binary networks.
@article{iersel2021unifying,
author = {van Iersel, Leo and Janssen, Remie and Jones, Mark and Murakami, Yukihiro and Zeh, Norbert},
title = {{A Unifying Characterization of Tree-based Networks and Orchard Networks using Cherry Covers}},
journal = {Advances in Applied Mathematics},
year = {2021},
volume = {129},
pages = {102222}
}
[55]
journal article
Applicability of several rooted phylogenetic network algorithms for representing the evolutionary history of SARS-CoV-2
BMC Ecology and Evolution, 21:220, 2021.
Applies several evolutionary-network reconstruction methods to real viral genome data from SARS-CoV-2 and related coronaviruses, developing a practical workflow to handle noisy data and computational limits, and using the resulting networks to explore — and partly challenge — existing theories about how SARS-CoV-2 arose through genetic recombination.
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 to recombine frequently, but rooted phylogenetic networks have not yet been used extensively to describe their evolutionary history. Here, we created a workflow to compare the evolutionary history of SARS-CoV-2 with other SARS-like viruses using several rooted phylogenetic network inference algorithms. This workflow includes filtering noise from sets of phylogenetic trees by contracting edges based on branch length and bootstrap support, followed by resolution of multifurcations. We explored the running times of the network inference algorithms, the impact of filtering on the properties of the produced networks, and attempted to derive biological insights regarding the evolution of SARS-CoV-2 from them. The network inference algorithms are capable of constructing rooted phylogenetic networks for coronavirus data, although running-time limitations require restricting such datasets to a relatively small number of taxa. Filtering generally reduces the number of reticulations in the produced networks and increases their temporal consistency. Taxon bat-SL-CoVZC45 emerges as a major and structural source of discordance in the dataset. The tested algorithms often indicate that SARS-CoV-2/RaTG13 is a tree-like clade, with possibly some reticulate activity further back in their history. A smaller number of constructed networks posit SARS-CoV-2 as a possible recombinant, although this might be a methodological artefact arising from the interaction of bat-SL-CoVZC45 discordance and the optimization criteria used. Our results demonstrate that as part of a wider workflow and with careful attention paid to running time, rooted phylogenetic network algorithms are capable of producing plausible networks from coronavirus data. These networks partly corroborate existing theories about SARS-CoV-2, and partly produce new avenues for exploration regarding the location and significance of reticulate activity within the wider group of SARS-like viruses. Our workflow may serve as a model for pipelines in which phylogenetic network algorithms can be used to analyse different datasets and test different hypotheses.
@article{wallin2021applicability,
author = {Wallin, Rosanne and van Iersel, Leo and Kelk, Steven and Stougie, Leen},
title = {{Applicability of several rooted phylogenetic network algorithms for representing the evolutionary history of SARS-CoV-2}},
journal = {BMC Ecology and Evolution},
year = {2021},
volume = {21},
pages = {220}
}
2020
[54]
journal article
Polynomial-Time Algorithms for Phylogenetic Inference Problems involving duplication and reticulation
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 17(1):14--26, 2020.
Preliminary version in AlCoB 2018, LNBI 10849:37–49.
Shows that two seemingly different and previously hard-seeming problems in reconstructing species histories from gene family trees — one involving gene duplication, one involving hybridization — can both surprisingly be solved efficiently using a shared underlying structure, while also cautioning that the optimal solutions these methods produce can be artificially restricted in form, and proposing a refined problem variant that avoids this pitfall while remaining efficiently solvable.
A common problem in phylogenetics is to try to infer a species phylogeny from gene trees. We consider different variants of this problem. The first variant, called Unrestricted Minimal Episodes Inference, aims at inferring a species tree based on a model with speciation and duplication where duplications are clustered in duplication episodes. The goal is to minimize the number of such episodes. The second variant, Parental Hybridization, aims at inferring a species \emph{network} based on a model with speciation and reticulation. The goal is to minimize the number of reticulation events. It is a variant of the well-studied Hybridization Number problem with a more generous view on which gene trees are consistent with a given species network. We show that these seemingly different problems are in fact closely related and can, surprisingly, both be solved in polynomial time, using a structure we call "beaded trees". However, we also show that methods based on these problems have to be used with care because the optimal species phylogenies always have a restricted form. To mitigate this problem, we introduce a new variant of Unrestricted Minimal Episodes Inference that minimizes the duplication episode depth. We prove that this new variant of the problem can also be solved in polynomial time
@article{iersel2020polynomialtime,
author = {van Iersel, Leo and Janssen, Remie and Jones, Mark and Murakami, Yukihiro and Zeh, Norbert},
title = {{Polynomial-Time Algorithms for Phylogenetic Inference Problems involving duplication and reticulation}},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
year = {2020},
volume = {17},
number = {1},
pages = {14--26}
}
[53]
journal article
Reconstructibility of unrooted level-k phylogenetic networks from distances
Advances in Applied Mathematics, 120:102075, 2020.
Determines precisely how complex an evolutionary network, considered without a direction of time, can become before it can no longer be reliably reconstructed from typical measurements of genetic distance between species, pinpointing the exact boundary between what can and cannot be recovered this way.
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 information on the evolutionary distances between present-day taxa. Here, we consider the following question. For which~$k$ are unrooted level-$k$ networks uniquely determined by their distance matrices? We consider this question for shortest distances as well as for the case that the multisets of all distances is given. We prove that level-$1$ networks and level-$2$ networks are reconstructible from their shortest distances and multisets of distances, respectively. Furthermore we show that, in general, networks of level higher than~$1$ are not reconstructible from shortest distances and that networks of level higher than~$2$ are not reconstructible from their multisets of distances.
@article{iersel2020reconstructibility,
author = {van Iersel, Leo and Moulton, Vincent and Murakami, Yukihiro},
title = {{Reconstructibility of unrooted level-k phylogenetic networks from distances}},
journal = {Advances in Applied Mathematics},
year = {2020},
volume = {120},
pages = {102075}
}
2019
[52]
journal article
Finding a most parsimonious or likely tree in a network with respect to an alignment
Journal of Mathematical Biology, 78(1-2):527--547, 2019.
Shows that, even in a fairly simple setting, finding which single evolutionary tree embedded within a larger network best explains a given set of aligned DNA sequences — whether by a parsimony or a likelihood criterion — is computationally hard in general, though the paper also explains why both criteria can often still be solved well in practice.
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 of taxa X and a rooted phylogenetic network N whose leaves are labelled by X, it is NP-hard to locate the most parsimonious phylogenetic tree displayed by N (with respect to A) even when the level of N - the maximum number of reticulation nodes within a biconnected component - is 1 and A contains only 2 distinct states. (If, additionally, gaps are allowed the problem becomes APX-hard.) We also show that under the same conditions, and assuming a simple binary symmetric model of character evolution, finding the most likely tree displayed by the network is NP-hard. These negative results contrast with earlier work on parsimony in which it is shown that if A consists of a single column the problem is fixed parameter tractable in the level. We conclude with a discussion of why, despite the NP-hardness, both the parsimony and likelihood problem can likely be well-solved in practice.
@article{kelk2019finding,
author = {Kelk, Steven and Pardi, Fabio and Scornavacca, Celine and van Iersel, Leo},
title = {{Finding a most parsimonious or likely tree in a network with respect to an alignment}},
journal = {Journal of Mathematical Biology},
year = {2019},
volume = {78},
number = {1-2},
pages = {527--547}
}
[51]
journal article
Not all phylogenetic networks are leaf-reconstructible
Journal of Mathematical Biology, 79(5):1623--1638, 2019.
Disproves a natural conjecture that any evolutionary network with enough species can always be uniquely pieced back together from the smaller networks obtained by removing one species at a time, providing counterexamples for every possible number of species from four upward.
Unrooted phylogenetic networks are graphs used to represent evolutionary relationships. Accurately reconstructing such networks is of great relevance for evolutionary biology. It has recently been conjectured that all phylogenetic networks with at least five leaves can be uniquely reconstructed from their subnetworks obtained by deleting a single leaf and suppressing degree-2 vertices. Here, we show that this conjecture is false, by presenting a counter example for each possible number of leaves that is at least~4. Moreover, we show that the conjecture is still false when restricted to binary networks.
@article{erds2019not,
author = {Erdős, Péter L and van Iersel, Leo and Jones, Mark},
title = {{Not all phylogenetic networks are leaf-reconstructible}},
journal = {Journal of Mathematical Biology},
year = {2019},
volume = {79},
number = {5},
pages = {1623--1638}
}
[50]
journal article
Reconstructing Tree-Child Networks from Reticulate-Edge-Deleted Subnetworks
Bulletin of Mathematical Biology, 81(10):3823--3863, 2019.
Shows that a well-behaved class of evolutionary network can always be uniquely and efficiently reconstructed just from the collection of simpler networks obtained by removing one hybridization connection at a time, as long as the network is not too simple to begin with.
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 component is $k$. Here, we show that level-$k$ tree-child networks are encoded by their reticulate-edge-deleted subnetworks, which are subnetworks obtained by deleting a single reticulation edge, if $k\geq 2$. Following this, we provide a polynomial-time algorithm for uniquely reconstructing such networks from their reticulate-edge-deleted subnetworks. Moreover, we show that this can even be done when considering subnetworks obtained by deleting one reticulation edge from each biconnected component with $k$ reticulations.
@article{murakami2019reconstructing,
author = {Murakami, Yukihiro and van Iersel, Leo and Janssen, Remie and Jones, Mark and Moulton, Vincent},
title = {{Reconstructing Tree-Child Networks from Reticulate-Edge-Deleted Subnetworks}},
journal = {Bulletin of Mathematical Biology},
year = {2019},
volume = {81},
number = {10},
pages = {3823--3863}
}
[49]
journal article
Deciding the existence of a cherry-picking sequence is hard on two trees
Discrete Applied Mathematics, 260:131--143, 2019.
Proves that a key computational test underlying the construction of biologically realistic, temporally consistent evolutionary networks from two conflicting trees is already computationally hard for just two trees, substantially strengthening earlier results that only showed hardness once at least eight trees were involved.
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 temporal phylogenetic networks, our result proves that it is NP-complete to determine the existence of a temporal phylogenetic network that contains topological embeddings of both trees. The hardness result also greatly strengthens previous inapproximability results for the minimum temporal-hybridization number problem. This is the optimization version of the problem where we wish to construct a temporal phylogenetic network that topologically embeds two given rooted binary phylogenetic trees and that has a minimum number of indegree-2 nodes, which represent events such as hybridization and horizontal gene transfer. We end on a positive note, pointing out that fixed parameter tractability results in this area are likely to ensure the continued relevance of the temporal phylogenetic network model.
@article{dcker2019deciding,
author = {Döcker, Janosch and van Iersel, Leo and Kelk, Steven and Linz, Simone},
title = {{Deciding the existence of a cherry-picking sequence is hard on two trees}},
journal = {Discrete Applied Mathematics},
year = {2019},
volume = {260},
pages = {131--143}
}
[48]
journal article
A third strike against perfect phylogeny
Systematic Biology, 68(5):814--827, 2019.
Disproves a long-standing conjecture about a simple "local checking" shortcut for confirming that a set of evolutionary traits could all have arisen just once in history, showing that no such fixed-size shortcut can exist once traits have enough possible states — closing off one hoped-for route to faster algorithms.
Perfect phylogenies are fundamental in the study of evolutionary trees because they capture the situation when each evolutionary trait emerges only once in history; if such events are believed to be rare, then by Occam's Razor such parsimonious trees are preferable as a hypothesis of evolution. A classical result states that 2-state characters permit a perfect phylogeny precisely if each subset of 2 characters permits one. More recently, it was shown that for 3-state characters the same property holds but for size-3 subsets. A long-standing open problem asked whether such a constant exists for each number of states. More precisely, it has been conjectured that for any fixed integer $r$, there exists a constant $f(r)$ such that a set of $r$-state characters $C$ has a perfect phylogeny if and only if every subset of at most $f(r)$ characters has a perfect phylogeny. In this paper, we show that this conjecture is false. In particular, we show that for any constant $t$, there exists a set $C$ of $8$-state characters such that $C$ has no perfect phylogeny, but there exists a perfect phylogeny for every subset of $t$ characters. This negative result complements the two negative results ("strikes") of Bodlaender et al. We reflect on the consequences of this third strike, pointing out that while it does close off some routes for efficient algorithm development, many others remain open.
@article{iersel2019third,
author = {van Iersel, Leo and Jones, Mark and Kelk, Steven},
title = {{A third strike against perfect phylogeny}},
journal = {Systematic Biology},
year = {2019},
volume = {68},
number = {5},
pages = {814--827}
}
[47]
preprint
Cutting an alignment with Ockham’s razor
arXiv:1910.11041, 2019.
Develops and tests several parsimony-based computational methods for automatically detecting where genetic recombination has spliced together DNA sequences with different evolutionary histories within a larger alignment, showing which formulations of the problem can be solved efficiently and which turn out to be computationally hard.
In this article, we investigate different parsimony-based approaches towards finding recombination breakpoints in a multiple sequence alignment. This recombination detection task is crucial in order to avoid errors in evolutionary analyses caused by mixing together portions of sequences which had a different evolution history. Following an overview of the field of recombination detection, we formulate four computational problems for this task with different objective functions. The four problems aim to minimize (1) the total homoplasy of all blocks (2) the maximum homoplasy per block (3) the total homoplasy ratio of all blocks and (4) the maximum homoplasy ratio per block. We describe algorithms for each of these problems, which are fixed-parameter tractable (FPT) when the characters are binary. We have implemented and tested the algorithms on simulated data, showing that minimizing the total homoplasy gives, in most cases, the most accurate results. Our implementation and experimental data have been made publicly available. Finally, we also consider the problem of combining blocks into non-contiguous blocks consisting of at most p contiguous parts. Fixing the homoplasy h of each block to 0, we show that this problem is NP-hard when p >= 3, but polynomial-time solvable for p = 2. Furthermore, the problem is FPT with parameter h for binary characters when p = 2. A number of interesting problems remain open.
@misc{jones2019cutting,
author = {Jones, Mark and Gambette, Philippe and van Iersel, Leo and Janssen, Remie and Kelk, Steven and Pardi, Fabio and Scornavacca, Celine},
title = {{Cutting an alignment with Ockham’s razor}},
year = {2019},
archivePrefix = {arXiv},
eprint = {1910.11041},
url = {https://arxiv.org/abs/1910.11041}
}
2018
[46]
journal article
A Priori TSP in the Scenario Model
Discrete Applied Mathematics, 250:313--341, 2018.
Preliminary version in WAOA 2016, LNCS 10138:183–196.
Studies a variant of the classic traveling-salesperson problem in which the customers to be visited are not known in advance but instead come from a limited menu of possible scenarios, analyzing how well one can pre-plan a route that stays close to optimal no matter which scenario actually occurs.
@article{ee2018priori,
author = {van Ee, Martijn and van Iersel, Leo and Janssen, Teun and Sitters, Rene},
title = {{A Priori TSP in the Scenario Model}},
journal = {Discrete Applied Mathematics},
year = {2018},
volume = {250},
pages = {313--341}
}
[45]
journal article
On unrooted and root-uncertain variants of several well-known phylogenetic network problems
Algorithmica, 80(11):2993--3022, 2018.
Addresses the practical difficulty that accurately determining the root (the starting point in time) of an evolutionary tree is notoriously hard, by studying versions of key network-reconstruction problems that don't require knowing the root in advance — showing that some of these relaxed problems remain efficiently solvable while others become considerably harder, but can still be solved well even when the root is deliberately left flexible.
The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view accurately inferring the root location in a phylogenetic tree is notoriously difficult and poor root placement can artificially inflate the hybridization number. To this end we study a number of relaxed variants of this problem. We start by showing that the fundamental problem of determining whether an unrooted phylogenetic network displays (i.e. embeds) an unrooted phylogenetic tree, is NP-hard. On the positive side we show that this problem is FPT in reticulation number. In the rooted case the corresponding FPT result is trivial, but here we require more subtle argumentation. Next we show that the hybridization number problem for unrooted networks (when given two unrooted trees) is equivalent to the problem of computing the tree bisection and reconnect distance of the two unrooted trees. In the third part of the paper we consider the "root uncertain" variant of hybridization number. Here we are free to choose the root location in each of a set of unrooted input trees such that the hybridization number of the resulting rooted trees is minimized. On the negative side we show that this problem is APX-hard. On the positive side, we show that the problem is FPT in the hybridization number, via kernelization, for any number of input trees.
@article{iersel2018unrooted,
author = {van Iersel, Leo and Kelk, Steven and Stamoulis, Georgios and Stougie, Leen and Boes, Olivier},
title = {{On unrooted and root-uncertain variants of several well-known phylogenetic network problems}},
journal = {Algorithmica},
year = {2018},
volume = {80},
number = {11},
pages = {2993--3022}
}
[44]
journal article
Nonbinary tree-based phylogenetic networks
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 14(1):205--217, 2018.
Extends the theory of evolutionary networks built from an underlying tree plus extra connections to the more realistic case where species can split into more than two descendants at once, giving simple criteria for recognizing such networks that can be checked efficiently, and demonstrating the approach on real biological examples.
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 networks are called tree-based. Here, we consider two possible generalizations of this concept to nonbinary networks, which we call tree-based and strictly-tree-based nonbinary phylogenetic networks. We give simple graph-theoretic characterizations of tree-based and strictly-tree-based nonbinary phylogenetic networks. Moreover, we show for each of these two classes that it can be decided in polynomial time whether a given network is contained in the class. Our approach also provides a new view on tree-based binary phylogenetic networks. Finally, we discuss two examples of nonbinary phylogenetic networks in biology and show how our results can be applied to them.
@article{jetten2018nonbinary,
author = {Jetten, Laura and van Iersel, Leo},
title = {{Nonbinary tree-based phylogenetic networks}},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
year = {2018},
volume = {14},
number = {1},
pages = {205--217}
}
[43]
journal article
Improved maximum parsimony models for phylogenetic networks
Systematic Biology, 67(3):518-542, 2018.
Proposes a more biologically realistic way of scoring how well an evolutionary network explains observed genetic data under the parsimony principle, capturing scenarios that earlier standard definitions could not represent, and lays algorithmic groundwork for building reconstruction methods around this improved scoring approach.
Phylogenetic networks are well 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 scenarios that cannot be modeled by the definitions currently present in the literature (namely, the "hardwired" and "softwired" parsimony). Building on this new definition, we provide several algorithmic results that lay the foundations for new parsimony-based methods for phylogenetic network reconstruction.
@article{iersel2018improved,
author = {van Iersel, Leo and Jones, Mark and Scornavacca, Celine},
title = {{Improved maximum parsimony models for phylogenetic networks}},
journal = {Systematic Biology},
year = {2018},
volume = {67},
number = {3},
pages = {518-542}
}
[42]
journal article
Exploring the tiers of rooted phylogenetic network space using tail moves
Bulletin of Mathematical Biology, 80(8):2177--2208, 2018.
Studies how to move between different possible shapes of an evolutionary network by making small, local edits, showing that a particularly simple and restricted type of edit already suffices to transform any network into any other network of the same complexity, gives bounds on how many such edits are ever needed, and shows that finding the shortest possible sequence of edits is computationally hard.
Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rNNI (rooted Nearest Neighbour Interchange) and rSPR (rooted Subtree Prune and Regraft). Recently, these moves were generalized to rooted phylogenetic networks, which are a more suitable representation of reticulate evolutionary histories, and it was shown that any two rooted phylogenetic networks of the same complexity are connected by a sequence of either rSPR or rNNI moves. Here, we show that this is possible using only tail moves, which are a restricted version of rSPR moves on networks that are more closely related to rSPR moves on trees. The connectedness still holds even when we restrict to distance-1 tail moves (a localized version of tail-moves). Moreover, we give bounds on the number of (distance-1) tail moves necessary to turn one network into another, which in turn yield new bounds for rSPR, rNNI and SPR (i.e. the equivalent of rSPR on unrooted networks). The upper bounds are constructive, meaning that we can actually find a sequence with at most this length for any pair of networks. Finally, we show that finding a shortest sequence of tail or rSPR moves is NP-hard.
@article{janssen2018exploring,
author = {Janssen, Remie and Jones, Mark and Erdős, Péter L and van Iersel, Leo and Scornavacca, Celine},
title = {{Exploring the tiers of rooted phylogenetic network space using tail moves}},
journal = {Bulletin of Mathematical Biology},
year = {2018},
volume = {80},
number = {8},
pages = {2177--2208}
}
[41]
journal article
Leaf-reconstructibility of phylogenetic networks
SIAM Journal on Discrete Mathematics, 32(3):2047--2066, 2018.
Investigates which evolutionary networks can be uniquely pieced back together from the smaller networks obtained by removing just one species at a time, showing that many practically important classes of networks — including ordinary trees and most moderately complex networks — can always be reconstructed this way, while leaving open whether this holds universally.
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 common approach used in phylogenetics to build a phylogenetic network on $X$ involves constructing it from networks on subsets of $X$. Here we consider the question of which (unrooted) phylogenetic networks are leaf-reconstructible, i.e. which networks can be uniquely reconstructed from the set of networks obtained from it by deleting a single leaf (its $X$-deck). This problem is closely related to the (in)famous reconstruction conjecture in graph theory but, as we shall show, presents distinct challenges. We show that some large classes of phylogenetic networks are reconstructible from their $X$-deck. This includes phylogenetic trees, binary networks containing at least one non-trivial cut-edge, and binary level-4 networks (the level of a network measures how far it is from being a tree). We also show that for fixed $k$, almost all binary level-$k$ phylogenetic networks are leaf-reconstructible. As an application of our results, we show that a level-3 network $N$ can be reconstructed from its quarnets, that is, 4-leaved networks that are induced by $N$ in a certain recursive fashion. Our results lead to several interesting open problems which we discuss, including the conjecture that all phylogenetic networks with at least five leaves are leaf-reconstructible.
@article{iersel2018leafreconstructibility,
author = {van Iersel, Leo and Moulton, Vincent},
title = {{Leaf-reconstructibility of phylogenetic networks}},
journal = {SIAM Journal on Discrete Mathematics},
year = {2018},
volume = {32},
number = {3},
pages = {2047--2066}
}
[40]
preprint
Parallel Machine Scheduling with a Single Resource per Job
arXiv:1809.05009, 2018.
Studies how to schedule jobs across multiple machines, where each job also needs a shared resource, so that jobs finish as quickly as possible on average; shows the basic case can be solved exactly and efficiently, gives a provably near-optimal shortcut for a common special case, and shows that several natural variations of the problem are computationally hard.
We study the problem of scheduling jobs on parallel machines minimizing the total completion time, with each job using exactly one resource. First, we derive fundamental properties of the problem and show that the problem is polynomially solvable if $p_j = 1$. Then we look at a variant of the shortest processing time rule as an approximation algorithm for the problem and show that it gives at least a $(2-\frac{1}{m})$-approximation. Subsequently, we show that, although the complexity of the problem remains open, three related problems are $\mathcal{NP}$-hard. In the first problem, every resource also has a subset of machines on which it can be used. In the second problem, once a resource has been used on a machine it cannot be used on any other machine, hence all jobs using the same resource need to be scheduled on the same machine. In the third problem, every job needs exactly two resources instead of just one.
@misc{janssen2018parallel,
author = {Janssen, Teun and Swennenhuis, Céline and Bitar, Abdoul and Bosman, Thomas and Gijswijt, Dion and van Iersel, Leo and Dauzére-Pérès, Stèphane and Yugma, Claude},
title = {{Parallel Machine Scheduling with a Single Resource per Job}},
year = {2018},
archivePrefix = {arXiv},
eprint = {1809.05009},
url = {https://arxiv.org/abs/1809.05009}
}
2017
[39]
journal article
Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets
Algorithmica, 77(1):173--200, 2017.
Studies how to reconstruct a moderately complex evolutionary network when only partial information about its smallest building blocks is available, showing this remains efficiently solvable using only the very smallest building blocks but becomes computationally hard once slightly larger ones are involved, and providing some of the first general methods for assembling a network from an incomplete collection of smaller networks.
Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set $\mathcal{T}$ of binary binets or trinets over a set $X$ of taxa, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an $O(3^{|X|} poly(|X|))$ time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.
@article{huber2017reconstructing,
author = {Huber, Katharina and van Iersel, Leo and Moulton, Vincent and Scornavacca, Celine and Wu, Taoyang},
title = {{Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets}},
journal = {Algorithmica},
year = {2017},
volume = {77},
number = {1},
pages = {173--200}
}
[38]
journal article
Binets: fundamental building blocks for phylogenetic networks
Bulletin of Mathematical Biology, 79(5):1135--1154, 2017.
Studies binets, the simplest possible building blocks into which an evolutionary network can be broken down, showing that although they cannot pin down a network's exact branching pattern, they always reveal how many hybridization events it contains, and that testing whether such building blocks can be assembled into a single network ranges from efficiently solvable to as hard as one of the notoriously difficult problems in graph theory, depending on the network's complexity.
Phylogenetic networks are a generalization of evolutionary trees that are used by biologists to represent the evolution of organisms which have undergone reticulate evolution. Essentially, a phylogenetic network is a directed acyclic graph having a unique root in which the leaves are labelled by a given set of species. Recently, some approaches have been developed to construct phylogenetic networks from collections of networks on 2- and 3-leaved networks, which are known as binets and trinets, respectively. Here we study in more depth properties of collections of binets, one of the simplest possible types of networks into which a phylogenetic network can be decomposed. More specifically, we show that if a collection of level-1 binets is compatible with some binary network, then it is also compatible with a binary level-1 network. Our proofs are based on useful structural results concerning lowest stable ancestors in networks. In addition, we show that, although the binets do not determine the topology of the network, they do determine the number of reticulations in the network, which is one of its most important parameters. We also consider algorithmic questions concerning binets. We show that deciding whether an arbitrary set of binets is compatible with some network is at least as hard as the well-known graph isomorphism problem. However, if we restrict to level-1 binets, it is possible to decide in polynomial time whether there exists a binary network that displays all the binets. We also show that to find a network that displays a maximum number of the binets is NP-hard, but that there exists a simple polynomial-time 1/3-approximation algorithm for this problem. It is hoped that these results will eventually assist in the development of new methods for constructing phylogenetic networks from collections of smaller networks.
@article{iersel2017binets,
author = {van Iersel, Leo and Moulton, Vincent and de Swart, Eveline and Wu, Taoyang},
title = {{Binets: fundamental building blocks for phylogenetic networks}},
journal = {Bulletin of Mathematical Biology},
year = {2017},
volume = {79},
number = {5},
pages = {1135--1154}
}
[37]
journal article
Graph realizations constrained by skeleton graphs
The Electronic Journal of Combinatorics, 24(2):P2.47, 2017.
Develops a more flexible mathematical framework for describing networks whose nodes are grouped into categories, with prescribed numbers of connections both within and between groups — useful for capturing the different connection patterns typically seen in social networks versus natural or biological networks — and works out two practically important special cases in detail.
In 2008 Amanatidis, Green and Mihail introduced the Joint Degree Matrix (JDM) model to capture the fundamental difference in assortativity of networks in nature studied by the physical and life sciences and social networks studied in the social sciences. In 2014 Czabarka proposed a direct generalization of the JDM model, the Partition Adjacency Matrix (PAM) model. In the PAM model the vertices have specified degrees, and the vertex set itself is partitioned into classes. For each pair of vertex classes the number of edges between the classes in a graph realization is prescribed. In this paper we apply the new {\em skeleton graph} model to describe the same information as the PAM model. Our model is more convenient for handling problems with low number of partition classes or with special topological restrictions among the classes. We investigate two particular cases in detail: (i) when there are only two vertex classes and (ii) when the skeleton graph contains at most one cycle.
@article{erds2017graph,
author = {Erdős, Péter L and Hartke, Stephen G and van Iersel, Leo and Miklós, István},
title = {{Graph realizations constrained by skeleton graphs}},
journal = {The Electronic Journal of Combinatorics},
year = {2017},
volume = {24},
number = {2},
pages = {P2.47}
}
[36]
journal article
Rearrangement moves on rooted phylogenetic networks
PLoS Computational Biology, 13(8):e1005611, 2017.
Introduces a set of basic edit operations for reshaping an evolutionary network step by step, proves that repeatedly applying them can turn any network into any other network of comparable or different complexity, and shows that these operations reduce to the well-known editing moves used for ordinary trees when applied to a tree-like network — providing a practical foundation for network search algorithms.
Phylogenetic tree reconstruction is usually done by local search heuristics that explore the space of the possible tree topologies via simple rearrangements of their structure. Tree rearrangement heuristics have been used in combination with practically all optimization criteria in use, from maximum likelihood and parsimony to distance-based principles, and in a Bayesian context. Their basic components are rearrangement moves that specify all possible ways of generating alternative phylogenies from a given one, and whose fundamental property is to be able to transform, by repeated application, any phylogeny into any other phylogeny. Despite their long tradition in tree-based phylogenetics, very little research has gone into studying similar rearrangement operations for phylogenetic network-that is, phylogenies explicitly representing scenarios that include reticulate events such as hybridization, horizontal gene transfer, population admixture, and recombination. To fill this gap, we propose "horizontal" moves that ensure that every network of a certain complexity can be reached from any other network of the same complexity, and "vertical" moves that ensure reachability between networks of different complexities. When applied to phylogenetic trees, our horizontal moves-named rNNI and rSPR-reduce to the best-known moves on rooted phylogenetic trees, nearest-neighbor interchange and rooted subtree pruning and regrafting. Besides a number of reachability results-separating the contributions of horizontal and vertical moves-we prove that rNNI moves are local versions of rSPR moves, and provide bounds on the sizes of the rNNI neighborhoods. The paper focuses on the most biologically meaningful versions of phylogenetic networks, where edges are oriented and reticulation events clearly identified. Moreover, our rearrangement moves are robust to the fact that networks with higher complexity usually allow a better fit with the data. Our goal is to provide a solid basis for practical phylogenetic network reconstruction.
@article{gambette2017rearrangement,
author = {Gambette, Philippe and van Iersel, Leo and Jones, Mark and Lafond, Manuel and Pardi, Fabio and Scornavacca, Celine},
title = {{Rearrangement moves on rooted phylogenetic networks}},
journal = {PLoS Computational Biology},
year = {2017},
volume = {13},
number = {8},
pages = {e1005611}
}
2016
[35]
journal article
Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees
Theoretical Computer Science, 609(1):1--21, 2016.
Studies when a set of ordering requirements on items — a problem closely related to reconciling conflicting evolutionary trees — can be satisfied by combining two or more separate orderings instead of just one, giving a complete classification of which variants remain easy and which become hard, and proving results about how many trees are needed, in the worst case, to satisfy all the requirements simultaneously in the biologically relevant version of the problem.
A ternary permutation constraint satisfaction problem (CSP) is specified by a subset Pi of the symmetric group S_3. An instance of such a problem consists of a set of variables V and a set of constraints C, where each constraint is an ordered triple of distinct elements from V. The goal is to construct a linear order alpha on V such that, for each constraint (a,b,c) in C, the ordering of a,b,c induced by alpha is in Pi. Excluding symmetries and trivial cases there are 11 such problems, and their complexity is well known. Here we consider the variant of the problem, denoted 2-Pi, where we are allowed to construct two linear orders alpha and beta and each constraint needs to be satisfied by at least one of the two. We give a full complexity classification of all 11 2-Pi problems, observing that in the switch from one to two linear orders the complexity landscape changes quite abruptly and that hardness proofs become rather intricate. We then focus on one of the 11 problems in particular, which is closely related to the '2-Caterpillar Compatibility' problem in the phylogenetics literature. We show that this particular CSP remains hard on three linear orders, and also in the biologically relevant case when we swap three linear orders for three phylogenetic trees, yielding the '3-Tree Compatibility' problem. Due to the biological relevance of this problem we also give extremal results concerning the minimum number of trees required, in the worst case, to satisfy a set of rooted triplet constraints on n leaf labels.
@article{iersel2016satisfying,
author = {van Iersel, Leo and Kelk, Steven and Lekic, Nela and Linz, Simone},
title = {{Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees}},
journal = {Theoretical Computer Science},
year = {2016},
volume = {609},
number = {1},
pages = {1--21}
}
[34]
journal article
Phylogenetic incongruence through the lens of Monadic Second Order logic
Journal of Graph Algorithms and Applications, 20(2):189--215, 2016.
Introduces a powerful logical tool from theoretical computer science, not previously well known in this field, to give short and elegant proofs that several notoriously hard-to-compute measures of disagreement between evolutionary trees can nonetheless be computed efficiently whenever that disagreement is limited, demonstrating the broader potential of this tool for phylogenetics.
Within the field of phylogenetics there is growing interest in measures for summarising the dissimilarity, or incongruence, of two or more phylogenetic trees. Many of these measures are NP-hard to compute and this has stimulated a considerable volume of research into fixed parameter tractable algorithms. In this article we use Monadic Second Order logic to give alternative, compact proofs of fixed parameter tractability for several well-known incongruence measures. In doing so we wish to demonstrate the considerable potential of MSOL - machinery still largely unknown outside the algorithmic graph theory community - within phylogenetics. A crucial component of this work is the observation that many measures, when bounded, imply the existence of an agreement forest of bounded size, which in turn implies that an auxiliary graph structure, the display graph, has bounded treewidth. It is this bound on treewidth that makes the machinery of MSOL available for proving fixed parameter tractability.
@article{kelk2016phylogenetic,
author = {Kelk, Steven and van Iersel, Leo and Scornavacca, Celine and Weller, Mathias},
title = {{Phylogenetic incongruence through the lens of Monadic Second Order logic}},
journal = {Journal of Graph Algorithms and Applications},
year = {2016},
volume = {20},
number = {2},
pages = {189--215}
}
[33]
journal article
Kernelizations for the hybridization number problem on multiple nonbinary trees
Journal of Computer and System Sciences, 82(6):1075--1089, 2016.
Preliminary version in WG 2014, LNCS 8747:299–311.
Shows that the problem of finding the simplest evolutionary network explaining several conflicting, not-necessarily-fully-resolved evolutionary trees can always be shrunk down to a much smaller instance before being solved exactly, and demonstrates using simulated data that this simplification step meaningfully speeds up solving the problem in practice.
Given a finite set $X$, a collection $\mathcal{T}$ of rooted phylogenetic trees on $X$ and an integer $k$, the Hybridization Number problem asks if there exists a phylogenetic network on $X$ that displays all trees from $\mathcal{T}$ and has reticulation number at most $k$. We show two kernelization algorithms for Hybridization Number, with kernel sizes $4k(5k)^t$ and $20k^2(Δ^+-1)$ respectively, with $t$ the number of input trees and $Δ^+$ their maximum outdegree. Experiments on simulated data demonstrate the practical relevance of these kernelization algorithms. In addition, we present an $n^{f(k)}t$-time algorithm, with $n=|X|$ and $f$ some computable function of $k$.
@article{iersel2016kernelizations,
author = {van Iersel, Leo and Kelk, Steven and Scornavacca, Celine},
title = {{Kernelizations for the hybridization number problem on multiple nonbinary trees}},
journal = {Journal of Computer and System Sciences},
year = {2016},
volume = {82},
number = {6},
pages = {1075--1089}
}
[32]
journal article
TriLoNet: Piecing together small networks to reconstruct reticulate evolutionary histories
Molecular Biology and Evolution, 33(8):2151--2162, 2016.
Presents TriLoNet, free software that reconstructs evolutionary networks directly from DNA sequence data by combining information from every possible group of three species, shown through simulations to avoid overestimating the number of hybridization events compared to an earlier competing method, and demonstrated on real recombining sequence data.
Phylogenetic networks are a generalization of evolutionary trees that can be used to represent reticulate processes such as hybridization and recombination. Here, we introduce a new approach called TriLoNet (Trinet Level- one Network algorithm) to construct such networks directly from sequence alignments which works by piecing together smaller phylogenetic networks. More specifically, using a bottom up approach similar to Neighbor-Joining, TriLoNet constructs level-1 networks (networks that are somewhat more general than trees) from smaller level-1 networks on three taxa. In simulations, we show that TriLoNet compares well with Lev1athan, a method for reconstructing level-1 networks from three-leaved trees. In particular, in simulations we find that Lev1athan tends to generate networks that overestimate the number of reticulate events as compared with those generated by TriLoNet. We also illustrate TriLoNet's applicability using simulated and real sequence data involving recombination, demonstrating that it has the potential to reconstruct informative reticulate evolutionary histories. TriLoNet has been implemented in JAVA and is freely available at https://www.uea.ac.uk/computing/TriLoNet.
@article{oldman2016trilonet,
author = {Oldman, James and Wu, Taoyang and van Iersel, Leo and Moulton, Vincent},
title = {{TriLoNet: Piecing together small networks to reconstruct reticulate evolutionary histories}},
journal = {Molecular Biology and Evolution},
year = {2016},
volume = {33},
number = {8},
pages = {2151--2162}
}
[31]
journal article
Hybridization Number on Three Rooted Binary Trees is EPT
SIAM Journal on Discrete Mathematics, 30(3):1607--1631, 2016.
Gives the first efficient algorithm, with a running time that scales gracefully with the number of hybridization events, for finding the simplest network explaining three conflicting evolutionary trees at once — extending a previously known efficient method that only worked for two trees, by overcoming fundamental extra difficulties that appear once a third tree is added.
Phylogenetic networks are leaf-labelled directed acyclic graphs that are used to describe non-treelike evolutionary histories and are thus a generalization of phylogenetic trees. The hybridization number of a phylogenetic network is the sum of all indegrees minus the number of nodes plus one. The Hybridization Number problem takes as input a collection of phylogenetic trees and asks to construct a phylogenetic network that contains an embedding of each of the input trees and has a smallest possible hybridization number. We present an algorithm for the Hybridization Number problem on three binary trees on $n$ leaves, which runs in time $O(c^k poly(n))$, with $k$ the hybridization number of an optimal network and $c$ a constant. For two trees, an algorithm with running time $O(3.18^k n)$ was proposed before whereas an algorithm with running time $O(c^k poly(n))$ had prior to this article remained elusive for more than two trees. The algorithm for two trees uses the close connection to acyclic agreement forests to achieve a linear exponent in the running time, while previous algorithms for more than two trees (explicitly or implicitly) relied on a brute force search through all possible underlying network topologies, leading to running times that are not $O(c^k poly(n))$ for any $c$. The connection to acyclic agreement forests is much weaker for more than two trees, so even given the right agreement forest, reconstructing the network poses major challenges. We prove novel structural results that allow us to reconstruct a network without having to guess the underlying topology. Our techniques generalize to more than three input trees with the exception of one key lemma that maps nodes in the network to tree nodes and, thus, minimizes the amount of guessing involved in constructing the network. The main open problem therefore is to establish a similar mapping for more than three trees.
@article{iersel2016hybridization,
author = {van Iersel, Leo and Kelk, Steven and Lekic, Nela and Whidden, Chris and Zeh, Norbert},
title = {{Hybridization Number on Three Rooted Binary Trees is EPT}},
journal = {SIAM Journal on Discrete Mathematics},
year = {2016},
volume = {30},
number = {3},
pages = {1607--1631}
}
[30]
journal article
Do branch lengths help to locate a tree in a phylogenetic network?
Bulletin of Mathematical Biology, 78(9):1773--1795, 2016.
Investigates whether knowing how much evolutionary change occurred along each branch — information usually available for trees but so far ignored in this context — can help determine whether a given tree is consistent with a larger evolutionary network; shows this remains computationally hard in general, but gives efficient methods for practically important special cases.
Phylogenetic networks are increasingly used in evolutionary biology to represent the history of species that have undergone reticulate events such as horizontal gene transfer, hybrid speciation and recombination. One of the most fundamental questions that arise in this context is whether the evolution of a gene with one copy in all species can be explained by a given network. In mathematical terms, this is often translated in the following way: is a given phylogenetic tree contained in a given phylogenetic network? Recently this tree containment problem has been widely investigated from a computational perspective, but most studies have only focused on the topology of the phylo- genies, ignoring a piece of information that, in the case of phylogenetic trees, is routinely inferred by evolutionary analyses: branch lengths. These measure the amount of change (e.g., nucleotide substitutions) that has occurred along each branch of the phylogeny. Here, we study a number of versions of the tree containment problem that explicitly account for branch lengths. We show that, although length information has the potential to locate more precisely a tree within a network, the problem is computationally hard in its most general form. On a positive note, for a number of special cases of biological relevance, we provide algorithms that solve this problem efficiently. This includes the case of networks of limited complexity, for which it is possible to recover, among the trees contained by the network with the same topology as the input tree, the closest one in terms of branch lengths.
@article{gambette2016do,
author = {Gambette, Philippe and van Iersel, Leo and Kelk, Steven and Pardi, Fabio and Scornavacca, Celine},
title = {{Do branch lengths help to locate a tree in a phylogenetic network?}},
journal = {Bulletin of Mathematical Biology},
year = {2016},
volume = {78},
number = {9},
pages = {1773--1795}
}
2015
[29]
journal article
WhatsHap: Weighted Haplotype Assembly for Future-Generation Sequencing Reads
Journal of Computational Biology, 22(6):498--509, 2015.
Preliminary version in RECOMB 2014, LNCS 8394:237–249.
Introduces WhatsHap, the first method that can provably find the best possible way to assign genetic variants to each of the two inherited copies of a chromosome directly from long sequencing reads while properly accounting for sequencing errors, something existing statistical approaches could not do, and shows it works reliably even at realistic error rates and read depths.
The human genome is diploid, which requires assigning heterozygous single nucleotide polymorphisms (SNPs) to the two copies of the genome. The resulting haplotypes, lists of SNPs belonging to each copy, are crucial for downstream analyses in population genetics. Currently, statistical approaches, which are oblivious to direct read information, constitute the state-of-the-art. Haplotype assembly, which addresses phasing directly from sequencing reads, suffers from the fact that sequencing reads of the current generation are too short to serve the purposes of genome-wide phasing. While future-technology sequencing reads will contain sufficient amounts of SNPs per read for phasing, they are also likely to suffer from higher sequencing error rates. Currently, no haplotype assembly approaches exist that allow for taking both increasing read length and sequencing error information into account. Here, we suggest WhatsHap, the first approach that yields provably optimal solutions to the weighted minimum error correction problem in runtime linear in the number of SNPs. WhatsHap is a fixed parameter tractable (FPT) approach with coverage as the parameter. We demonstrate that WhatsHap can handle datasets of coverage up to 20×, and that 15× are generally enough for reliably phasing long reads, even at significantly elevated sequencing error rates. We also find that the switch and flip error rates of the haplotypes we output are favorable when comparing them with state-of-the-art statistical phasers.
@article{patterson2015whatshap,
author = {Patterson, Murray and Marschall, Tobias and Pisanti, Nadia and van Iersel, Leo and Stougie, Leen and Klau, Gunnar W and Schoenhuth, Alexander},
title = {{WhatsHap: Weighted Haplotype Assembly for Future-Generation Sequencing Reads}},
journal = {Journal of Computational Biology},
year = {2015},
volume = {22},
number = {6},
pages = {498--509}
}
[28]
journal article
How much information is needed to infer reticulate evolutionary histories?
Systematic Biology, 64(1):102--111, 2015.
Identifies a fundamental obstacle facing an entire family of approaches to building evolutionary networks from smaller pieces, showing that even complete information about every smaller sub-network obtained by removing any subset of species is still not always enough to uniquely pin down the original network — meaning such building-block methods can, in principle, produce an incorrect history even from perfect input.
Phylogenetic networks are a generalization of evolutionary trees and are an important tool for analyzing reticulate evolutionary histories. Recently, there has been great interest in developing new methods to construct rooted phylogenetic networks, that is, networks whose internal vertices correspond to hypothetical ancestors, whose leaves correspond to sampled taxa, and in which vertices with more than one parent correspond to taxa formed by reticulate evolutionary events such as recombination or hybridization. Several methods for constructing evolutionary trees use the strategy of building up a tree from simpler building blocks (such as triplets or clusters), and so it is natural to look for ways to construct networks from smaller networks. In this article, we shall demonstrate a fundamental issue with this approach. Namely, we show that even if we are given all of the subnetworks induced on all proper subsets of the leaves of some rooted phylogenetic network, we still do not have all of the information required to completely determine that network. This implies that even if all of the building blocks for some reticulate evolutionary history were to be taken as the input for any given network building method, the method might still output an incorrect history. We also discuss some potential consequences of this result for constructing phylogenetic networks.
@article{huber2015how,
author = {Huber, Katharina and van Iersel, Leo and Moulton, Vincent and Wu, Taoyang},
title = {{How much information is needed to infer reticulate evolutionary histories?}},
journal = {Systematic Biology},
year = {2015},
volume = {64},
number = {1},
pages = {102--111}
}
[27]
journal article
On Computing the Maximum Parsimony Score of a Phylogenetic Network
SIAM Journal on Discrete Mathematics, 29(1):559--585, 2015.
Studies how to score an evolutionary network against genetic character data using the parsimony principle in two different ways, finding that one variant can be computed efficiently in simple cases but becomes hard as data complexity increases, while the other variant is difficult even in very restricted cases — though both can still be solved efficiently in practice using a general optimization technique, backed by freely available software.
Phylogenetic networks are used to display the relationship of different species whose evolution is not treelike, which is the case, for instance, in the presence of hybridization events or horizontal gene transfers. Tree inference methods such as Maximum Parsimony need to be modified in order to be applicable to networks. In this paper, we discuss two different definitions of Maximum Parsimony on networks, "hardwired" and "softwired", and examine the complexity of computing them given a network topology and a character. By exploiting a link with the problem Multicut, we show that computing the hardwired parsimony score for 2-state characters is polynomial-time solvable, while for characters with more states this problem becomes NP-hard but is still approximable and fixed parameter tractable in the parsimony score. On the other hand we show that, for the softwired definition, obtaining even weak approximation guarantees is already difficult for binary characters and restricted network topologies, and fixed-parameter tractable algorithms in the parsimony score are unlikely. On the positive side we show that computing the softwired parsimony score is fixed-parameter tractable in the level of the network, a natural parameter describing how tangled reticulate activity is in the network. Finally, we show that both the hardwired and softwired parsimony score can be computed efficiently using Integer Linear Programming. The software has been made freely available.
@article{fischer2015computing,
author = {Fischer, Mareike and van Iersel, Leo and Kelk, Steven and Scornavacca, Celine},
title = {{On Computing the Maximum Parsimony Score of a Phylogenetic Network}},
journal = {SIAM Journal on Discrete Mathematics},
year = {2015},
volume = {29},
number = {1},
pages = {559--585}
}
[26]
journal article
Hoe zijn ze verwant?
Nieuw Archief voor Wiskunde, 5/16(3):174--178, 2015.
Explains, in an accessible setting, how evolutionary relationships can be modeled and inferred. The piece introduces phylogenetic relationships and the role of trees or networks in representing them.
@article{iersel2015hoe,
author = {van Iersel, Leo},
title = {{Hoe zijn ze verwant?}},
journal = {Nieuw Archief voor Wiskunde},
year = {2015},
volume = {5/16},
number = {3},
pages = {174--178}
}
2014
[25]
journal article
Approximation algorithms for nonbinary agreement forests
SIAM Journal on Discrete Mathematics, 28(1):49--66, 2014.
Proves that the key computational technique for measuring disagreement between two evolutionary trees, previously understood mainly for fully resolved binary trees, extends with the same efficient approximation and exact guarantees to the more general and biologically realistic case of trees with unresolved branching.
Given two rooted phylogenetic trees on the same set of taxa $X$, the Maximum Agreement Forest (maf) problem asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest (maaf) problem has the additional restriction that the components of the forest cannot have conflicting ancestral relations in the input trees. There has been considerable interest in the special cases of these problems in which the input trees are required to be binary. However, in practice, phylogenetic trees are rarely binary, due to uncertainty about the precise order of speciation events. Here, we show that the general, nonbinary version of maf has a polynomial-time 4-approximation and a fixed-parameter tractable (exact) algorithm that runs in $O(4^k {\rm poly}(n))$ time, where $n=|X|$ and $k$ is the number of components of the agreement forest minus one. Moreover, we show that a $c$-approximation algorithm for nonbinary maf and a $d$-approximation...
@article{iersel2014approximation,
author = {van Iersel, Leo and Kelk, Steven and Lekic, Nela and Stougie, Leen},
title = {{Approximation algorithms for nonbinary agreement forests}},
journal = {SIAM Journal on Discrete Mathematics},
year = {2014},
volume = {28},
number = {1},
pages = {49--66}
}
[24]
journal article
A practical approximation algorithm for solving massive instances of hybridization number for binary and nonbinary trees
BMC Bioinformatics, 15:127, 2014.
Preliminary version in WABI 2012, LNCS 7534:430–440.
Extends fast approximate and exact algorithms for measuring how much two evolutionary trees disagree from the idealized case of fully resolved trees to the more realistic case where trees can be only partially resolved, providing a practical, freely available implementation capable of handling much larger datasets than previous exact methods.
Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest problem (MAF) asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest problem (MAAF) has the additional restriction that the components of the forest cannot have conflicting ancestral relations in the input trees. There has been considerable interest in the special cases of these problems in which the input trees are required to be binary. However, in practice, phylogenetic trees are rarely binary, due to uncertainty about the precise order of speciation events. Here, we show that the general, nonbinary version of MAF has a polynomial-time 4-approximation and a fixed-parameter tractable (exact) algorithm that runs in O(4^k poly(n)) time, where n = |X| and k is the number of components of the agreement forest minus one. Moreover, we show that a c-approximation algorithm for nonbinary MAF and a d-approximation algorithm for the classical problem Directed Feedback Vertex Set (DFVS) can be combined to yield a d(c+3)-approximation for nonbinary MAAF. The algorithms for MAF have been implemented and made publicly available.
@article{iersel2014practical,
author = {van Iersel, Leo and Kelk, Steven and Lekic, Nela and Scornavacca, Celine},
title = {{A practical approximation algorithm for solving massive instances of hybridization number for binary and nonbinary trees}},
journal = {BMC Bioinformatics},
year = {2014},
volume = {15},
pages = {127}
}
[23]
journal article
Trinets encode tree-child and level-2 phylogenetic networks
Journal of Mathematical Biology, 68(7):1707--1729, 2014.
Provides further evidence for the idea that a moderately complex evolutionary network is always fully determined by the information contained in every possible group of three species within it, proving this for two broad and important classes of network and laying groundwork for future methods that build networks up from this kind of small-scale information.
Phylogenetic networks generalize evolutionary trees, and are commonly used to represent evolutionary histories of species that undergo reticulate evolutionary processes such as hybridization, recombination and lateral gene transfer. Recently, there has been great interest in trying to develop methods to construct rooted phylogenetic networks from triplets, that is rooted trees on three species. However, although triplets determine or encode rooted phylogenetic trees, they do not in general encode rooted phylogenetic networks, which is a potential issue for any such method. Motivated by this fact, Huber and Moulton recently introduced trinets as a natural extension of rooted triplets to networks. In particular, they showed that level-1 phylogenetic networks are encoded by their trinets, and also conjectured that all "recoverable" rooted phylogenetic networks are encoded by their trinets. Here we prove that recoverable binary level-2 networks and binary tree-child networks are also encoded by their trinets. To do this we prove two decomposition theorems based on trinets which hold for all recoverable binary rooted phylogenetic networks. Our results provide some additional evidence in support of the conjecture that trinets encode all recoverable rooted phylogenetic networks, and could also lead to new approaches to construct phylogenetic networks from trinets.
@article{iersel2014trinets,
author = {van Iersel, Leo and Moulton, Vincent},
title = {{Trinets encode tree-child and level-2 phylogenetic networks}},
journal = {Journal of Mathematical Biology},
year = {2014},
volume = {68},
number = {7},
pages = {1707--1729}
}
[22]
journal article
The agreement problem for unrooted phylogenetic trees is FPT
Journal of Graph Algorithms and Applications, 18(3):385--392, 2014.
Shows that a natural way of measuring how much two evolutionary trees, considered without a direction of time, disagree with each other can always be computed efficiently once that disagreement is small, extending a similar earlier result from rooted to unrooted trees.
@article{scornavacca2014agreement,
author = {Scornavacca, Celine and van Iersel, Leo and Kelk, Steven and Bryant, David},
title = {{The agreement problem for unrooted phylogenetic trees is FPT}},
journal = {Journal of Graph Algorithms and Applications},
year = {2014},
volume = {18},
number = {3},
pages = {385--392}
}
[21]
preprint
Exact Reconciliation of undated trees
arXiv:1410.7004, 2014.
Introduces an exact optimization method for matching up a gene family's evolutionary tree with the species tree even without knowing exactly when past speciation events occurred, searching efficiently over all plausible timings to find the most parsimonious explanation — a proof-of-concept, backed by free software, that opens the door to more advanced dating methods for species trees.
Reconciliation methods aim at recovering macro evolutionary events and at localizing them in the species history, by observing discrepancies between gene family trees and species trees. In this article we introduce an Integer Linear Programming (ILP) approach for the NP-hard problem of computing a most parsimonious time-consistent reconciliation of a gene tree with a species tree when dating information on speciations is not available. The ILP formulation, which builds upon the DTL model, returns a most parsimonious reconciliation ranging over all possible datings of the nodes of the species tree. By studying its performance on plausible simulated data we conclude that the ILP approach is significantly faster than a brute force search through the space of all possible species tree datings. Although the ILP formulation is currently limited to small trees, we believe that it is an important proof-of-concept which opens the door to the possibility of developing an exact, parsimony based approach to dating species trees. The software (ILPEACE) is freely available for download.
@misc{iersel2014exact,
author = {van Iersel, Leo and Scornavacca, Celine and Kelk, Steven},
title = {{Exact Reconciliation of undated trees}},
year = {2014},
archivePrefix = {arXiv},
eprint = {1410.7004},
url = {https://arxiv.org/abs/1410.7004}
}
2013
[20]
preprint
A short note on exponential-time algorithms for hybridization number
arXiv:1312.1255, 2013.
Gives a faster brute-force-beating algorithm for exactly computing the minimum number of hybridization events needed to reconcile two conflicting evolutionary trees, guaranteed to finish in a time that scales predictably with the number of species even in the worst case.
In this short note we prove that, given two (not necessarily binary) rooted phylogenetic trees T_1, T_2 on the same set of taxa X, where |X|=n, the hybridization number of T_1 and T_2 can be computed in time O^{*}(2^n) i.e. O(2^{n} poly(n)). The result also means that a Maximum Acyclic Agreement Forest (MAAF) can be computed within the same time bound.
@misc{iersel2013short,
author = {van Iersel, Leo and Kelk, Steven and Lekic, Nela and Stougie, Leen},
title = {{A short note on exponential-time algorithms for hybridization number}},
year = {2013},
archivePrefix = {arXiv},
eprint = {1312.1255},
url = {https://arxiv.org/abs/1312.1255}
}
[19]
journal article
Book Review: Basic Phylogenetic Combinatorics. — Andreas Dress, Katharina T. Huber, Jacobus Koolen, Vincent Moulton and Andreas Spillner
Systematic Biology, 62(2):346--348, 2013.
Reviews the book Basic Phylogenetic Combinatorics by Dress, Huber, Koolen, Moulton, and Spillner. The review discusses the book's treatment of combinatorial foundations for phylogenetics.
@article{iersel2013book,
author = {van Iersel, Leo},
title = {{Book Review: Basic Phylogenetic Combinatorics. — Andreas Dress, Katharina T. Huber, Jacobus Koolen, Vincent Moulton and Andreas Spillner}},
journal = {Systematic Biology},
year = {2013},
volume = {62},
number = {2},
pages = {346--348},
note = {Book review}
}
[18]
journal article
A quadratic kernel for computing the hybridization number of multiple trees
Information Processing Letters, 113(9):318--323, 2013.
Extends a known efficient method for finding the smallest network that reconciles two conflicting evolutionary trees to work for any number of trees at once, by showing that such problems can always be shrunk down to an instance whose size grows only quadratically with the answer.
It has recently been shown that the NP-hard problem of calculating the minimum number of hybridization events that is needed to explain a set of rooted binary phylogenetic trees by means of a hybridization network is fixed-parameter tractable if an instance of the problem consists of precisely two such trees. In this paper, we show that this problem remains fixed-parameter tractable for an arbitrarily large set of rooted binary phylogenetic trees. In particular, we present a quadratic kernel.
@article{iersel2013quadratic,
author = {van Iersel, Leo and Linz, Simone},
title = {{A quadratic kernel for computing the hybridization number of multiple trees}},
journal = {Information Processing Letters},
year = {2013},
volume = {113},
number = {9},
pages = {318--323}
}
[17]
journal article
Ancient dispersal of the human fungal pathogen Cryptococcus gattii from the Amazon rainforest
PLoS ONE, 8(8):e71148, 2013.
Uses genetic analysis to trace the origin of several dangerous outbreaks of the fungal pathogen Cryptococcus gattii in temperate regions such as Vancouver Island, tracing them back to a single, highly diverse ancestral population in the Amazon rainforest from which the outbreak strains spread around the world.
Over the past two decades, several fungal outbreaks have occurred, including the high-profile 'Vancouver Island' and 'Pacific Northwest' outbreaks, caused by Cryptococcus gattii, which has affected hundreds of otherwise healthy humans and animals. Over the same time period, C. gattii was the cause of several additional case clusters at localities outside of the tropical and subtropical climate zones where the species normally occurs. In every case, the causative agent belongs to a previously rare genotype of C. gattii called AFLP6/VGII, but the origin of the outbreak clades remains enigmatic. Here we used phylogenetic and recombination analyses, based on AFLP and multiple MLST datasets, and coalescence gene genealogy to demonstrate that these outbreaks have arisen from a highly-recombining C. gattii population in the native rainforest of Northern Brazil. Thus the modern virulent C. gattii AFLP6/VGII outbreak lineages derived from mating events in South America and then dispersed to temperate regions where they cause serious infections in humans and animals.
@article{hagen2013ancient,
author = {Hagen, Ferry and Ceresini, Paulo C. and Polacheck, Itzhack and Ma, Hansong and van Nieuwerburgh, Filip and Gabaldón, Toni and Kagan, Sarah and Pursall, E. Rhiannon and Hoogveld, Hans L. and van Iersel, Leo and Klau, Gunnar W. and Kelk, Steven and Stougie, Leen and Bartlett, Karen H. and Voelz, Kerstin and Pryszcz, Leszek P. and Castañeda, Elizabeth and Lazera, Marcia and Meyer, Wieland and Deforce, Dieter and Meis, Jacques F. and May, Robin C. and Klaassen, Corné H. W. and Boekhout, Teun},
title = {{Ancient dispersal of the human fungal pathogen Cryptococcus gattii from the Amazon rainforest}},
journal = {PLoS ONE},
year = {2013},
volume = {8},
number = {8},
pages = {e71148},
doi = {10.1371/journal.pone.0071148},
url = {https://doi.org/10.1371/journal.pone.0071148}
}
[16]
journal article
Geographically Structured Populations of Cryptococcus neoformans Variety grubii in Asia Correlate with HIV Status and Show a Clonal Population Structure
PLoS ONE, 8(9):e72222, 2013.
Analyzes genetic data from Cryptococcus neoformans, a fungus that causes life-threatening infections in people with HIV/AIDS, across many Asian countries, finding that most circulating strains descend from a limited number of closely related genetic lineages that vary by geography and are linked to patients' HIV status.
Cryptococcosis is an important fungal disease in Asia with an estimated 140,000 new infections annually the majority of which occurs in patients suffering from HIV/AIDS. Cryptococcus neoformans variety grubii (serotype A) is the major causative agent of this disease. In the present study, multilocus sequence typing (MLST) using the ISHAM MLST consensus scheme for the C. neoformans/C. gattii species complex was used to analyse nucleotide polymorphisms among 476 isolates of this pathogen obtained from 8 Asian countries. Population genetic analysis showed that the Asian C. neoformans var. grubii population shows limited genetic diversity and demonstrates a largely clonal mode of reproduction when compared with the global MLST dataset. HIV-status, sequence types and geography were found to be confounded. However, a correlation between sequence types and isolates from HIV-negative patients was observed among the Asian isolates. Observations of high gene flow between the Middle Eastern and the Southeastern Asian populations suggest that immigrant workers in the Middle East were originally infected in Southeastern Asia.
@article{khayhan2013geographically,
author = {Khayhan, Kantarawee and Hagen, Ferry and Pan, Weihua and Simwami, Sitali and Fisher, Matthew C. and Wahyuningsih, Retno and Chakrabarti, Arunaloke and Chowdhary, Anuradha and Ikeda, Reiko and Taj-Aldeen, Saad J. and Khan, Ziauddin and Ip, Margaret and Imran, Darma and Sjam, Ridhawati and Sriburee, Pojana and Liao, Wanqing and Chaicumpar, Kunyaluk and Vuddhakul, Varaporn and Meyer, Wieland and Trilles, Luciana and van Iersel, Leo and Meis, Jacques F. and Klaassen, Corné H. W. and Boekhout, Teun},
title = {{Geographically Structured Populations of Cryptococcus neoformans Variety grubii in Asia Correlate with HIV Status and Show a Clonal Population Structure}},
journal = {PLoS ONE},
year = {2013},
volume = {8},
number = {9},
pages = {e72222},
doi = {10.1371/journal.pone.0072222},
url = {https://doi.org/10.1371/journal.pone.0072222}
}
[15]
journal article
Networks: expanding evolutionary thinking
Trends in Genetics, 29(8):439--441, 2013.
Argues that evolutionary relationships are often better represented by networks than by trees alone. The article highlights how network models capture reticulation and complex genomic histories.
Networks allow the investigation of evolutionary relationships that do not fit a tree model. They are becoming a leading tool for describing the evolutionary relationships between organisms, given the comparative complexities among genomes.
@article{bapteste2013networks,
author = {Bapteste, Eric and van Iersel, Leo and Janke, Axel and Kelchner, Scot and Kelk, Steven and McInerney, James O and Morrison, David A and Nakhleh, Luay and Steel, Mike and Stougie, Leen and Whitfield, James},
title = {{Networks: expanding evolutionary thinking}},
journal = {Trends in Genetics},
year = {2013},
volume = {29},
number = {8},
pages = {439--441}
}
2012
[14]
journal article
Every Ternary Permutation Constraint Satisfaction Problem Parameterized Above Average Has a Kernel with a Quadratic Number of Variables
Journal of Computer and System Sciences, 78:151--163, 2012.
Preliminary version in ESA 2010, LNCS 6346:326–337.
Proves a general result about a broad family of problems asking for the best possible ordering of a set of items subject to triple-wise preferences, including one relevant to combining conflicting evolutionary trees — whenever a solution is required to beat the average by some margin, the problem can always be reduced to an instance whose size grows only quadratically with that margin.
A ternary Permutation-CSP is specified by a subset $Π$ of the symmetric group $\mathcal S_3$. An instance of such a problem consists of a set of variables $V$ and a multiset of constraints, which are ordered triples of distinct variables of $V.$ The objective is to find a linear ordering $α$ of $V$ that maximizes the number of triples whose ordering (under $α$) follows a permutation in $Π$. We prove that all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.
@article{gutin2012every,
author = {Gutin, Gregory and van Iersel, Leo and Mnich, Matthias and Yeo, Anders},
title = {{Every Ternary Permutation Constraint Satisfaction Problem Parameterized Above Average Has a Kernel with a Quadratic Number of Variables}},
journal = {Journal of Computer and System Sciences},
year = {2012},
volume = {78},
pages = {151--163}
}
[13]
journal article
On the elusiveness of clusters
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 9(2):517--534, 2012.
Studies the limits of using a simplified summary of evolutionary relationships, called clusters, to build an evolutionary network, showing that although finding the simplest such network is generally computationally hard, it becomes efficiently solvable once a bound is placed on how tangled the network is allowed to be, and pins down exactly when a widely used practical algorithm succeeds or falls short.
Rooted phylogenetic networks are often used to represent conflicting phylogenetic signals. Given a set of clusters, a network is said to represent these clusters in the "softwired" sense if, for each cluster in the input set, at least one tree embedded in the network contains that cluster. Motivated by parsimony we might wish to construct such a network using as few reticulations as possible, or minimizing the "level" of the network, i.e. the maximum number of reticulations used in any "tangled" region of the network. Although these are NP-hard problems, here we prove that, for every fixed k >= 0, it is polynomial-time solvable to construct a phylogenetic network with level equal to k representing a cluster set, or to determine that no such network exists. However, this algorithm does not lend itself to a practical implementation. We also prove that the comparatively efficient Cass algorithm correctly solves this problem (and also minimizes the reticulation number) when input clusters are obtained from two not necessarily binary gene trees on the same set of taxa but does not always minimize level for general cluster sets. Finally, we describe a new algorithm which generates in polynomial-time all binary phylogenetic networks with exactly r reticulations representing a set of input clusters (for every fixed r >= 0).
@article{kelk2012elusiveness,
author = {Kelk, Steven and Scornavacca, Celine and van Iersel, Leo},
title = {{On the elusiveness of clusters}},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
year = {2012},
volume = {9},
number = {2},
pages = {517--534}
}
[12]
journal article
Cycle killer… qu’est-ce que c’est? On the comparative approximability of hybridization number and directed feedback vertex set
SIAM Journal on Discrete Mathematics, 26(4):1635--1656, 2012.
Shows that finding a good approximate solution for reconciling two conflicting evolutionary trees is exactly as hard, in a precise technical sense, as a famous long-open problem in graph theory about removing the fewest possible connections to eliminate all cycles in a one-way network, and uses this connection to give the first algorithm that reliably gets close to the optimal answer.
We show that the problem of computing the hybridization number of two rooted binary phylogenetic trees on the same set of taxa X has a constant factor polynomial-time approximation if and only if the problem of computing a minimum-size feedback vertex set in a directed graph (DFVS) has a constant factor polynomial-time approximation. The latter problem, which asks for a minimum number of vertices to be removed from a directed graph to transform it into a directed acyclic graph, is one of the problems in Karp's seminal 1972 list of 21 NP-complete problems. However, despite considerable attention from the combinatorial optimization community it remains to this day unknown whether a constant factor polynomial-time approximation exists for DFVS. Our result thus places the (in)approximability of hybridization number in a much broader complexity context, and as a consequence we obtain that hybridization number inherits inapproximability results from the problem Vertex Cover. On the positive side, we use results from the DFVS literature to give an O(log r log log r) approximation for hybridization number, where r is the value of an optimal solution to the hybridization number problem.
@article{kelk2012cycle,
author = {Kelk, Steven and van Iersel, Leo and Lekic, Nela and Linz, Simone and Scornavacca, Celine and Stougie, Leen},
title = {{Cycle killer… qu’est-ce que c’est? On the comparative approximability of hybridization number and directed feedback vertex set}},
journal = {SIAM Journal on Discrete Mathematics},
year = {2012},
volume = {26},
number = {4},
pages = {1635--1656}
}
2011
[11]
journal article
Constructing the Simplest Possible Phylogenetic Network from Triplets
Algorithmica, 60:207--235, 2011.
Preliminary version in ISAAC 2008, LNCS 5369:472–483.
Extends earlier work showing that a moderately tangled evolutionary network can be efficiently constructed from a sufficiently complete set of small three-species relationship hypotheses, by proving that even more complex networks can still be built this way in polynomial time when the input is complete enough, while confirming that the problem remains computationally hard whenever that information is incomplete.
Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of species), it is possible to determine in polynomial time whether there exists a level-1 network consistent with T, and if so to construct such a network. They also showed that, unlike in the case of trees (i.e. level-0 networks), the problem becomes NP-hard when the input is non-dense. Here we further extend this work by showing that, when the set of input triplets is dense, the problem is even polynomial-time solvable for the construction of level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily non-tree like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also show that, in the non-dense case, the level-2 problem remains NP-hard.
@article{iersel2011constructing,
author = {van Iersel, Leo and Kelk, Steven},
title = {{Constructing the Simplest Possible Phylogenetic Network from Triplets}},
journal = {Algorithmica},
year = {2011},
volume = {60},
pages = {207--235}
}
[10]
journal article
A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(3):635--649, 2011.
Presents Lev1athan, freely available software that efficiently reconstructs a moderately complex evolutionary network from information about every possible group of three species, always running quickly and falling back to a simple tree when the data supports one, shown through extensive simulations and real biological data to perform well even when the input is noisy.
Recently, much attention has been devoted to the construction of phylogenetic networks which generalize phylogenetic trees in order to accommodate complex evolutionary processes. Here, we present an efficient, practical algorithm for reconstructing level-1 phylogenetic networks-a type of network slightly more general than a phylogenetic tree-from triplets. Our algorithm has been made publicly available as the program Lev1athan. It combines ideas from several known theoretical algorithms for phylogenetic tree and network reconstruction with two novel subroutines. Namely, an exponential-time exact and a greedy algorithm both of which are of independent theoretical interest. Most importantly, Lev1athan runs in polynomial time and always constructs a level-1 network. If the data are consistent with a phylogenetic tree, then the algorithm constructs such a tree. Moreover, if the input triplet set is dense and, in addition, is fully consistent with some level-1 network, it will find such a network. The potential of Lev1athan is explored by means of an extensive simulation study and a biological data set. One of our conclusions is that Lev1athan is able to construct networks consistent with a high percentage of input triplets, even when these input triplets are affected by a low to moderate level of noise.
@article{huber2011practical,
author = {Huber, Katharina and van Iersel, Leo and Kelk, Steven and Suchecki, Radoslaw},
title = {{A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks}},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
year = {2011},
volume = {8},
number = {3},
pages = {635--649}
}
[9]
journal article
When Two Trees Go to War
Journal of Theoretical Biology, 269:245--255, 2011.
Shows that four seemingly different ways of measuring the minimum complexity of an evolutionary network needed to reconcile two conflicting evolutionary trees actually always give exactly the same answer, a surprising unification that resolves several previously open questions in the field, while also showing that this neat correspondence breaks down once a third tree is added.
Rooted phylogenetic networks are often constructed by combining trees, clusters, triplets or characters into a single network that in some well-defined sense simultaneously represents them all. We review these four models and investigate how they are related. In general, the model chosen influences the minimum number of reticulation events required. However, when one obtains the input data from two binary trees, we show that the minimum number of reticulations is independent of the model. The number of reticulations necessary to represent the trees, triplets, clusters (in the softwired sense) and characters (with unrestricted multiple crossover recombination) are all equal. Furthermore, we show that these results also hold when not the number of reticulations but the level of the constructed network is minimised. We use these unification results to settle several complexity questions that have been open in the field for some time. We also give explicit examples to show that already for data obtained from three binary trees the models begin to diverge.
@article{iersel2011when,
author = {van Iersel, Leo and Kelk, Steven},
title = {{When Two Trees Go to War}},
journal = {Journal of Theoretical Biology},
year = {2011},
volume = {269},
pages = {245--255}
}
2010
[8]
journal article
Phylogenetic Networks Do not Need to Be Complex: Using Fewer Reticulations to Represent Conflicting Clusters
Bioinformatics, 26:i124--i131, 2010.
Presents Cass, freely available software (integrated into the popular Dendroscope program) that combines conflicting groupings of species from different gene trees into a single evolutionary network, and shows that it reliably produces simpler networks, using fewer hybridization events, than previously available methods.
Phylogenetic trees are widely used to display estimates of how groups of species are evolved. Each phylogenetic tree can be seen as a collection of clusters, subgroups of the species that evolved from a common ancestor. When phylogenetic trees are obtained for several datasets (e.g. for different genes), then their clusters are often contradicting. Consequently, the set of all clusters of such a dataset cannot be combined into a single phylogenetic tree. Phylogenetic networks are a generalization of phylogenetic trees that can be used to display more complex evolutionary histories, including reticulate events, such as hybridizations, recombinations and horizontal gene transfers. Here, we present the new Cass algorithm that can combine any set of clusters into a phylogenetic network. We show that the networks constructed by Cass are usually simpler than networks constructed by other available methods. Moreover, we show that Cass is guaranteed to produce a network with at most two reticulations per biconnected component, whenever such a network exists. We have implemented Cass and integrated it into the freely available Dendroscope software. Contact: l.j.j.v.iersel@gmail.com Supplementary information: Supplementary data are available at Bioinformatics online.
@article{iersel2010phylogenetic,
author = {van Iersel, Leo and Kelk, Steven and Rupp, Regula and Huson, Daniel},
title = {{Phylogenetic Networks Do not Need to Be Complex: Using Fewer Reticulations to Represent Conflicting Clusters}},
journal = {Bioinformatics},
year = {2010},
volume = {26},
pages = {i124--i131}
}
[7]
journal article
Quantifying the Extent of Lateral Gene Transfer Required to Avert a ‘Genome of Eden’
Bulletin of Mathematical Biology, 72(7):1783--1798, 2010.
Develops a rigorous mathematical way to measure how much horizontal gene transfer between species is really needed to explain the patchy presence and absence of genes across genomes — a question at the heart of the debate over whether evolution is better described as a tree or a tangled network — and connects this measurement problem to well-studied concepts in graph theory.
The complex pattern of presence and absence of many genes across different species provides tantalising clues as to how genes evolved through the processes of gene genesis, gene loss, and lateral gene transfer (LGT). The extent of LGT, particularly in prokaryotes, and its implications for creating a ‘network of life’ rather than a ‘tree of life’ is controversial. In this paper, we formally model the problem of quantifying LGT, and provide exact mathematical bounds, and new computational results. In particular, we investigate the computational complexity of quantifying the extent of LGT under the simple models of gene genesis, loss, and transfer on which a recent heuristic analysis of biological data relied. Our approach takes advantage of a relationship between LGT optimization and graph-theoretical concepts such as tree width and network flow.
@article{iersel2010quantifying,
author = {van Iersel, Leo and Semple, Charles and Steel, Mike},
title = {{Quantifying the Extent of Lateral Gene Transfer Required to Avert a ‘Genome of Eden’}},
journal = {Bulletin of Mathematical Biology},
year = {2010},
volume = {72},
number = {7},
pages = {1783--1798}
}
[6]
journal article
Locating a Tree in a Phylogenetic Network
Information Processing Letters, 110(23):1037--1043, 2010.
Studies when it is possible to efficiently check whether a proposed evolutionary tree, or a proposed grouping of species, is consistent with a larger network, showing this can be done quickly for several well-behaved, biologically motivated network types, while confirming the problem remains computationally hard even for other fairly restricted and seemingly simple ones.
Phylogenetic trees and networks are leaf-labelled graphs that are used to describe evolutionary histories of species. The Tree Containment problem asks whether a given phylogenetic tree is embedded in a given phylogenetic network. Given a phylogenetic network and a cluster of species, the Cluster Containment problem asks whether the given cluster is a cluster of some phylogenetic tree embedded in the network. Both problems are known to be NP-complete in general. In this article, we consider the restriction of these problems to several well-studied classes of phylogenetic networks. We show that Tree Containment is polynomial-time solvable for normal networks, for binary tree-child networks, and for level-$k$ networks. On the other hand, we show that, even for tree-sibling, time-consistent, regular networks, both Tree Containment and Cluster Containment remain NP-complete.
@article{iersel2010locating,
author = {van Iersel, Leo and Semple, Charles and Steel, Mike},
title = {{Locating a Tree in a Phylogenetic Network}},
journal = {Information Processing Letters},
year = {2010},
volume = {110},
number = {23},
pages = {1037--1043}
}
2009
[5]
journal article
Constructing Level-2 Phylogenetic Networks from Triplets
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(4):667--681, 2009.
Preliminary version in RECOMB 2008, LNBI 4955:450–462.
Shows that even a fairly tangled type of evolutionary network can be efficiently and exactly reconstructed from a sufficiently complete set of three-species relationship hypotheses, extending earlier tractability results to a broader and more complex class of networks, while confirming the reconstruction problem remains computationally hard whenever that information is incomplete.
Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of species), it is possible to determine in polynomial time whether there exists a level-1 network consistent with T, and if so to construct such a network. They also showed that, unlike in the case of trees (i.e. level-0 networks), the problem becomes NP-hard when the input is non-dense. Here we further extend this work by showing that, when the set of input triplets is dense, the problem is even polynomial-time solvable for the construction of level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily non-tree like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also show that, in the non-dense case, the level-2 problem remains NP-hard.
@article{iersel2009constructing,
author = {van Iersel, Leo and Keijsper, Judith and Kelk, Steven and Stougie, Leen and Hagen, Ferry and Boekhout, Teun},
title = {{Constructing Level-2 Phylogenetic Networks from Triplets}},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
year = {2009},
volume = {6},
number = {4},
pages = {667--681},
archivePrefix = {arXiv},
eprint = {0707.2890},
url = {https://arxiv.org/abs/0707.2890}
}
[4]
journal article
Uniqueness, Intractability and Exact Algorithms: Reflections on Level-k Phylogenetic Networks
Journal of Bioinformatics and Computational Biology, 7(4):597--623, 2009.
Reflects on a family of evolutionary networks graded by how far they deviate from being a simple tree, showing that increasingly tangled networks are still uniquely determined by their smallest three-species building blocks, proving that constructing such networks from this information is nevertheless computationally hard in general, and offering an exact algorithm that copes with this hardness for the simplest non-tree case.
Phylogenetic networks provide a way to describe and visualize evolutionary histories that have undergone so-called reticulate evolutionary events such as recombination, hybridization or horizontal gene transfer. The level k of a network determines how non-treelike the evolution can be, with level-0 networks being trees. We study the problem of constructing level-k phylogenetic networks from triplets, i.e. phylogenetic trees for three leaves (taxa). We give, for each k, a level-k network that is uniquely defined by its triplets. We demonstrate the applicability of this result by using it to prove that (1) for all k > or = 1 it is NP-hard to construct a level-k network consistent with all input triplets, and (2) for all k > or = 0 it is NP-hard to construct a level-k network consistent with a maximum number of input triplets, even when the input is dense. As a response to this intractability, we give an exact algorithm for constructing level-1 networks consistent with a maximum number of input triplets.
@article{iersel2009uniqueness,
author = {van Iersel, Leo and Kelk, Steven and Mnich, Matthias},
title = {{Uniqueness, Intractability and Exact Algorithms: Reflections on Level-k Phylogenetic Networks}},
journal = {Journal of Bioinformatics and Computational Biology},
year = {2009},
volume = {7},
number = {4},
pages = {597--623}
}
2008
[3]
journal article
Shorelines of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(2):301--312, 2008.
Preliminary version in WABI 2006, LNCS 4175:80–91.
Maps out the precise boundary between which versions of two classic genetic-data reconstruction problems — inferring parsimonious explanations and inferring perfect phylogenies from genetic marker data — can be solved efficiently and which cannot, clarifying exactly how far a problem's assumptions can be relaxed before it becomes computationally intractable.
@article{iersel2008shorelines,
author = {van Iersel, Leo and Keijsper, Judith and Kelk, Steven and Stougie, Leen},
title = {{Shorelines of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems}},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
year = {2008},
volume = {5},
number = {2},
pages = {301--312}
}
2007
[2]
journal article
The Complexity of the Single Individual SNP Haplotyping Problem
Algorithmica, 49(1):13--36, 2007.
Preliminary version in WABI 2005, LNCS 3692:128–139.
Pins down exactly how the computational difficulty of reconstructing an individual's two inherited chromosome copies from imperfect, incomplete DNA sequencing fragments depends on how fragmented that data is, showing some natural versions of the problem are efficiently solvable while closely related versions are provably hard, and correcting an earlier claim in the literature about one such version.
We present several new results pertaining to haplotyping. These results concern the combinatorial problem of reconstructing haplotypes from incomplete and/or imperfectly sequenced haplotype fragments. We consider the complexity of the problems Minimum Error Correction (MEC) and Longest Haplotype Reconstruction (LHR) for different restrictions on the input data. Specifically, we look at the gapless case, where every row of the input corresponds to a gapless haplotype-fragment, and the 1-gap case, where at most one gap per fragment is allowed. We prove that MEC is APX-hard in the 1-gap case and still NP-hard in the gapless case. In addition, we question earlier claims that MEC is NP-hard even when the input matrix is restricted to being completely binary. Concerning LHR, we show that this problem is NP-hard and APX-hard in the 1-gap case (and thus also in the general case), but is polynomial time solvable in the gapless case.
@article{cilibrasi2007complexity,
author = {Cilibrasi, Rudi and van Iersel, Leo and Kelk, Steven and Tromp, John},
title = {{The Complexity of the Single Individual SNP Haplotyping Problem}},
journal = {Algorithmica},
year = {2007},
volume = {49},
number = {1},
pages = {13--36}
}
[1]
journal article
Prefix reversals on binary and ternary strings
SIAM Journal on Discrete Mathematics, 21(3):592--611, 2007.
Preliminary version in AB 2007, LNCS 4545:292–306.
Studies a variant of the classic "pancake sorting" puzzle — repeatedly flipping over the front part of a stack to put it in order — for stacks made of only two or three types of item, giving efficient methods to sort such stacks optimally, proving that measuring the distance between two specific arrangements is nevertheless computationally hard, and working out how many flips are ever needed in the worst case.
Given a permutation pi, the application of prefix reversal f^(i) to pi reverses the order of the first i elements of pi. The problem of Sorting By Prefix Reversals (also known as pancake flipping), made famous by Gates and Papadimitriou (Bounds for sorting by prefix reversal, Discrete Mathematics 27, pp. 47-57), asks for the minimum number of prefix reversals required to sort the elements of a given permutation. In this paper we study a variant of this problem where the prefix reversals act not on permutations but on strings over a fixed size alphabet. We determine the minimum number of prefix reversals required to sort binary and ternary strings, with polynomial-time algorithms for these sorting problems as a result; demonstrate that computing the minimum prefix reversal distance between two binary strings is NP-hard; give an exact expression for the prefix reversal diameter of binary strings, and give bounds on the prefix reversal diameter of ternary strings. We also consider a weaker form of sorting called grouping (of identical symbols) and give polynomial-time algorithms for optimally grouping binary and ternary strings. A number of intriguing open problems are also discussed.
@article{hurkens2007prefix,
author = {Hurkens, Cor and van Iersel, Leo and Keijsper, Judith and Kelk, Steven and Stougie, Leen and Tromp, John},
title = {{Prefix reversals on binary and ternary strings}},
journal = {SIAM Journal on Discrete Mathematics},
year = {2007},
volume = {21},
number = {3},
pages = {592--611}
}
Theses
•
thesis
Algorithms, Haplotypes and Phylogenetic Networks
Ph.D. Thesis, Eindhoven University of Technology, 2009.
Doctoral thesis presenting algorithmic and computational-complexity results across two related areas — reconstructing an individual's genetic haplotypes from sequencing data, and reconstructing and analyzing evolutionary networks that capture hybridization and other non-tree-like evolutionary events.
@phdthesis{iersel2009algorithms,
author = {van Iersel, Leo},
title = {{Algorithms, Haplotypes and Phylogenetic Networks}},
school = {Eindhoven University of Technology},
year = {2009}
}