PaperlayerView exact revision on arXiv

Source-linked AI summary

Finding Tree-Like Substructures in Phylogenetic Networks: ILP Approaches and Their Application

Takatora Suzuki

arXiv:2608.28659v1q-bio.PEcs.DM

TL;DR

LEVEL MINIMIZATION seeks support networks that are as tree-like as possible, but existing exhaustive methods are exponential and the problem is NP-hard. The paper introduces exact and heuristic ILP formulations, which experiments find practical and useful for distinguishing the complexity of inferred ancestral recombination graphs.

  • Problem

    LEVEL MINIMIZATION seeks a minimum-level support network, but the problem is NP-hard and existing exhaustive algorithms apply only to limited-size networks.

  • Method

    The paper formulates an exact ILP for level at most one and a heuristic ILP for general LEVEL MINIMIZATION, encoding structural results as linear constraints.

  • Results

    The formulations were practical: the exact formulation scaled to 800 reticulations, while the heuristic was faster and more stable than exhaustive search with nearly the same level.

  • Takeaways & Limitations

    Different base levels for two inferred ancestral recombination graphs suggest that base level can provide an alternative measure of topological complexity.

  • Takeaways & Limitations

    The methods are stated for rooted almost-binary networks, and incorporating inheritance intervals would be necessary for biological analyses beyond ARG topology.

Abstract

from arXiv · show

Phylogenetic networks model evolutionary histories that involve reticulate events, but their structural complexity makes them difficult to interpret. Extracting their simple substructures both clarifies the evolutionary pathways and quantifies the complexity of the networks themselves. For a given rooted almost-binary phylogenetic network, the Level Minimization problem asks for a spanning subgraph that has the same root and leaf-set and whose level is minimum, i.e., which is as close to a tree as possible. Networks for which the minimum level is zero are known as tree-based networks and can be recognized in linear time. However, Level Minimization is NP-hard in general. State-of-the-art algorithms rely on exhaustive searches of the solution spaces and hence apply only to networks of limited size. In this paper, we propose two methods for Level Minimization using integer linear programming: an exact formulation for finding such a subgraph of level at most one, and a heuristic formulation for the general case. Computational experiments confirmed the practicality of both formulations. An application to ancestral recombination graphs suggests that the minimum level provides an alternative measure of the topological complexity of an inferred network.

1 Introduction

Phylogenetic networks capture reticulate evolution but are harder to interpret than trees. The paper addresses this complexity by minimizing the level of extracted support networks using ILP formulations.

  • Phylogenetic networks represent horizontal gene transfer, hybridization, and recombination that trees cannot capture, but their added expressive power increases structural complexity.
  • A support network is a spanning subgraph with the same root and leaf-set, while tree-based networks contain a support tree.
  • LEVEL MINIMIZATION seeks a support network with minimum level, whose value is called the base level.
  • Existing algorithms exhaustively search exponential solution spaces, and LEVEL MINIMIZATION is NP-hard.
  • The paper proposes an exact ILP for support networks of level at most one and a heuristic ILP for general LEVEL MINIMIZATION.
  • Experiments found the formulations practical, while two ancestral recombination graphs had different base levels, suggesting base level as an alternative complexity measure.

2 Preliminaries

The preliminaries define the graph-theoretic and phylogenetic-network objects used throughout the paper. They also introduce support networks, network level, and maximal zig-zag trail decompositions.

  • Graph theoretical terminology: Graphs are finite, simple, acyclic directed graphs, with vertices, edges, subgraphs, spanning subgraphs, and connected blocks defined accordingly.
  • Phylogenetic networks: A rooted almost-binary phylogenetic network has one root, leaf-set X, and internal vertices with in- and out-degrees in {1,2}.
  • Phylogenetic networks: A support network is a spanning subgraph that is itself a rooted almost-binary network on X; a support tree has no reticulations, and a network is tree-based when one exists.
  • Phylogenetic networks: The level of a network is the maximum reticulation count in any block, while the base level minimizes this value over all support networks.
  • Structure theorem: A zig-zag trail orders edges so consecutive edges share a head or a tail, and maximal trails cannot be extended.
  • Structure theorem: Maximal zig-zag trails are classified as crowns, M-fences, W-fences, or N-fences, and the unique decomposition is computable in Θ(|E(N)|) time.

3 Problems and known results

The paper studies LEVEL MINIMIZATION and its level-at-most-one variant for rooted almost-binary networks. Existing exhaustive algorithms are exponential, motivating specialized ILP methods.

  • LEVEL MINIMIZATION asks for the base level and a support network attaining it.
  • The partial problem asks whether a support network of level at most one exists and outputs one when it does.
  • Both problems are NP-hard, although tree-basedness, equivalent to base level zero, can be recognized in O(|E(N)|) time.
  • The known support-network characterization expresses the relevant family as a direct product over maximal zig-zag trails.
  • State-of-the-art exact and heuristic algorithms exhaustively search support-network families and therefore have exponential runtimes.

4 ILP formulations for finding support network of small level

The paper develops two ILP formulations for extracting low-level support networks: an exact method for level at most one and a heuristic method for general level minimization. The formulations encode structural characterizations as linear constraints, with experiments and examples supporting their intended use.

  • 4 ILP formulations for finding support network of small level: The formulations target support networks: spanning subgraphs with the same root and leaf-set as the input network.The variables select a support network and, where applicable, reticulation cycles within it.
  • 4 ILP formulations for finding support network of small level: The structural assumptions include excluding vertices with both in-degree and out-degree equal to two, without changing the base level.Such a vertex can be replaced by two vertices joined by a new edge.
  • 4.1 An exact ILP formulation for Problem 2: The exact formulation characterizes level-1 support networks through pairwise vertex-disjoint r-cycles, one for each reticulation.This condition is necessary and sufficient for a rooted almost-binary network without degree-four vertices to have level at most one.
  • 4.1 An exact ILP formulation for Problem 2: The exact ILP uses edge-selection and cycle variables, while vertex variables encode the possible in-degree and out-degree patterns in the selected cycle subgraph.The construction makes each connected component of the cycle subgraph an r-cycle and enforces the required support-network structure.
  • 4.1 An exact ILP formulation for Problem 2: The exact formulation is feasible if and only if the input has a support network of level at most one.Thus, a feasible solution directly yields a desired level-1 support network.
  • 4.2 A heuristic ILP formulation for Problem 1: The heuristic formulation minimizes overlaps among reticulation cycles because fewer shared edges are expected to produce support networks with smaller level.Its variables and constraints track each reticulation cycle separately rather than requiring all cycles to be disjoint.
  • 4.2 A heuristic ILP formulation for Problem 1: In the illustrated network, the level-3 support network has cycles sharing five edges, whereas the level-2 support network has cycles sharing two.The two-edge overlap is the minimum over the support networks and cycle choices described in the example.

5 Experimental Results

The experiments evaluated scalability, runtime, and accuracy of the two ILP formulations against prior exhaustive-search methods. Formulation 1 scaled to large synthetic networks, while Formulation 2 became faster for larger instances with only small accuracy losses.

  • 5.1 Experiment 1: scalability of Formulation 1: Formulation 1 solved networks with up to 800 reticulations in less than 26 seconds on average.Both YES and NO instances occurred at every tested reticulation count.
  • 5.1 Experiment 1: scalability of Formulation 1: Mean runtime grew approximately as |E(N)|^3.15 for YES instances and |E(N)|^2.98 for NO instances, with R^2 > 0.98 in both cases.These growth rates were observed on the tested randomly generated instance family.
  • 5.2 Experiment 2: performance of Formulation 2: For r up to around 20, Formulation 2 was slower than Algorithm 2, but around r = 35 it was more than ten times faster.Formulation 2 runtimes varied little among networks with the same number of reticulations, unlike the exhaustive search.
  • 5.2 Experiment 2: performance of Formulation 2: Formulation 2 attained the exact base level slightly less often than Algorithm 2, with the largest difference at r = 36: 13 exact inputs versus 21.The comparison uses deviation from the actual base level.
  • 5.2 Experiment 2: performance of Formulation 2: At r = 36, Formulation 2 returned a support network of minimum level for more than half the inputs, while inputs with ∆≥3 fell from four to two.The observed accuracy loss was confined to small deviations.

6 Case study: application to phylogenetic networks inferred from biological data

The case study applied the methods to two ancestral recombination graphs inferred from the same Drosophila melanogaster data. Their differing base levels were captured efficiently and suggest that base level can help compare inferred network complexity.

  • 6 Case study: application to phylogenetic networks inferred from biological data: The case study analyzed NKw and Nweaver, two ARGs inferred from 11 Drosophila melanogaster sequences at the Adh locus using KwARG and ARGweaver.Both graphs were converted to the tskit graph-ARG representation and treated as rooted binary phylogenetic networks.
  • 6 Case study: application to phylogenetic networks inferred from biological data: Formulation 1 returned a level-1 support network for NKw in 0.0042 seconds, about half the runtime of either algorithm of [14].For Nweaver, Formulation 1 only established that the base level exceeds one.
  • 6 Case study: application to phylogenetic networks inferred from biological data: For Nweaver, Formulation 2 returned a level-6 support network more than 1800 times faster than the exact algorithm and about 8 times faster than the heuristic of [14].The base levels of NKw and Nweaver were 1 and 6, respectively, and both heuristics attained these values.
  • 6 Case study: application to phylogenetic networks inferred from biological data: NKw and Nweaver contained 7 and 37 reticulations and had base levels 1 and 6, respectively, showing that base level captures differences in inferred network complexity.The authors suggest base level as an alternative complexity measure for inferred networks.
  • 6 Case study: application to phylogenetic networks inferred from biological data: Nweaver’s base level of six was close to the at-least-seven recombination events required to explain the Adh data under the infinite-sites model.The paper states that the two quantities cannot be identified because the methods use only ARG topology.

7 Conclusions

The paper uses integer linear programming to address LEVEL MINIMIZATION, combining an exact level-at-most-one formulation with a heuristic for the general case. Experiments support the formulations’ practicality, while the ARG application identifies scope limitations and shows that base level can capture differences in inferred-network complexity.

  • Contributions: The paper proposes an exact ILP formulation for support networks of level at most one and a heuristic ILP formulation for general LEVEL MINIMIZATION.Formulation 1 extracts pairwise vertex-disjoint reticulation cycles, while Formulation 2 relaxes this disjointness.
  • Computational findings: Experiments found polynomial runtime growth for Formulation 1 and faster, more stable performance for Formulation 2 on larger inputs, with a slight accuracy cost.The two experimental ranges for r were chosen by design rather than imposed by formulation limitations.
  • Application: The ARG application showed that base level captures differences in topological complexity between networks inferred from the same empirical data.The extracted support networks shown for Formulations 1 and 2 correspond to the networks NKw and Nweaver, respectively.
  • Open directions: Extending Formulation 1 beyond rooted almost-binary networks and designing a better objective for Formulation 2 remain open directions.An exact method for computing base level is also difficult to generalize, and interpreting ARG support networks as evolutionary histories requires incorporating inheritance intervals.
Loading 2608.28659v1…