A Relational Extension of the Notion of Motifs : Application to the Protein Common 3D Substructures Searching Problem

Abstract : 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.
Mots-clés : motifs
Type de document :
Article dans une revue
Journal of Computational Biology, Mary Ann Liebert, 2009, 16 (12), pp.1635-1660
Liste complète des métadonnées

https://hal-univ-paris13.archives-ouvertes.fr/hal-00618073
Contributeur : Henry Soldano <>
Soumis le : mercredi 31 août 2011 - 15:46:09
Dernière modification le : mercredi 21 mars 2018 - 18:57:28

Identifiants

  • HAL Id : hal-00618073, version 1

Collections

Citation

Nadia Pisanti, Henry Soldano, Mathilde Carpentier, Joël Pothier. A Relational Extension of the Notion of Motifs : Application to the Protein Common 3D Substructures Searching Problem. Journal of Computational Biology, Mary Ann Liebert, 2009, 16 (12), pp.1635-1660. 〈hal-00618073〉

Partager

Métriques

Consultations de la notice

103