## 2 The Maximum Contact Map Overlap Metric
and:  
\[D_{\min}(G_{3},G_{4})=1-\frac{2}{3}=\frac{1}{3}\]  
as well as:  
\[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}|}\]0  
Hence,  
\[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}|}\]1  
Let \(G_{1}(V,E_{1}),G_{2}(U,E_{2})\) be two contact map graphs. We propose a new similarity measure:  
\[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}|}\]2  
The following claim states that \(D_{\max}\) is a distance (metric) on the space of contact maps, and we refer to it as the max-CMO metric. **Lemma 2**. : \(D_{\max}\) _is a metric on the space of contact maps._  
Proof. : To prove the triangle inequality for the function \(D_{\max}\), we consider three contact maps \(G_{1}(V,E_{1}),G_{2}(U,E_{2}),G_{3}(W,E_{3})\), and we want to prove that \(D_{\max}(G_{1},G_{2})+D_{\max}(G_{2},G_{3})\geq D_{\max}(G_{1},G_{3})\). We will use the fact that a similar function \(d_{max}\) on sets is a metric [19], which is defined as:  
\[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}|}\]3  
The mapping \(\mathcal{M}\) corresponding to \(\mathrm{CMO}(G_{1},G_{2})\) generates an alignment \((V^{{}^{\prime}},U^{{}^{\prime}})\), where \(V^{{}^{\prime}}\subseteq V\) and \(U^{{}^{\prime}}\subseteq U\) are ordered sets of vertices preserving the order of \(V\) and \(U\), correspondingly. Since \(\mathcal{M}\) is a one-to-one mapping, we can rename the vertices of \(U^{\prime}\) to the names of the corresponding vertices of \(V^{\prime}\) and keep the old names of the vertices of \(U\setminus U^{\prime}\). Denote the resulting ordered vertex set by \(\overline{U}\), and denote by \(\overline{E_{2}}\) the corresponding set of edges. Define the graph \(\overline{G_{2}}=(\overline{U},\overline{E_{2}})\). Note that \(|\overline{E_{2}}|=|E_{2}|\) and  
\[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}|}\]4 Four contact map graphs. any common edge discovered by \(\mathrm{CMO}(G_{1},G_{2})\) has the same endpoints (after renaming) in \(\overline{E_{2}}\) as in \(E_{1}\); hence, \(\mathrm{CMO}(G_{1},G_{2})=\mathrm{CMO}(G_{1},\overline{G_{2}})=|E_{1}\cap \overline{E_{2}}|\). Then, from Equation (2):  
\[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}|}\]5  
Similarly, we compute the mapping corresponding to \(\mathrm{CMO}(\overline{G_{2}},G_{3})\) and generate an optimal alignment \((\overline{U^{\prime}},W^{{}^{\prime}})\). As before, we use the mapping to rename the vertices of \(W^{\prime}\) to the corresponding vertices of \(\overline{U^{\prime}}\) and denote the resulting sets of vertices and edges by \(\overline{W}\) and \(\overline{E_{3}}\). Similarly to the above case, it follows that \(D_{\mathrm{max}}(G_{2},G_{3})=d_{\mathrm{max}}(\overline{E_{2}},\overline{E_{ 3}})\).