## 4 Algorithms and Experimental Results
### Bpmr
At every iteration of BPMF after choosing two trees maximizing the, the algorithm tests every possible swapping of these two trees with subtrees of each other and, then, chooses the tree with the maximum consistency of the triplets. We call this algorithm BPMTR (Best Pair Merge with Total Reconstruction). See Algorithm 2 for details of the BPMTR. ```
1:Initialize a set, \(T\), consisting of \(n\) one-node trees labeled by species. 2:while\(|T|\)\(>\)1 do
3: Find and remove two trees, \(T_{x}\), \(T_{y}\), with maximum \(e\_score\). 4: Create a new tree, \(T_{merge}\), by adding a common parent to \(T_{x}\) and \(T_{y}\)
5:\(T_{best}\) : = \(T_{merge}\)
6:for each subtree \(T_{sub}\) of \(T_{x}\)do
7: Let \(T_{swapped}\) be the tree constructed by swapping \(T_{sub}\) with \(T_{y}\)
8:if the number of consistent triplets with \(T_{swapped}\) was larger than the number of triplets consistent with \(T_{best}\)then
9:\(T_{best}\) : = \(T_{swapped}\)
10:endif
11:endfor
12:for each subtree \(T_{sub}\) of \(T_{y}\)do
13: Let \(T_{swapped}\) be the tree constructed by swapping \(T_{sub}\) with \(T_{x}\)
14:if the number of consistent triplets with \(T_{swapped}\) was larger than the number of triplets consistent with \(T_{best}\)then
15:\(T_{best}\) : = \(T_{swapped}\)
16:endif
17:endfor
18: Add \(T_{best}\) to \(T\). 19:endwhile
20:return the tree in \(T\)
```  
**Algorithm 2** BPMTR  
**Theorem 2**. : _BPMTR runs in \(O(mn^{3})\) time._  
Proof. : Step 1 takes \(O(n)\) time. In Step 2, initially, \(T\) contains \(n\) clusters, but in each iteration, two clusters merge into a cluster. Hence, the while loop in Step 2 takes \(O(n)\) time. In Step 3, \(e\_score\) is computed for every subset of \(T\) of size two. By applying [PERSON]'s preprocessing algorithm [21], which runs in \(O(n)\) time for a tree with \(n\) nodes, every LCAquery can be answered in \(O(1)\) time. Therefore, the consistency of a triplet with a cluster can be checked in \(O(1)\) time. Since there are \(m\) triplets, Step 3 takes \({|T|\choose 2}O(m)\) time. In Steps 5, 9 and 15, \(T_{best}\) is a pointer that stores the best topology found so far during each iteration of the while loop in \(O(1)\) time. The complexity analysis of the loops in Steps 6-11 and 12-17 are similar, and it is enough to consider one. Every rooted binary tree with \(n\) leaves has \(O(n)\) internal nodes, so the total number of swaps in Step 7 for any two clusters will be at most \(O(n-|T|)\). In Step 8, computing the number of consistent triplets with \(T_{swapped}\) takes no more than \(O(m)\) time. Steps 4, 7 and 18 are implementable in \(O(1)\) time. Accordingly, the running time of Steps 2-19 would be:  
\[\sum_{|T|=2}^{n}\left[m{|T|\choose 2}+O(n-|T|)+m)\right]=O(mn^{3}) \tag{1}\]  
Step 20 takes \(O(1)\) time. Hence, the time complexity of BPMTR is \(O(mn^{3})\). We tested BPMTR over randomly generated triplet sets with \(n\) = 15, 20 species and \(m\) = 500, 1,000 triplets. We experimented hundreds of times for each combination of \(n\) and \(m\). The results in Table 2 indicate that BPMTR outperforms BPMR. However, in these hundreds of tests, there were a few examples of BPMR performing better than BPMTR. For \(n\) = 30 and \(m\) = 1,000, in 62 triplet sets out of a hundred randomly generated triplet sets, BPMTR satisfied more triplets. In 34 triplet sets, BPMR and BPMTR had the same results, and in four triplet sets, BPMR satisfied more triplets.