A Relational Extension of the Notion of Motifs : Application to the Protein Common 3D Substructures Searching Problem
Résumé
Geometrical configurations of atoms in protein structures can be viewed as approximated relations between them. Then, finding similar common substructures within a set of protein structures belongs to a new class of problems that generalizes that of finding repeated motifs. The novelty lies in the addition of constraints on the motifs in terms of relations that must hold between pairs of positions of the motifs. We will hence denote them as "relational motifs". For this class of problems we give an algorithm that is a suitable extension of the KMR (Karp et al, 1972) paradigm and, in particular, of the KMRC (Soldano et al, 1995) as it uses a degenerate alphabet. The algorithm contains several improvements with respect to KMRC that become especially useful when---as it is required for relational motifs---the inference is made by partially overlapping shorter motifs, rather than concatenating them like in KMR. The efficiency, correctness and completeness of the algorithm is ensured by several non-trivial properties that we prove in this paper. The algorithm has been applied in the important field of protein common 3D substructure searching. The methods implemented have been tested on several examples of protein families such as serine proteases, globins and cytochromes P450 additionally. The detected mo- tifs have been compared to those found by multiple structural alignments methods.