Identifying Species Network Features from Gene Tree Quartets Under the Coalescent Model

Abstract

We show that many topological features of level-1 species networks are identifiable from the distribution of the gene tree quartets under the network multi-species coalescent model. In particular, every cycle of size at least 4 and every hybrid node in a cycle of size at least 5 are identifiable. This is a step toward justifying the inference of such networks which was recently implemented by Solís-Lemus and Ané. We show additionally how to compute quartet concordance factors for a network in terms of simpler networks, and explore some circumstances in which cycles of size 3 and hybrid nodes in 4-cycles can be detected.

Keywords: Coalescent theory; Concordance factors; Networks; Phylogenetics.

Fig. 1

(Left) A binary rooted phylogenetic network on X, with LSA(X) the node labeled x, and (Right) its induced unrooted semidirected network. In a depiction of a rooted network, all edges are directed downward, from the root, but arrowheads are shown only on hybrid edges. For the unrooted network, all edges except hybrid ones are undirected.

Fig. 2

A binary rooted phylogenetic network where the node labeled y is ancestral to all taxa in X but is not LSA(X). LSA(X) here is the root of the network.

Fig. 3

On the left are all the semidirected graphs, up to isomorphism, on a degree two node z and its adjacent vertices x and y. On the right are the corresponding graphs obtained by suppressing z.

Fig. 4

The top graph is not a topological unrooted semidirected phylogenetic network, since its directed edges cannot be obtained by suppressing the root of any 6-taxon topological binary rooted phylogenetic network. The middle graph is the induced topological unrooted network from either of the bottom rooted networks, as well as others.

>Fig. 5

In a level-1 network on X, the structure between the root and m =LSA(X) is a chain of two cycles. The number of two cycles in the chain could be zero.

Fig. 6

(Left) A level-1 unrooted network ${\mathcal{N}}^{-}$ and (Right) the tree of cycles of${\mathcal{N}}^{-}$.

Fig. 7

Two gene trees within a species network with one hybrid node.

Fig. 8

Cases 1–4 (Left-Right) of Example 1, of how lineages may behave under the NMSC model on the network of Figure 7.

Fig. 9

(Left) The three types of 2-cycles in an unrooted quartet network (2₁-,2₂- and a 2₃-cycle); (Center) The two types of 3-cycles in the unrooted quartet network (3₁- and a 3₂-cycle). (Right) The only type of 4-cycle in an unrooted quartet network (a 4₁-cycle). The dashed lines represent subgraphs that may contain other cycles.

Fig. 10

A graph with two 3₂ cycles. Each dashed edge represents a chain of 2-cycles with, possibly, other cycles.

Fig. 11

Possible structures for unrooted quartet networks. Every dashed arrow represents a chain of an arbitrary number of 2-cycles, as the one in the bottom of the Figure. The direction of these 2-cycles must be such that the obtained graph is induced from a rooted network.

Fig. 12

A level-1 rooted network where the root differs from the LSA(a,b,c,d).

Fig. 13

The two trees T_d and T_c in the proof of Lemma 9, obtained when K = 2, K_y = 2 and the lineages c and d trace different hybrid edges.

Fig. 14

A LSA quartet Q^⊕ with a cycle C that induces a 3₂-cycle in the unrooted quartet and the graphs obtained by deleting everything below the hybrid node, disjointing, and labeling the leaves.

Fig. 15

An unrooted quartet with a single 2₂-cycle.

Fig. 16

An unrooted quartet with a single 3₁-cycle.

Fig. 17

An unrooted quartet with a single 4₁-cycle.

Fig. 18

An unrooted quartet with a single 3₂-cycle.

Fig. 19

On the left a planar projection of the simplex ∆₂, where the black lines represent concordance factors that are treelike. In the center, the gray segments in ∆₂ represent all the concordance factors arising from unrooted quartet networks with a 3₂-cycle. On the right, the black lines represent the variety V ((x − z)(y − z)(x − y),x + y + z − 1), these are all concordance factors not satisfying the BC property of Definition 17

Fig. 20

The function f maps the cube χ_s (left) to ∆₂ (right). The blue facets (rear and top) of the cube are mapped by f to the blue (vertical) segment and the red facets (bottom and right) to the red (skewed) segment. The full cube is mapped onto the shaded triangle with all the concordance factor displayed by a network with a 4-cycle. The three line segments, two on the boundary of and one within the shaded triangle, are comprised of points not satisfying the BC property.

Fig. 21

Four unrooted metric level-1 quartet networks with the same concordance factors.

Fig. 22

Each section of the simplex is depicted with an unrooted quartet network topology whose image under the concordance factor map fills that region, independent of the placement of the hybrid node.

Fig. 23

A rooted metric phylogenetic network ${\mathcal{N}}^{+}$ (left) and the network structure $\tilde{\mathcal{N}}$ (right) that can be identified by Theorem 4. The 4-cycle on the network in the right, colored gray, has 3 different candidates for the hybrid node.

Fig. 24

A network $\tilde{\mathcal{N}}$ with a four cycle such that if {a,b,c,e} satisfies the Cycle property, the hybrid block can be detected.

Fig. 25

In gray we see the subgraph composed by P and P′, the dashed edges represent that P and P′ could intersect, the dotted segments represent just a succession of edges. In black we see the different cases of the possible edges in P^∗ above b but below a.

Fig. 26

The treks in case 1 (left), case 2 (center), and case 3 (right).

>Fig. 27

(Left) The treks in the two possibilities of case 4. (Right) The two possibilities of case 5, where the black segments represent possible edges red and blue at the same time.