## 2 The Maximum Contact Map Overlap Metric  
We focus here on the notions of contact map overlap (CMO) and the related max-CMO distance between protein structures. A contact map describes the structure of a protein \(P\) in terms of a simple, undirected graph \(G=(V,E)\) with vertex set \(V\) and edge set \(E\). The vertices of \(V\) are linearly ordered and correspond to the sequence of residues of \(P\). Edges denote residue contacts, that is pairs of residues that are close to each other. More precisely, there is an edge \((i,j)\) between residues \(i\) and \(j\) iff the Euclidean distance in the protein fold is smaller than a given threshold. The size \(|G|:=|E|\) of a contact map is the number of its contacts. Given two contact maps \(G_{1}(V,E_{1})\) and \(G_{2}(U,E_{2})\) for two protein structures, let \(I=(i_{1},i_{2},\ldots,i_{m})\) and \(J=(j_{1},j_{2},\ldots,j_{m})\) be subsets of \(V\) and \(U\), respectively, respecting the linear order. Vertex sets \(I\) and \(J\) encode an alignment of \(G_{1}\) and \(G_{2}\) in the sense that vertex \(i_{1}\) is aligned to \(j_{1}\), \(i_{2}\) to \(j_{2}\), and so on. In other words, the alignment \((I,J)\) is a one-to-one mapping between the sets \(V\) and \(U\). Given an alignment \((I,J)\), a shared contact (or common edge) occurs if both \((i_{k},i_{l})\in E_{1}\) and \((j_{k},j_{l})\in E_{2}\) exist. We say in this case that the shared contact \((i_{k},i_{l})\) is activated by the alignment \((I,J)\)The maximum contact map overlap problem consists of finding an alignment \((I^{*},J^{*})\) that maximizes the number of shared contacts, and \(\mathrm{CMO}(G_{1},G_{2})\) denotes then this maximum number of shared contacts between the contact maps \(G_{1}\) and \(G_{2}\); see Figure 1.  
Computing \(\mathrm{CMO}(G_{1},G_{2})\) is NP-hard following from [18]. Nevertheless, maximum contact map overlap has been shown to be a meaningful way for comparing two protein structures [5, 6, 7, 8, 9, 10, 11]. Previously, several distances have been proposed based on the maximum contact map overlap, for example \(D_{\mathrm{min}}\)[5, 7] and \(D_{\mathrm{sum}}\)[6, 8, 11] with:  
\[D_{\mathrm{min}}(G_{1},G_{2})=1-\frac{\mathrm{CMO}(G_{1},G_{2})}{\min\{|E_{1} |,|E_{2}|\}}\text{ and }D_{\mathrm{sum}}(G_{1},G_{2})=1-\frac{2\mathrm{CMO}(G_{1},G_{2})}{|E_{1}|+ |E_{2}|}\]  
Note that \(D_{\mathrm{min}}\) and \(D_{\mathrm{sum}}\) have been normalized, so that their values are in the interval \([0,1]\) and are, thus, measures of similarity between proteins. However, they are not metrics, as the next lemma shows. **Lemma 1**. : _Distances \(D_{\mathrm{min}}\) and \(D_{\mathrm{sum}}\) do not satisfy the triangle inequality._  
Proof. : Consider the contact map graphs \(G_{1},\ldots,G_{4}\) in Figure 2. It is easily seen that \(\mathrm{CMO}(G_{1},G_{2})=1,\mathrm{CMO}(G_{2},G_{3})=3\) and \(\mathrm{CMO}(G_{1},G_{3})=3\). We then obtain:  
\[D_{\mathrm{sum}}(G_{1},G_{2})=1-\frac{2}{|E_{1}|+|E_{2}|}=1-\frac{2}{6}=\frac {2}{3}\]  
\[D_{\mathrm{sum}}(G_{2},G_{3})=1-\frac{6}{|E_{2}|+|E_{3}|}=1-\frac{6}{8}=\frac {1}{4}\]  
\[D_{\mathrm{sum}}(G_{1},G_{3})=1-\frac{6}{|E_{1}|+|E_{3}|}=1-\frac{6}{8}=\frac {1}{4}\]  
Hence:  
\[D_{\mathrm{sum}}(G_{1},G_{3})+D_{\mathrm{sum}}(G_{3},G_{2})=\frac{1}{2}<\frac {2}{3}=D_{\mathrm{sum}}(G_{1},G_{2})\]  
Furthermore, \(\mathrm{CMO}(G_{2},G_{4})=1\) and \(\mathrm{CMO}(G_{3},G_{4})=2\). We then obtain:  
\[D_{\mathrm{min}}(G_{2},G_{4})=1-\frac{\mathrm{CMO}(G_{2},G_{4})}{\min\{|E_{2} |,|E_{4}|\}}=1-\frac{1}{3}=\frac{2}{3}\]  
Figure 1: The alignment visualized with dashed lines \(((v_{1}\leftrightarrow u_{1})(v_{2}\leftrightarrow u_{2})(v_{3}\leftrightarrow u _{4})(v_{4}\leftrightarrow u_{5}))\) maximizes the number of the common edges between the graphs \(G_{1}\) and \(G_{2}\). The four activated common edges are emphasized in bold (_i.e._, \(\mathrm{CMO}(G_{1},G_{2})=4\)).