AI Solves Evolutionary Puzzles with New Algorithm

Understanding how species evolve is a fundamental in biology, but traditional tree-like models often fall short when events like hybridization or horizontal gene transfer create more complex networks of relationships. A new computational approach, developed by researchers at Technische Universität Berlin and CNRS, addresses this by solving the Soft Tree Containment problem, which determines whether a phylogenetic network—a graph representing evolutionary connections—is compatible with a given phylogenetic tree while accounting for uncertainty in the data. This advancement is crucial because biological data often contains poorly supported branches that can lead to false negatives in analysis, hindering accurate reconstructions of evolutionary history. By allowing for "soft polytomies," where high-degree vertices represent unresolved relationships, provides a more robust framework for comparing trees and networks, which is essential for studies in fields like virology or ecology where reticulate events are common.

The key finding of the research is an algorithm that solves Soft Tree Containment in time exponential in a parameter combining the scanwidth of the network and the maximum out-degrees of the tree and network, but polynomial in the input size. Specifically, the algorithm runs in 2^O(∆T·k·log(k)) · n^O(1) time, where k := sw(Γ) + ∆N, with ∆T and ∆N denoting the maximum out-degrees in the tree and network, respectively, and sw(Γ) representing the scanwidth of a given tree extension of the network. This efficiency is achieved by leveraging the fact that phylogenetic networks in practice often exhibit low scanwidth, a measure of tree-likeness that respects the direction of arcs, making the problem more tractable. The researchers demonstrated that their approach can handle instances where classical s fail due to weakly supported branches, as illustrated in Figure 1 of the paper, which shows how contracting a low-support branch in a tree can make it compatible with a network that otherwise would not firmly display it.

Ology involves two main steps: first, reducing the problem to a special case where the network is binary, and second, using dynamic programming along a tree extension of the network. The researchers start by making the network binary through operations called "stretching" and "in-splitting," which replace high-out-degree vertices with gadgets that represent all possible binary resolutions, as depicted in Figure 3. This ensures that the network's structure captures the uncertainty in the data. Then, for binary networks, they employ a bottom-up dynamic programming algorithm that constructs valid signatures—combinations of top arcs from the tree and arcs from the network—to check for soft display. The algorithm, detailed in Algorithm 1, processes the tree extension Γ, with each step verifying conditions for embedding parts of the tree into the network while maintaining eventual arc-disjointness for paths from the same parent, as defined in the paper.

From the paper show that the algorithm correctly decides soft containment by validating signatures at each vertex of the tree extension, with Lemma 6 proving that the network softly displays the tree if and only if a specific signature exists at the child of the root. The dynamic programming approach efficiently manages the exponential dependence on parameters like scanwidth and out-degrees, with Lemma 2 bounding the number of valid signatures to at most (4·|B|)^(∆T·|B|) for a set B of arcs. In practice, this means that for networks with low scanwidth—common in empirical studies—the algorithm can solve large instances quickly, as highlighted in the discussion where real-world networks are noted to have scanwidth not much smaller than treewidth. The paper includes proofs in the appendix, such as Lemma 1, which establishes the equivalence between soft pseudo-embeddings and soft display, ensuring the algorithm's theoretical soundness.

Of this work are significant for evolutionary biology and computational phylogenetics. By providing a tool to handle uncertainty in phylogenetic data, researchers can more accurately analyze complex evolutionary scenarios, such as those involving hybridization in plants or horizontal gene transfer in bacteria, without being misled by artifacts from low-support branches. This could improve reconstruction s and distance estimations between evolutionary scenarios, as mentioned in the introduction. Moreover, the algorithm's parameterization by scanwidth opens avenues for future research into other containment problems or weaker parameters that might yield even better practical performance. The paper concludes by noting that future work could focus on eliminating the superpolynomial dependence on out-degrees or developing algorithms to construct low-scanwidth tree extensions more efficiently.

Limitations of the approach are discussed in the paper, primarily revolving around the assumptions and parameters required. The algorithm assumes a canonical tree extension Γ is given as part of the input, which might be problematic in practice if such extensions are hard to compute or approximate. Additionally, the running time depends exponentially on the maximum out-degrees of the tree and network (∆T and ∆N) and the scanwidth, meaning that for instances with high out-degrees or high scanwidth, the algorithm may become impractical. The paper also notes that the reduction to binary networks via stretching and in-splitting increases the scanwidth by at most 2·∆N, as shown in Lemma 9, which could affect performance for networks with many high-out-degree vertices. Future research is needed to address these constraints, possibly by exploring parameters like node-scanwidth or edge-treewidth for more efficient solutions.