📄 evolutionary biology

SNaQ.jl: Improved Scalability for Phylogenetic Network Inference

This paper introduces SNaQ.jl, a new Julia package that significantly enhances the scalability and computational efficiency of phylogenetic network inference through parallelization, weighted random quartet selection, and probabilistic decision-making, achieving up to a 499% reduction in runtime without compromising accuracy.

Original authors: Kolbow, N., Kong, S., Chafin, T., Justison, J., Ane, C., Solis-Lemus, C.

Published 2026-04-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kolbow, N., Kong, S., Chafin, T., Justison, J., Ane, C., Solis-Lemus, C.

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ⚕️ This is an AI-generated explanation of a preprint that has not been peer-reviewed. It is not medical advice. Do not make health decisions based on this content. Read full disclaimer

Imagine you are trying to draw a family tree for a group of animals. Usually, these trees look like simple branches splitting apart, like a river delta. But in nature, life is messier. Sometimes, two distinct branches merge back together (like two rivers joining), or genes jump sideways from one species to another. This creates a "web" or a "net" of relationships rather than a simple tree.

Scientists call these phylogenetic networks. Figuring out the exact shape of this web is incredibly hard because there are billions of possible ways the branches could connect. It's like trying to find the perfect route through a maze that keeps changing its walls.

For a long time, the software used to solve this puzzle (called SNaQ) was accurate but painfully slow. It was like trying to solve a massive jigsaw puzzle by looking at every single piece one by one, under a single dim lightbulb. If you had a huge puzzle (many species), you might have to wait days or weeks for an answer.

This paper introduces SNaQ.jl version 1.1, a major upgrade that makes this process lightning-fast without losing accuracy. Here is how they did it, using some everyday analogies:

1. The "Assembly Line" Upgrade (Parallelization)

The Old Way: Imagine a single worker trying to sort a mountain of mail. They have to open every envelope, read the address, and sort it. Even if they work super fast, they can only do one thing at a time.
The New Way: SNaQ.jl v1.1 hires a whole team of workers. Instead of one person sorting the mail, they split the mountain into piles and give each worker a stack. They all sort their piles at the exact same time.

The Result: The job gets done in a fraction of the time. The paper shows that by using multiple computer processors at once, the software runs up to 5 times faster (and sometimes even more) than before.

2. The "Spot Check" Strategy (Weighted Quartet Sampling)

The Old Way: To figure out the family tree, the software used to look at every single possible group of four animals in the dataset. If you have 100 animals, the number of groups of four is huge (over 3 million!). It's like a detective trying to interview every single person in a city to solve a crime. It's thorough, but it takes forever.
The New Way: The new version uses a "smart sampling" trick. Instead of interviewing everyone, it picks a smaller, random sample of groups to interview.

The Twist: It doesn't just pick randomly; it uses a "weighted" approach. If a group of animals looks confusing or contradictory (like a witness with a shaky story), the software pays extra attention to them. If a group looks very clear, it glances at them quickly.
The Result: You can get 99% of the answer by looking at only 50% of the data. The paper found that by looking at just half the groups, the software ran 8 times faster with almost no loss in accuracy.

3. The "Smart Navigator" (Probabilistic Decision Making)

The Old Way: When the software tried to improve the shape of the web, it would randomly pick a branch to move, hoping for the best. It was like a hiker wandering through a forest, tripping over random bushes and hoping they eventually find the summit.
The New Way: The new version is a bit more strategic. It looks at which parts of the web are "stuck" or don't fit the data well, and it focuses its energy on moving those specific parts.

The Result: It's like the hiker now has a GPS that tells them, "Hey, that path looks rocky; try the one to the left." While this specific feature didn't speed things up as much as the other two in this study, it makes the search smarter.

The Big Picture

The authors tested this new software on both fake data (simulations) and real data (fish from the Xiphophorus genus).

Speed: In one real-world example, a task that took the old software 208 hours (almost 9 days) was finished by the new software in just 16.5 hours. That's a massive time-saver!
Accuracy: Despite being so much faster, the new software didn't make mistakes. The family trees it drew were just as accurate as the slow, old version.

Why Should You Care?

Think of this as upgrading from a bicycle to a high-speed train. Scientists can now tackle much bigger and more complex biological puzzles. Instead of waiting weeks to understand how species evolved, they can get answers in hours. This allows researchers to study larger groups of animals, understand how diseases spread, or figure out how crops evolved, all without needing a supercomputer the size of a building.

In short: SNaQ.jl v1.1 is the same smart detective, but now it has a team of assistants, a better map, and a faster car.

1. Problem Statement

Phylogenetic networks are essential for modeling complex evolutionary scenarios such as hybridization, introgression, and horizontal gene transfer, which standard phylogenetic trees cannot capture. However, inferring these networks is computationally prohibitive for large datasets.

Full Likelihood Limitations: Existing methods using full likelihood (e.g., PhyloNet, Bayesian approaches) are limited to datasets with roughly a dozen taxa due to the high computational complexity of the equations.
Composite Likelihood Bottlenecks: Methods using composite (pseudo-) likelihood, such as SNaQ (Species Networks applying Quartets), decompose the problem into smaller 4-taxon units (quartets) to improve speed. While faster, the original implementation (v1.0 within PhyloNetworks.jl) still struggled with scalability, typically capping out around 30 taxa. This is insufficient for modern genomic datasets involving hundreds of taxa.
The Gap: There is a need for a scalable implementation of composite likelihood network inference that can handle datasets routinely analyzed by tree-based methods without sacrificing accuracy.

2. Methodology

The authors introduce SNaQ.jl v1.1, a standalone Julia package that refactors the original SNaQ algorithm to improve computational efficiency through three primary technical innovations:

A. Parallelization of Quartet Calculations

v1.0: Only parallelized independent runs across different processors. Within a single run, calculations were sequential.
v1.1: Implements multi-threading within individual runs. It parallelizes the computation of the composite likelihood function and all quartet-related operations across multiple threads, significantly reducing the time spent on the most computationally intensive part of the algorithm.

B. Weighted Random Quartet Selection (`propQuartets`)

The Issue: The number of possible 4-taxon subsets scales quartically ( $O(n^4)$ ) with the number of taxa ( $n$ ). Using all subsets is the primary bottleneck.
The Solution: Introduced the propQuartets argument (range 0, 1].
- Instead of using all $k = \binom{n}{4}$ quartets, the algorithm randomly samples a proportion of them at the start of each run.
- Determinism: Sampling is controlled by a seed, ensuring reproducibility.
- Final Optimization: Once the network topology is found using the subset, a final numerical optimization is performed using all $k$ quartets to ensure the final log-likelihood score is accurate.

C. Probabilistic Topological Moves (`probQR`)

The Issue: The original hill-climbing algorithm randomly selected reticulation edges to modify (e.g., moving the origin of a hybridization event). This was often inefficient as it did not prioritize edges that poorly fit the data.
The Solution: Introduced the probQR argument.
- When enabled, the algorithm calculates a weight $W$ for each quartet based on the absolute difference between observed concordance factors ( $X_{qi}$ ) and expected factors ( $CF_{qi}$ ): $W = \sum |X_{qi} - CF_{qi}|$ .
- Quartets with high weights (poor fit) are sampled more frequently to guide topological moves, aiming to resolve the specific areas of the network causing the most error.

3. Key Contributions

Software Release: The release of SNaQ.jl v1.1, a high-performance, standalone Julia package for inferring level-1, identifiable, semi-directed phylogenetic networks under the multispecies network coalescent model.
Algorithmic Efficiency: Demonstration that parallelizing quartet calculations and subsampling quartets can drastically reduce runtime without altering the underlying statistical model.
New Parameters: Introduction of propQuartets and probQR to give users control over the trade-off between speed and search thoroughness.

4. Results

Simulation Study

Accuracy: There was no significant difference in accuracy (measured by Hardwired Cluster Distance, HWCD) between v1.0 and v1.1 when identical parameters were used. Reducing propQuartets to 0.5 also maintained accuracy.
Runtime Performance:
- Parallelization: With 16 processors, v1.1 showed massive speedups. For a network with 20 taxa and 3 reticulations, v1.1 was 499% faster on average than v1.0.
- Subsampling: Reducing propQuartets to 0.5 yielded even greater gains, with speedups reaching 757% (approx. 8x faster) compared to v1.0.
- Scalability: The runtime improvements were linear with respect to the number of threads, indicating efficient multi-threading implementation.
Parameter probQR: Surprisingly, enabling weighted sampling (probQR > 0) did not improve runtime or accuracy in these simulations, suggesting the random selection was sufficient for the tested topologies.

Empirical Data Analysis (Xiphophorus Fish)

Dataset: 24 species (swordtails and platyfishes) with 1,183 gene trees.
Runtime: Analyzing networks with 0 to 5 reticulations took 54 hours total with v1.1, compared to 346.2 hours with v1.0 (a 641% improvement). The worst-case scenario (5 reticulations) dropped from 208.8 hours to 16.5 hours.
Topology & Model Selection:
- The inferred topologies were largely identical between versions.
- Model Selection Shift: Due to the improved likelihood optimization in v1.1, the "best-fitting" network (selected via slope heuristics) changed from $h=2$ (in the original 2016 study) to $h=1$ .
- Subsampling Robustness: Using propQuartets = 0.1 (only 10% of quartets) produced networks with topologies and likelihood scores nearly identical to using 100% of the data, confirming that massive subsampling is viable for empirical data.

5. Significance

Bridging the Scalability Gap: SNaQ.jl v1.1 allows researchers to infer phylogenetic networks for datasets with 20–30+ taxa, a scale previously only accessible via tree inference methods.
Practical Utility: The ability to reduce runtime by factors of 5x to 8x makes network inference feasible for large-scale genomic studies that were previously computationally intractable.
Methodological Insight: The study demonstrates that composite likelihood methods are robust to significant data subsampling (propQuartets), suggesting that the "curse of dimensionality" in quartet space can be mitigated without losing biological signal.
Future Directions: While v1.1 improves efficiency, the authors note that for massively large networks (hundreds of taxa), other methods like InPhyNet or Neighbor-Net may still be required, but SNaQ.jl v1.1 sets a new standard for intermediate-scale network inference.

Conclusion: SNaQ.jl v1.1 represents a major leap forward in phylogenetic network inference, offering a highly scalable, accurate, and user-friendly tool that leverages modern parallel computing and smart sampling strategies to overcome previous computational barriers.