# Efficient Approaches to the Mixture Distance Problem
## 2 Mixture Distance Metric  
A tree \(T=(V(T),E(T))\) is a connected and acyclic graph with a node set \(V(T)\) and an edge set \(E(T)\). \(T\) is a rooted tree if exactly one node of \(T\) has been designated the root. A node \(v\in V(T)\) is a leaf if it has no child; otherwise, \(v\) is an internal node. A node \(v\in V(T)\) is called in level \(i\), denoted by \(level(v)=i\), which means the number of edges on the path between the root and \(v\) is \(i\). Let \(L(T)\) denote a subset of node set \(V(T)\), where each member is a leaf in \(T\) and \(n=|L(T)|\). Let \(height(T)\) denote the height of tree \(T\), which is \(\max\{level(v)|v\in L(T)\}\). \(T\) is a full binary tree if each node of \(T\) either has two children or it is a leaf. A complete binary tree is a full binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. Let \(h_{1}=height(T_{1})\), \(h_{2}=height(T_{2})\). For a mixture tree \(T\), each leaf is associated with a species, and every internal node \(v\) is associated with a mutation time \(m_{T}(v)\) that represents the time when a mutation event occurs on the species node. In fact, the mutation time of an internal node in a mixture tree can be regarded as the distance between the node and any leaf of its descendants. Any two mixture trees \(T_{1}\) and \(T_{2}\) are comparable if \(L(T_{1})=L(T_{2})\). Throughout this paper, a tree refers to a rooted full binary tree and each internal node of the tree is associated with its mutation time, if not mentioned particularly. Given any two nodes \(u,v\in V(T)\), the least common ancestor or lowest common ancestor (abbreviated LCA) of \(u\) and \(v\) is an ancestor of both \(u\) and \(v\) with the smallest mutation time. (It is also called the most recent common ancestor (abbreviated MRCA), or the last common ancestor (abbreviated LCA) in biology and genealogy.) Let \(P_{T}(u,v)\) denote the mutation time \(m_{T}(w)\) of the LCA \(w\) of two leaves \(u\) and \(v\) in \(T\). The mixture distance metric, a metric for the mixture tree, is formally defined as follows. The mixture distance between two comparable mixture trees \(T_{1}\) and \(T_{2}\), denoted by \(d_{m}(T_{1},T_{2})\), is defined as the sum of difference of the mutation times with respect to the LCAs of any two leaves in \(T_{1}\) and \(T_{2}\). That is, \(d_{m}(T_{1},T_{2})=\sum_{u,v\in L(T_{1})=L(T_{2})}|P_{T_{1}}(u,v)-P_{T_{2}}(u,v)|\). The significance of the mixture distance metric is to measure the similarity between two mixture trees, considering the mutation times (molecular clock) and mutation sites simultaneously. The study sought to develop two algorithms for efficiently computing the mixture distance between two comparable mixture trees. Before we go into the algorithms, three properties of the mixture distance metric are demonstrated. [PERSON] [20] derived three mathematical properties--reflexivity, symmetry and triangle inequality--required for a well-defined metric. We show that the mixture distance is well-defined in Theorem 1. Theorem 1: _The mixture distance \(d_{m}\) satisfies:_  
1. _Reflexivity: for any two comparable mixture trees_ \(T_{1}\) _and_ \(T_{2}\)_,_ \(d_{m}(T_{1},T_{2})=0\) _if and only if_ \(T_{1}\) _and_ \(T_{2}\) _are identical._
2. _Symmetry: for any two comparable mixture trees_ \(T_{1}\) _and_ \(T_{2}\)_,_ \(d_{m}(T_{1},T_{2})=d_{m}(T_{2},T_{1})\)_Triangle inequality: for any three comparable mixture trees \(T_{1}\), \(T_{2}\) and \(T_{3}\), \(d_{m}(T_{1},T_{2})+d_{m}(T_{2},T_{3})\geq d_{m}(T_{1},T_{3})\)._  
Proof. : 1. Due to \(T_{1}=T_{2}\), for any two nodes \(u,v\in L(T_{1})=L(T_{2})\), we have \(P_{T_{1}}(u,v)=P_{T_{2}}(u,v)\). Therefore, \(d_{m}(T_{1},T_{2})=0\) can be concluded. On the other hand, if \(d_{m}(T_{1},T_{2})=0\) for any two comparable mixture trees \(T_{1}\) and \(T_{2}\). We have \(P_{T_{1}}(u,v)-P_{T_{2}}(u,v)\) for any \(u,v\in L(T_{1})=L(T_{2})\) by the definition. Then we can prove \(T_{1}=T_{2}\) by induction on the height of \(T_{1}\) (or \(T_{2}\)). 2.