∎

11institutetext: R. Yoshida 22institutetext: Naval Postgraduate School
1411 Cunningham Road
Naval Postgraduate School
Monterey, CA 93943-5219
Tel.: +1-831-656-2973
Fax: +1-831-656-2595
22email<EMAIL_ADDRESS>33institutetext: S. Cox 44institutetext: University
of Michigan
2074 East Hall
530 Church Street
Ann Arbor, MI 48109-1043

# Tree Topologies along a Tropical Line Segment††thanks: R.Y. is partially
supported by NSF (DMS 1916037)

Ruriko Yoshida  Shelby Cox

(Received: date / Accepted: date)

###### Abstract

Tropical geometry with the max-plus algebra has been applied to statistical
learning models over tree spaces because geometry with the tropical metric
over tree spaces has some nice properties such as convexity in terms of the
tropical metric. One of the challenges in applications of tropical geometry to
tree spaces is the difficulty interpreting outcomes of statistical models with
the tropical metric. This paper focuses on combinatorics of tree topologies
along a tropical line segment, an intrinsic geodesic with the tropical metric,
between two phylogenetic trees over the tree space and we show some properties
of a tropical line segment between two trees. Specifically we show that a
probability of a tropical line segment of two randomly chosen trees going
through the origin (the star tree) is zero if the number of leave is greater
than four, and we also show that if two given trees differ only one nearest
neighbor interchange (NNI) move, then the tree topology of a tree in the
tropical line segment between them is the same tree topology of one of these
given two trees with possible zero branch lengths.

###### Keywords:

Phylogenetic trees Phylogenomics Tree Spaces Ultrametrics

##  1 Introduction

Due to the increasing amount of data today, data science is one of the most
exciting fields in science. It finds applications in statistics, computer
science, business, biology, data security, physics, and so on. Most
statistical models in data sciences assume that data points in an input sample
are distributed over a Euclidean space if they have numerical measurements.
However, in some cases this assumption can fail. For example, a space of
phylogenetic trees with a fixed set of leaves is a union of lower dimensional
cones over $\mathbb{R}^{e}$, where $e=\binom{n}{2}$ with $n$ as the number of
leaves AK . Since the space of phylogenetic trees is a union of lower
dimensional cones, we cannot just apply statistical models in data science to
a set of phylogenetic trees YZZ .

There has been much work in spaces of phylogenetic trees. In 2001, Billera-
Holmes-Vogtman (BHV) developed the notion of a space of phylogenetic trees
with a fixed set of labels for leaves BHV , which is a set of all possible
unrooted phylogenetic trees with the fixed set of labels on leaves and which
is a union of orthants; each orthant contains possible unrooted phylogenetic
trees with a fixed tree topology. They also showed that this space is ${\rm
CAT}(0)$ space so that there is a unique shortest connecting path, or
geodesic, between any two points in the space defined by the ${\rm
CAT}(0)$-metric. We can also generalize this tree space to the space of rooted
phylogenetic trees with a given set of leaves.

There is some work in development on machine learning models with the BHV
metric. For example, Nye defined the notion of the first order principal
component geodesic as the unique geodesic with the BHV metric over the tree
space which minimizes the sum of residuals between the geodesic and each data
point Nye . However, we cannot use a convex hull under the BHV metric for
higher principal components because Lin et al. showed that the convex hull of
three points with the BHV metric over the tree space can have arbitrarily high
dimension LSTY .

Another space of phylogenetic trees with a given set of leaves is the edge-
product space 10.2307/23238597 ; 10.1093/sysbio/syx080 . Metrics defined over
the edge-product space are associated with probability distributions on
characters and the Hellinger and Jensen–Shannon metrics are used between two
distributions over the edge-product space with a given set of leaves
10.1093/sysbio/syx080 . This space is also well studied from the view of
algebraic geometry (for example, 10.2307/23238597 ). Since the edge-product
space is based on distributions on a set of characters to represent
phylogenetic trees with a given set of leaves, it is natural to conduct
statistical analysis over such tree spaces using information geometry. For
more details, Garba et al. summarize these three tree spaces in a recent their
work Nye2021  and they extended the edge-product space to a new tree space
called the Wald space.

In 2004, Speyer and Sturmfels showed a space of phylogenetic trees with a
given set of labels on their leaves is a tropical Grassmannian SS , which is a
tropicalization of a linear space defined by a set of linear equations YZZ
with the max-plus algebra. It is important to note that the tree space defined
by Speyer and Sturmfels is not isometric to the tree space defined by Billera-
Holmes-Vogtman although they are homeomorphic to each other. The first attempt
to apply tropical geometry to computational biology and statistical models was
done by Pachter and Sturmfels PS . The tropical metric with the max-plus
algebra on the tree space is known to behave very well AGNS ; CGQ . For
example, contrary to the BHV metric, the dimension of the convex hull of $s$
tropical points is at most $s-1$ LSTY . There has been much work done with the
tropical metric over the tree space of equidistant trees to analyze a set of
phylogenetic trees with $n$ leaves $X=\\{1,2,\ldots,n\\}$. For example,
Yoshida et al. defined tropical principal component analysis (PCA) with the
tropical metric over the space of equidistant trees to reduce dimensionality
and to visualize data sets YZZ . Also Tang et al. developed hard and soft
tropical support vector machines (SVMs) and the authors applied them to
classifying sets of equidistant trees TWY . For more details on applications
of tropical geometry to tree spaces, see Yoshida2 .

One of the challenges in statistical learning models with the tropical metric
over the space of equidistant trees is the difficulty to interpret outputs
from such methods. For example, the principal geodesic developed by Nye in Nye
has a natural interpretation of the geodesic with the BHV metric over the
space of phylogenetic trees with $n$ leaves. However, it is not obvious how to
interpret a tropical principal polytope developed by Yoshida et al. in YZZ ;
10.1093/bioinformatics/btaa564 . Interpretation of the output from a
statistical learning model is one of the most important processes in data
analysis. Therefore, this paper focuses on the interpretation of a tropical
“geodesic” with the tropical metric on the space of equidistant trees with $n$
leaves. However, a tropical geodesic between two equidistant trees is known to
be not unique (e.g., see anthea ). In fact, there are infinitely many tropical
geodesics between two points. This makes it difficult to analyze behavior of a
tropical geodesic between trees, thus in this paper we consider a tropical
line segment between trees which is intrinsic and unique on the space of
equidistant trees anthea . Thus, here we use a tropical line segment between
two equidistant trees as a tropical geodesic between them.

In this paper, we focus on rooted phylogenetic trees with $n$ leaves. More
specifically we focus on equidistant trees, rooted phylogenetic trees whose
total branch lengths from the root to each leaf are the same for all leaves.
It is important to note that the tree spaces defined by Billera-Holmes-
Vogtmann BHV , Speyer-Sturmfels SS , and the edge-product space with a
distribution based metric 10.1093/sysbio/syx080  can be applied to a space of
rooted phylogenetic trees, but they do not assume equidistant trees.

Among these three tree spaces: the BHV space; the edge-product space; and the
tree space with the tropical metric, a tree space with the tropical metric has
the least attention because the geodesic between trees with the tropical
metric is not unique and also is hard to interpret in terms of tree
topologies. Therefore we focus on combinatrics of tree topologies on the
geodesic between trees with the tropical metric, especially tropical line
segment between trees, which is a unique geodesic in terms of the tropical
metric. Monod et al. investigated tree topologies along a tropical line
segment over the space of ultrametrics and characterizes symmetry of tree
topologies on a tropical line segment in LMY2 . Therefore, we investigate
explicitly how tree topologies change over a tropical line segment for some
specific cases. Specifically, we show that the probability of a tropical line
segment of two randomly chosen trees going through the origin (the star tree)
is zero if the number of leaves is greater than four. In addition, we also
show that if two given trees differ by only one nearest neighbor interchange
(NNI) move, then the tree topology of a tree in the tropical line segment
between them is the same tree topology of one of these two given trees with
possible zero branch lengths. We end this paper with a conjecture that tree
topologies of trees on a tropical line segment change by a sequence of NNI
moves. Through this paper we propose open problems to understand combinatorics
of tree topologies along a tropical line segment between equidistant trees.

##  2 Notation and Definitions

###  2.1 Tropical Basics

In the tropical semiring $(\,\mathbb{R}\cup\\{-\infty\\},\oplus,\odot)\,$, we
define the basic operations of addition and multiplication as:

$a\oplus b:=\max\\{a,b\\},~{}~{}~{}~{}a\odot b:=a+b~{}~{}~{}~{}\text{ where
}a,b\in\mathbb{R}.$

In this semiring, the identity element for addition is $-\infty$ and $0$ is
the identity element for multiplication. An essential feature of tropical
arithmetic is that there is no subtraction. Tropical division is defined to be
classical subtraction, so $(\,\mathbb{R}\cup\\{-\infty\\},\oplus,\odot)\,$
satisfies all ring axioms (and indeed field axioms) except for the existence
of an additive inverse. In tropical geometry, we work on the _tropical
projective torus_ , $\mathbb{R}^{e}\\!/\mathbb{R}{\bf 1}$, where ${\bf 1}$
denotes the all-ones vector, i.e., for any
$x=(x_{1},\ldots,x_{e})\in\mathbb{R}^{e}\\!/\mathbb{R}{\bf 1},$

$(x_{1},\ldots,x_{e})=(x_{1}+c,\ldots,x_{e}+c),$

for any constant $c\in\mathbb{R}$.

###### Definition 1

Over the tropical semiring $(\,\mathbb{R}\cup\\{-\infty\\},\oplus,\odot)\,$,
suppose $u=(u_{1},\ldots,u_{e}),\,v=(v_{1},\ldots,v_{e})$ are in the tropical
projective space $\mathbb{R}^{e}/\mathbb{R}{\bf 1}$. Then the tropical metric
$d_{\rm tr}$ is defined as

$d_{\rm tr}(u,v)=\max_{i}\\{u_{i}-v_{i}\\}-\min_{i}\\{u_{i}-v_{i}\\}.$

######  Definition 2 (Tropical Convex Hull)

The tropical convex hull or tropical polytope of a given finite subset
$V=\\{v^{1},\ldots,v^{s}\\}\subset\mathbb{R}^{e}\\!/\mathbb{R}{\bf 1}$ is the
smallest tropically-convex subset containing
$V\subset\mathbb{R}^{e}\\!/\mathbb{R}{\bf 1}$: it is written as the set of all
tropical linear combinations of $V$ such that:

$\mathrm{tconv}(V)=\\{a_{1}\odot v^{1}\oplus a_{2}\odot
v^{2}\oplus\cdots\oplus a_{s}\odot v^{s}\mid
a_{1},\ldots,a_{s}\in\mathbb{R}\\}.$

A tropical line segment between two points $v^{1},\,v^{2}$ is the tropical
polytope of $\\{v^{1},\,v^{2}\\}$.

###### Example 1

Suppose we have two vectors

$v^{1}=(0,0,0),\,v^{2}=(0,3,1),$

over $\mathbb{R}^{3}\\!/\mathbb{R}{\bf 1}$. Then we consider the tropical line
segment between $v^{1}$ and $v^{2}$, that is

$\mathrm{tconv}(V)=\\{a_{1}\odot v^{1}\oplus a_{2}\odot v^{2}\mid
a_{1},a_{2}\in\mathbb{R}\\}.$

Note that

$a_{1}\odot v^{1}=(a_{1}+0,a_{1}+0,a_{1}+0)=(0,0,0)=v^{1},$

and

$a_{2}\odot v^{2}=(a_{2}+0,a_{2}+3,a_{2}+1)=(0,3,1)=v^{2}.$

Also

$\begin{array}[]{rl}&a_{1}\odot v^{1}\oplus a_{2}\odot v^{2}\\\
=&(\max\\{a_{1}+0,a_{2}+0\\},\max\\{a_{1}+0,a_{2}+3\\},\max\\{a_{1}+0,a_{2}+1\\})\\\
=&(\max\\{a_{1},a_{2}\\},\max\\{a_{1},a_{2}+3\\},\max\\{a_{1},a_{2}+1\\}).\end{array}$

When we have $a_{1}\geq a_{2}+3$, then

$\begin{array}[]{rl}&a_{1}\odot v^{1}\oplus a_{2}\odot v^{2}\\\
=&(\max\\{a_{1},a_{2}\\},\max\\{a_{1},a_{2}+3\\},\max\\{a_{1},a_{2}+1\\})\\\
=&(a_{1},a_{1},a_{1})\\\ =&v^{1}.\end{array}$

When we have $a_{2}+1\leq a_{1}<a_{2}+3$, then

$\begin{array}[]{rl}&a_{1}\odot v^{1}\oplus a_{2}\odot v^{2}\\\
=&(\max\\{a_{1},a_{2}\\},\max\\{a_{1},a_{2}+3\\},\max\\{a_{1},a_{2}+1\\})\\\
=&(a_{1},a_{2}+3,a_{1})\\\ =&(0,a_{2}+3-a_{1},0)\\\ =&(0,l,0),\\\ \end{array}$

where $l=a_{2}+3-a_{1}$ for $0<l<2$.

When we have $a_{2}\leq a_{1}<a_{2}+1$, then

$\begin{array}[]{rl}&a_{1}\odot v^{1}\oplus a_{2}\odot v^{2}\\\
=&(\max\\{a_{1},a_{2}\\},\max\\{a_{1},a_{2}+3\\},\max\\{a_{1},a_{2}+1\\})\\\
=&(a_{1},a_{2}+3,a_{2}+1)\\\ =&(0,a_{2}+3-a_{1},a_{2}+1-a_{1})\\\
=&(0,l+2,l),\\\ \end{array}$

where $l=a_{2}+3-a_{1}+1$ for $0<l<1$. Therefore the tropical line segment
$v^{1}$ and $v^{2}$ are the line segments from $v^{1}$ to $(0,2,0)$ and from
$(0,2,0)$ to $v^{2}$.

Let $\Gamma_{u,v}$ be a tropical line segment between two ultrametrics
$u,\,v\in\mathcal{U}_{n}$.

###### Example 2

Suppose we have a set
$V=\left\\{v^{1},\,v^{2},\,v^{3}\right\\}\subset\mathbb{R}^{3}\\!/\mathbb{R}{\bf
1}$ where

$v^{1}=(0,0,0),\,v^{2}=(0,3,1),\,v^{3}=(0,2,5).$

First, we compute the tropical line segment $\Gamma_{v^{1},v^{2}}$ as Example
1 shows. Then, similarly we can compute the tropical line segment
$\Gamma_{v^{2},v^{3}}$ which is a line segment of

$v^{2}=(0,3,1),\,(0,3,5),\,v^{3}=(0,2,5),$

and the tropical line segment $\Gamma_{v^{1},v^{3}}$ is a line segment of

$v^{1}=(0,0,0),\,(0,0,3),\,v^{3}=(0,2,5).$

The tropical polytope $\mathrm{tconv}(V)$ of $V$ is shown in Fig. 1.

Figure 1: Tropical polytope of three points $(0,0,0),\,(0,3,1),\,(0,2,5)$ in
$\mathbb{R}^{3}\\!/\mathbb{R}{\bf 1}$.

###  2.2 Space of Ultrametrics

A phylogenetic tree is a weighted tree with labels $X=\\{1,\ldots,n\\}$ on its
leaves and its internal nodes do not have any labels. Each edge on a
phylogenetic tree has non-negative weight which represents evolutionary time
and mutation rates. A phylogenetic tree can be rooted or unrooted. Throughout
this paper we assume that all phylogenetic trees are rooted. Also we assume
that all phylogenetic trees are equidistant trees, that is, rooted
phylogenetic trees with the property that the distance from the root to each
leaf is the same for all leaves and all trees have the same height. This is
the same assumption of the multispecies coalescent model coalescent , one of
the most popular models to model gene trees under the species tree.

A dissimilarity map is a map $u_{ij}:X\times X\to\mathbb{R}_{+}$ such that

$u_{ij}=\begin{cases}u_{ji}&\mbox{if }i\not=j\\\ 0&\mbox{if }i=j,\end{cases}$

for any $i,j\in X$. Suppose $u=(u_{12},\ldots,u_{n-1n})$ are dissimilarity
maps. Then, note that $u$ is a metric if $u$ satisfies the triangle
inequality. If there exists a phylogenetic tree $T$ with the leaf label $X$
such that $u_{ij}$ is a pairwise distance from a leaf $i\in X$ to a leaf $j\in
X$, then we call $u$ a tree metric.

###### Definition 3

$u:=(u_{12},u_{13},\ldots,u_{n-1n})$ is called an ultrametric if

$\max\\{u_{ij},\,u_{ik},\,u_{jk}\\}$

for distinct $i,\,j,\,k\in X=\\{1,2,\ldots n\\}$ is achieved at least twice.

It is well-known that $u=(u_{12},u_{13},\ldots,u_{n-1n})$ is an ultrametric if
and only if $u=(u_{12},u_{13},\ldots,u_{n-1n})$ is a tree metric with an
equidistant tree $T$ anthea . In phylogenetics it is called the three point
condition buneman1974note . Therefore, here we work on the space of
ultrametrics as a space of equidistant trees with $n$ leaves. Let
$\mathcal{U}_{n}$ denote the space of all ultrametrics in the tropical
projective space $\mathbb{R}^{e}/{\bf 1}\mathbb{R}$ where $e=\binom{n}{2}$.

Note that $\mathcal{U}_{n}$ can be considered as the space of equidistant
trees since for each equidistant tree there is a unique ultrametric to define
the equidistant tree.

Let $L_{n}$ be the subspace of $\mathbb{R}^{e}$ defined by the linear
equations $x_{ij}-x_{ik}+x_{jk}=0$ for $1\leq i<j<k\leq n$, where
$x_{ij},x_{ik},x_{jk}$ are variables. The tropicalization
$\text{trop\,}(L_{n})\subseteq\mathbb{R}^{e}/\mathbb{R}{\bf 1}$ is the
tropical linear space consisting of points $(v_{12},v_{13},\ldots,v_{n-1,n})$
such that $\max(v_{ij},v_{ik},v_{jk})$ is obtained at least twice for all
triples $i,j,k\in\\{1,\ldots,n\\}$. Then we have the following theorem.

######  Theorem 1 (Theorem 3 in YZZ )

The image of $\mathcal{U}_{n}$ in $\mathbb{R}^{e}/\mathbb{R}{\bf 1}$ is
$\text{trop\,}(L_{n})$.

Therefore, we can think of $\mathcal{U}_{n}$ as a tropical linear space. Also
note that $\mathcal{U}_{n}$ is a tropical linear space over the tropical
projective space. Therefore $\mathcal{U}_{n}$ is tropically convex. Thus, if
we take any two points $u,\,v\in\mathcal{U}_{n}$ then the tropical intrinsic
geodesic between $u$ and $v$ is in $\mathcal{U}_{n}$. This means that all
points in a tropical intrinsic geodesic between $u,\,v\in\mathcal{U}_{n}$ are
ultrametrics and there are equidistant trees associated with these
ultrametrics. These leads to the following problem: Suppose we have two
equidistant trees $T_{u},\,T_{v}$ with their ultrametrics
$u,\,v\in\mathcal{U}_{n}$, respectively. Then how do tree topologies change
along a tropical intrinsic geodesic between ultrametrics $u,\,v$?

This is one of the most important questions in order to develop data science
models using the tropical metric over $\mathcal{U}_{n}$ since this will answer
the interpretation of results from a model with the tropical metric. For
example, the output from the tropical principal component analysis (PCA) is
not obvious to interpret.

It is very important to note that tropical geodesics between two points are
not unique. For example, we consider two points from Example 1. Then we have
the distance over the tropical line segment between $v_{1}=(0,0,0)$ and
$v_{2}=(0,3,1)$ is $d_{\rm tr}(v_{1},(0,2,0))+d_{\rm
tr}((0,2,0),v_{2})=2+1=3$. But the straight line from $v_{1}$ to $v_{2}$ is
also a tropical geodesic since $d_{\rm tr}(v_{1},v_{2})=3$.

However, if we consider a tropical line segment defined in Definition 2
between two ultrametrics $u,\,v\in\mathcal{U}_{n}$ associated with equidistant
trees, that is, a tropical polytope generated by $u,\,v\in\mathcal{U}_{n}$,
then the tropical line segment is unique. Let $\Gamma_{u,v}$ be a tropical
line segment between two ultrametrics $u,\,v\in\mathcal{U}_{n}$.

###### Proposition 2

A tropical line segment $\Gamma_{u,v}$ of
$u,\,v\in\mathbb{R}^{e}\\!/\mathbb{R}{\bf 1}$ is unique, it is a geodesic in
$\mathcal{U}_{n}$, and it is intrinsic.

###### Proof

The first part of the statement is directly from Proposition 24 in anthea .
The second and the third statements can be proven by the fact that
$\mathcal{U}_{n}$ is a tropical linear space by Theorem 1 and a tropical line
segment is a tropical polytope of two points in $\mathcal{U}_{n}$.

Thus, we consider the following question:

###### Problem 1

Suppose we have two equidistant trees $T_{u},\,T_{v}$ with their ultrametrics
$u,\,v\in\mathcal{U}_{n}$, respectively. Then how do tree topologies change
along the tropical line segment between ultrametrics $u,\,v$?

We can generalize this question to a tropical polytope generated by finitely
many ultrametrics $u^{1},\,\ldots,u^{k}\in\mathcal{U}_{n}$.

###### Problem 2

Suppose we have $k$ equidistant trees $T_{1},\,\ldots,T_{k}$ with their
ultrametrics $u^{1},\,\ldots,u^{k}\in\mathcal{U}_{n}$, respectively. Then how
do tree topologies change in the tropical polytope generated by ultrametrics
$u^{1},\,\ldots,u^{k}$?

In the paper by Page et al. in 10.1093/bioinformatics/btaa564 , we partially
addressed this problem.

###### Definition 4

Let
$\mathcal{P}=\text{tconv\,}(u^{1},\dots,u^{k})\subseteq\mathbb{R}^{e}/\mathbb{R}{\bf
1}$ be a tropical polytope. Each point $x=(x_{1},\ldots,x_{e})$ in
$\mathbb{R}^{e}/\mathbb{R}{\bf 1}$ has a _type_ ${Q}=({Q}_{1},\dots,{Q}_{e})$
according to $\mathcal{P}$, where an index $i$ is in ${Q}_{j}$ if

$u^{i}_{j}-x_{j}=\max(u^{i}_{1}-x_{1},\dots,u^{i}_{e}-x_{e}),$

where $u^{i}=(u^{i}_{1},\ldots,u^{i}_{e})$ for $i=1,\ldots,e$ and
$j=1,\ldots,e$. The tropical polytope $\mathcal{P}$ consists of all points $x$
whose type ${Q}=({Q}_{1},\dots,{Q}_{e})$ has all ${Q}_{i}$ nonempty. Each
collection of points with the same type is called a _cell_.

For more details on a cell of a tropical polytope, see
10.1093/bioinformatics/btaa564 .

######  Theorem 3 (10.1093/bioinformatics/btaa564 )

Let
$\mathcal{P}=\text{tconv\,}(u^{1},\dots,u^{k})\subseteq\mathbb{R}^{n}/\mathbb{R}{\bf
1}$ be a tropical polytope spanned by ultrametrics. Then any two points $x$
and $y$ in the same cell of $\mathcal{P}$ are also ultrametrics with the same
tree topology.

Now it is natural to ask the following question:

###### Problem 3

How do tree topologies change if a tropical geodesic crosses between two cells
on a tropical polytope $\mathcal{P}$ over $\mathcal{U}_{n}$?

##  3 Drawing a Tropical Line Segment on $\mathcal{U}_{n}$

In this section we interpret the algorithm to compute a tropical line segment
in MS . In order to compute the tropical line segment between equidistant
trees $T_{1}$ and $T_{2}$ with leaves $X$, we adapt the algorithm shown in the
proof of Proposition 5.2.5 in MS . Note that Proposition 5.2.5 uses the min-
plus algebra, whereas we are using the max-plus algebra. Recall that we use
the max-plus algebra because the tree space is a tropical Grassmannian with
the max-plus algebra SS .

Let $\Gamma_{u,v}$ be a tropical line segment between two ultrametrics
$u,\,v\in\mathcal{U}_{n}$. Suppose $u$ and $v$ are ultrametrics corresponding
to equidistant trees $T_{u}$ and $T_{v}$, then we use a notation
$\Gamma_{T_{u},T_{v}}$ as well. First we adapt the algorithm shown in the
proof of Proposition 5.2.5 in MS .

Input: A point $u=(u_{1},\ldots,u_{e})$ and a point $v=(v_{1},\ldots,v_{e})$
in $\mathbb{R}^{e}/\mathbb{R}{\bf 1}$

Output: A tropical line segment $\Gamma_{u,v}$ between $u$ and $w$ in
$\mathbb{R}^{e}/\mathbb{R}{\bf 1}$

1 Compute $\lambda=v-u=(v_{1}-u_{1},\ldots,v_{e}-u_{e})$.

2 Set $L=\emptyset$ and set $y^{0}=v$.

3 for  _$i\leftarrow 1$ to $e$_ do

4 Find the $i$th smallest coordinate in $\lambda$, and denote its value as
$\lambda_{i}$.

5 Set
$y^{i}=\left(\max\\{\lambda_{i}+u_{1},v_{1}\\},\ldots,\max\\{\lambda_{i}+u_{e},v_{e}\\}\right)$.

6 Set $L=L\cup\\{y^{i}\\}$.

7

8Set $y^{e+1}=u$.

9 return _the line segments of lines from $y^{i}$ to $y^{i+1}$ in $L$ for
$i=0,1,\ldots,e$._

Algorithm 1 Tropical line segment in $\mathbb{R}^{e}/\mathbb{R}{\bf 1}$

Now the following algorithm is to compute a tropical line segment between
ultrametrics in $\mathcal{U}_{n}$ modified from Algorithm 1:

Input: An ultrametric $u=(u_{12},\ldots,u_{n-1n})$ computed from an
equidistant tree $T_{1}$ with $n$ leaves and an ultrametric
$v=(v_{12},\ldots,v_{n-1n})$ computed from an equidistant tree $T_{2}$ with
$n$ leaves

Output: A tropical line segment $\Gamma_{u,v}$ between $u$ and $w$ in
$\mathcal{U}_{n}$

1 Compute $\lambda=v-u=(v_{12}-u_{12},\ldots,v_{n-1n}-u_{n-1n})$.

2 Set $L=\emptyset$ and set $y^{0}=v$.

3 for  _$i\leftarrow 1$ to ${n\choose 2}$_ do

4 Find the $i$th smallest coordinate $(i_{1},i_{2})$ in $\lambda$, and denote
its value as $\lambda_{i_{1}i_{2}}$.

5 Set
$y^{i}=\left(\max\\{\lambda_{i_{1}i_{2}}+u_{12},v_{12}\\},\ldots,\max\\{\lambda_{i_{1}i_{2}}+u_{n-1n},v_{n-1n}\\}\right)$.

6 Set $L=L\cup\\{y^{i}\\}$.

7

8Set $y^{\binom{n}{2}+1}=u$.

9 return _the line segments of lines from $y^{i}$ to $y^{i+1}$ in $L$ for
$i=0,1,\ldots,\binom{n}{2}$._

Algorithm 2 Tropical line segment in $\mathcal{U}_{n}$

###### Example 3

Suppose we have two points

$v^{1}=(0,0,0),\,v^{2}=(0,3,1)$

from Example 1. We wish to compute the tropical line segment
$\Gamma_{v^{1},v^{2}}$ using Algorithm 1.

First we compute $\lambda=v^{2}-v^{1}=(0,3,1)$. Then, order elements of
$\lambda$ from the smallest to the largest, that is

$\lambda=(0,1,3).$

Then first we compute

$\max(\lambda_{1}+v^{1},v^{2})=(\max\\{0+0,0\\},\max\\{0+0,3\\},\max\\{0+0,1\\})=(0,3,1).$

This is one of the end points of $\Gamma_{v^{1},v^{2}}$. Then we compute

$\max(\lambda_{2}+v^{1},v^{2})=(\max\\{1+0,0\\},\max\\{1+0,3\\},\max\\{1+0,1\\})=(1,3,1)=(0,2,0).$

This is a point where $\Gamma_{v^{1},v^{2}}$ bends. Finally, we compute

$\max(\lambda_{3}+v^{1},v^{2})=(\max\\{3+0,0\\},\max\\{3+0,3\\},\max\\{3+0,1\\})=(3,3,3)=(0,0,0).$

This is one of the end points of $\Gamma_{v^{1},v^{2}}$. Thus,
$\Gamma_{v^{1},v^{2}}$ is a line segment

$v^{1}=(0,0,0),\,(0,2,0),\,v^{2}=(0,3,1).$

Here we show some properties of tropical line segments:

###### Proposition 4

Let $\Gamma_{u,v}$ be the tropical line segment between ultrametrics
$u,v\in\mathcal{U}_{n}$. If $x,y$ are in one straight line on $\Gamma_{u,v}$,
then $x$ and $y$ have the same tree topology.

###### Proof

This is a corollary of Theorem 3.

###### Theorem 5

If we take $x,y$ randomly from $\mathcal{U}_{n}$ from a uniform distribution
on equidistant trees with fixed height of the equidistant trees, then the
tropical line segment $\Gamma_{x,y}$ between $x,y\in\mathcal{U}_{n}$ goes
through the star tree (the origin in terms of ultrametrics) with probability
zero for $n\geq 5$.

###### Proof

Note that the tropical line segment $\Gamma_{x,y}\subset\mathcal{U}_{n}$
between $x,y\in\mathcal{U}_{n}$ is a tropical polytope generated by $x,y$. We
will use Lemma 3.3 from 10.1093/bioinformatics/btaa564  which states that the
origin is contained in $\Gamma_{x,y}$ if and only if $x\oplus y=0.$ Suppose
the trees both have height $h>0$.

When $n=3$, if two trees are in the different polyhedral cones, the tropical
line segment between them has to go through the origin.

When $n=4$, suppose we have two trees with ultrametrics such that

$\begin{array}[]{c}x=(2a_{1},2h,2h,2h,2h,2h,)\\\
y=(2h,2a_{2},2h,2h,2b_{2},2h)\end{array}$

for any $a_{1},a_{2},b_{1},b_{2}<h$, then we have $x\oplus y=0.$ So the
tropical line segment between them contains the origin for any
$a_{1},a_{2},b_{1},b_{2}<h$.

For $n\geq 5$, consider the two trees $T_{1}$ and $T_{2}$ shown in Figure 2.
$R_{1},R_{2},L_{1},L_{2}\subset[n]:=\\{1,\ldots n\\}$ such that $L_{1},R_{1}$
partition $[n]$, i.e., $L_{1}\cap R_{1}=\emptyset$ and $L_{1}\cup R_{1}=[n]$,
and $L_{2},R_{2}$ partition $[n]$, i.e., $L_{2}\cap R_{2}=\emptyset$ and
$L_{2}\cup R_{2}=[n]$. Denote $L\sqcup R=[n]$ be a partition $\\{R,\,L\\}$ of
$[n]$ for $R,L\subset[n]$. Suppose $x$ is the ultrametric of $T_{1}$ and $y$
is the ultrametric of $T_{2}$.

Figure 2: Two trees the proof of Theorem 5 for $n\geq 5$.

Also note that

$(L_{1}\cap L_{2})\sqcup(L_{1}\cap R_{2})\sqcup(L_{2}\cap
R_{1})\sqcup(L_{2}\cap R_{2})=[n].$

Since $n\geq 5$, therefore, one of the four sets must have at least two
elements. Since $n\geq 5$, there exist a pair of two leaves $i,j$ from one of
$(L_{1}\cap L_{2})$, $(L_{1}\cap R_{2})$, $(L_{2}\cap R_{1})$, and $(L_{2}\cap
R_{2})$. Then we have

$x_{ij}<2h,\mbox{ and }y_{ij}<2h.$

Therefore, $(x\oplus y)_{ij}<2h$. Therefore, $x\oplus y$ is not the star tree,
so by Lemma 3.3 from 10.1093/bioinformatics/btaa564 , the tropical line from
$x$ to $y$ does not pass through the origin, i.e., the star tree.

Now we interpret Algorithm 2 in terms of equidistant trees. Before the
algorithm to draw a tropical line between two equidistant trees, we have the
following definition:

###### Definition 5

Suppose we have an equidistant tree $T$ with $n$ leaves. An external branch of
$T$ is an edge directly attached to a leaf $i\in X$.

###### Definition 6

Let $T$ be an equidistant tree with $n$ leaves and let $b_{i}$ be the external
branch lengths of leaf $i$ in $T$ for $i=1,\ldots,n$. Also let $\alpha T$ be
an equidistant tree with $n$ leaves such that the tree topology of $\alpha T$
is the same as the tree topology of $T$ and its external branch length of leaf
$i$ is $\alpha/2+b_{i}$ for $i=1,\ldots,n$.

Input: An ultrametric $u=(u_{12},\ldots,u_{n-1n})$ computed from an
equidistant tree $T_{1}$ with $n$ leaves and an ultrametric
$v=(v_{12},\ldots,v_{n-1n})$ computed from an equidistant tree $T_{2}$ with
$n$ leaves

Output: A tropical line segment $\Gamma_{u,v}$ between $u$ and $v$ in
$\mathcal{U}_{n}$ written a sequence of equidistant trees associated with
segments in the tropical line segments

1 Compute
$\lambda=(\lambda_{12},\ldots,\lambda_{n-1n})=v-u=((v_{12}-u_{12}),\ldots,(v_{n-1n}-u_{n-1n}))$.

2 Set $L=\emptyset$ and $T^{0}=T_{2}$. for  _$i\leftarrow 1$ to ${n\choose
2}$_ do

3 Find the $i$th smallest coordinate $(i_{1},i_{2})$ in
$(\lambda_{12},\ldots,\lambda_{n-1n})$, and denote its value as
$\lambda_{i_{1}i_{2}}$.

4 Initialized $T^{i}$ as a star tree.

5 for  _each pair of leaves $(k,\,l)$_ do

6 Compare the height of the internal node of $(k,\,l)$ in
$\lambda_{i_{1}i_{2}}T_{1}$ which equals to $\lambda_{i_{1}i_{2}}+u_{kl}$ with
the height of the internal node of $(k,\,l)$ in $T_{2}$, which equals to
$v_{kl}$.

7 Set an internal node with its height
$\max\\{\lambda_{i_{1}i_{2}}+u_{kl},v_{kl}\\}$ which is the ancestor of leaves
$(k,\,l)$.

8 Make the height of $T^{i}$ the same height of $T_{1}$ and $T_{2}$ by
adjusting all external branch length.

9

10 Set $L=L\cup\\{T^{i}\\}$.

11 Set $T^{{n\choose 2}+1}=T_{1}$.

12

13return _the line segments of lines from $T^{i}$ to $T^{i+1}$ in $L$ for
$i=0,1,\ldots,{n\choose 2}$._

Algorithm 3 Tropical line segment in $\mathcal{U}_{n}$ written in terms of
equidistant trees

###### Example 4

The input for Algorithm 3 $T_{1}$ and $T_{2}$ are shown in Fig. 3. Their
ultrametrics are

$\begin{array}[]{rcl}u&=&(0.4,0.8,2,0.8,2,2)\\\ v&=&(0.8,0.8,2,0.4,2,2)\\\
\end{array}$

Here $\lambda=v-u=(0.4,0,0,-0.4,0,0)$. The tropical line segment between $u$
and $v$ is a line segment consisting of the following ultrametrics:

$\begin{array}[]{rcl}v&=&(0.8,0.8,2,0.4,2,2)\\\ &&(0.8,0.8,2,0.8,2,2)\\\
u&=&(0.4,0.8,2,0.8,2,2)\\\ \end{array}$

We sort the elements in $\lambda$ from the smallest to the largest as

$\lambda=(-0.4,0,0,0,0,0.4).$

For $\lambda_{23}=-0.4$, then the tree topology of the tree associated with
the ultrametric $(0.8,0.8,2,0.4,2,2)$ is $T_{2}$. For
$\lambda_{i^{\prime}j^{\prime}}=0$ for
$(i^{\prime},j^{\prime})=(1,3),(1,4),(2,4),(3,4)$, then the tree topology
associated with the ultrametric $(0.8,0.8,2,0.8,2,2)$ is the tree with leaves
$1,\,2,\,3$ are attached to a single interior node. When $\lambda_{12}=0.4$,
the tree topology of the tree associated with the ultrametric
$(0.4,0.8,2,0.8,2,2)$ is $T_{1}$.

Figure 3:  Trees shown in Example 4.

The output from Algorithm 3 is the set of trees in the left column in Fig. 3.
The tropical line segment between $T_{1}$ and $T_{2}$ for this example is a
line segment from $T_{1}$ to $T_{2}$ via the bending point which is the tree
with the ultrametric $(0.8,0.8,2,0.8,2,2)$.

######  Proposition 6 (Proposition 5.2.5 in MS )

The time complexity to compute the tropical line segment between $T_{1}$ and
$T_{2}$ with $n$ leaves is $O(n^{2}\log n)=O(e\log e)$.

##  4 Tree Topologies along a Tropical Line Segment

Now we consider Problem 1, i.e., tree topologies along with the tropical line
segment between two trees. In order to solve Problem 1, we need to consider
relations between an equidistant tree and its ultrametric. First we consider
when one of the two trees in the end of a tropical line segment is the star
tree.

###### Definition 7

A sequence $\\{t_{1},\ldots,t_{k}\\}$ is called speciation times in a given
equidistant tree $T$ with $n$ leaves if $t_{i}$ is one half of the $i$th
smallest pairwise distance $d_{ij}$ for any $i,j\in[n]$.

In terms of an equidistant tree $T$, a speciation time $t_{i}$ is the height
from the leaves to the internal node which is the $i$th smallest branch length
from its offspring leaf.

###### Example 5

Consider the tree shown in Fig. 4. $t_{1},\,t_{2},\,t_{3}$ are speciation
times. For this tree $t_{1}=0.2$, $t_{2}=0.4$ and $t_{3}=1$.

Figure 4:  An equidistant tree $T$ for Example 5.

For an equidistant tree $T$ with $n$ leaves and with a sequence of speciation
times $\\{t_{1},\ldots,t_{k}\\}$, we define a sequence of trees $T^{1},\ldots
T^{k}$ associated with the tree $T$, where $k\leq n-1$, such that $T$ and
$T^{i}$ have the same tree topology except that $T^{i}$ has the sequence of
speciation times $\\{t_{1},\ldots,t_{k}\\}$ for $1\leq i\leq k$. In general
$T^{1}=T$. Also note that $T^{k}$ is the star tree with $n$ leaves.

###### Example 6

Consider the tree with $8$ leaves shown in Fig. 5. Then we have
$T^{2},\,T^{3},\,T^{4},\,T^{5},\,T^{6}$ as shown in Fig. 5. $T^{7}$ is the
star tree.

The shortest pairwise distance is the distance between leaves 7 and 8. So
$t_{1}=0.2$. The second shortest pairwise distance is the distance between
leaves 3 and 4. So $t_{2}=0.3$ and by Theorem 7, $T^{2}$ is same as $T$,
except the pairwise distance between 7 and 8 which is equal to the pairwise
distance between 3 and 4 ($=2\cdot t_{2}=0.6$).

The next shortest pairwise distance is the pairwise distance between leaves 5
and 6. So, by Theorem 7, $T^{3}$ is same as $T^{2}$, except the pairwise
distances between leaves 7 and 8, between leaves 3 and 4, and between leaves 5
and 6 are equal to $2\cdot t_{3}$ where $t_{3}=0.4$.

Then, the next shortest pairwise distances in $T$ are the pairwise distance
between two leaves from $\\{2,3,4\\}$. So by Theorem 7, $T^{4}$ is same as
$T^{3}$, except leaves 2, 3, and 4 form a polytomy with its height
$t_{4}=0.6$, and the pairwise distances between leaves 5 and 6 and between 7
and 8 are $2\cdot t_{4}$.

The next shortest pairwise distances are the pairwise distance between two
leaves from $\\{5,6,7,8\\}$. So by Theorem 7, $T^{5}$ is same as $T^{4}$,
except leaves 5, 6, 7, and 8 form a polytomy with its height $t_{5}=0.7$ and
leaves 2, 3, and 4 form a polytomy with its height $t_{5}=0.7$. The next
shortest pairwise distances are the pairwise distances between leaves $i$ and
$j$ for $i,j\in\\{1,2,3,4\\}$. Thus, by Theorem 7, $T^{6}$ is the equidistant
tree where the leaves 1, 2, 3, 4 form a polytomy with its height 1.0 and the
leaves 5, 6, 7, 8 form a polytomy with its height 1.0.

The tropical line segment from the star tree to $T$ is the line segment of
ultrametrics computed from the trees
$T,\,T^{2},\,T^{3},\,T^{4},\,T^{5},\,T^{6}$ as shown in Fig. 5 and $T^{7}$
which is the star tree.

Figure 5:  Trees shown in Example 6.

###### Theorem 7

Suppose we have an equidistant tree $T$ with $n$ leaves and a sequence of
speciation times $\\{t_{1},\ldots,t_{k}\\}$ where $k\leq n-1$. Then the
tropical line segment from $T$ in $\mathcal{U}_{n}$ to the origin, i.e., the
star tree with $n$ leaves, is the line segments of lines between the
ultrametrics of trees $T^{i},T^{i+1}$, for $i=1,\ldots,k-1$ associated with
the tree $T$.

###### Proof

Follow Algorithms 2 and 3. In this case we have $u_{ij}=0$ for all
$i,j\in\\{1,2,\ldots,n\\}$. Thus $\lambda=v$. At the for-loop in Algorithm 2
for the iteration $i$, i.e., the $i$th smallest pairwise distance with the
pair $(i_{1},i_{2})$ in $\lambda=v$

$\max\\{\lambda_{i_{1}i_{2}},v_{kl}\\}=\max\\{v_{i_{1}i_{2}},v_{kl}\\}=\begin{cases}v_{i_{1}i_{2}}&\mbox{if
}v_{i_{1}i_{2}}\geq v_{kl}\\\ v_{kl}&\mbox{otherwise,}\end{cases}$ (1)

for all $k,l\in\\{1,\ldots,n\\}$. Note that the equidistant tree corresponds
to this ultrametric in (1) is $T^{i}$.

###### Example 7

Consider the tree with $8$ leaves shown in Fig. 5. We are interested in
drawing a tropical line segment from the tree $T$ to the origin, i.e., the
star tree with $8$ leaves.

First we compute $\lambda=u-0=u$, where $u$ is the ultrametric of $T$. Then we
order $\lambda$ from the smallest to the largest, i.e.,

$\lambda=(2\cdot t_{1},\ldots,2\cdot t_{7}).$

Now, we iterate for each element in $\lambda$ from the smallest to the
largest.

For $2\cdot t_{1}$, we have

$u_{ij}=\max\\{2\cdot t_{1},u_{ij}\\}$

for $i,j\in X$ with $i<j$. Thus the equidistant tree for $2\cdot t_{1}$ is
$T$.

For $2\cdot t_{2}$, we have

$u_{ij}=\max\\{2\cdot t_{2},u_{ij}\\}$

for $(i,j)\in(X\times X)-\\{(7,8)\\}$ and

$2\cdot t_{2}=\max\\{2\cdot t_{2},u_{78}\\}.$

Then, this ultrametric gives the equidistant tree $T^{2}$ in Fig. 5.

For $2\cdot t_{3}$, we have

$u_{ij}=\max\\{2\cdot t_{3},u_{ij}\\}$

for $(i,j)\in(X\times X)-\\{(3,4),(7,8)\\}$ and

$\begin{array}[]{c}2\cdot t_{3}=\max\\{2\cdot t_{3},u_{34}\\},\\\ 2\cdot
t_{3}=\max\\{2\cdot t_{3},u_{78}\\}.\end{array}$

Then, this ultrametric gives the equidistant tree $T^{3}$ in Fig. 5.

For $2\cdot t_{4}$, we have

$u_{ij}=\max\\{2\cdot t_{4},u_{ij}\\}$

for $(i,j)\in(X\times X)-\\{(3,4),(5,6),(7,8)\\}$ and

$\begin{array}[]{c}2\cdot t_{4}=\max\\{2\cdot t_{4},u_{34}\\},\\\ 2\cdot
t_{4}=\max\\{2\cdot t_{4},u_{56}\\},\\\ 2\cdot t_{4}=\max\\{2\cdot
t_{4},u_{78}\\}.\end{array}$

Then, this ultrametric gives the equidistant tree $T^{4}$ in Fig. 5.

For $2\cdot t_{5}$, we have

$u_{ij}=\max\\{2\cdot t_{5},u_{ij}\\}$

for $(i,j)\in(X\times
X)-\\{(2,3),(2,4),(3,4),(5,6),(5,7),(5,8),(6,7),(6,8),(7,8)\\}$ and

$\begin{array}[]{c}2\cdot t_{5}=\max\\{2\cdot t_{5},u_{23}\\},\\\ 2\cdot
t_{5}=\max\\{2\cdot t_{5},u_{24}\\},\\\ 2\cdot t_{5}=\max\\{2\cdot
t_{5},u_{34}\\},\\\ 2\cdot t_{5}=\max\\{2\cdot t_{5},u_{56}\\},\\\ 2\cdot
t_{5}=\max\\{2\cdot t_{5},u_{57}\\},\\\ 2\cdot t_{5}=\max\\{2\cdot
t_{5},u_{58}\\},\\\ 2\cdot t_{5}=\max\\{2\cdot t_{5},u_{67}\\},\\\ 2\cdot
t_{5}=\max\\{2\cdot t_{5},u_{68}\\},\\\ 2\cdot t_{5}=\max\\{2\cdot
t_{5},u_{78}\\}.\end{array}$

Then, this ultrametric gives the equidistant tree $T^{5}$ in Fig. 5.

For $2\cdot t_{6}$, we have

$u_{ij}=\max\\{2\cdot t_{5},u_{ij}\\}$

for $(i,j)\in(\\{1,2,3,4\\}\times\\{5,6,7,8\\})$ and

$\begin{array}[]{c}2\cdot t_{6}=\max\\{2\cdot t_{6},u_{ij}\\},\\\ 2\cdot
t_{6}=\max\\{2\cdot t_{6},u_{kl}\\},\\\ \end{array}$

where $(i,j)\in\\{1,2,3,4\\}\times\\{1,2,3,4\\}$ and
$(k,l)\in\\{5,6,7,8\\}\times\\{5,6,7,8\\}$. Then, this ultrametric gives the
equidistant tree $T^{6}$ in Fig. 5.

Finally, for $2\cdot t_{7}$, we have

$\begin{array}[]{c}2\cdot t_{7}=\max\\{2\cdot t_{7},u_{ij}\\},\\\ \end{array}$

for all $(i,j)\in X\times X$. Thus we have the result shown in Fig. 5.

With this theorem, we can solve our problem for $n=3$.

###### Lemma 1

Suppose $T_{1},T_{2}$ are equidistant trees with $n=3$ leaves such that
$T_{1},T_{2}$ have different tree topologies. Then tree topologies along
$\Gamma_{T_{1},T_{2}}$ change from the tree topology of $T_{1}$ to the star
tree, and then change from the star tree to the tree topology of $T_{2}$.

###### Proof

Without loss of generality, $T_{1}$ and $T_{2}$ have tree topologies shown in
Fig 6. Let $u^{1}=(u^{1}_{12},u^{1}_{13},u^{1}_{23})$ be an ultrametric for
$T_{1}$ and $u^{2}=(u^{2}_{12},u^{2}_{13},u^{2}_{23})$ be an ultrametric for
$T_{2}$. Then we have

$\begin{array}[]{c}u^{1}_{23}\leq u^{1}_{12}=u^{1}_{13}\\\ u^{2}_{13}\leq
u^{2}_{12}=u^{2}_{23}.\\\ \end{array}$

Figure 6: $T_{1}$ and $T_{2}$ in the proof of Lemma 1

Then we have
$u^{2}-u^{1}=(u^{2}_{12}-u^{1}_{12},u^{2}_{13}-u^{1}_{13},u^{2}_{23}-u^{1}_{23})$.
Then since all elements in an ultrametric are non-negative, we have

$u^{2}_{13}-u^{1}_{13}\leq u^{2}_{12}-u^{1}_{12}\leq u^{2}_{23}-u^{1}_{23}.$

Using Algorithm 3, for $\lambda_{13}=u^{2}_{13}-u^{1}_{13}$, then we have
$T_{2}$. Also for $\lambda_{23}=u^{2}_{23}-u^{1}_{23}$, then we have $T_{1}$.
So we have to see the tree topology if $\lambda_{12}=u^{2}_{12}-u^{1}_{12}$.
Then we have

$\left(\begin{array}[]{c}\max\\{u^{1}_{12}+u^{2}_{12}-u^{1}_{12},u^{2}_{12}\\}\\\
\max\\{u^{1}_{13}+u^{2}_{12}-u^{1}_{12},u^{2}_{13}\\}\\\
\max\\{u^{1}_{23}+u^{2}_{12}-u^{1}_{12},u^{2}_{23}\\}\\\
\end{array}\right)=\left(\begin{array}[]{c}u^{2}_{12}\\\ u^{2}_{12}\\\
u^{2}_{23}\\\ \end{array}\right)=\left(\begin{array}[]{c}u^{2}_{12}\\\
u^{2}_{12}\\\ u^{2}_{12}\\\ \end{array}\right)$

which is the star tree. With Theorem 7 we are done.

###### Remark 1

Suppose $T_{1},\,T_{2}\in\mathcal{U}_{3}$ with $n=3$. Then, the tree
topologies along the geodesic between equidistant trees $T_{1}$ and $T_{2}$
under the BHV metric are the same as tree topologies along
$\Gamma_{T_{1},T_{2}}$.

###### Example 8

In this example, we map a tropical line segment between two points in
$\mathcal{U}_{4}$ onto the BHV treespace for rooted trees with $n=4$ leaves
shown in Fig. 7. $T_{1},T_{2}$ have the tree topologies $((1,2),(3,4))$ and
$(((1,2),3),4)$ written in the Newick format newick . Note that with this map,
we use the tree space coordinate of the BHV metric, but technically this is
not the tree space defined by the BHV metric.

Figure 7: The tree topologies for the ends of the tropical line segment are
$((1,2),(3,4))$ and $(((1,2),3),4)$ in Example 8.

###### Definition 8

Suppose we have an equidistant phylogenetic tree $T$ with the leave set $X$
and the ultrametric $u=(u_{12},\ldots,u_{n-1n})$. A subtree of $T$ with leaves
$X_{0}=\\{i_{1},\ldots,i_{n_{0}}\\}\subset X$, where $n_{0}\leq n$, is an
equidistant tree constructed from an ultrametric $u^{0}$ such that

$u^{0}=(u_{i_{1}i_{2}},\ldots,u_{i_{n_{0}-1}i_{n_{0}}}).$

###### Definition 9

Suppose we have an equidistant phylogenetic tree $T$ with the leave set $X$. A
clade of $T$ with leaves $X_{0}\subset X$ is an equidistant tree constructed
from $T$ by adding all common ancestral interior nodes of any combinations of
only leaves $X_{0}$ and excluding common ancestors including any leaf from
$X-X_{0}$ in $T$, and all edges in $T$ connecting to these ancestral interior
nodes and leaves $X_{0}$.

###### Remark 2

Suppose we have an equidistant phylogenetic tree $T$ with the leave set $X$. A
clade of an equidistant tree $T$ with leave set $X_{0}\subset X$ is a subtree
of $T$ with the leaves $X_{0}$.

###### Example 9

Suppose we have two equidistant trees $T_{1}$ and $T_{2}$ with the leaf set
$\\{S_{1},S_{2},S_{3},S_{4},S_{5}\\}$ shown in Fig. 8. Let
$X_{0}=\\{S_{1},S_{2},S_{3}\\}$. Suppose we have interior nodes
$\\{y_{1},y_{2},y_{3},y_{4}\\}$ for $T_{1}$ such that the root of $T_{1}$ is
$y_{4}$ and we have interior nodes $\\{y_{1},y_{2},y_{3},y_{5}\\}$ for $T_{2}$
such that the root of $T_{2}$ is $y_{3}$.

$T^{\prime}_{1}$ is a clade of $T_{1}$ with leaves $X_{0}$ since $y_{1}$ is a
common ancestor of $S_{1}$ and $S_{2}$, and $y_{2}$ is a common ancestor of
$S_{1}$, $S_{2}$ and $S_{3}$, but we exclude an interior node $y_{3}$ from
$T_{1}$ since $y_{3}$ is a common ancestor of $\\{S_{1},S_{2},S_{3},S_{4}\\}$,
where $S_{4}\not\in X_{0}$.

Similarly, $T^{\prime}_{2}$ is a clade of $T_{2}$ with leaves $X_{0}$ since
$y_{1}$ is a common ancestor of $S_{1}$ and $S_{2}$ and $y_{2}$ is a common
ancestor of $S_{1}$, $S_{2}$ and $S_{3}$, but we exclude an interior node
$y_{3}$ from $T_{2}$ since $y_{3}$ is a common ancestor of
$\\{S_{1},S_{2},S_{3},S_{4},S_{5}\\}$, where $S_{4},S_{5}\not\in X_{0}$.

Fig. 9 shows ultrametrics $u$ and $v$ associate with equidistant trees $T_{1}$
and $T_{2}$, respectively. Then $u^{0}$ and $v^{0}$ are ultrametrics of clades
of $T_{1}$ and $T_{2}$, respectively, with leaves $X_{0}$.

Figure 8: Example of clades in equidistant trees written in Example 9. Figure
9: Example of ultrametrics of clades in equidistant trees written in Example
9.

Now we consider the tropical line segment with two trees which share that same
tree topology of their clades with leaves $X_{0}\subset X$. In order to see
how tree topologies change over the tropical line segment when these two trees
share that same tree topology of their clades with leaves $X_{0}\subset X$, we
let

$(\operatorname*{arg\,max})^{i}\\{x\\}$

be the set of indices of entries of $x$ achieving the $i$th largest value
among entries of a vector $x$. Then, we have the following lemma.

###### Lemma 2

Suppose we have equidistant trees $T_{1}$ and $T_{2}$ with their ultrametrics
$u^{1}$ and $u^{2}$, respectively. If

$(\operatorname*{arg\,max})^{i}\\{u^{1}\\}=(\operatorname*{arg\,max})^{i}\\{u^{2}\\}$

for all $0<i<e$, then $T_{1}$ and $T_{2}$ have the same tree topology.

###### Proof

Suppose we have

$(\operatorname*{arg\,max})^{i}\\{u^{1}\\}=(\operatorname*{arg\,max})^{i}\\{u^{2}\\}$

for all $0<i<e$. Then we have

$\operatorname*{arg\,max}\\{u^{1}_{ij},u^{1}_{ik},u^{1}_{jk}\\}=\operatorname*{arg\,max}\\{u^{2}_{ij},u^{2}_{ik},u^{2}_{jk}\\}$

where $i,j,k\in X$ are distinct labels of leaves in $T_{1}$ and $T_{2}$.
Therefore, $T_{1}$ and $T_{2}$ have the same tree topologies by Theorem 1 in
Yoshida .

###### Theorem 8

Suppose $T_{1}$, $T_{2}$ are equidistant trees on $n=|X|$ leaves and $X_{0}$
is a subset of leaves $X$ which forms a clade in both $T_{1}$ and $T_{2}$,
with the same tree topology in $T_{1}$, $T_{2}$. Then for any tree $T$ on the
tropical line segment from $T_{1}$ to $T_{2}$, $X_{0}$ is also a clade of $T$
with the same tree topology as in $T_{1}$, $T_{2}$.

###### Proof

Let $u=(u_{11},u_{12},\ldots,u_{n-1n})$ and
$v=(v_{11},v_{12},\ldots,v_{n-1n})$ be ultrametrics associated to $T_{1}$ and
$T_{2}$, respectively. Let $w=u\odot\alpha\oplus v$ be an ultrametric for any
tree $T$ on the tropical line segment from $u$ to $v$.

  1. 1.

The restriction of $T_{1}$ to the leaves $X_{0}$ is again an equidistant tree.

###### Proof

This is shown in Definition 9.

  2. 2.

$X_{0}$ is a clade of $T$.

###### Proof

A clade is the collection of all descendant leaves of an internal vertex.
$X_{0}$ is a clade of $T$ if for any $i,j\in X_{0}$ and $k\notin X_{0}$, we
have

$w_{ij}<w_{ik}=w_{jk}.$

By definition of $w$,

$w_{ij}=\max(u_{ij}+\alpha,v_{ij}),$ $w_{ik}=\max(u_{ik}+\alpha,v_{ik}).$

Since $X_{0}$ forms a clade in $T_{1}$ and $T_{2}$ by assumption,
$v_{ij}<v_{ik}$ and $u_{ij}+\alpha<u_{ik}+\alpha$, so $w_{ij}<w_{ik}$. This
proves that $X_{0}$ forms a clade in every intermediate tree $w$.

  3. 3.

$T|_{X_{0}}$ has the same tree topology as $T_{1}|_{X_{0}}$ and
$T_{2}|_{X_{0}}$.

###### Proof

Let $i,j,k\in X_{0}$, and without loss of generality, say

$\max(u_{ij},u_{ik},u_{jk})=u_{ik}=u_{jk},$
$\max(v_{ij},v_{ik},v_{jk})=v_{ik}=v_{jk}$

(since we assume that $u$, $v$ have the same tree topology when restricted to
$X_{0}$, we know that the indices achieving the max are the same). By
definition of $w$, we have

$w_{ij}=\max(u_{ij}+\alpha,v_{ij}),$ $w_{ik}=\max(u_{ik}+\alpha,v_{ik}),$
$w_{jk}=\max(u_{jk}+\alpha,v_{jk}).$

We want to show that

$w_{ij}\leq w_{ik}=w_{jk}$

with equality if and only if $u_{ij}=u_{ik}=u_{jk}=v_{ij}=v_{ik}=v_{jk}$
Define:

$\lambda_{1}=v_{ij}-u_{ij},$ $\lambda_{2}=v_{ik}-u_{ik}=v_{jk}-u_{jk}.$

There are four cases to consider:

    1. (a)

Case 1: $\lambda_{1},\lambda_{2}>\alpha$. In this case, $w=v$, and we are
done.

    2. (b)

Case 2: $\lambda_{1}\geq\alpha\geq\lambda_{2}$. In this case,

$\displaystyle w_{ij}$
$\displaystyle=\max(u_{ij}+\alpha,v_{ij})=u_{ij}+\alpha,$ $\displaystyle
w_{ik}$ $\displaystyle=\max(u_{ik}+\alpha,v_{ik})=v_{ik},$ $\displaystyle
w_{jk}$ $\displaystyle=\max(u_{jk}+\alpha,v_{jk})=v_{jk}.$

Then

$w_{ij}=u_{ij}+\alpha\leq u_{ik}+\alpha\leq v_{ik}=v_{jk}=w_{ik}=w_{jk}$

and the leftmost inequality is strict if $u_{ij}<u_{ik}=u_{jk}$, so we are
done.

    3. (c)

Case 3: $\lambda_{2}\geq\alpha\geq\lambda_{1}$. In this case,

$\displaystyle w_{ij}$ $\displaystyle=\max(u_{ij}+\alpha,v_{ij})=v_{ij},$
$\displaystyle w_{ik}$
$\displaystyle=\max(u_{ik}+\alpha,v_{ik})=u_{ik}+\alpha,$ $\displaystyle
w_{jk}$ $\displaystyle=\max(u_{jk}+\alpha,v_{jk})=u_{jk}+\alpha.$

Then

$w_{ij}=v_{ij}\leq u_{ij}+\alpha<u_{ik}+\alpha=u_{jk}+\alpha=w_{ik}=w_{jk}$

and the rightmost inequality is strict if $u_{ij}<u_{ik}=u_{jk}$, so we are
done.

    4. (d)

Case 4: $\alpha>\lambda_{1},\lambda_{2}$. In this case $w=u$, and we are done.

This completes the proof.

###### Example 10

Suppose we have equidistant trees $T_{1}$ and $T_{2}$ from Example 9. Then,
the tropical line segment $\Gamma_{T_{1},T_{2}}$ is shown in Fig. 10. The tree
topology of the clades of trees with leaves $X_{0}$ on the tropical line
segment $\Gamma_{T_{1},T_{2}}$ are the same as these of clades in $T_{1}$ and
$T_{2}$ with leaves $X_{0}$.

Figure 10: The tropical line segment $\Gamma_{T_{1},T_{2}}$ from $T_{1}$ and
$T_{2}$ shown in Fig. 8.

###### Definition 10

For a rooted phylogenetic tree, a nearest neighbor interchange (NNI) is an
operation of a phylogenetic tree to change its tree topology by picking three
mutually exclusive leaf sets $X_{1},X_{2},X_{3}\subset X$ and changing a tree
topology of the clade, possibly the whole tree, consisting with three distinct
clades with leaf sets $X_{1}$, $X_{2}$, and $X_{3}$ shown in Fig. 11. One NNI
move is one of these tree moves shown in Fig. 11.

Figure 11: A NNI move is one of these two possible moves. Triangles with label
$\\{X_{1},X_{2},X_{3}\\}$ are clades with leaves $X_{1}$, $X_{2}$, and
$X_{3}$, where $X_{1},X_{2},X_{3}\subset X$ are mutually exclusive subsets
from $X$.

###### Theorem 9

Let $T_{1},\,T_{2}$ be equidistant trees with leaves $X$ such that the tree
topology of $T_{1}$ and the tree topology of $T_{2}$ are different by only one
NNI move. Then tree topologies on $\Gamma_{T_{1},T_{2}}$ have the same tree
topology of $T_{1}$ or $T_{2}$ with possible $0$ branch lengths.

###### Proof

Suppose $T_{1},\,T_{2}$ are equidistant trees with leaves $X$ such that the
tree topology of $T_{1}$ and the tree topology of $T_{2}$ differs by only one
NNI move. By the definition of an NNI move, $T_{1},\,T_{2}$ have the same tree
topology, except clades (possible full trees) of $T_{1}$ and $T_{2}$ differ by
one NNI move shown in Fig. 11. Let $X_{0}=X_{1}\cup X_{2}\cup X_{3}$. Note
that the clade $T^{\prime}_{1}$ with leaves $X_{0}$ in $T_{1}$ and the clade
$T^{\prime}_{2}$ with leaves $X_{0}$ in $T_{2}$ are equidistant trees. Also
clades with leaf sets $X_{1}$, $X_{2}$, and $X_{3}$ in $T_{1}$ and clades with
leaf sets $X_{1}$, $X_{2}$, and $X_{3}$ in $T_{2}$ are also equidistant trees.
Let $u=(u_{12},\ldots,u_{n-1n})$ be an ultrametric associated with the tree
$T_{1}$ and $v=(v_{12},\ldots,v_{n-1n})$ be an ultrametric associated with the
tree $T_{2}$. Suppose the tree topology of $T_{1}$ is the top tree topology in
Fig. 11. Then we have

$\begin{array}[]{c}u_{i_{1}j_{1}}=u_{i_{2}j_{2}}\\\
u_{i_{1}k_{1}}=u_{i_{2}k_{2}}\\\ u_{j_{1}k_{1}}=u_{j_{2}k_{2}}\\\ \end{array}$

for any $i_{1},i_{2}\in X_{1}$, for any $j_{1},j_{2}\in X_{2}$, and for any
$k_{1},k_{2}\in X_{3}$ since the subtree consisting of $X_{1}$ and $X_{3}$ is
also a clade so that it is also an equidistant tree with the root which is the
most recent common ancestor of $X_{1}$ and $X_{3}$. Thus they also satisfy the
condition of ultrametrics such that

$\begin{array}[]{c}u_{i^{\prime}k^{\prime}}\leq u_{i^{\prime}j^{\prime}}\\\
u_{i^{\prime}k^{\prime}}\leq u_{j^{\prime}k^{\prime}}\\\
u_{i^{\prime}j^{\prime}}=u_{j^{\prime}k^{\prime}}\\\ \end{array}$

for any $i^{\prime}\in X_{1}$, for any $j^{\prime}\in X_{2}$, and for any
$k^{\prime}\in X_{3}$.

If the tree topology of $T_{2}$ is the left bottom in Fig. 11, then

$\begin{array}[]{c}v_{i_{1}j_{1}}=v_{i_{2}j_{2}}\\\
v_{i_{1}k_{1}}=v_{i_{2}k_{2}}\\\ v_{j_{1}k_{1}}=v_{j_{2}k_{2}}\\\ \end{array}$

for any $i_{1},i_{2}\in X_{1}$, for any $j_{1},j_{2}\in X_{2}$, and for any
$k_{1},k_{2}\in X_{3}$ since the subtree consisting of $X_{1}$ and $X_{2}$ is
also a clade so that it is also an equidistant tree with the root which is the
most recent common ancestor of $X_{1}$ and $X_{2}$. Thus they also satisfy the
condition of ultrametrics such that

$\begin{array}[]{c}v_{i^{\prime}j^{\prime}}\leq v_{i^{\prime}k^{\prime}}\\\
v_{i^{\prime}j^{\prime}}\leq v_{j^{\prime}k^{\prime}}\\\
v_{i^{\prime}k^{\prime}}=v_{j^{\prime}k^{\prime}}\\\ \end{array}$

for any $i^{\prime}\in X_{1}$, for any $j^{\prime}\in X_{2}$, and for any
$k^{\prime}\in X_{3}$.

Similarly, if the tree topology of $T_{2}$ is the right bottom in Fig. 11,
then

$\begin{array}[]{c}v_{i_{1}j_{1}}=v_{i_{2}j_{2}}\\\
v_{i_{1}k_{1}}=v_{i_{2}k_{2}}\\\ v_{j_{1}k_{1}}=v_{j_{2}k_{2}}\\\ \end{array}$

for any $i_{1},i_{2}\in X_{1}$, for any $j_{1},j_{2}\in X_{2}$, and for any
$k_{1},k_{2}\in X_{3}$ since the subtree consisting of $X_{2}$ and $X_{3}$ is
also a clade so that it is also an equidistant tree with the root which is the
most recent common ancestor of $X_{2}$ and $X_{3}$. Thus they also satisfy the
condition of ultrametrics such that

$\begin{array}[]{c}v_{j^{\prime}k^{\prime}}\leq v_{i^{\prime}k^{\prime}}\\\
v_{j^{\prime}k^{\prime}}\leq v_{i^{\prime}j^{\prime}}\\\
v_{i^{\prime}j^{\prime}}=v_{i^{\prime}k^{\prime}}\\\ \end{array}$

for any $i^{\prime}\in X_{1}$, for any $j^{\prime}\in X_{2}$, and for any
$k^{\prime}\in X_{3}$.

Therefore, we set dummy leaves $\\{i,j,k\\}$ such that

$\begin{array}[]{c}u_{ij}=u_{i_{1}j_{1}}=u_{i_{2}j_{2}}\\\
u_{ik}=u_{i_{1}k_{1}}=u_{i_{2}k_{2}}\\\
u_{jk}=u_{j_{1}k_{1}}=u_{j_{2}k_{2}}\\\ \end{array}$

and

$\begin{array}[]{c}v_{ij}=v_{i_{1}j_{1}}=v_{i_{2}j_{2}}\\\
v_{ik}=v_{i_{1}k_{1}}=v_{i_{2}k_{2}}\\\
v_{jk}=v_{j_{1}k_{1}}=v_{j_{2}k_{2}}\\\ \end{array}$

then we have

$\begin{array}[]{c}u_{ik}\leq u_{ij}\\\ u_{ik}\leq u_{jk}\\\ u_{ij}=u_{jk}.\\\
\end{array}$

If the tree topology of $T_{2}$ is the left bottom in Fig. 11, then

$\begin{array}[]{c}v_{ij}\leq v_{ik}\\\ v_{ij}\leq v_{jk}\\\ v_{ik}=v_{jk}.\\\
\end{array}$

If the tree topology of $T_{2}$ is the right bottom in Fig. 11, then

$\begin{array}[]{c}v_{jk}\leq v_{ij}\\\ v_{jk}\leq v_{ik}\\\ v_{ij}=v_{ik}.\\\
\end{array}$

These reduce to the trees with three leaves $\\{i,j,k\\}$. Therefore, by
applying Lemma 1, we have the result.

###### Example 11

Consider $T_{1}$ and $T_{2}$ in Example 9. Then, let
$X_{1}=\\{S_{1},S_{2},S_{3}\\}$, $X_{2}=\\{S_{5}\\}$ and $X_{3}=\\{S_{4}\\}$.
Then we notice that

$u_{S_{1}S_{4}}=u_{S_{2}S_{4}}=u_{S_{3}S_{4}}=3.8,$

and

$u_{S_{1}S_{5}}=u_{S_{2}S_{5}}=u_{S_{3}S_{5}}=4.0.$

Also

$v_{S_{1}S_{4}}=v_{S_{2}S_{4}}=v_{S_{3}S_{4}}=4.0,$

and

$v_{S_{1}S_{5}}=v_{S_{2}S_{5}}=v_{S_{3}S_{5}}=4.0.$

Then we introduce a leaf $i$ such that

$u_{iS_{4}}:=u_{S_{1}S_{4}}=u_{S_{2}S_{4}}=u_{S_{3}S_{4}}=3.8,$
$u_{iS_{5}}:=u_{S_{1}S_{5}}=u_{S_{2}S_{5}}=u_{S_{3}S_{5}}=4.0,$
$v_{iS_{4}}:=v_{S_{1}S_{4}}=v_{S_{2}S_{4}}=v_{S_{3}S_{4}}=4.0,$

and

$v_{iS_{5}}=v_{S_{1}S_{5}}=v_{S_{2}S_{5}}=v_{S_{3}S_{5}}=4.0.$

Then we can reduce the tree with five leaves
$\\{S_{1},S_{2},S_{3},S_{4},S_{5}\\}$ to the tree with three leaves
$\\{i,S_{4},S_{5}\\}$.

##  5 Discussion

This paper is the first step toward understanding combinatorics of tree
topologies along a tropical line segment between equidistant trees with $n$
leaves. There is still so much work to be done in order to understand outputs
of statistical learning models using tropical geometry over the space of
equidistant trees with $n$ leaves $X$. It is still an open problem that we can
generalize Theorem 9. More specifically, we have the following conjecture:

###### Conjecture 10

Suppose we have a tropical line segment $\Gamma_{T_{1},T_{2}}$ between
equidistant trees $T_{1},T_{2}$ with $n$ leaves $X$. Then given tree
topologies of $T_{1},T_{2}$, the tree topology changes according to a sequence
of NNI moves from $T_{1}$ to $T_{2}$ along the tropical line segment
$\Gamma_{T_{1},T_{2}}$.

###### Acknowledgements.

R.Y. is partially supported by NSF (DMS 1916037). Also the author thank the
editor and referees for improving this manuscript.

## References

  * (1) Akian, M., Gaubert, S., Viorel, N., Singer, I.: Best approximation in max-plus semimodules.  Linear Algebra Appl. 435, 3261–3296 (2011)
  * (2) Ardila, F., Klivans, C.J.: The Bergman complex of a matroid and phylogenetic trees. journal of combinatorial theory.  Series B 96(1), 38–49 (2006)
  * (3) Billera, L.J., Holmes, S.P., Vogtmann, K.: Geometry of the space of phylogenetic trees.  Advances in Applied Mathematics 27(4), 733–767 (2001)
  * (4) Buneman, P.: A note on the metric properties of trees.  Journal of Combinatorial Theory, Series B 17(1), 48–50 (1974)
  * (5) Cardona, G., Rosselló, F., Valiente, G.: Extended Newick: it is time for a standard representation of phylogenetic networks.  BMC Bioinformatics 9(532) (2008)
  * (6) Cohen, G., Gaubert, S., Quadrat, J.: Duality and separation theorems in idempotent semimodules.  Linear Algebra Appl. 379, 395–422 (2004)
  * (7) Garba, M., Nye, T., Lueg, J., Huckemann, S.F.: Information geometry for phylogenetic trees.  J. Math. Biol. 82(19) (2021).  Https://doi.org/10.1007/s00285-021-01553-x
  * (8) Garba, M.K., Nye, T.M.W., Boys, R.J.: Probabilistic Distances Between Trees.  Systematic Biology 67(2), 320–327 (2017).  DOI 10.1093/sysbio/syx080.  URL https://doi.org/10.1093/sysbio/syx080
  * (9) Lin, B., Sturmfels, B., Tang, X., Yoshida, R.: Convexity in tree spaces.  SIAM Discrete Math 3, 2015–2038 (2017)
  * (10) Maclagan, D., Sturmfels, B.: Introduction to Tropical Geometry, vol. 161.  American Mathematical Soc. (2015)
  * (11) Maddison, W.: Gene trees in species trees.  Systematic Biology 46(3), 523–536 (1997)
  * (12) Monod, A., Lin, B., Yoshida, R.: Tropical geometric variation of tree shapes (2020).  Available at https://arxiv.org/pdf/2010.06158.pdf
  * (13) Monod, A., Lin, B., Yoshida, R., Kang, Q.: Tropical geometry of phylogenetic tree space:a statistical perspective (2019).  Available at https://arxiv.org/pdf/1805.12400.pdf
  * (14) Nye, T.M.W.: Principal components analysis in the space of phylogenetic trees.  Ann. Stat. 39(5), 2716–2739 (2011)
  * (15) Page, R., Yoshida, R., Zhang, L.: Tropical principal component analysis on the space of phylogenetic trees.  Bioinformatics 36(17), 4590–4598 (2020).  DOI 10.1093/bioinformatics/btaa564.  URL https://doi.org/10.1093/bioinformatics/btaa564
  * (16) Speyer, D., Sturmfels, B.: Tropical mathematics.  Mathematics Magazine 82, 163–173 (2009)
  * (17) Sturmfels, B., Pachter, L.: Tropical geometry of statistical models.  Proceedings of the National Academy of Sciences 101, 16132–16137 (2004)
  * (18) Tang, X., Wang, H., Yoshida, R.: Tropical support vector machines and its applications to phylogenomics (2020).  Available at https://arxiv.org/abs/2003.00677
  * (19) Yoshida, R.: Tropical balls and its applications to k nearest neighbor over the space of phylogenetic trees.  Mathematics 9(7), 779 (2021)
  * (20) Yoshida, R.: Tropical data science over the space of phylogenetic trees.  In: The Lecture Notes in Networks and Systems series, chap. 26, p. To appear. Springer, Oxford (2021)
  * (21) Yoshida, R., Zhang, L., Zhang, X.: Tropical principal component analysis and its application to phylogenetics.  arXiv preprint arXiv:1710.02682 (2017)
  * (22) Zwiernik, P., Smith, J.Q.: Tree cumulants and the geometry of binary tree models.  Bernoulli 18(1), 290–321 (2012).  URL http://www.jstor.org/stable/23238597

Author, Article title, Journal, Volume, page numbers (year) Author, Book
title, page numbers. Publisher, place (year)