# Stochastic Safety Radius on UPGMA
## 2 Stochastic Safety Radius  
Let \(\mathbb{Z}_{\geq 0}\) be the set of all non-negative integers. Let \(X=\{1,\ldots,n\}\) be the set of labels for given species (or taxa) and let \(T\) be a rooted phylogenetic tree with leaves \(X\). **Definition 3**. : _Let \(D\in\mathbb{Z}_{\geq 0}^{n\times n}\) be an \(n\times n\) matrix with non-negative elements. If \(D\) is a symmetric matrix with its diagonal equal to \(0\), then we call \(D\) a distance matrix or dissimilarity maps._  
_Let \(d_{ij}\in\mathbb{Z}_{\geq 0}\) be the \((i,j)\)th element of a distance matrix \(D\). If \(d_{ij}\) satisfies_  
* \(d_{ij}=d_{ji}\) _for any_ \(i,j\in X\)_,_
* \(d_{ii}=0\) _for all_ \(i\in X\)_,_
* \(d_{ik}+d_{kj}\geq d_{ij}\) _for all_ \(i,j,k\in X\)_,_  
_then we call \(D\) a metric._  
_If \(D\) is a metric and if there exist a phylogenetic tree with leaves \(X\) such that \(d_{ij}\) is the total distance of branch lengths of the path from a leaf \(i\) to a leaf \(j\) for all \(i,j\in X\), then \(D\) is called a tree metric._  
_Suppose \(D\) is a metric on \(X\). Then if \(D\) satisfies_  
\[\max\{d_{ij},d_{ik},d_{jk}\}\text{ and is achieved at least twice,} \tag{1}\]  
_for distinct \(i,j,k\in X\), then \(D\) is called an ultrametric._  
**Definition 4**. : _Suppose we have a rooted phylogenetic tree \(T\) with a leaf label set \(X\). If a distance from its root to each leaf \(i\in X\) is the same distance for all \(i\in X\), then we call \(T\) an equidistant tree._  
**Theorem 5** ([14]). : _Suppose we have an equidistant tree \(T\) with a leaf label set \(X\) and suppose \(d_{ij}\) for all \(i,j\in X\) is a distance from a leaf \(i\) to a leaf \(j\). Then, \(D\) is an ultrametric if and only if \(T\) is an equidistant tree._  
In this paper, we focus on equidistant trees with leaves \(X\). In practice, we compute a distance matrix from an observed alignment. When we compute a distance matrix from an alignment via a maximum likelihood estimation, usually a distance matrix is not a tree metric [1]. Therefore, in this paper, we investigate a probability that we obtain the tree topology of the true phylogenetic tree from a distance matrix obtained from an input alignment using _stochastic safety radius_[2]. **Definition 6** (Stochastic safety radius). : _Let \(\sigma=\frac{c^{2}}{\log(n)}\) for some positive \(c\in\mathbb{R}\). For any \(\eta>0\), we say that a distance-based tree reconstruction method \(M\) has \(\eta\)-stochastic safety radius \(s=s_{n}\) if for every binary phylogenetic \(X\)-tree \(T\) on \(n\) leaves, with minimum interior edge length \(w_{\min}>0\), and with the distance matrix \(\delta\) on \(X\) described by the random errors model, we have_  
\[c<s\cdot w_{\min}\implies P(M(\delta)=T)\geq 1-\eta.\]  
In this paper, we focus on the stochastic safety radius of a distance-based method, _Unweighted Pair Group Method with Arithmetic Mean (UPGMA)_. In reality, if we obtain all pairwise distances from a genetic data set, then we rarely have an ultrametric. Instead, we usually have dissimilarity maps. In order to infer an equidistant tree from dissimilarity maps, we can use UPGMA [15], which is a weighted least squared method to estimate the closest ultrametric in the space of ultrametrics [16]. **Example 7**. : _In order to demonstrate Algorithm 1, consider an equidistant tree with \(X=\{1,2,3,4\}\) shown in Figure 2._  
```
Input: Dissimilarity map \(D\in\mathbb{R}^{e}\) on \(X\). Output: An estimated equidistant tree \(T\) on \(X\). Set \(S:=X\) and \(T=\emptyset\). for\(k=1,\ldots,n-1\), do  Pick smallest \(D_{ij}\) for all pair of \((i,j)\in S\) with \(i\
eq j\). Set \(x\) as a parent node for the node \(i\) and \(j\), compute branch length from \(i\) to \(x\) and \(j\) to \(x\), and then record them in a tree \(T\). Set a new node \(x\) with \(D_{xk}=\frac{1}{2}(D_{jk}+D_{jk})\) for all \(k\in X\) with \(k\
eq i\) and \(k\
eq j\). Remove \(i,j\) from \(S\) and add \(x\) to \(S\). endfor  Record the branch lengths from the root to each leaf in the two leaves. return\(T\).