A Phylogenetic Trees Analysis of SARS-CoV-2

We first introduce some basic notions of phylogenetics that are common knowledge in Biology. A phylogenetic tree is a directed tree (directed simply connected graph), having a distinguished vertex, that is an ancestor of all other vertices, called root; all vertices that have no descendants are called leaves of the phylogenetic tree. In a phylogenetic tree, each edge is called a branch. Each vertex where the two branches meet is called a branching point, or node. A node is the most recent common ancestor of all species on the other vertices of those branches.

Deoxyribonucleic acid (DNA) sequences can be used to draw a phylogenetic tree. A nucleotide consists of a sugar molecule (either ribose in ribonucleic acid (RNA) or DNA attached to a phosphate group and a nitrogen-containing base. The bases used in DNA are purines adenine (A) and guanine (G), pyrimidine cytosine (C) and pyrimidine thymine (T). In RNA, the base pyrimidine uracil (U) takes the place of T. To construct a tree, we will compare the RNA or DNA sequences of different species or individuals. Related individuals have a common ancestor. Before species split into separate descendants, they had the same RNA (or DNA). But as species evolve and diverge, they will accumulate changes in the DNA sequences. We can use these changes in the DNA to tell how closely related two individuals are. If there are not very many differences, they are probably closely related; if there are many changes, they might be distant relatives.
The DNA sequences are double-stranded and are made of letters A, G, C, and T, and RNA sequences are similar to those of the DNA and made of letters A, G, C, and U. Chromosomes are thread-like structures located inside the nucleus of animal and plant cells. Each chromosome is made of protein and a single molecule of DNA. Passed from parents to offspring, DNA contains the specific instructions that make each type of living creature unique. A gene is an ordered sequence of nucleotides located in a particular position on a particular chromosome that encodes a specific functional product (i.e., a protein or RNA molecule). Biologists commonly use one homogeneous sequence, which in the biologist’s language concerns the relationship between gene trees and genes that are made from one tree. The gene sequence might be about 200 base pairs long. One of the problems that has occurred in the last fifty years is that biologists believe that the way evolution works is that there would only be one species tree. Different genes have different histories, so you get different gene trees. Putting them together is a statistical problem that helps study of the evolutionary process.

A phylogenetic tree with $p$ leaves is an equivalence class based on a certain equivalence of a DNA-based connected directed graph of species with no loops, having an unobserved root (common ancestor) and $p$ observed leaves (currently observed species of a certain family of living creatures). The paper is organized as follows; in the first section one introduces tree spaces of trees with $m$ leafs, which are regarded as stratified spaces of dimension $m-2$. In particular the detailed description is fiven for the spaces $T_{3}$ and $T_{4}$. It is shown that $T_{3}$ is a 3-spider, and $T_{4}$ can be described in terms of the so called Petersen graph. Section three is dedicated to a proof of the central limit theorem for intrinsic means of spiders. An elementary proof of the stickiness theorem (see Hotz et al (2013)[9] is given here. The fourth section is dedicated to the CLT for intrinsic means on $T_{4}$ (see Bardem et al.(2013)[1]). Here the key result is the partial stickiness of the intrinsic means, that stick to the 1D stratum of the tree space. The last part of the paper is applied, classifying SARS-CoV-2 data, according to stickiness of their intrinsic sample means.

Our stratified data analysis requires certain basic concepts, that are fairly recent in Statistics (see eg Patrangenaru and Ellingson (2015)[10], p.475, and references there in).

An elementary example of a 2 dimensional stratified space is a cone $\mathcal{C},$ set of solutions in $\mathbb{R}^{3}$ of the equation $x^{2}+y^{2}-z^{2}=0;$ In this case $F_{0}=\{(0,0,0)\},F_{2}=\mathcal{C},F_{i}\setminus F_{i-1}=,\forall i\notin{0,2}.$

A tree with $p$ leaves is a connected, simply connected graph , with a distinguished vertex, labeled $o$, called the root, and $p$ vertices of degree 1, called leaves, that are labeled from 1 to $p$. In addition, we assume that with all interior edges have positive lengths. (An edge of a p-tree is called interior if it is not connected to a leaf.)

Now consider a tree $T$, with interior edges $e_{1},...,e_{r}$ of lengths $l_{1},...,l_{r}$, respectively. If $T$ is binary, then $r=p-2$, otherwise $r<p-2$. The vector${(l_{1},...,l_{r})}^{T}$ specifies a point in the positive open orthant ${(0,\infty)}^{r}$.

An $p$-tree has the maximal possible number of interior edges $p-2$ and thus determines the largest possible dimensional orthant, when it is a binary tree; in this case the orthant is $p-2$ dimensional. The open orthants form the highest dimensional stratum $F_{p-2}\setminus F_{p-3}$ of $T_{p},$ regarded as a $p-2$ dimensional stratified space. The orthant corresponding to each tree which is not binary appears as a boundary face of the orthants corresponding to at least three binary trees; in particular the origin of each orthant corresponds to the (unique) tree with no interior edges. We construct the space $T_{p}$ by taking one $p-2$ dimensional orthant for each of the $(2p-3)!!$ possible binary trees, and gluing them together along their common faces. Due to such gluing operations, tree spaces are not manifolds. Singularities (points where the space does not have a tangent space of the same dimension as the space itself) are present in the tree space structure. For further details on the construction of the tree space $T_{p}$, see Billera et al.(2001)[6];

In this paper, we are considering phylogenetic trees with 3 or 4 leafs. The space of trees with 3 leafs is $T_{3}$ can be identified with $S_{3}$, a $3$-spider, which is the union of three line segments with a common end (see left hand side of Figure 1).

$T_{4}$ as a stratified space has $15=(2\times 4-3)!!$ 2D quadrants glued according to tree identification rules (see Billera et. al.(2001)[6]). Interior points of these quadrants are combinatorial binary trees with four leaves, the coordinates of an interior point being given by the two interior edges of a binary tree in one of these combinatorial binary trees. Points on the boundaries of the quadrants, are on the one dimensional stratum, and correspond to combinatorial trees with four leaves, which are obtained from a combinatorial binary tree by shrinking one of the interior edges to zero length (see right hand side of Figure 1). The zero dimensional stratum is made of one point only, the star tree.

Therefore a representation of $T_{4}$ as a surface with singularities can be obtained from the polyhedral surface obtained by the identifications of three semi-axes labeled with the same letter as shown in Figure 2. While this is a 3D pictorial representation only, in general $T_{m}$ can be embedded in $\mathbb{R}{{}^{k}}$, $k=2^{m}-m-2$ ( see Ellingson et al(2014) [7]), so, in fact, given that the number of edges that form the one dimensional stratum of $T_{4}$ is $2^{4}-4-2=10,$ this stratified space is embedded in $\mathbb{R}^{10}$ having the star tree at the origin. In this representation, the intersection of a sphere in $\mathbb{R}^{10}$ centered at the origin with $T_{4}$ is the so called Petersen graph. The embedded surface can be thus regarded as a one sheet cone over the Petersen graph. An edge of the Petersen graph is the transverse intersection of one quadrant with the sphere; thus there are $15$ edges; a vertex of this graph is a point where one of the coordinate semi-axes pierces the sphere; therefore there are $10$ vertices ( see figure 3).

The intrinsic mean on $T_{m},$ with the piecewise Euclidean metric is unique, since $T_{m}$ with this metric is a CAT(0) space. A CLT for the intrinsic sample mean on a tree space $T_{m}$, for $m$ fixed, is however still ongoing research. The most recent results, to our knowledge, are due to Shen (2021)[23], Barden et al.(2018)[3], and Barden and Le(2018)[2] are are concerned only with the case when the intrinsic mean lies on the first and second highest dimensional strata of $T_{m}.$ In this section we are concerned with the case $m=3,$ when it is known that $T_{3}=S_{3}.$ Therefore we study at no additional effort, that case of the CLT for the intrinsic sample mean on a spider $S_{p}.$ Assume $X_{i},i=1,\dots,n$ are i.i.d. random objects on a spider $S_{p},$ having legs $L_{a},a=1,\dots p,$ and center $C.$ Further, assume the intrinsic mean $\mu_{X_{1},I}$ exists and the intrinsic variance is finite. Any probability measure $Q$ on $S_{p}$ decomposes uniquely as a weighted sum of probability measures $Q_{k}$ on the legs $L_{k}$ and an atom $Q_{0}$ at $C$ (Hotz et. al.(2013)[9]). More precisely, there are nonnegative real numbers $\{w_{k}\}_{k=0}^{p}$ summing to $1$ such that, for any Borel set $A\subseteq S_{p}$, the measure $Q$ takes the value

We will consider the nontrivial case when the moments $\nu_{a}=E(Q_{a}),a=1,\dots,p$ are all positive.

For a proof, recall that if $x\in L_{a}$, the Fréchet function $F$ is defined as follows,

where $v_{i}=\int_{0}^{\infty}uw_{i}Q_{i}(du)=w_{i}\nu_{i}.$

Since there exists an unique minimizer for the Fréchet function $F$ in (2), this minimizer is intrinsic mean $\mu_{I}$. The minimizer of this quadratic function is $x^{*}=v_{a}-\sum_{i\neq a}v_{i}$, where $x\in L_{a}=\{(a,u):u\in[0,\infty)\}$. Thus, we have three situations:(i)$v_{a}-\sum_{i\neq a}v_{i}>0$ or $v_{a}>\sum_{i\neq a}v_{i}$, (ii)$v_{a}-\sum_{i\neq a}v_{i}=0$ or $v_{a}=\sum_{i\neq a}v_{i}$ and iii $v_{a}-\sum_{i\neq a}v_{i}<0$ or $v_{a}<\sum_{i\neq a}v_{i}$. In case(i), we have $\mu_{I}$ well defined on $L_{a}$, then classical C.L.T is applied. In case (ii), we can fold other legs into that half line opposite to $L_{a}$ then apply C.L.T. and since the negative part is undefined, so the result goes to a positive truncated normal distribution. In case (iii), for any $a\in\{1,\dots,K\}$, we have $\mu_{I}=C$, which shows that intrinsic mean $\mu_{I}$ sticks to the center $C$;

However, Basrak’s condition for trees can be extended to the case of graphs in some general cases even if the graph $G$ has cycles with positive mass on any arc of a cycle. Given a graph $G,$ for each $x\in G$ and leg $L_{a}$, $d(x,\xi)$ is either increasing or decreasing for $\xi\in L_{a}$. We define $\varepsilon_{a}(x)=+1$ if increasing and $\varepsilon_{a}(x)=-1$ if decreasing. Then $\mu_{I}$ is sticky if for all legs $L_{a}$

This is easily identified as a condition that implies that $\mu_{I}$ is a local minimum of the Fréchet function. The quantity $m_{a}=E(d(X,\mu_{I})\varepsilon_{a}(X))$ is called the net moment in the direction of $L_{a}$.
As an aside, one can consider for any $\xi\in G$ its star neigborhood $S_{\xi}$ and the “derivative” in the direction of leg $L_{a}$ of $S_{\xi},$ given by

Returning to the Fréchet mean $\mu_{I}$, it follows that for large $n$ and samples $X_{1},\ldots,X_{n}$ and leg $L_{a},$ then

Therefore, as in Theorem2(iii), with high probability $\mu_{I}$ is a local minimum for the Fréchet function corresponding to the sample. One should show that with high probability $\mu_{I}$ is a point of absolute minimum for the Fréchet function corresponding to the empirical.

The space $T_{4}$ consists of fifteen 2-dimensional faces that are quadrants of planes bounded by certain pairs of the out of the ten positive semi-axes in $\mathbb{R}^{1}0,$ that are dictated by the leaf tree structure, as shown on the Petersen graph in Figure 5 (see Barden et al(2013)[1]).

There are a number of cases to consider, when it comes to CLT on $T_{4}$, depending on whether the population intrinsic mean lies in the 2D stratum, in the 1D stratum or at the origin (star tree). The limiting distribution for all cases are given in Barden et al (2013)[1]. In particular here we detail the case, when the data lies on three quadrants forming what is known as an open book with three leafs (see Hotz el al(2013)[9]), obtained by gluing these quadrants along a common boundary (spine). Such a particular type of open book could be defined as $L_{i}=\{(i,x_{1},x_{2}):x_{1},x_{2}\in[0,\infty)\}i=1,2,3$, together at the common spine $S=[0,\infty)$ which comprises the equivalence classes in $\cup_{i=1}^{3}([0,\infty)\times[0,\infty)\times\{i\}$. Thus, the open book $O_{3}$ is the disjoint union

of the spine $S$ and the interiors $L_{i}^{+}=L_{i}/S$ of the leaves, $i=1,2,3$. If the points $\textbf{x}=(x_{1},x_{2}),\textbf{y}=(y_{1},y_{2})$ are on the same flat convex leaf (as a subset of $\mathbb{R}^{2},$ the distance between them $d(\textbf{x},\textbf{y})=\|\textbf{x}-\textbf{y}\|$. If the points $\textbf{x},\textbf{y}$ are on different leafs (see figure 6), one could replace point x by x’ onto the half space opposite to $L_{a}$, then the distance is defined as $d(\textbf{x},\textbf{y})=\|\textbf{x'}-\textbf{y}\|$, where $\textbf{x'}=(x_{1},-x_{2})$.

Assume $X_{i},i=1,\dots,n$ are i.i.d. random objects on $O_{3}$. Denote a weighted sum of probability measure $Q_{3}$ on the legs $L_{i}$ and an atom $Q_{0}$ at $C$. Further, note that the intrinsic mean $\mu_{I}$ exists since space has and the intrinsic variance is finite. We assume $w_{0}=0$ and $x\in L_{a}$, the Fréchet function is defined as follows,

where $v_{i}^{(j)}=\int_{0}^{\infty}uw_{i}Q_{i}^{(j)}(du)$.

To minimize $F(\textbf{x})$ is to minimize the quadratic form for $x_{1},x_{2}$ and the solution is $x_{1}^{*}=\sum_{i=1}^{3}v_{i}^{(1)},x_{2}^{*}=v_{a}^{(2)}-\sum_{i\neq a}v_{i}^{(2)}$. Since $v_{i}^{(j)}\geq 0,x_{1}^{*}$ is always non-negative. Thus, one could apply C.L.T. on $x_{1}^{*}$ . However, for $x_{2}^{*}$, one have to discuss the three situations as did for the spider spaces. Therefore, in this case, if one separate the space into two directions, the stickiness of intrinsic mean would only occur on one direction, which is in a lower dimensional space. If for all a, $v_{a}^{(2)}<\sum_{i\neq a}v_{i}^{(2)}$, the intrinsic sample mean would stick to the spine S, but still has one degree of freedom. Thus for $n\to\infty,$ the intrinsic sample mean would stick to the spine S, and if it’s coordinate on the spine is $\bar{X}_{I,n},$ than $\sqrt{n}(\bar{X}_{I,n},-\mu_{I})\to_{d}Y,$ where $Y\sim\mathcal{N}(0,\sigma^{2}).$ Here $\mu_{I}$ is the mean of the projection of $Y$ on the spine, and $\sigma^{2}$ is its variance.

Another case of interest (see Barden et al(2013)[1]), is data on a $Q_{5}$, as a union of five quadrants, that is isometric with a subset made of five quadrants on $T_{4},$ whose trace on a the Petersen form a cycle ( see eg the cycle of quadrants from the edge $x$ to itself in Figure 2. In this case the asymptotic distribution according to Barden et al (2013)[1] (see also Barden and Le(2018)[2]), behaves, via the piecewise Riemannian Log map, like a bivariate normal.