Publications with Implementations
Below you can find my publications and preprints with implemented algorithms, with links and toggleable abstracts.
To filter by a certain topic, click one of the buttons.
2026
[3]
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}
}
[2]
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
[1]
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}
}