Source-linked AI summary
Which Phylogenetic Networks are Level-k Networks with Additional Arcs? Structure and Algorithms
Takatora Suzuki, Momoko Hayamizu
TL;DR
Reticulate evolution produces complex networks, and support trees do not cover networks that are not tree-based. This paper generalizes Hayamizu’s structure theorem to support networks, characterizes three support-network families, and derives counting, generation, and optimization algorithms. It provides a linear-time minimum-reticulation algorithm and exponential-time level-minimization algorithms that are practical across a reasonably wide reticulation range.
Problem
Support trees are inadequate for non-tree-based phylogenetic networks, where support networks can be more biologically relevant for studying reticulate evolution.
Source: §1 · pp. 1–2Method
The paper generalizes Hayamizu’s structure theorem to characterize all, minimal, and minimum support networks through direct products over maximal zig-zag trails.
Source: §1 · p. 2, §2.1 · p. 3Results
The resulting algorithms count and list each support-network family, find minimum-reticulation support networks in linear time, and solve minimum-level search exactly or heuristically in exponential time.
Source: §1 · p. 2Takeaways & Limitations
Support networks extend structural and algorithmic analysis from tree-based networks to general rooted binary phylogenetic networks.
Source: §7 · p. 12The framework does not directly extend to fully non-binary networks because maximal zig-zag trail decompositions may not be unique beyond the almost-binary case.
Source: §7 · p. 13
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends support-tree analysis to support networks, addressing non-tree-based networks where concise subgraphs can better represent reticulate evolution. It characterizes three support-network families and develops algorithms for counting, generation, and reticulation- and level-minimization.
1 Introduction
- Hayamizu’s structure theorem provides a canonical maximal zig-zag trail decomposition and support-tree characterization that this paper generalizes.Earlier work enabled optimal counting, listing, and optimization algorithms for support trees.Source: §1 · pp. 1–2
- Non-tree-based networks motivate support networks because concise subgraphs with few reticulations or low level can represent reticulate evolution more meaningfully than trees.These metrics equal zero for tree-based networks.Source: §1 · p. 2
- Direct-product characterizations define all, minimal, and minimum support networks, with product formulas linked to Fibonacci, Lucas, Padovan, and Perrin numbers.The resulting families are denoted AN, BN, and CN.Source: §1 · p. 2
- Linear-time counting and linear-delay listing algorithms are obtained for all three support-network families.The algorithms operate on the direct-product characterizations.Source: §1 · p. 2
- A linear-time optimal algorithm finds a support network with the fewest reticulations, while exact and heuristic level-minimization algorithms are exponential but practical across many reticulation numbers.The heuristic is particularly scalable and accurate in most cases.Source: §1 · p. 2
- The paper evaluates the level-minimization algorithms on synthetic data and reports their performance in Sections 4 and 6.Section 4 includes numerical results, while Section 6 evaluates the exact and heuristic algorithms.Source: §1 · p. 2
2 Preliminaries
The preliminaries define rooted binary phylogenetic networks, admissible edge sets, support trees, and maximal zig-zag trails. Hayamizu’s structure theorem uniquely decomposes a network into trail types and characterizes support trees through independent admissible choices on those trails.
2 Preliminaries
- Graphs are finite, simple, acyclic directed graphs; rooted binary phylogenetic networks have one root, leaf set X, and internal in- and out-degrees in {1,2}.Reticulations have in-degree 2 and out-degree 1; networks without reticulations are rooted binary phylogenetic trees.Source: §2 · p. 2, §2.1 · p. 3
2.1 Phylogenetic networks and support trees
- A support tree is a spanning tree whose smoothing yields a rooted binary phylogenetic tree on the same leaf set, and the network is tree-based when such a tree exists.The resulting rooted tree is called the base tree.Source: §2.1 · p. 3
- Admissible edge subsets characterize support trees: forced edges are included, sibling outgoing edges require at least one selection, and sibling incoming edges require exactly one.Theorem 3 gives a one-to-one correspondence between admissible subsets and support-tree edge sets.Source: §2.1 · pp. 3–4
- Different admissible subsets can induce isomorphic support trees, so the paper counts admissible edge sets while identifying each support tree with its edge set.This distinction creates subtly different counting problems.Source: §2.1 · p. 4
2.2 The structure theorem for rooted binary phylogenetic networks
- A zig-zag trail alternates shared heads and tails; maximal trails are uniquely classified as crowns, N-fences, M-fences, or W-fences.Trails can be encoded as ordered 0-1 edge sequences, such as ⟨10101⟩.Source: §2.2 · p. 4
- The unique maximal zig-zag decomposition can be computed in Θ(|E(N)|) time.This decomposition underpins the structure theorem and its algorithms.Source: §2.2 · pp. 4–5
- A support tree is exactly a combination of admissible edge subsets chosen independently on every maximal zig-zag trail.Support trees exist precisely when no trail is a W-fence; the family is the direct product of the local admissible families.Source: §2.2 · pp. 4–5
3 The family of support networks and its two subfamilies
The paper defines support networks and their base tier and level, then distinguishes all, minimal, and minimum support networks for optimizing reticulation number and level.
3 The family of support networks and its two subfamilies
- A support network is a spanning subgraph whose smoothed form is a rooted binary phylogenetic network; the original network itself always qualifies.The base tier and base level are the minimum reticulation number and level over all support networks.Source: §3 · pp. 5–6
- For rooted networks, base tier and base level need not coincide, unlike the equality established for certain unrooted networks.Figure 2 illustrates a rooted example with r∗(N) = 2 and level∗(N) = 1.Source: §3 · p. 6, Figure 2 · p. 6
- The paper focuses on computing base tier and especially base level through minimal and minimum support networks, because restricting to these subfamilies may reduce the search space.It defines A_N, B_N, and C_N as all, minimal-edge, and minimum-edge support networks, respectively.Source: §3 · p. 6
- These families satisfy A_N ⊇ B_N ⊇ C_N and can all be distinct; for tree-based networks, C_N coincides with the support trees.Figure 3 displays representatives from A_N \ B_N, B_N \ C_N, and C_N.Source: §3 · p. 6, Figure 3 · p. 6
4 Counting the support networks of three types
The generalized structure theorem decomposes support-network choices into independent local selections on maximal zig-zag trails, enabling product formulas and linear-time counting and listing.
4 Counting the support networks of three types
- The framework establishes one-to-one, trail-wise characterizations of A_N, B_N, and C_N by relaxing the tree admissibility condition while retaining local constraints.A-admissible selections may induce reticulations, whereas B- and C-admissibility impose minimality and minimum cardinality, respectively.Source: §4 · p. 7
4.1 The number |A_N| of all support networks
- |A_N| is computed in Θ(|E(N)|) time and all support networks can be listed with Θ(|E(N)|) delay using the maximal zig-zag trail decomposition.The count factors over trail-local admissible selections, with Fibonacci and Lucas formulas depending on trail type.Source: §4.1 · pp. 7–8
4.2 The number |B_N| of minimal support networks
- |B_N| has a direct-product formula involving Padovan and Perrin sequences, and its count and enumeration are both achievable in linear time or delay.Minimal selections exclude both consecutive unselected edges and three consecutive selected edges in the trail encodings.Source: §4.2 · pp. 8–9
4.3 The number |C_N| of minimum support networks
- |C_N| equals 2^c times the product of |E(Z_i)|/2 over M- and W-fences, and it can likewise be counted and listed in linear time or delay.C-admissibility differs from support-tree admissibility by allowing W-fences.Source: §4.3 · p. 9
4.4 Counting support networks in random phylogenetic networks
- The random-network study found exponential growth in all three support-network counts, with |B_N| consistently below |A_N| and |C_N| smaller still.Counts varied widely among networks sharing the same numbers of leaves and reticulations, indicating substantial structural diversity.Source: §4.4 · p. 9
5 Finding a support network with the fewest reticulations
The linear-time algorithm for Reticulation Minimization constructs a minimum support network by selecting any element from the direct-product family C_N. Its minimum reticulation number equals the number of W-fences in the maximal zig-zag trail decomposition.
5 Finding a support network with the fewest reticulations
- A support network minimizes reticulations exactly when it is a minimum support network with the fewest edges.Source: §5 · p. 10
- For the Figure 1 example, combining C-admissible subsets across seven trails yields a support network with reticulation number 1.Source: §5 · p. 10
- The algorithm solves Reticulation Minimization in Θ(|E(N)|) time by selecting one element from C_N.It computes the maximal zig-zag trail decomposition and selects an appropriate C-admissible subset from each trail.Source: §5 · p. 10
- The minimum reticulation number is zero for tree-based networks, while generally it equals the number of W-fences in the maximal trail decomposition.Source: §5 · p. 10
6 Finding a support network with the minimum level
The paper solves minimum-level support-network selection exactly over minimal support networks and heuristically over minimum support networks. Both algorithms scale exponentially with reticulation number, while the heuristic is substantially faster and often matches the exact method.
6.1 Exact algorithm
- Algorithm 1 exhaustively searches B_N, which is guaranteed to contain a minimum-level support network, and runs in O(|B_N| · |E(N)|) time.Source: §6.1 · pp. 10–11
6.2 Heuristic algorithm
- Algorithm 2 searches the smaller family C_N and runs in O(|C_N| · |E(N)|) time.Source: §6.2 · p. 11
- Algorithm 2 can fail because minimizing reticulations does not necessarily minimize level.In the illustrated case, every network in C_N has two reticulations and level 2, while an optimal level-1 network with three reticulations lies in B_N \ C_N.Source: §6.2 · p. 11, Figure 4 · p. 11
6.3 Performance evaluation of the exact and heuristic algorithms
- The evaluation used 100 random networks for each reticulation number from 1 to 43, with n = 8 leaves, comparing runtimes and exact-output agreement.Source: §6.3 · p. 12, Figure 5 · p. 12
- Algorithm 2 ran at 1/10 to 1/100 of Algorithm 1’s runtime and matched its output in approximately 70% of instances near r = 30.Both runtimes increased exponentially with r; Algorithm 1 stopped beyond r = 34, whereas Algorithm 2 reached r = 43 before memory limits.Source: §6.3 · p. 12, Figure 5 · p. 12
7 Conclusion and future directions
The paper extends Hayamizu’s structure theorem from support trees to support networks, enabling direct-product characterizations, counting and listing algorithms, and optimization methods. It provides a linear-time minimum-tier algorithm and practical exponential-time methods for minimum-level optimization, while identifying limits beyond almost-binary networks.
7 Conclusion and future directions
- Direct-product characterizations of A_N, B_N, and C_N yield linear-time counting formulas and linear-delay listing algorithms for three support-network families.The counting formulas connect to Fibonacci, Lucas, Padovan, and Perrin numbers.Source: §7 · pp. 12–13
- A linear-time Reticulation Minimization algorithm finds an optimal support network by selecting any element of C_N.Source: §7 · p. 13
- Exact and heuristic Level Minimization algorithms are practical across a wide range of reticulation levels, with the heuristic usually finding optimal or good approximate solutions.Source: §7 · p. 13
- The framework applies to almost-binary networks but does not directly extend to fully non-binary networks because maximal zig-zag trail decompositions may not be unique.Source: §7 · p. 13
A Appendix
The appendix fixes notation for a rooted binary phylogenetic network, its maximal zig-zag trail decomposition, and the edge count of each trail.
A Appendix
- The appendix denotes the maximal zig-zag trail decomposition by Z = {Z_1, ..., Z_d}, orders its trails as vector Z⃗, and defines m_i = |E(Z_i)|.Source: A Appendix · p. 14
A.1 Proof of Theorem 9
The proof counts A-admissible subsets by bijecting them with matchings in paths for fences and cycles for crowns, then applies Fibonacci and Lucas formulas to obtain exponential growth in network size.
Fence case
- A-admissible subsets of a fence correspond bijectively to matchings in an undirected path formed from its non-terminal edges.Binary networks ensure this subgraph is a path; the almost-binary case can be reduced without changing SA(Zi).Source: §A.1 · p. 14
- For the fence Zi, the number of A-admissible subsets satisfies |SA(Zi)| = Fmi, using that matchings in a path with ℓ≥1 edges number Fℓ+2.Source: §A.1 · p. 14
Crown case
- A-admissible subsets of a crown correspond bijectively to matchings in the undirected cycle obtained by ignoring edge orientations.Because crowns have no terminal edges, admissibility is equivalent to forbidding adjacent selected edges.Source: §A.1 · p. 14
- The number of A-admissible subsets for a crown with mi edges is Lmi, by the cycle-matching formula in Theorem 2 of [3].The count includes possibly empty matchings.Source: §A.1 · p. 14
Asymptotic conclusion
- Using Fn = Θ(ϕn) and Ln = Θ(ϕn), the total number of A-admissible subsets grows as Θ(ϕ|E(N)|) across the network’s biconnected components.The direct-product count multiplies the component contributions.Source: §A.1 · p. 14
A.2 Proof of Theorem 11
The proof counts minimal admissible subsets through maximal matchings: paths represent fences and cycles represent crowns, yielding product formulas with asymptotic growth governed by ψ.
Asymptotic conclusion
- Since Pn = Θ(ψn) and Qn = Θ(ψn), the total number of minimal support networks is Θ(ψ|E(N)|).The componentwise counts combine multiplicatively across the network.Source: §A.2 · pp. 14–15
Fence case
- Minimal A-admissible subsets of a fence correspond to maximal matchings in its associated undirected path.The complement of an admissible subset is used, so minimality becomes maximality of the corresponding matching.Source: §A.2 · p. 14
- The number of minimal support subsets for a fence with mi edges is Pmi, using the maximal-matching count Pℓ+2 for paths.The associated path has the edge count required to obtain the stated index.Source: §A.2 · p. 14
Crown case
- Minimal A-admissible subsets of a crown correspond to maximal matchings in the associated undirected cycle.This gives the crown analogue of the fence correspondence.Source: §A.2 · p. 15
- The number of minimal support subsets for a crown with mi edges is Qmi, by the maximal-matching count for cycles in [2].The result applies to crowns with at least three edges.Source: §A.2 · p. 15
A.3 Proof of Theorem 16
The proof establishes that enumerating minimal support networks and evaluating their block levels yields a correct algorithm for finding a minimum-level support network, with exponential dependence on network size.
Correctness
- If every minimal support network has level greater than k, then no level-k support network can exist outside the minimal set.Any non-minimal level-k support network contains a minimal support network whose level is no larger.Source: §A.3 · p. 15
- Therefore, checking the level of every minimal support network and selecting the smallest value correctly finds a minimum-level support network.The argument relies on each block of a minimal subnetwork being contained in the corresponding block of the original support network.Source: §A.3 · p. 15
Complexity
- For each minimal support network, depth-first search computes its block decomposition and block reticulation values in O(|E(N)|) time.Binaryness gives O(|V(N)|) = O(|E(N)|), and every minimal support network is a subgraph of N.Source: §A.3 · p. 15
- The overall running time is O(|BN| · |E(N)|) = O(ψ|E(N)| · |E(N)|).The exponential factor comes from the number of minimal support networks examined.Source: §A.3 · p. 15