## 2 Results and Discussion
### Algorithm
To this end we compare \(D_{A}\) with \(D_{B}\) element by element:  
\[d_{ijkl}=|D_{A,ij}-D_{B,kl}|\leq\delta_{1}. \tag{2}\]  
The parameter \(\
u\) is set by the user. We have obtained good results with \(\
u=4\). The resulting pairs of atoms \(ab\) define pairs of star graphs of at least \(\
u\) edges, as shown schematically in Figure 1.  
The time complexity in this step is \(O\left(m^{2}n^{2}\right)\), since it is dominated by the number of distance difference computations given by \(\frac{1}{4}m\cdot\left(m-1\right)\cdot n\cdot\left(n-1\right)\), i.e. the number of pairs of matrix elements in the upper diagonal parts of the symmetric distance matrices \(D_{A}\) and \(D_{B}\) (see Algorithm 2 in Appendix). This step determines the overall time complexity of EpitopeMatch. In the current implementation of the algorithm we reduce time complexity by several means, e.g. by avoiding to investigate distance differences with distances in \(B\) beyond the largest distance in the query epitope \(A\). In general some seed matches can be consolidated after investigation of further distance differences between nodes in the stars, whereas many other seed matches turn out to be dead ends - a kind of noise of accidental false positive matches. Step 2 is intended to reduce this noise. The aim of this step is to identify amongst the matching stars obtained from Step 1 those matches that are guaranteed to have between all corresponding nodes a maximum distance difference below a second distance tolerance \(\delta_{2}\geq\delta_{1}\). This is achieved by testing all distance differences between corresponding nodes in the graphs from Step 1 that have not been investigated in the previous steps for fulfillment of Inequality 3 (see also Figure 2):  
\[|D_{A,ij}-D_{B,kl}|\leq\delta_{2}. \tag{3}\]  
The exact relation between \(\delta_{1}\) and \(\delta_{2}\) is defined by the user and determines how sensitive and specific the algorithm finally is. We have found \(\delta_{2}=4\cdot\delta_{1}\) to give reasonable results for various protein matching problems. In this way, the nodes in the stars from Step 1 are supplemented with new edges. The aim is now to consolidate these graphs to complete graphs (cliques) with all edges fulfilling Inequality 3. To this end, every pair of nodes \(a_{i}b_{k}\) is attributed with its degree, i.e. the number of edge pairs that fulfill Inequality 3. Then the node pair with the smallest degree is removed from the graph and the degrees in the graph are recomputed; this is repeated until all remaining nodes have the same degree. (We have found that the removal of weak nodes is more specific if we use as criterion the sum of degrees of the node and of its neighbors, instead of using the degree of the node alone.) If the number of nodes drops below \(\
u\) the graph is abandoned. The remaining graphs then form cliques of at least \(\
u\) members (Figure 2, and pseudo-code in Algorithm 3 in Appendix). Figure 1: Schematic of situation after Step 1 of algorithm. The two sets \(A\) and \(B\) of atoms to be matched are shown as circles and squares, respectively. For clarity, all atoms are of the same type, and the minimum degree of the central node in each star is \(\
u=2\). We find two pairs of atoms from \(A\) and \(B\) with \(\
u=2\) or more distance differences smaller than \(\delta_{1}\): atom pair \(a_{1}b_{3}\) (solid lines) and atom pair \(a_{6}b_{7}\) (dotted lines). For instance \(a_{1}b_{3}\) has three distance differences smaller than \(\delta_{1}\), namely \(||\mathbf{x}_{1}-\mathbf{x}_{2}|-|\mathbf{y}_{3}-\mathbf{y}_{4}||\), \(||\mathbf{x}_{1}-\mathbf{x}_{3}|-|\mathbf{y}_{3}-\mathbf{y}_{5}||\), \(||\mathbf{x}_{1}-\mathbf{x}_{4}|-|\mathbf{y}_{3}-\mathbf{y}_{2}||\). If two cliques from Step 2 have at least one common node, they are joined to a single graph (Figure 3). This is done for all clique pairs so that it may happen that all cliques are merged into a single graph.