## 4 Algorithms and Experimental Results
### Bpmr  
Before explaining the second heuristic algorithm, we need to review BPMF [11] and BPMR [16]. BPMF utilizes a bottom-up approach similar to hierarchical clustering. Initially, there are \(n\) trees, each containing a single node representing one of \(n\) given species. In each iteration, the algorithm computes a function, called \(e\_score\), for each combination of two trees. Furthermore, two trees with the maximum \(e\_score\) are merged into a single tree by adding a new node as the common parent of the selected trees. [PERSON] [11] introduced six alternatives for computing the \(e\_score\) using combinations of \(w\), \(p\) and \(t\). (see Table 1). However, in each run, one of the six alternatives must be used. In the function, \(e\_score(C_{1},C_{2})\), \(w\) is the number of triplets satisfied by merging \(C_{1}\) and \(C_{2}\), which is the number of triplets of the form \(ij|k\), in which \(i\) is in \(C_{1}\), \(j\) is in \(C_{2}\) and \(k\) is neither in \(C_{1}\) nor in \(C_{2}\). The value of \(p\) is the number of triplets that are in conflict with merging \(C_{1}\) and \(C_{2}\). It is the number of triplets of the form, \(ij|k\), in which \(i\) is in \(C_{1}\), \(k\) is in \(C_{2}\) and \(j\) is neither in \(C_{1}\) nor in \(C_{2}\). The value of \(t\) is the total number of triplets of the form, \(ij|k\), in which \(i\) is in \(C_{1}\)and \(j\) is \(C_{2}\). [PERSON] compared the BPMF with One-Leaf-Split and Min-Cut-Split and showed that BPMF works better on randomly generated triplet sets. He also pointed out that none of the six alternatives of \(e\_score\) is significantly better than the other. Figure 2: Output of FastTree for a dense triplet set of the yeast, _Cryptococcus gatti_, data. [PERSON] _et al._[16] introduced a modified version of BPMF, called BPMR, that outperforms the results of BPMF. BPMR works very similarly in comparison to BPMF, except for a reconstruction step used in BPMR. Suppose \(T_{x}\) and \(T_{y}\) are two trees having the maximum, \(e\_score\), at some iteration and are selected to merge into a new tree. By merging \(T_{x}\) and \(T_{y}\), some triplets will be satisfied, but some other triplets will be in conflict. Without loss of generality, suppose \(T_{x}\) has two subtrees, namely the left subtree and the right subtree. In addition, suppose a triplet, \(\textit{ij}|k\), in which \(i\) is in the left subtree of \(T_{x}\), \(k\) is in the right subtree of \(T_{x}\) and \(j\) is in \(T_{y}\). Observe that by merging \(T_{x}\) and \(T_{y}\), the mentioned triplet becomes inconsistent. However, swapping \(T_{y}\) with the right subtree of the \(T_{x}\) satisfies this triplet, while some other triplets become inconsistent. It is possible that the resulting tree of this swap satisfies more triplets than the primary tree. This is the main idea behind the BPMR. In BPMR, in addition to the regular merging of \(T_{x}\) and \(T_{y}\), \(T_{y}\) is swapped with the left and the right subtree of \(T_{x}\), and also, \(T_{x}\) is swapped with the left and the right tree of \(T_{y}\). Finally, among these five topologies, we choose the one that satisfies the most triplets. Suppose the left subtree of the \(T_{x}\) also has two subtrees. Swapping \(T_{y}\) with one of these subtrees would probably satisfy new triplets, while some old ones would become inconsistent. There are examples in which this swap results in a tree that satisfies more triplets. This forms our second heuristic idea that swapping of \(T_{y}\) with every subtree of \(T_{x}\) should be checked. \(T_{x}\) should also be swapped with every \begin{table}
\begin{tabular}{l c c c} \hline \hline
**If-Penalty** & \multicolumn{3}{c}{**Ratio Type**} \\ \hline False & w & w/(w + p) & w/t \\ True & w \(-\) p & (w \(-\) p)/(w + p) & (w \(-\) p)/t \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The six alternatives of \(e\_score\). Figure 3: A Level-2 network for a dense triplet set of the yeast, _Cryptococcus gatti_, data. subtree of \(T_{y}\).