# Efficient Approaches to the Mixture Distance Problem
## 3 An \(O(nh_{1}h_{2})\)-Time Algorithm
### Modified Algorithm  
After introducing Algorithm MixtureDistance, we can give a \(O(nh_{1}h_{2})\) computational time algorithm for computing the mixture distance between two mixture trees in the following part. In Algorithm MixtureDistance, when the leaves of the subtree rooted by an internal node \(v\) in \(T_{1}\) are colored, other leaves in \(T_{1}\) have no color, as do the mapped leaves in \(T_{2}\). That is, \(color(w)=(0,0)\) for \(w\in L(T_{2})\). However, Algorithm MixtureDistance still processes the ancestors of such leaves in \(T_{2}\). In the following, we propose an algorithm for disregarding the nodes without meaningful coloring information, and reduce the time complexity from \(O(n^{2})\) to \(O(nh_{1}h_{2})\). The algorithm contains three main stages, as follows:  
1. Rank the leaves in \(T_{1}\) and \(T_{2}\). 2. Construct a minimal subtree \(T_{2}^{\prime}\) of \(T_{2}\) involved in colored leaves with respect to node \(v\), for each internal node \(v\) in \(T_{1}\). 3. Compute the mixture distance between \(v\) and each internal node in \(T_{2}^{\prime}\). In stage 1, the nodes of \(T_{2}\) are ranked in postorder, and the leaves of \(T_{1}\) are assigned by the same rank of the mapped leaves in \(T_{2}\). In Figure 2, red numbers nearby leaves in two given comparable mixture trees \(T_{1}\) and \(T_{2}\) indicate the ranking achieved by stage 1 of the algorithm. Note that the number within the nodes means the mutation time \(m_{T_{i}}(v)\) of the associated node \(v\) for \(i=1\) or 2. The algorithm proceeds to stage 2 for each internal node \(v\) of \(T_{1}\) in the reverse order of breadth-first search. When \(v\) in \(T_{1}\) is processed, stage 2 seeks to construct a minimal subtree \(T_{2}^{\prime}\) of \(T_{2}\) involved in colored leaves with respect to node \(v\). For node \(v\), a nondecreasing list of the leaves of the subtree rooted by \(v\), denoted by \(leaf(v)\), is obtained from the leaf lists of its two children, where the leaves in the list are sorted by their ranks. Suppose that there are \(k\) ordered nodes in \(leaf(v)\), that is, \(leaf(v)=\{w_{1},w_{2},\ldots,w_{k}\}\). With the list \(leaf(v)\), the subtree \(T_{2}^{\prime}\) can be constructed as follows. Let \(lca(w_{i},w_{j})\) denote the LCA of leaves \(w_{i}\) and \(w_{j}\) in \(T_{2}\), for any \(i,j\in\{1,2,\ldots,k\}\). The subtree \(T_{2}^{\prime}=(V^{\prime},E^{\prime})\) is initialized by \(V^{\prime}=\{w_{1},w_{2},lca(w_{1},w_{2})\}\), \(E^{\prime}=\{\overline{lca(w_{1},w_{2})w_{1},\overline{lca(w_{1},w_{2})w_{2}}}\}\) and \(root=lca(w_{1},w_{2})\). For node \(w_{i}\), \(i\in\{1,2,\ldots,k-2\}\),  
\[V^{\prime}=V^{\prime}\cup\{lca(w_{i+1},w_{i+2}),w_{i+2}\}\text{ and }\]  
\[E^{\prime}=E^{\prime}\cup\{\overline{lca(w_{i+1},w_{i+2})w_{i+2}}\}\]  
Moreover, if the mutation time (the number written in the node circle) of \(lca(w_{i+1},w_{i+2})\), denoted by \(t(lca(w_{i+1},w_{i+2}))\), is larger than the mutation time of \(root\), denoted by \(t(root)\), the edge \(\overline{lca(w_{i+1},w_{i+2})root}\) is inserted into \(E^{\prime}\) and reset \(lca(w_{i+1},w_{i+2})\) as the new \(root\). Otherwise, if \(t(lca(w_{i+1},w_{i+2}))\) is smaller than the mutation time of \(lca(w_{i},w_{i+1})\), denoted by \(t(lca(w_{i},w_{i+1}))\), the edge \(\overline{lca(w_{i},w_{i+1})w_{i+1}}\) is removed from \(E^{\prime}\) and the edges \(\overline{lca(w_{i+1},w_{i+2})w_{i+1}}\) and \(\overline{lca(w_{i},w_{i+1})lca(w_{i+1},w_{i+2})}\) are inserted into \(E^{\prime}\). Otherwise, let \(x=w_{i+1}\) and repeat do \(x=father(x)\) until \(t(x)<t(lca(w_{i+1},w_{i+2}))<t(father(x))\), where \(father(x)\) is the node \(y\) such that \(\overline{yx}\in E^{\prime}\). Then the edge \(\overline{father(x)x}\) is removed from \(E^{\prime}\) and the edges \(\overline{lca(w_{i+1},w_{i+2})x}\) and \(\overline{father(x)lca(w_{i+1},w_{i+2})}\) are inserted into \(E^{\prime}\). Figure 2: An example of ranking leaves of \(T_{1}\) and \(T_{2}\). **Example 1**.