## 5 Computational Results
### Results for SCOPCath Benchmark  
When classifying the \(236\) queries of SCOPCath, we achieve between 89% and 95% correct superfamily assignments; see Table 2. Remarkably, the highest accuracy is reached for \(k\) = 1, so here, just classifying the query as belonging to the superfamily of the nearest neighbor is the best choice. Our \(k\)-NN classification resulted for any \(k\) in a large number of ties, especially for \(k\) = 2; see Table 2. These currently unresolved ties also decrease assignment accuracy compared to \(k=1\), for which a tie is not possible. Table 2 further lists the number of queries that have been assigned, where exact denotes that the provable \(k\) nearest neighbors have been computed. The percentage of exactly-computed nearest neighbors varies between 50% and 99% and increases with decreasing \(k\). A likely reason for this is that the larger the \(k\), the weaker is the \(k\)-th distance upper bound that is used for domination, especially if the target on rank \(k\) is dissimilar to the query. Since SCOPCath domains have low sequence similarity, this is likely to happen. It is also interesting to note that there are for any \(k\) quite a few queries that have been assigned exactly, but that are nonetheless wrongly assigned; see Table 2. These are cases in which our distance metric fails in ranking the targets correctly with respect to the gold standard.  
Figure 6 displays the progress of our algorithm in terms of the percentages of removed targets. We initially compute six rounds of triangle dominance, starting with one CPU second for every query representative alignment and doubling the run time every iteration up to 32 CPU seconds. The same  
\begin{table}
\begin{tabular}{l r r r r r r r r r r} \hline \hline
**k** & **10** & **9** & **8** & **7** & **6** & **5** & **4** & **3** & **2** & **1** \\ \hline \# correct & 210 & 211 & 213 & 213 & 214 & 217 & 217 & 219 & 213 & 224 \\ \# exact & 117 & 143 & 156 & 165 & 188 & 206 & 204 & 211 & 209 & 234 \\ \# exact and correct & 110 & 134 & 149 & 155 & 178 & 198 & 195 & 205 & 206 & 224 \\ \# ties & 10 & 9 & 11 & 8 & 10 & 10 & 10 & 10 & 20 & 0 \\ \# TM-align correct & 219 & 220 & 220 & 225 & 225 & 228 & 226 & 227 & 226 & 228 \\ \# TM-align ties & 4 & 4 & 9 & 5 & 5 & 3 & 8 & 5 & 8 & 0 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Classification results showing the number of queries out of the overall \(236\) queries that have been assigned to a superfamily, the number of correct assignments, the number of assignments computed exactly, thereof the number of correct classifications and the number of ties that do not allow a superfamily assignment based on majority vote. The last two lines display the number of correct assignments and ties for \(k\)-NN classification using TM-align.  
is done in the pairwise dominance step of the algorithm, in which we compute the distance from the query to every remaining target. As shown in Figure 6, the percentage of dominated targets within each iteration varies widely between queries, which results in a large variance of run times between queries. For some queries, up to 80% of targets can be removed by just computing the distance to the family representatives using a time limit of 1 s and applying triangle dominance; for others, even after several iterations of pairwise dominance, 50% of targets remain. Overall, most queries need, after triangle dominance, several iterations of pairwise dominance before being assigned, and quite a few cannot even be assigned exactly.