Publications
Below are my publications and preprints, each with links, an abstract, a short plain-language summary, and a BibTeX entry; use the filter to narrow by type, or download every reference as a single .bib file. See also my Google Scholar profile.
Publications
2026
[14]
On Tree-Network Distinguishability and Full Identifiability of Phylogenetic Networks
[13]
Algebraic Invariants for Inferring 4-leaf Semi-Directed Phylogenetic Networks
[12]
PhyloZoo: a unified framework for phylogenetic network analysis in Python
[11]
Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth
[10]
Bounds on the Sequence Length Sufficient to Reconstruct Binary Level-1 Phylogenetic Networks Under the CFN Model
[9]
Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
In plain language
Many hard computational problems on evolutionary networks become easy when the network has a simple enough shape, measured by a number called its scanwidth. To take advantage of this you first have to compute that number, which was previously impractical. This paper gives the first efficient algorithm that computes scanwidth exactly, together with a fast heuristic that comes close to optimal on real datasets.
Abstract
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{holtgrefe2026scanwidth-exact,
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},
volume = {160},
pages = {103802},
doi = {10.1016/j.jcss.2026.103802},
year = {2026}
}
[8]
Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
[7]
Characterizing semi-directed phylogenetic networks and their multi-rootable variants
2025
[6]
PaNDA: Efficient Optimization of Phylogenetic Diversity in Networks
[5]
Distinguishing Phylogenetic Level-2 Networks with Quartets and Inter-Taxon Quartet Distances
[4]
Identifiability of Phylogenetic Level-2 Networks under the Jukes-Cantor Model
[3]
Reconstructing semi-directed level-1 networks using few quarnets
[2]
Squirrel: Reconstructing Semi-directed Phylogenetic Level-1 Networks from Four-Leaved Networks or Sequence Alignments
In plain language
Biologists reconstruct evolutionary history from DNA, but when species have hybridized this history is a network rather than a simple branching tree. Squirrel builds such a network directly from a DNA sequence alignment: it first breaks the problem into all four-species subnetworks and then stitches them back together. It runs in minutes on a standard laptop and comes with an easy-to-use graphical interface.
Abstract
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 cannot 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 Squirrel (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 Squirrel's performance through simulations and on real sequence datasets, 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 Squirrel 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. Squirrel 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,
author = {Holtgrefe, Niels and Huber, Katharina T and van Iersel, Leo and Jones, Mark and Martin, Samuel and Moulton, Vincent},
title = {{Squirrel: Reconstructing Semi-directed Phylogenetic Level-1 Networks from Four-Leaved Networks or Sequence Alignments}},
journal = {Molecular Biology and Evolution},
volume = {42},
number = {4},
pages = {msaf067},
doi = {10.1093/molbev/msaf067},
year = {2025}
}
2024
[1]
Invariants for level-1 phylogenetic networks under the random walk 4-state Markov model
Theses
•
Computing the Scanwidth of Directed Acyclic Graphs
In plain language
Many hard computations on evolutionary networks get easier when the network is "almost tree-like", measured by a quantity called scanwidth. This MSc thesis develops the first practical exact algorithm to compute scanwidth, together with a fast heuristic, and shows that scanwidth stays close to the classic treewidth measure in practice.
Abstract
Phylogenetic networks are a specific type of directed acyclic graph (DAG), used to depict evolutionary relationships among, for example, species or other groups of organisms. To solve computationally hard problems, treewidth has been used to parametrize algorithms in phylogenetics. In the hope of simplifying the algorithmic design process, Berry, Scornavacca and Weller [BSW20] recently proposed a new measure of tree-likeness that takes into account the directions of the arcs: scanwidth. They showed that the corresponding decision problem of this parameter - which can be seen as a variant of directed cutwidth, using a tree instead of a linear ordering - is NP-complete. This thesis aims to widen the structural knowledge of scanwidth and to find efficient ways of computing it on general DAGs, both by exact and heuristic algorithms.With the help of reduction rules, we construct an explicit dynamic programming algorithm that computes scanwidth exactly, along with its corresponding tree extension, in \( O(k \cdot n^k \cdot m) \) time for rooted DAGs of scanwidth \( k \). This slicewise polynomial algorithm proves that computing the scanwidth is in the complexity class XP. The algorithm also functions as an FPT algorithm for networks of level-\(\ell\), with the complexity bounded by \(O(2^{4 \ell - 1} \cdot \ell \cdot n + n^2) \). It performs well in practice, being able to compute the scanwidth of networks up to 30 reticulations and 100 leaves within 500 seconds.
On the heuristic side, an algorithm that repeatedly splits at a specific type of smallest cut is proposed. Enhanced with simulated annealing, this heuristic shows promising results, obtaining an average approximation ratio of 1.5 for large synthetic networks of 30 reticulations and 100 leaves. Applied to a real-world dataset of networks, the heuristic performs near-optimal. Although we prove that the scanwidth is always greater than or equal to the treewidth, experiments show that they are close to each other in practice. This further motivates the use of scanwidth over treewidth as a parameter in algorithms.
@masterthesis{holtgrefe2023scanwidth-thesis,
title={Computing the Scanwidth of Directed Acyclic Graphs},
author={Niels Holtgrefe},
year={2023},
address={Delft, The Netherlands},
note={Available at \url{http://resolver.tudelft.nl/uuid:9c82fd2a-5841-4aac-8e40-d4d22542cdf5}},
school={Delft University of Technology},
type= {MSc thesis}
}
•
Maximum Coverage Problems: Theory and Application in Optimal Sensor Selection
Miscellaneous
•
Extended abstract, EPSC–DPS Joint Meeting 2025, Helsinki, Finland, 2025
Optimising the Synthetic Aperture Radar Repeat Imaging Strategy for the EnVision Mission
No publications match this filter.
Spotted an error? See the list of corrections.