Exploiting Low Scanwidth to Resolve Soft Polytomies

Phylogenetic networks allow modeling reticulate evolution, capturing events such as hybridization and horizontal gene transfer. A fundamental computational problem in this context is the Tree Containment problem, which asks whether a given phylogenetic network is compatible with a given phylogenetic tree. However, the classical statement of the problem is not robust to poorly supported branches in biological data, possibly leading to false negatives. In an effort to address this, a relaxed version that accounts for uncertainty, called Soft Tree Containment, has been introduced by Bentert, Malík, and Weller [SWAT'18]. We present an algorithm that solves Soft Tree Containment in $2^{O(Δ_T \cdot k \cdot \log(k))} \cdot n^{O(1)}$ time, where $k = \operatorname{sw}(Γ) + Δ_N$, with $Δ_T$ and $Δ_N$ denoting the maximum out-degrees in the tree and the network, respectively, and $\operatorname{sw}(Γ)$ denoting the "scanwidth" [Berry, Scornavacca, and Weller, SOFSEM'20] of a given tree extension of the network, while $n$ is the input size. Our approach leverages the fact that phylogenetic networks encountered in practice often exhibit low scanwidth, making the problem more tractable.

Authors

Institutions

Publication Details

Journal
Discrete Mathematics & Theoretical Computer Science
Published
2026-11-16
DOI
https://doi.org/10.46298/dmtcs.17720
Primary Topic
Genomics and Phylogenetic Studies
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Exploiting Low Scanwidth to Resolve Soft Polytomies

Mathias Weller, Sebastian Bruchhold
Discrete Mathematics & Theoretical Computer Science
Genomics and Phylogenetic Studies
article

Exploiting Low Scanwidth to Resolve Soft Polytomies

Mathias Weller, Sebastian Bruchhold
article en

Abstract

Phylogenetic networks allow modeling reticulate evolution, capturing events such as hybridization and horizontal gene transfer. A fundamental computational problem in this context is the Tree Containment problem, which asks whether a given phylogenetic network is compatible with a given phylogenetic tree. However, the classical statement of the problem is not robust to poorly supported branches in biological data, possibly leading to false negatives. In an effort to address this, a relaxed version that accounts for uncertainty, called Soft Tree Containment, has been introduced by Bentert, Malík, and Weller [SWAT'18]. We present an algorithm that solves Soft Tree Containment in $2^{O(Δ_T \cdot k \cdot \log(k))} \cdot n^{O(1)}$ time, where $k = \operatorname{sw}(Γ) + Δ_N$, with $Δ_T$ and $Δ_N$ denoting the maximum out-degrees in the tree and the network, respectively, and $\operatorname{sw}(Γ)$ denoting the "scanwidth" [Berry, Scornavacca, and Weller, SOFSEM'20] of a given tree extension of the network, while $n$ is the input size. Our approach leverages the fact that phylogenetic networks encountered in practice often exhibit low scanwidth, making the problem more tractable.

Discrete Mathematics & Theoretical Computer ScienceVol. vol. 28:4, SOFSEM 2026(Special issues)
Laboratoire d'Informatique Gaspard-Monge (FR), Technische Universität Berlin (DE)
Genomics and Phylogenetic Studies
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon