Implicit and Explicit Representation of Approximated Motifs

Detecting repeated 3D protein substructures has become a new crucial frontier in motifs inference. In [7] we have suggested a possible solution to this problem by means of a new framework in which the repeated pat- tern is required to be conserved also in terms of relations between its position pairs. In our application these relations are the distances be- tween α-carbons of amino acids in 3D proteins structures, thus leading to a structural consensus as well. In this paper we motivate some com- plexity issues claimed (and assumed, but not proved) in [7] concerning inclusion tests between occurrences of repeated motifs. These inclusion tests are performed during the motifs inference in KMRoverlapR (pre- sented in [7]), but also within other motifs inference tools such as KMRC ([9]). These involve alternative representations of motifs, for which we also prove here some interesting properties concerning pattern matching issues. We conclude this contribution with a few tests on cytochrome P450 protein structures.