PN Publications
Below you can find my publications and preprints on Phylogenetic Networks, with links and toggleable abstracts.
To filter by a certain topic, click one of the buttons.
2026
[9]
Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
Leo van Iersel,
Mark Jones,
Jannik Schestag,
Celine Scornavacca, and
Mathias Weller
Proceedings of the 21st International Symposium on Parameterized and Exact Computation (IPEC 2026)
In terms of laymen
This paper investigates when the average amount of evolutionary history represented by selected species can be computed efficiently on complex evolutionary networks. It shows that subtle differences in how tree-like the network is can make the difference between an easy and a difficult problem, and gives fast algorithms for several important network structures.
In Laiensprache (German translation)
Diese Arbeit untersucht, unter welchen Bedingungen sich die durchschnittliche Menge an Evolutionsgeschichte, die durch ausgewählte Arten repräsentiert wird, auf komplexen evolutionären Netzwerken effizient berechnen lässt. Sie zeigt, dass bereits feine Unterschiede darin, wie baumähnlich ein Netzwerk ist, darüber entscheiden können, ob ein Problem leicht oder schwierig zu lösen ist, und entwickelt schnelle Algorithmen für mehrere wichtige Netzwerkstrukturen.
Abstract
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 \(\mathcal{O}(2^{\mathrm{sw}} n)\) time, where \(\mathrm{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.
@inproceedings{vanIersel2026averagetree,
title = {{Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility}},
author = {van Iersel, Leo and Jones, Mark and Schestag, Jannik and Scornavacca, Celine and Weller, Mathias},
booktitle = {Proceedings of the 21th International Symposium on Parameterized and Exact Computation (IPEC 2026)},
year = {2026},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{\"u}r Informatik}
}
[8]
PaNDA: Efficient Optimization of Phylogenetic Diversity in Networks
Niels Holtgrefe,
Leo van Iersel,
Ruben Meuwese,
Yukihiro Murakami, and
Jannik Schestag
In terms of laymen
When only some species can be protected, conservationists would like to choose those that preserve as much evolutionary history as possible. PaNDA provides algorithms and an interactive software tool for solving and visualizing this problem on complex evolutionary networks, with experiments showing that realistically large networks can be handled efficiently.
In Laiensprache (German translation)
Wenn nur ein Teil der Arten geschützt werden kann, möchte man diejenigen auswählen, durch deren Schutz möglichst viel Evolutionsgeschichte erhalten bleibt. PaNDA stellt Algorithmen und ein interaktives Softwarewerkzeug bereit, mit denen dieses Problem auf komplexen evolutionären Netzwerken gelöst und visualisiert werden kann. Experimente zeigen, dass sich damit auch realistisch große Netzwerke effizient bearbeiten lassen.
Abstract
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 canwidth, 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 phylogene- tic 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.
@article{holtgrefe2026panda,
title = {{PaNDA: Efficient Optimization of Phylogenetic Diversity in Networks}},
author = {Holtgrefe, Niels and van Iersel, Leo and Meuwese, Ruben and Murakami, Yukihiro and Schestag, Jannik},
year = {2026},
journal = {Journal of Computational Biology},
publisher={Springer},
doi = {10.1101/2025.11.14.688467}
}
[7]
Orienting Unrooted Binary Networks Faster: Focus on the Generator
Jannik Schestag and
Norbert Zeh
In terms of laymen
Evolutionary networks are sometimes reconstructed without directions on their connections, even though interpreting them as an evolutionary history requires deciding which way those connections point. This paper shows how to find suitable directions much faster when the complicated core of the network is small, covering the most relevant classes of evolutionary networks.
In Laiensprache (German translation)
Evolutionäre Netzwerke werden manchmal rekonstruiert, ohne dass die Verbindungen eine Richtung haben. Um ein solches Netzwerk als Evolutionsgeschichte interpretieren zu können, muss jedoch festgelegt werden, in welche Richtung die einzelnen Verbindungen verlaufen. Diese Arbeit zeigt, wie sich geeignete Richtungen deutlich schneller bestimmen lassen, wenn der komplizierte Kern des Netzwerks klein ist, und behandelt dabei die wichtigsten Klassen evolutionärer Netzwerke.
Abstract
The problem of orienting an unrooted network to obtain a specific class of rooted phylogenetic networks is known to be NP-hard in many cases. In this paper, we introduce two algorithmic frameworks that yield significantly improved fixed-parameter tractable (FPT) algorithms parameterized by the network level \(\ell\). Our first main contribution shows that for several prominent network classes, the core algorithmic difficulty lies in finding a directed spanning tree on the network's undirected generator. By enumerating these spanning trees in \(\mathcal{O}(5.3334^\ell + \ell)\) time and orienting all remaining edges in polynomial time, we solve the orientation problem in \(\mathcal{O}(5.3334^\ell \cdot n)\) time for tree-based networks and in \(\mathcal{O}(5.3334^\ell \cdot n^2)\) time for orchards, where \(n\) is the number of vertices of the graph. Extending this approach with further branching yields \(\mathcal{O}(10.6667^\ell \cdot n^2)\)-time algorithms for tree-child and normal networks. Our second technique bypasses spanning trees by directly guessing the placement of reticulations on the generator. This framework provides \(\mathcal{O}(12.2071^\ell \cdot n^2)\)-time algorithms for temporal, reticulation-visible, and tree-sibling networks. Finally, we demonstrate the versatility of the reticulation-guessing framework by showing that even computing an orientation with minimum scanwidth is single-exponential FPT with respect to the level. Together, these results significantly improve the best-known running times for phylogenetic network orientation.
@article{Schestag2026Orienting,
title = {{Orienting Unrooted Binary Networks Faster: Focus on the Generator}},
author = {Schestag, Jannik and Zeh, Norbert},
journal = {arXiv preprint},
year = {2026},
archivePrefix = {arXiv},
eprint = {2606.31597}
}
[6]
Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth
Niels Holtgrefe and
Jannik Schestag
In terms of laymen
When conservation funds are limited and different species cost different amounts to protect, we would like to preserve as much evolutionary history as possible with the available budget. This paper develops efficient methods for doing this on sufficiently tree-like evolutionary networks and shows experimentally that the resulting algorithms can handle large networks quickly.
In Laiensprache (German translation)
Wenn die Mittel für den Artenschutz begrenzt sind und der Schutz verschiedener Arten unterschiedlich viel kostet, möchte man mit dem verfügbaren Budget möglichst viel Evolutionsgeschichte bewahren. Diese Arbeit entwickelt effiziente Methoden dafür auf evolutionären Netzwerken, die eine hinreichend baumähnliche Struktur besitzen, und zeigt experimentell, dass die Algorithmen auch große Netzwerke schnell bearbeiten können.
Abstract
Background: Identifying a subset of taxa that maximizes phylogenetic diversity is a cornerstone of quantitative conservation planning. Traditionally, phylogenetic diversity is defined over a phylogenetic tree in which leaves resemble present-day taxa and the branch lengths capture the estimated evolutionary distinctiveness. While maximizing phylogenetic diversity is computationally tractable on trees with unit costs, the problem becomes computationally intractable when transitioning to phylogenetic networks or to budgeted versions in which protecting taxa incurs non-homogeneous costs. This paper addresses these two challenges together, providing definitions and a comprehensive analysis of three distinct variants of budgeted phylogenetic diversity on networks.
Results: We conduct our study through the lens of a small structural parameter, node scanwidth (\(nsw\)), which measures the tree-likeness of a phylogenetic network. Given a tree-extension of width \(nsw\), we show that two of the considered variants can be optimized in \(\mathcal{O}^*(3^{nsw} \cdot B^2)\) time, where \(B\) is the budget. For the computationally harder third variant, we provide an algorithm to compute phylogenetic diversity scores in \(\mathcal{O}^*(4^{nsw})\) time. We further contribute the first exact algorithms to compute node scanwidth itself. On highly reticulated, simulated networks with several hundred taxa and heterogeneous costs, our implementation computes phylogenetic diversity scores and optimal node scanwidth in fractions of a second, and the budgeted optimization algorithms significantly outperform existing benchmarks previously limited to unit-cost scenarios.
Conclusions: Node scanwidth proves to be a small and computable parameter that makes budgeted phylogenetic diversity tractable on realistic networks, scaling comfortably to a thousand taxa. This narrows the gap between realistic models of reticulate evolution and the computational tools available for conservation planning.
Results: We conduct our study through the lens of a small structural parameter, node scanwidth (\(nsw\)), which measures the tree-likeness of a phylogenetic network. Given a tree-extension of width \(nsw\), we show that two of the considered variants can be optimized in \(\mathcal{O}^*(3^{nsw} \cdot B^2)\) time, where \(B\) is the budget. For the computationally harder third variant, we provide an algorithm to compute phylogenetic diversity scores in \(\mathcal{O}^*(4^{nsw})\) time. We further contribute the first exact algorithms to compute node scanwidth itself. On highly reticulated, simulated networks with several hundred taxa and heterogeneous costs, our implementation computes phylogenetic diversity scores and optimal node scanwidth in fractions of a second, and the budgeted optimization algorithms significantly outperform existing benchmarks previously limited to unit-cost scenarios.
Conclusions: Node scanwidth proves to be a small and computable parameter that makes budgeted phylogenetic diversity tractable on realistic networks, scaling comfortably to a thousand taxa. This narrows the gap between realistic models of reticulate evolution and the computational tools available for conservation planning.
@article{holtgrefe2026tractable,
title = {{Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth}},
author = {Holtgrefe, Niels and Schestag, Jannik},
year = {2026},
journal = {arXiv preprint},
archivePrefix = {arXiv},
eprint = {2605.23319}
}
2025
[5]
Parameterized Algorithms for Diversity of Networks with Ecological Dependencies
Mark Jones and
Jannik Schestag
Proceedings of the 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)
In terms of laymen
Conservation decisions should take into account both how much evolutionary history species represent and whether the selected species can survive together in an ecosystem. This paper combines these two requirements by incorporating food-web dependencies into conservation planning on evolutionary networks and identifies several structural conditions under which the resulting problem can be solved efficiently.
In Laiensprache (German translation)
Entscheidungen im Artenschutz sollten sowohl berücksichtigen, wie viel Evolutionsgeschichte die ausgewählten Arten repräsentieren, als auch, ob diese Arten gemeinsam in einem Ökosystem überleben können. Diese Arbeit verbindet beide Anforderungen, indem sie Abhängigkeiten aus Nahrungsnetzen in die Schutzplanung auf evolutionären Netzwerken einbezieht. Sie identifiziert mehrere strukturelle Bedingungen, unter denen das entstehende Problem effizient gelöst werden kann.
Abstract
For a phylogenetic tree, the phylogenetic diversity of a set \(A\) of taxa is the total weight of edges on paths to \(A\). Finding small sets of maximal diversity is crucial for conservation planning, as it indicates where limited resources can be invested most efficiently. In recent years, efficient algorithms have been developed to find sets of taxa that maximize phylogenetic diversity either in a phylogenetic network or in a phylogenetic tree subject to ecological constraints, such as a food web. However, these aspects have mostly been studied independently. Since both factors are biologically important, it seems natural to consider them together.
In this paper, we introduce decision problems where, given a phylogenetic network, a food web, and integers \(k\), and \(D\), the task is to find a set of \(k\) taxa with phylogenetic diversity of at least \(D\) under the maximize all paths measure, while also satisfying viability conditions within the food web. Here, we consider different definitions of viability, which all demand that a ``sufficient'' number of prey species survive to support surviving predators.
We investigate the parameterized complexity of these problems and present several fixed-parameter tractable (FPT) algorithms. Specifically, we provide a complete complexity dichotomy characterizing which combinations of parameters---out of the size constraint \(k\), the acceptable diversity loss \(\overline{D}\), the scanwidth of the food web \(sw\), the maximum in-degree \(\delta\) in the network, and the network height \(h\)---lead to W[1]-hardness and which admit FPT algorithms.
Our primary methodological contribution is a novel algorithmic framework for solving phylogenetic diversity problems in networks where dependencies (such as those from a food web) impose an order, using a color coding approach.
In this paper, we introduce decision problems where, given a phylogenetic network, a food web, and integers \(k\), and \(D\), the task is to find a set of \(k\) taxa with phylogenetic diversity of at least \(D\) under the maximize all paths measure, while also satisfying viability conditions within the food web. Here, we consider different definitions of viability, which all demand that a ``sufficient'' number of prey species survive to support surviving predators.
We investigate the parameterized complexity of these problems and present several fixed-parameter tractable (FPT) algorithms. Specifically, we provide a complete complexity dichotomy characterizing which combinations of parameters---out of the size constraint \(k\), the acceptable diversity loss \(\overline{D}\), the scanwidth of the food web \(sw\), the maximum in-degree \(\delta\) in the network, and the network height \(h\)---lead to W[1]-hardness and which admit FPT algorithms.
Our primary methodological contribution is a novel algorithmic framework for solving phylogenetic diversity problems in networks where dependencies (such as those from a food web) impose an order, using a color coding approach.
@inproceedings{jones2025parameterized,
title = {{Parameterized Algorithms for Diversity of Networks with Ecological Dependencies}},
author = {Jones, Mark and Schestag, Jannik},
booktitle = {Proceedings of the 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
pages = {11:1--11:21},
year = {2025},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.IPEC.2025.11}
}
[4]
Average-Tree Phylogenetic Diversity of Networks
Leo van Iersel,
Mark Jones,
Jannik Schestag,
Celine Scornavacca, and
Mathias Weller
Proceedings of the 25th International Workshop on Algorithms in Bioinformatics (WABI 2025)
In terms of laymen
A phylogenetic network can represent many different possible evolutionary trees, with some histories being more likely than others. This paper measures the diversity of a set of species by averaging over these possible histories and shows that, although optimization is difficult in general, it can be practical when the network contains relatively few points where evolutionary histories merge.
In Laiensprache (German translation)
Ein phylogenetisches Netzwerk kann viele verschiedene mögliche Evolutionsbäume darstellen, wobei manche Evolutionsgeschichten wahrscheinlicher sind als andere. Diese Arbeit misst die Vielfalt einer Gruppe von Arten, indem über diese möglichen Geschichten gemittelt wird. Obwohl die Optimierung im Allgemeinen schwierig ist, kann sie effizient durchgeführt werden, wenn das Netzwerk nur relativ wenige Stellen besitzt, an denen unterschiedliche Evolutionswege zusammenlaufen.
Abstract
Phylogenetic diversity is a measure used to quantify the biodiversity of a set of species. Here, we introduce the average-tree phylogenetic diversity score in rooted binary phylogenetic networks and consider algorithms for computing and maximizing the score on a given network. Basically, the score is the weighted average of the phylogenetic diversity scores in all trees displayed by the network, with the weights determined by the inheritance probabilities on the reticulation edges used in the embeddings. We show that computing the score of a given set of taxa in a given network is #P-hard, directly implying #P-hardness of finding a subset of \(k\) taxa achieving maximum diversity score and thereby ruling out polynomial-time algorithms for these problems unless the polynomial hierarchy collapses. However, we show that both problems can be solved efficiently if the input network is close to being a tree in the sense that its reticulation number is small. More precisely, we prove that we can solve the optimization problem in networks with \(n\) leaves and \(r\) reticulations in \(2^{\mathcal{O}(r)} \cdot n \cdot k\) time. Using experiments on data produced by simulating a reticulate-evolution process, we show that our algorithm runs efficiently on networks with hundreds of taxa and tens of reticulations.
@inproceedings{vanIersel2025averagetree,
title = {{Average-Tree Phylogenetic Diversity of Networks}},
author = {van Iersel, Leo and Jones, Mark and Schestag, Jannik and Scornavacca, Celine and Weller, Mathias},
booktitle = {Proceedings of the 25th International Conference on Algorithms in Bioinformatics (WABI 2025)},
pages = {15:1--15:20},
year = {2025},
organization = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.WABI.2025.15}
}
[3]
Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond
Leo van Iersel,
Mark Jones,
Jannik Schestag,
Celine Scornavacca, and
Mathias Weller
Proceedings of the 22nd RECOMB International Workshop on Comparative Genomics (RECOMB-CG 2025)
In terms of laymen
Evolutionary networks allow several possible histories for a species, for example because of hybridization, and these histories may have different probabilities. This paper shows that selecting a maximally diverse group of species can be done efficiently when the number of such evolutionary merging events is small. Another, related, seemingly natural measure of network simplicity does not suffice.
In Laiensprache (German translation)
Evolutionäre Netzwerke erlauben mehrere mögliche Abstammungsgeschichten für eine Art, beispielsweise aufgrund von Hybridisierungen, und diese Geschichten können unterschiedliche Wahrscheinlichkeiten haben. Diese Arbeit zeigt, dass sich eine möglichst vielfältige Gruppe von Arten effizient auswählen lässt, wenn die Anzahl solcher evolutionären Verschmelzungsereignisse klein ist. Ein anderes, verwandtes, zunächst naheliegend erscheinendes Maß für die Einfachheit eines Netzwerks reicht dafür dagegen nicht aus.
Abstract
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 Maximize 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 \(\mathcal{O}(2^r \log(k)(n+r))\) time, with \(n\) the total number of species in the network and \(r\) its reticulation number. Furthermore, we show that Maximize 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{vanIersel2025phylogenetic,
title = {{Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond}},
author = {van Iersel, Leo and Jones, Mark and Schestag, Jannik and Scornavacca, Celine and Weller, Mathias},
booktitle = {Proceedings of the 22nd RECOMB International Workshop on Comparative Genomics (RECOMB-CG 2025)},
pages = {107--130},
year = {2025},
organization = {Springer},
doi = {10.1007/978-3-031-94928-9_7}
}
2023
[2]
Finding Degree-Constrained Acyclic Orientations
Jaroslav Garvardt,
Malte Renken,
Jannik Schestag, and
Mathias Weller
Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
In terms of laymen
Sometimes the connections of an undirected network need to be assigned directions while obeying local restrictions on how many connections may point into each vertex, and without creating any directed cycles. This paper shows that this task is difficult in general but can be solved efficiently in important cases arising from evolutionary networks when the underlying structure or the number of ambiguous choices is sufficiently simple.
In Laiensprache (German translation)
Manchmal müssen den Verbindungen eines ungerichteten Netzwerks Richtungen zugewiesen werden, wobei für jeden Knoten Einschränkungen gelten, wie viele Verbindungen auf ihn zeigen dürfen, und gleichzeitig keine gerichteten Kreise entstehen sollen. Diese Arbeit zeigt, dass diese Aufgabe im Allgemeinen schwierig ist, sich aber in wichtigen Fällen aus dem Bereich evolutionärer Netzwerke effizient lösen lässt, wenn die zugrundeliegende Struktur oder die Anzahl mehrdeutiger Entscheidungen hinreichend einfach ist.
Abstract
We consider the problem of orienting a given, undirected graph into a (directed) acyclic graph such that the in-degree of each vertex \(v\) is in a prescribed list \(\lambda(v)\). Variants of this problem have been studied for a long time and with various applications, but mostly without the requirement for acyclicity. Without this requirement, the problem is closely related to the classical General Factor problem, which is known to be NP-hard in general, but polynomial-time solvable if no list \(\lambda(v)\) contains large “gaps” [Cornuéjols, J. Comb. Theory B, 1988]. In contrast, we show that deciding if an acyclic orientation exists is NP-hard even in the absence of such “gaps”.
On the positive side, we design parameterized algorithms for various, natural parameterizations of the acyclic orientation problem. A special case of the orientation problem with degree constraints recently came up in the context of reconstructing evolutionary histories (that is, phylogenetic networks). This phylogenetic setting imposes additional structure onto the problem that can be exploited algorithmically, allowing us to show fixed-parameter tractability when parameterized by either the treewidth of \(G\) (a smaller parameter than the frequently employed “level”), by the number of vertices \(v\) for which \(|\lambda(v)| \geq 2\), by the number of vertices \(v\) for which the highest value in \(\lambda(v)\) is at least 2. While the latter result can be extended to the general degree-constraint acyclic orientation problem, we show that the former cannot unless FPT=W[1].
On the positive side, we design parameterized algorithms for various, natural parameterizations of the acyclic orientation problem. A special case of the orientation problem with degree constraints recently came up in the context of reconstructing evolutionary histories (that is, phylogenetic networks). This phylogenetic setting imposes additional structure onto the problem that can be exploited algorithmically, allowing us to show fixed-parameter tractability when parameterized by either the treewidth of \(G\) (a smaller parameter than the frequently employed “level”), by the number of vertices \(v\) for which \(|\lambda(v)| \geq 2\), by the number of vertices \(v\) for which the highest value in \(\lambda(v)\) is at least 2. While the latter result can be extended to the general degree-constraint acyclic orientation problem, we show that the former cannot unless FPT=W[1].
@inproceedings{garvardt2023finding,
title = {{Finding Degree-Constrained Acyclic Orientations}},
author = {Garvardt, Jaroslav and Renken, Malte and Schestag, Jannik and Weller, Mathias},
booktitle = {Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {19:1--19:14},
year = {2023},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.IPEC.2023.19}
}
[1]
Maximizing All-Paths Phylogenetic Diversity: Parameterized Approaches for Networks
Mark Jones and
Jannik Schestag
Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
In terms of laymen
Evolution is not always well represented by a tree because events such as hybridization can create several ancestral routes to the same species. This paper studies how to select a small group of species that preserves as much of such an evolutionary network as possible. The problem is computationally difficult in general but becomes efficiently solvable when certain reasons of network complexity are limited.
In Laiensprache (German translation)
Evolution lässt sich nicht immer angemessen durch einen Baum darstellen, da Ereignisse wie Hybridisierungen dazu führen können, dass eine Art über mehrere Abstammungswege erreicht wird. Diese Arbeit untersucht, wie man eine kleine Gruppe von Arten auswählen kann, die möglichst viel eines solchen evolutionären Netzwerks bewahrt. Das Problem ist im Allgemeinen schwierig zu berechnen, kann aber effizient gelöst werden, wenn bestimmte Ursachen der Netzwerkkomplexität begrenzt sind.
Abstract
Phylogenetic Diversity (PD) is a fundamental measure of biodiversity, originally defined on phylogenetic trees and widely used in conservation biology. Phylogenetic trees are often generalised to directed acyclic graphs, called phylogenetic networks. As such, a corresponding generalization of PD is needed. A natural generalization to edge-weighted phylogenetic networks is the all-paths measure, where the diversity of a set \(S\) of species (taxa) is defined as the total weight of all edges that lie on a path from the root to at least one species in \(S\). While maximizing PD on trees can be solved in polynomial time, the corresponding problem on networks is NP-hard and difficult to approximate. We undertake a systematic parameterized complexity study of the Max-All-Paths-PD (MapPD) problem. We establish W[2]-hardness when parameterized by the number of species that are included in a solution, and W[1]-hardness for the number of species that are excluded. On the positive side, we show that the problem is fixed-parameter tractable with respect to the threshold of diversity and the acceptable loss of diversity. We further analyze how the network's proximity to a tree influences algorithmic behavior and present single-exponential fixed-parameter algorithms when parameterized by the number of reticulations and by the treewidth of the underlying graph. Finally, we present a polynomial kernelization for MapPD with respect to the number of reticulation edges.
@inproceedings{jones2023maximize,
title = {{How Can We Maximize Phylogenetic Diversity? Parameterized Approaches for Networks}},
author = {Jones, Mark and Schestag, Jannik},
booktitle = {Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {30:1--30:12},
year = {2023},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.IPEC.2023.30}
}