Tree-average distances on certain phylogenetic networks have their weights uniquely determined

Abstract

A phylogenetic network N has vertices corresponding to species and arcs corresponding to direct genetic inheritance from the species at the tail to the species at the head. Measurements of DNA are often made on species in the leaf set, and one seeks to infer properties of the network, possibly including the graph itself. In the case of phylogenetic trees, distances between extant species are frequently used to infer the phylogenetic trees by methods such as neighbor-joining. This paper proposes a tree-average distance for networks more general than trees. The notion requires a weight on each arc measuring the genetic change along the arc. For each displayed tree the distance between two leaves is the sum of the weights along the path joining them. At a hybrid vertex, each character is inherited from one of its parents. We will assume that for each hybrid there is a probability that the inheritance of a character is from a specified parent. Assume that the inheritance events at different hybrids are independent. Then for each displayed tree there will be a probability that the inheritance of a given character follows the tree; this probability may be interpreted as the probability of the tree. The tree-average distance between the leaves is defined to be the expected value of their distance in the displayed trees. For a class of rooted networks that includes rooted trees, it is shown that the weights and the probabilities at each hybrid vertex can be calculated given the network and the tree-average distances between the leaves. Hence these weights and probabilities are uniquely determined. The hypotheses on the networks include that hybrid vertices have indegree exactly 2 and that vertices that are not leaves have a tree-child.

Keywords: digraph; distance; hybrid; metric; network; normal network; phylogeny; tree-child.

Figure 1

A network N with root 1, and the two trees N_p and N_p' that it displays. If N is equiprobable, then 7 inherits approximately half its characters from 6 and the other characters from 8.

Figure 2

A minimal configuration needed to be able to find the probability α₁ = α(q₁, h₀) = 1 - α₂ that a character state in h₀ is inherited from q₁.

Figure 3

This tree-child network has X = {1, 2, 3, 4}. There are 7 arcs not leading to a hybrid vertex but only 6 distances, and the weights are not uniquely determined. The network is not normal because arc (5, 10) is redundant.

Figure 4

A normal phylogenetic X-network with X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} and root 1. The root corresponds to an outgroup species. Measurements on DNA are assumed possible on members of X.

Figure 5

The situation of Lemma 4.2 (a), the situation of Lemmas 4.4 and 4.7 (b). If p is a parent map with p(a) = q₁, the figure shows part of N_p together with the arc (q₂, a).

Figure 6

Case A₁B₃.

Figure 7

Case A₂B₃(a), Case A₃B₃(b).