The $$\mathcal {C}$$ C - Orientation problem asks whether it is possible to orient an undirected graph to a directed phylogenetic network of a desired network class $$\mathcal {C}$$ C . This problem arises, for example, when visualising evolutionary data, as popular methods such as Neighbor-Net are distance-based and inevitably produce undirected graphs. The complexity of $$\mathcal {C}$$ C - Orientation remains open for many classes $$\mathcal {C}$$ C , including binary tree-child networks, and practical methods are still lacking. In this paper, we propose (1) an exact FPT algorithm for $$\mathcal {C}$$ C - Orientation , applicable to any class $$\mathcal {C}$$ C admitting a tractable membership test, and parameterised by the reticulation number and the maximum size of minimal basic cycles, and (2) a very fast heuristic for Tree-Child Orientation . While the state-of-the-art for $$\mathcal {C}$$ C - Orientation is a simple exponential time algorithm whose computational bottleneck lies in searching for appropriate reticulation vertex placements, our methods significantly reduce this search space. Experiments show that, although our FPT algorithm is still exponential, it significantly outperforms the existing method. The heuristic runs even faster but with increasing false negatives as the reticulation number grows. Given this trade-off, we also discuss theoretical directions for improvement and biological applicability of the heuristic approach.
Urata, Tsuyoshi, Yokoyama, Manato, Miyaji, Haruki et al. Orientability of undirected phylogenetic networks to a desired class: practical algorithms and application to tree-child orientation. // Algorithms for Molecular Biology. – 2026. – DOI: 10.1186/s13015-025-00282-w. – URL: https://www.biomedcentral.com/openurl?doi=10.1186/s13015-025-00282-w
Urata, Tsuyoshi, Yokoyama, Manato, Miyaji, Haruki, Hayamizu, & Momoko (2026). Orientability of undirected phylogenetic networks to a desired class: practical algorithms and application to tree-child orientation. Algorithms for Molecular Biology. https://doi.org/10.1186/s13015-025-00282-w
Urata, et al. “Orientability of undirected phylogenetic networks to a desired class: practical algorithms and application to tree-child orientation.” Algorithms for Molecular Biology, 2026. doi:10.1186/s13015-025-00282-w.
@article{Urata2026,
title = {Orientability of undirected phylogenetic networks to a desired class: practical algorithms and application to tree-child orientation},
author = {Urata and Tsuyoshi and Yokoyama and Manato and Miyaji and Haruki and Hayamizu and Momoko},
journal = {Algorithms for Molecular Biology},
year = {2026},
doi = {10.1186/s13015-025-00282-w},
url = {https://www.biomedcentral.com/openurl?doi=10.1186/s13015-025-00282-w}
}
Background Aquaculture production of Atlantic salmon is a rapidly growing food sector, offering numerous advantages over terrestrial livestock. However, infectious diseases remain a major constraint, reducing production efficiency and...
The eukaryotic genome is folded into a functionally consequential three-dimensional architecture whose organizing principles have recently attracted substantial interest. Two physical mechanisms dominate current thinking: active loop...
Background The mitochondrial and nuclear genomes must coevolve to ensure cell homeostasis, legacy and consequence of their endosymbiotic origin. Mitonuclear coevolution is central to the oxidative phosphorylation pathway (OXPHOS), where...
Background Intrinsically disordered regions (IDRs) are widespread in proteins and play essential roles in regulation, signaling, and molecular recognition. IDRs of different lengths often exhibit distinct sequence and functional...