## 6 Discussion  
The difficulty to optimally compute a superfamily assignment using \(k\)-NN increases with the dissimilarity of the \(k\)-th closest target and the query, because this target determines the domination bound, and this bound becomes weaker when \(k\) increases. This can be observed in the different number of exactly-assigned queries between SCOPCath and extended SCOPCath, on the one hand, and for different \(k\), on the other hand. Since SCOPCath has been filtered for low sequence identity, we can expect that the \(k\)-th neighbor is less similar to the query than the \(k\)-th neighbor in extended SCOPCath, and therefore, it is easier to compute extended SCOPCath exactly. Accordingly, the number of exactly-assigned queries tends to increase with decreasing \(k\). In future work, we may use such properties of the distance bounds to decide which \(k\) is most appropriate for a given query. Our exact classification is based on a well-known property of exact CMO computation: similar structures are quick to align and are usually computed exactly, whereas dissimilar structures are extremely slow to align and usually not exactly. Therefore, we remove dissimilar structures early using bounds. Distances between similar structures can then be computed (near-)optimal, and the resulting \(k\)-NN classification is exact. Except for the case \(k=1\) on the extended benchmark, in terms of assignment accuracy, TM-align performs slightly better than max-CMO, and it usually has to some extent fewer ties. On the other hand, both max-CMO and TM-align perform best in the case \(k=1\), and for that most relevant case, the two methods have the same accuracy. Considering that max-CMO is a metric and, thus, needs to compare structures globally, while TM-align is not, it still allows one to perform very accurate superfamily assignment. While for the extended benchmark, max-CMO and TM-align have the same number of correct classifications for the best choice of value for \(k\), the somewhat better performance of TM-align in the other cases indicates that the max-CMO method could be further improved. A possible disadvantage of our metric is that it does not apply proper length normalization. For instance, if a protein structure is identical to a substructure of another protein, the corresponding max-CMO distance depends on the length of the longer protein. For classification purposes, it would usually be better to rank a protein with such local similarity higher than another protein that is less similar, but of smaller length. Moreover, although the current results suggest that, in terms of assignment accuracy, using only the nearest neighbor for classification works best, finding the \(k\)-nearest neighbor structures is still interesting and important. A new query structure is in need of being characterized, and the set of \(k\) closest structures from a given classification gives a useful description on its location in structure space, especially if this space is metric. Note that, besides using the presented algorithm for determining the \(k\)-nearest neighbors, it could straightforwardly also be used to find all structures within a certain distance threshold of a given query. We show that our approach is beneficial for handling large datasets, the structures of which form clusters in some metric space, because it can quickly discard dissimilar structures using metric properties, such as triangle inequality. This way, the target dataset does not need to be reduced previously using a different distance measure, such as sequence similarity, which can lead to mistakes. Our classification is at all times based exclusively on structural distance. Among the disadvantages of a heuristic approach for the task of large-scale structure classification, we can point to the observation that the obtained classifications are not stable. As versions of tools or random seeds change, the distance between structures may change, since the provable distance between two structures is not known.