Papers › Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical...
Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation
Tsuyoshi Urata, Manato Yokoyama, Haruki Miyaji, Momoko Hayamizu
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The C-Orientation problem asks whether it is possible to orient an undirected graph to a directed phylogenetic network of a desired network class 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 C-Orientation remains open for many classes C, including binary tree-child networks, and practical methods are still lacking. In this paper, we propose an exact FPT algorithm for C-Orientation that is applicable to any class C and parameterised by the reticulation number and the maximum size of minimal basic cycles, and a very fast heuristic for Tree-Child Orientation. While the state-of-the-art for 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections