## 4 Experimental Setup  
We evaluated the classification performance and efficiency of different types of dominance of our algorithm on domains from SCOPCath [22], a benchmark that consists of a consensus of the two major structural classifications SCOP [1] (Version 1.75) and Cath [2] (Version 3.2.0). We use this consensus benchmark in order to obtain a gold standard classification that very likely reflects structural similarities that are detectable automatically, since two classifications, each using a mix of expert knowledge and automatic methods, agree in their superfamily assignments. For generating SCOPCath, the intersection of SCOP and Cath has been filtered, such that SCOPCath only contains proteins with less than 50% sequence identity. Since this results in a rather small benchmark with only \(6759\) structures, we added these filtered structures for our evaluation in order to have a much larger, extended version of the benchmark, which is representative of the overlap between the existing classifications SCOP and Cath. There were \(264\) domains in extended SCOPCath that share more than 50% sequence similarity with a domain in SCOPCath, but do not both belong to the same SCOP family; since their families are perhaps not in SCOPCath and their classification in SCOP and Cath may not agree, we removed them. This way, we obtained \(60,850\) additional structures (_i.e._, the extended benchmark is composed of \(67,609\) structures). These belong to \(1348\) superfamilies and \(2480\) families, of which \(2093\) families have more than one member. For SCOPCath, there are \(1156\) multi-member families. Structures and families are divided into classes according to Table 1. For superfamily assignment, we compared a structure only to structures of the corresponding class, since class membership can in most cases be determined automatically, for example by a program that computes secondary structure content. In rare cases where class membership is unclear, one could combine the target structures of possible classes before classification. The four major protein classes are labeled from a to d and refer to: (a) all \(\alpha\) proteins, _i.e._, consisting of \(\alpha\)-helices; (b) all \(\beta\) proteins, _i.e._, consisting of \(\beta\)-sheets; (c) \(\alpha\) and \(\beta\) proteins with parallel \(\beta\) sheets, _i.e._, \(\beta\)-\(\alpha\)-\(\beta\) units; and (d) \(\alpha\) and \(\beta\) proteins with antiparallel \(\beta\) sheets, _i.e._, segregated \(\alpha\) and \(\beta\) regions. These classes are thus defined by secondary structure content and arrangement, which, in turn, is defined by class-specific contact map patterns. We therefore consider them individually when characterizing our max-CMO metric. For classification, we randomly selected one query from every family with at least six members. This resulted in \(236\) queries for SCOPCath and \(1369\) queries for the extended SCOPCath benchmark. \begin{table}
\begin{tabular}{c r r r r r r r r r r r} \hline \hline
**Class** & **a** & **b** & **c** & **d** & **e** & **f** & **g** & **h** & **i** & **j** & **k** \\ \hline \# str & 1195 & 1593 & 1774 & 1591 & 30 & 103 & 342 & 72 & 11 & 38 & 10 \\ \# ext & 10,796 & 19,215 & 17,497 & 15,679 & 349 & 1006 & 2398 & 520 & 43 & 81 & 25 \\ \# fam & 524 & 516 & 548 & 632 & 6 & 59 & 121 & 32 & 5 & 29 & 8 \\ \# sup & 303 & 266 & 191 & 375 & 6 & 52 & 82 & 31 & 5 & 29 & 8 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: For every protein class, the table lists the number of structures in SCOPCath (str) and extended SCOPCath (ext), the corresponding number of families (fam) and superfamilies (sup). We then computed all-_versus_-all distances, Equation (1), or distance bounds within each family using optimal maximum contact map overlap or the Lagrangian bound on it.