Which Phylogenetic Networks are Level- k k Networks with Additional Arcs? Structure and Algorithms

Takatora Suzuki, Momoko Hayamizu · 2025

Read Which Phylogenetic Networks are Level- k k Networks with Additional Arcs? Structure and Algorithms by Takatora Suzuki, Momoko Hayamizu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-11947.txt.

Introduction

Evolution sometimes braids lineages together instead of splitting them, and the family diagrams that result are networks, not trees. Takatora Suzuki and Momoko Hayamizu ask, in a 2025 paper, which of those networks are just a standard class with extra arcs added. The question extends a line of work that began with trees hidden inside networks.

The authors generalize a structure theorem so it covers support networks, not only support trees. That yields direct descriptions of all support networks, and of the minimal and smallest ones. Each description spawns best-possible algorithms to count and list them. One runs in linear time and finds the support network with the fewest braids, a number biologists read as the tier of the network.

Catalog record

CREATORTakatora Suzuki, Momoko Hayamizu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-11947

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Which Phylogenetic Networks are Level- k k Networks with Additional Arcs? Structure and Algorithms Takatora Suzuki, Momoko Hayamizu Abstract Reticulate evolution gives rise to complex phylogenetic networks, making their interpretation challenging. A typical approach is to extract trees within such networks. Since Francis and Steel’s seminal paper, “Which Phylogenetic Networks are Merely Trees with Additional Arcs?” (2015), tree-based phylogenetic networks and their support trees (spanning trees with the same root and leaf set as a given network) have been extensively studied. However, not all phylogenetic networks are tree-based, and for the study of reticulate evolution, it is often more biologically relevant to identify support networks rather than trees. This study generalizes Hayamizu’s structure theorem for rooted binary phylogenetic networks, which yielded optimal algorithms for various computational problems on support trees, to extend the theoretical framework for support trees to support networks. This allows us to obtain a direct-product characterization of each of three sets: all, minimal, and minimum support networks, for a given network. Each characterization yields optimal algorithms for counting and generating the support networks of each type. Applications include a linear-time algorithm for finding a support network with the fewest reticulations (i.e., the minimum tier). We also provide exact and heuristic algorithms for finding a support network with the minimum level, both running in exponential time but practical across a reasonably wide range of reticulation numbers. Department of Pure and Applied Mathematics, Graduate School of Fundamental Science and Engineering, Waseda University, [email protected]://orcid.org/0009-0007-3425-7006JST SPRING Program Grant Number JPMJSP2128, Japan Department of Applied Mathematics, Faculty of Science and Engineering, Waseda University, [email protected]://orcid.org/0000-0001-8825-6331JST FOREST Program Grant Number JPMJFR2135, Japan The authors thank Tsuyoshi Urata, Haruki Miyaji, and Yukihiro Murakami for their discussions and Manato Yokoyama for help with the GitHub repository. ccs Applied computing \rightarrow Biological networks keywords Phylogenetic networks, Support networks, Level- k networks, Tier- k networks, Structure theorem, Enumeration, Optimization † † runningtitle: Which Phylogenetic Networks are Level- k Networks with Additional Arcs? † † runningauthor: Takatora Suzuki and Momoko Hayamizu † † copyright: Takatora Suzuki and Momoko Hayamizu † † supplement: Software: https://github.com/hayamizu-lab/structure-support-networks † † editors: Broňa Brejová and Rob Patro † † event-title: 25th International Workshop on Algorithms in Bioinformatics (WABI 2025) † † event-shorttitle: WABI 2025 † † event-acronym: WABI † † year: 2025 † † event-date: August 20–22, 2025 † † event-location: University of Maryland, in College Park, MD † † series-volume: xxx † † articleno: x 1 Introduction Evolutionary histories involving reticulate events, such as horizontal gene transfer, hybridization, and recombination, are better represented by networks than trees. However, networks can be far more complex than trees, making their interpretation challenging. A typical approach is to find meaningful subgraphs, particularly spanning trees, of these networks. Since Francis and Steel’s seminal paper “Which Phylogenetic Networks are Merely Trees with Additional Arcs?” [ 6 ] , tree-based networks and their support trees (spanning trees with the same root and leaf set as the network) have been extensively studied (e.g., [ 7 , 8 , 12 ] ). Hayamizu [ 7 ] developed optimal (linear-time or linear-delay) algorithms for various computational problems, including counting, listing, and optimization of support trees, by establishing a theoretical foundation called a structure theorem for rooted binary phylogenetic networks. It provides a canonical way to decompose any rooted binary phylogenetic network into its unique maximal zig-zag trails, and characterizes the family of edge-sets of support trees of a given network. While tree-based phylogenetic networks encompass many well-studied subclasses such as tree-child, stack-free, and orchard networks, networks inferred from biological data are not necessarily tree-based. This has led to increased interest in non-tree-based networks (e.g., [ 1 , 4 , 5 , 11 ] ). Indeed, for the study of reticulate evolution, it is often more biologically relevant to consider networks within networks rather than trees. In such contexts, finding a most concise subgraph, such as one with the fewest reticulations (minimum tier) or with the minimum level, is particularly meaningful. These metrics can be interpreted as measures of deviation from being tree-based [ 5 , 4 ] , as they equal zero for tree-based networks. In this paper, we generalize Hayamizu’s structure theorem to build a theoretical framework for support networks of rooted binary phylogenetic networks. Building on the maximal zig-zag trail decomposition established in [ 7 ] , we derive direct-product characterizations of three families of support networks for a given network N : all support networks \mathcal{A}_{N} , minimal support networks \mathcal{B}_{N} , and minimum support networks \mathcal{C}_{N} . These characterizations yield closed-form product formulas for their cardinalities, revealing unexpected connections to Fibonacci, Lucas, Padovan, and Perrin numbers. We present a linear-time algorithm for counting each of |\mathcal{A}_{N}| , |\mathcal{B}_{N}| , and |\mathcal{C}_{N}| , as well as a linear-delay algorithm to list the support networks in each family. Our theoretical results lead to practical algorithms for two key optimization problems: Problem 1 ( Reticulation Minimization ) and Problem 2 ( Level Minimization ). Problem 1 asks for a support network with the minimum reticulation number (minimum tier). We present a linear-time optimal algorithm for solving Problem 1 , which can be achieved by selecting any element from \mathcal{C}_{N} . Problem 2 asks for a support network with the minimum level. We conjecture that this problem is NP-hard and present exact and heuristic algorithms for solving Problem 2 (Algorithms 1 and 2 ). Although they are both exponential-time algorithms, they are practical for networks with a reasonably wide range of reticulation numbers. The heuristic is particularly scalable and accurate in most cases. The remainder of the paper is organized as follows. In Section 2 , we define graph theoretical terminology and review the relevant materials on support trees (Section 2.1 ) and the structure theorem (Section 2.2 ). In Section 3 , we define support networks, their families \mathcal{A}_{N} , \mathcal{B}_{N} , and \mathcal{C}_{N} , and relevant concepts. Section 4 provides characterizations and counting formulas for each family. Numerical results are also presented in Section 4.4 . In Section 5 , we give a linear-time algorithm for solving Problem 1 . Section 6 presents the exact and heuristic algorithms for Problem 2 , along with performance evaluations using synthetic data. Section 7 concludes with a summary of our contributions and directions for future research. 2 Preliminaries The graphs in this paper are finite, simple (i.e. having neither loops nor multiple edges), acyclic directed graphs, unless otherwise stated. For a graph G , V(G) and E(G) denote the sets of vertices and edges of G , respectively. For two graphs G and H , G is a subgraph of H if both V(G)\subseteq V(H) and E(G)\subseteq E(H) hold, in which case we write G\subseteq H . In particular, G and H are isomorphic , denoted by G=H , if there exists a bijection between V(G) and V(H) that yields a bijection between E(G) and E(H) . For a graph G , a block of G is a maximal connected subgraph that contains no cut edge. A subgraph G of H is proper if G\neq H . A subgraph G of H is a spanning subgraph of H if V(G)=V(H) . Given a graph G and a non-empty subset S\subseteq E(G) , the

Read the complete text