New Algorithm Infers Species Network Trees of Blobs Under Coalescent Evolution

Elizabeth S. Allman, Hector Baños, Jonathan D. Mitchell, and John A. Rhodes have introduced TINNiK, a statistically consistent quartet-based algorithm designed to infer the tree of blobs of a species network under the Network Multispecies Coalescent model. Developed for complex evolutionary histories that cannot be modeled by bifurcating trees, TINNiK isolates the tree-like components of species relationships while contracting reticulate substructures—regions termed blobs where hybridization or lateral gene transfer take place—into single nodes. By shrinking each maximal connected subgraph lacking cut edges to a vertex, the algorithm reconstructs a reduced unrooted tree of blobs that clarifies species divergence patterns without imposing restrictive assumptions on network levels or reticulation counts. Implemented in the MSCquartets 2.0 R package with C++ routines via Rcpp, the software evaluates genome-scale gene tree collections in seconds on standard personal computers.

The growth of genome-scale sequencing has fundamentally reshaped phylogenetic research, prompting systematic biologists to account for gene tree discordance caused by incomplete lineage sorting. However, empirical studies demonstrate that strictly branching trees cannot accommodate complex evolutionary mechanisms involving horizontal gene transfer, introgression, and hybridization. When reticulation occurs among closely related taxa alongside incomplete lineage sorting, researchers rely on the Network Multispecies Coalescent model to describe how gene lineages sort backward through directed network graphs. Yet simultaneous Bayesian estimation of species networks and gene trees directly from molecular sequences remains computationally intractable for all but tiny datasets with few taxa and loci, while pseudolikelihood optimizations across entire network topological spaces remain severely constrained by prohibitive computational burdens.

To bypass the computational limits of full network searches, phylogenomic pipelines increasingly adopt data-summary methods that treat pre-computed gene trees as empirical data. Established summary programs, including SNaQ, PhyloNet, PhyNEST, and NANUQ, analyze distributions of rooted triples or unrooted quartets to estimate reticulate networks. Furthermore, networks deviating even slightly from level-1 structure often lack theoretical identifiability from low-dimensional summary statistics. Applying level-constrained tools to complex networks can therefore yield distorted topologies and misleading branch parameters, highlighting the urgent need for methods that do not impose arbitrary structural ceilings.

TINNiK overcomes these limitations by targeting the reduced unrooted tree of blobs rather than attempting to resolve every internal reticulation edge. In graph theory, a cut edge is one whose removal disconnects the graph into additional components, whereas a blob is a maximal connected subgraph containing no cut edges. While a strict tree of blobs contracts every blob into a vertex, degree-two nodes representing two-blobs cannot be detected from unrooted quartets; the authors therefore focus on the reduced unrooted tree of blobs, where degree-two vertices are suppressed. Multifurcations in this reconstructed tree represent complex reticulate regions whose internal cycles remain unspecified, behaving like soft polytomies in gene trees. Grounded in mathematical proofs of network identifiability under the coalescent model, TINNiK classifies sets of four taxa into tree-like quartets reflecting resolved tree splits and blob quartets whose taxa connect to a reticulate blob through four disjoint paths.

The statistical foundation of the algorithm rests on quartet concordance factors, which quantify the probabilities of observing the three possible resolved unrooted quartet topologies for any four taxa under the Network Multispecies Coalescent. Geometrically, these probabilities define a point within a two-dimensional simplex whose coordinates sum to one. A concordance factor is defined as cut when two coordinate entries are equal, and strictly cut when the third entry differs. The authors established that on four-taxon networks with generic parameters, the tree of blobs possesses a resolved tree topology if and only if its concordance factor is strictly cut, whereas an unresolved topology occurs if and only if the vector is non-cut. Because researchers must work from empirical quartet counts rather than exact theoretical distributions, TINNiK deploys hypothesis testing to classify quartets, implementing a likelihood ratio cut test or an alternative T3 test designed to handle boundary geometries.

The computational execution of TINNiK begins by tabulating quartet count concordance factors across m input gene trees for N taxa in O(m N^4) time. To avoid slow linear scans, quartet rows are stored in lexicographical order, allowing immediate O(1) index computation using an exact binomial coefficient formula pre-computed in O(N) time. The algorithm then applies a two-degree-of-freedom chi-squared star tree test at significance level beta to identify quartets consistent with the simplex centroid, designating unresolved quartets as initial blob quartets. Remaining quartets are evaluated with the cut or T3 test at level alpha to detect non-cut concordance factors, while maximum likelihood assigns topologies to resolved tree quartets. Once these initial assignments are complete, TINNiK iteratively applies a combinatorial B-quartet inference rule. This rule deduces additional blob quartets across overlapping taxon subsets sharing three taxa, exhaustively identifying all network blob quartets in O(N^5) total time.

With all blob and tree quartets categorized, TINNiK translates quartet data into an intertaxon distance matrix using an established quartet distance formulation. In the absence of error, this distance matrix exactly matches the true reduced tree of blobs, allowing distance-based algorithms such as Neighbor-Joining or FastME to infer the tree in O(N^3) time. To eliminate noise-induced micro-branches, internal edge lengths below a user-selected threshold delta are collapsed to zero. In Theorem 4, the authors demonstrated that TINNiK is an asymptotically statistically consistent estimator under the Network Multispecies Coalescent for generic network parameters. Specifically, as the number of gene trees m approaches infinity, there exists a sequence of significance levels converging to zero ensuring that the probability of recovering the true reduced unrooted tree of blobs approaches one, with branch length cutoffs between zero and two leaving true internal branches unaffected.

To validate algorithmic performance, the authors conducted simulation benchmarks across synthetic gene tree datasets generated under the Network Multispecies Coalescent. A primary experiment evaluated a 23-taxon network containing seven hybrid nodes, non-binary vertices, non-tree-child structures, and three distinct multi-reticulation blobs. The researchers tested gene tree sample sizes of 300, 500, 1000, and 10,000 across scaling factors representing low, moderate, and high incomplete lineage sorting. For sample sizes of at least 500 gene trees under low or moderate incomplete lineage sorting, TINNiK recovered the true tree of blobs across significance parameter intervals spanning up to eleven orders of magnitude. The results confirmed that small samples and severe incomplete lineage sorting obscure hybridization signals, demonstrating that empiricists require adequately sampled gene collections for accurate reticulation detection.

The simulations also clarified how statistical thresholds interact with network geometry and incomplete lineage sorting. Short internal branches pull concordance factors toward the simplex centroid, where hybridization signals resemble an absence of phylogenetic resolution. By adjusting the star tree significance level beta, users can flag centroid-adjacent quartets as blob quartets, preventing artificial over-resolution and recovering the true tree of blobs under conditions where tests without star tree filtering failed. Furthermore, comparative simulations contrasting a level-1 seven-cycle network with an equivalent level-3 network containing crossing hybrid edges demonstrated that increasing reticulation complexity concentrates concordance factors toward the simplex centroid. Because empirical gene tree estimation errors exert a similar central pull on quartet distributions, the authors emphasized that extreme reticulation complexity creates intrinsic practical limits on how deeply internal blob substructures can be disentangled from biological sequence data.

To illustrate the consequences of applying level-restricted methods to complex networks, the authors analyzed simulated data from a level-2 network whose true tree of blobs is a single star tree, comparing TINNiK with the level-1 inference program SNaQ. When constrained to one or two hybridizations, SNaQ returned optimal level-1 networks that conflicted sharply with the true history, failing to find the star tree of blobs while inferring distorted branch lengths and misleading hybrid relationships. In contrast, TINNiK accurately reconstructed the true star tree of blobs across significance thresholds spanning over one hundred orders of magnitude. Because both programs operated on identical quartet concordance factors, this contrast showed that TINNiK avoids restrictive structural assumptions, providing an objective diagnostic tool that can reveal whether the assumptions of level-constrained network models are violated in empirical studies.

Across 569 gene trees from Hawaiian Cyrtandra, TINNiK’s inferred tree of blobs for the seven-species Kauai group matched previously published networks regardless of how unresolved quartets were handled, while its analysis of the eight-species Oahu group revealed structural conflicts with level-1 networks, indicating that reported hybridizations require cautious reexamination. In a dataset of 1,730 primate gene trees, TINNiK clarified unresolved relationships among New World monkeys by demonstrating that centroid-clustered quartets support a degree-four multifurcation rather than forced bifurcations.

Subject of Research: Inference of the tree of blobs of a species network under the coalescent model

Article Title: TINNiK: inference of the tree of blobs of a species network under the coalescent model

Article References: Allman, E. S., Baños, H., Mitchell, J. D., & Rhodes, J. A. (2024). TINNiK: inference of the tree of blobs of a species network under the coalescent model. Algorithms for Molecular Biology, 19(1), Article 23. https://doi.org/10.1186/s13015-024-00266-2

Image Credits: AI Generated

DOI: 10.1186/s13015-024-00266-2

Keywords: TINNiK algorithm, tree of blobs, species networks, network multispecies coalescent, incomplete lineage sorting, MSCquartets, quartet concordance factors, B-quartet inference rule, reticulate evolution, hybridization, statistical consistency, cut model test, T3 hypothesis test, intertaxon distance, star tree test, Hawaiian Cyrtandra, primate phylogenomics