## 2 Results and Discussion
### Applications
#### Matching two protein structures  
The matching of two complete large molecular structures is a worst case scenario for EpitopeMatch since then Step 1, which dominates time complexity, becomes very large. Here we try to match the \(\alpha\)-chain (141 amino-acids) and \(\beta\)-chains (146 amino-acids) of human hemoglobin, available as chains A and B under PDB-code 2 DN2. We have tested two different modes of matching. In the first (\"unspecific\") we have matched protein backbone atoms \(N\), \(C_{\alpha}\), \(C^{\prime}\) of all amino-acids irrespective of the type of amino-acids. In the second (\"specific\") we have tried to match \(C_{\alpha}\)- and \(C_{\beta}\)-atoms with amino-acid types as attributes (for Gly \(C_{\beta}\) is not considered). The plot in the left part of Figure 5 shows the unspecific and specific results as points colored in cyan and magenta, respectively. The plot does not only show RMSD and number of matched pairs of amino-acids for the largest common subgraph, but also for graphs that are obtained if node by node is removed from the largest common down to graphs of \(\
u=4\) nodes, with each removed node having the lowest \(P\)-score in the respective graph. Thus the envelopes of the points in the plot towards low RMSD and high number of matches pairs also mark a kind of Pareto-front with a trade-off between low RMSD and low number of matched pairs up to high RMSD and high number of matched pairs. In the unspecific mode, a maximum of 138 amino-acid pairs could be matched with a RMSD of 1.41 A after a run of 173 s. Apart from matches of the full polypeptide chain, EpitopeMatch finds also  
Figure 4: Pareto-front of optimal matches found in database search. The circles connected by broken line are the set of Pareto-optimal matches. All other matches are (unconnected circles) are dominated by one of the members of the Pareto-optimal set as they have both lower RMSD and higher number of matched pairs. matches of helices at different positions in the protein fold. These partial matches with low number of matched pairs and higher RMSD are displayed in the left part of Figure 5 as cloud of magenta points above the almost straight line of low-RMSD matches of the global fold. The run in the specific mode took 52.46 s. Remarkably, the plot shows a kink at 61 matched pairs of amino-acids. At this point the RMSD is 1.26 A. Below 61, the matched pairs are true positive matches in the helices of the two proteins. Above 61, the algorithm starts to match parts of the structurally and sequentially more divergent loop regions, including also false positives, i.e. amino-acids that of are of corresponding types but non-equivalent positions in the fold. We have from the matches up to the 61 th pair derived a sequence alignment (top right of Figure 5). This alignment is almost identical to a pure sequence alignment with the Needleman-Wunsch algorithm with the Gonnet scoring matrix as implemented in ClustalW [13]. ClustalW finds as identities the 61 pairs found by EpitopeMatch, and additionally the two pairs marked with \"0\". The superimposed structures of both runs are shown in the lower right part of Figure 5. The the two chains are matched well in both modes. Figure 5: Matching \(\alpha\)- and \(\beta\)-chains of human hemoglobin. Left: matched pairs of amino-acids vs. RMSD after optimal superposition for two matching modes. Right bottom: optimal superposition of the match of \(\beta\)-chain (green) with \(\alpha\)-chain matched using the amino-acid specific mode (magenta), and the unspecific mode (cyan). Right top: sequence alignment (\(\alpha\)-chain in top row, \(\beta\)-chain in bottom row) derived from the structural alignment. Matching pairs of amino-acids are marked with asterisks. Recognition of a binding site in a homolog  
This example is a typical small scale application of EpitopeMatch. The protein Hst2 from yeast (PDB-code 1Q1A) and the human Sir2 protein (PDB-code 1 MA3) are homologous and their 3D-structures have been determined experimentally.