Finding Tree-Like Substructures in Phylogenetic Networks: ILP Approaches and Their Application
Abstract
Phylogenetic networks model evolutionary histories that involve reticulate events, but their structural complexity makes them difficult to interpret. Extracting their simple substructures both clarifies the evolutionary pathways and quantifies the complexity of the networks themselves. For a given rooted almost-binary phylogenetic network, the Level Minimization problem asks for a spanning subgraph that has the same root and leaf-set and whose level is minimum, i.e., which is as close to a tree as possible. Networks for which the minimum level is zero are known as tree-based networks and can be recognized in linear time. However, Level Minimization is NP-hard in general. State-of-the-art algorithms rely on exhaustive searches of the solution spaces and hence apply only to networks of limited size. In this paper, we propose two methods for Level Minimization using integer linear programming: an exact formulation for finding such a subgraph of level at most one, and a heuristic formulation for the general case. Computational experiments confirmed the practicality of both formulations. An application to ancestral recombination graphs suggests that the minimum level provides an alternative measure of the topological complexity of an inferred network.
Related
- Species limits in Veronica hederifolia and relatives: experimental, morphometric, and phylogenetic approaches in a weedy polyploid complex
- Best Matches in Phylogenetic Networks
- Exact Counts of Binary Phylogenetic Networks with Four Reticulations
- The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks
- The parental parsimony problem on binary, tree-child phylogenetic networks
BibTeX
@misc{suzuki2026finding,
title = {{Finding Tree-Like Substructures in Phylogenetic Networks: ILP Approaches and Their Application}},
author = {Takatora Suzuki},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.28659},
eprint = {2608.28659},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28659},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Finding Tree-Like Substructures in Phylogenetic Networks: ILP Approaches and Their Application
AU - Takatora Suzuki
PY - 2026
DA - 2026/08/21
PB - arXiv
DO - 10.48550/arxiv.2608.28659
UR - https://arxiv.org/abs/2608.28659
AB - Phylogenetic networks model evolutionary histories that involve reticulate events, but their structural complexity makes them difficult to interpret. Extracting their simple substructures both clarifies the evolutionary pathways and quantifies the complexity of the networks themselves. For a given rooted almost-binary phylogenetic network, the Level Minimization problem asks for a spanning subgraph that has the same root and leaf-set and whose level is minimum, i.e., which is as close to a tree as possible. Networks for which the minimum level is zero are known as tree-based networks and can be recognized in linear time. However, Level Minimization is NP-hard in general. State-of-the-art algorithms rely on exhaustive searches of the solution spaces and hence apply only to networks of limited size. In this paper, we propose two methods for Level Minimization using integer linear programming: an exact formulation for finding such a subgraph of level at most one, and a heuristic formulation for the general case. Computational experiments confirmed the practicality of both formulations. An application to ancestral recombination graphs suggests that the minimum level provides an alternative measure of the topological complexity of an inferred network.
ER -