## 4 Experimental Setup
For obtaining the latter, we use our Lagrangian solver A_purva [8] (see also [[https://www.irisa.fr/symbiose/software](https://www.irisa.fr/symbiose/software)]([https://www.irisa.fr/symbiose/software](https://www.irisa.fr/symbiose/software)), as well as [[http://csa.project.cwi.nl/](http://csa.project.cwi.nl/)]([http://csa.project.cwi.nl/](http://csa.project.cwi.nl/))), which reads PDB files, constructs contact maps and returns (bounds on) the contact map overlap. Using corresponding distance bounds, we determined the family representative according to Equation (4). The complexity of this step is \(\sum_{\forall\mathcal{F}\in\mathcal{C}}|\mathcal{F}|^{2}\), where \(|\mathcal{F}|\) denotes the number of the members of the family \(\mathcal{F}\). Note that this step is query independent and is performed as a preprocessing. For every pairwise distance computation, we used a maximum time limit of \(10\) s. Since most comparisons were computed optimally, the average run time is approximately \(2\) s.  
For every query, the \(k=10\) nearest neighbor structures from SCOPCath and extended SCOPCath, respectively, were computed using our \(k\)-NN Algorithm 1. The algorithm is a two-step procedure. First, it improves bounds by applying several rounds of triangle dominance, for which the alignment from query to representatives is computed, and second, it switches to pairwise dominance, for which the alignment to any remaining target is computed. In the first step, query representative alignments are computed using an initial time limit of \(\tau=1\) s; then, triangle dominance is applied to all targets, and the algorithm iterates with the time limit doubled until a termination criterion is met. This way, bounds on query target distances are improved successively. Since the query is compared uniquely with the family representative, only \(\sum_{\forall\mathcal{F}\in\mathcal{C}}1\) alignments are needed at each iteration. The computation of triangle dominance terminates if any of the following holds: (i) \(k\) targets are left; (ii) all query-representative distances have been computed optimally or with a time limit of \(32\) CPU seconds; (iii) the number of targets did not reduce from one round to the next. Pairwise dominance terminates if any of the following holds: (i) \(k\) targets are left; (ii) all remaining targets belong to the same superfamily; (iii) all query-target distances have been computed with a time limit of \(32\) CPU seconds. The query is then assigned to the superfamily to which the majority of the \(k\)-nearest neighbors belongs. In cases in which the pairwise dominance terminates with more than \(k\) targets or more than one superfamily remains, the exact \(k\)-nearest neighbors are not known. In that case, we order the targets based on the upper bound distance to the query and assign the superfamily using the top ten queries. In the case that there is a tie among the superfamilies to which the top ten targets belong, we report this situation. We compare our exact \(k\)-NN classifier with respect to classification accuracy with \(k\)-NN classification using TM-align [17] (Version 20130511). TM-align is a widely-used, fast structure alignment heuristic, which the authors, amongst others, applied for fold classification. TM-align alignments further were shown to have high accuracy with respect to manually-curated reference alignments [23, 24]. Using TM-align, we align each query to all targets of the same class and compute the corresponding TM-score. The targets are then ranked based on TM-score (normalized with respect to query), and the superfamily that most of the \(k\) nearest neighbors belong to is assigned. In order to investigate the impact of \(k\) on classification accuracy, we additionally decreased \(k\) from nine to one, using each time the \(k+1\) nearest neighbors from the classification result for \(k+1\).