NANUQ+: A divide-and-conquer approach to network estimation

Abstract

Inference of a species network from genomic data remains a difficult problem, with recent progress mostly limited to the level-1 case. However, inference of the Tree of Blobs of a network, showing only the network's cut edges, can be performed for any network by TINNiK, suggesting a divide-and-conquer approach to network inference where the tree's multifurcations are individually resolved to give more detailed structure. Here we develop a method, ${\text{NANUQ}}^{+}$ , to quickly perform such a level-1 resolution. Viewed as part of the NANUQ pipeline for fast level-1 inference, this gives tools for both understanding when the level-1 assumption is likely to be met and for exploring all highly-supported resolutions to cycles.

Keywords: Level-1; Multispecies coalescent; Phylogenetic network; Tree of blobs.

Fig. 1

A topological rooted binary phylogenetic network $N^{+}$ (left) and its induced topological unrooted phylogenetic network $N^{-}$ (right). In $N^{+}$ only hybrid edges are highlighted as directed, but all other edges are implicitly assumed to be directed away from the root. In $N^{-}$ all non-hybrid edges are undirected

Fig. 2

The five quartet networks induced from the topological unrooted phylogenetic network $N^{-}$ of Fig. 1

Fig. 3

An unrooted 7-sunlet on $X=\{x_1,\dots ,x_7\}$ with hybrid taxon $x_1$ and taxa ordered counter-clockwise around the cycle

Fig. 4

A network $N^{-}$ containing eight trivial and two non-trivial blobs (all shaded in gray) (top) and its tree of blobs T(N) (bottom). Note that T(N) contains two nodes of degree four arising from $N^{-}$’s 4-blobs

Fig. 5

An unrooted binary topological level-1 network $N^{-}$ on $X=\{x_1,\dots ,x_{10}\}$ containing two non-trivial cycle blobs (left) and the generalized sunlet network $N_C^{-}$ induced by the 5-cycle C in $N^{-}$ (right). Here, $X_1=\{x_1,x_2\}$, $X_2=\{x_4\}$, $X_3=\{x_5\}$, $X_4=\{x_6,x_7\dots ,x_{10}\}$, and $X_5=\{x_3\}$

Algorithm 1

ResolveCycle

Algorithm 2

HeuristicResolveCycle, $m>4$

Algorithm 3

CombineCycles

Fig. 6

A rooted level-1 network $N^{+}$ (left), and the tree of blobs T(N) obtained from the unrooted network $N^{-}$ (right). Note that T(N) has four multifurcations, labeled $b_1,b_2,b_3$, and $b_4$, corresponding to the 4 cycles of $N^{+}$

Fig. 7

NANUQ splits graph and TINNiK tree of blobs for $k=1.0$, $s=10000$ gene trees, using $\alpha ={10}^{-6}$ and $\beta =0.05$. Notice that the NANUQ splits graph suggests a level-1 structure since the four blob structures are ‘darts,’ and the TINNiK tree of blobs matches the true tree of blobs depicted in Fig. 6

Fig. 8

Resolutions of the four multifurcations of the tree of blobs in T(N) in Fig. 6 combined into a level-1 network for $s=10000$ gene trees and $k=1.0$ for $\alpha ={10}^{-6}$ and $\beta =0.05$ when using the true tree of blobs and the NANUQ distance. Internal node labels #Hi and THi indicate hybrid nodes and the tail of one hybrid edge, respectively

Fig. 9

Resolutions of the four multifurcations in the true tree of blobs in T(N) in Fig. 6 for $s=10000$ gene trees and $k=1.0$ and with test levels $\alpha ={10}^{-26}$ and $\beta =0.05$, using the NANUQ distance. There is a 2-way tie for the best resolution of $b_1$, with the alternatives shown in the top row. The unique resolutions for the three other high-degree multifurcations in T(N) are shown in row 2. Since resolving node 18 required creation of a 4-cycle, the hybrid node was placed at random (row 2, column 1). Internal node labels #Hi and THi indicate hybrid nodes and the tail of one hybrid edge

Fig. 10

Simplex plot (left) and splits graph (center) produced by NANUQ for Leopardus data, with tests levels $\alpha =5·{10}^{-29}$, $\beta =0.95$. TINNiK tree of blobs (right) for the same data and test levels. Red triangles in the simplex plot indicate empirical quartet concordance factors judged as involving hybridization. In the splits graph, the blue blob b1 is a dart, consistent with the level-1 assumption underlying NANUQ, but the gold blob b2 is not. TINNiK makes no assumptions about underlying blob complexity

Fig. 11

Residual-sums-of-squares for all 60 possible resolutions of nodes b1 (left) and b2 (right). For b1 there is a single optimal resolution, while for b2 there are five tied optimal resolutions

Fig. 12

The five ${\text{NANUQ}}^{+}$ level-1 networks obtained by resolving two degree-5 multifurcations in the TINNiK tree of blobs. The hybridization cycle resolving node b1 on the tree of blobs is consistent with a level-1 hypothesis and is present in all five optimal ${\text{NANUQ}}^{+}$ networks. For node b2 there are five optimal cycle resolutions in the ${\text{NANUQ}}^{+}$ framework, with the hybrid node placed at each of the articulation nodes of the cycle. Log-quartet-pseudolikelihood scores for each network are shown, with the optimal network reported in [11] at top, left