Shape Matching by Localized Calculations of Quasi-isometric Subsets, with Applications to the Comparison of Protein Binding Patches

Frédéric Cazals 1, * Noël Malod-Dognin 1
* Auteur correspondant
1 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Étant donné un complexe protéique impliquant deux partenaires, un récepteur et un ligand, ce papier étudie le problème de comparer leur patchs de liaison, i.e. les ensembles d'atomes participant à leur interaction. Ce problème est classiquement formulé comme une recherche de sous-ensembles d'atomes quasi-isométriques entre les deux patchs, une tâche qui est équivalente à une recherche de cliques maximums. Ce problème étant NP-difficile, des patchs de liaison impliquant plus de 300 atomes ne peuvent-être traités. Nous étendons les travaux précédant dans deux directions. Premièrement, nous présentons un encodage générique pour les formes représentées par des complexes cellulaires. Nous partitionnons une forme en couches concentriques, basées sur ''l'ordre de couche'' des cellules du complexe. L'ordre des couches produisant un arbre de couches qui encode la géométrie et la topologie de la forme. Deuxièmement, pour le cas particulier de complexes cellulaires représentant des patchs de liaison de complexes protéiques, nous proposons trois algorithmes de comparaison de formes. Ces algorithmes combinent une distance d'édition d'arbre (TED, pour tree-edit-distance) sur les arbres de couches, avec des opérations d'éditions favorisant respectivement la comparaison topologique ou géométrique des patchs. Nous montrons en particulier que la TED géométrique établit un équilibre, en termes de précision et de temps de calculs, entre des comparaisons purement géométriques ou purement topologiques, et nous commentons brièvement les résultats biologiques qui sont détaillés dans un article compagnon.
Type de document :
Communication dans un congrès
Loog, Marco and Wessels, Lodewyk and Reinders, Marcel and de Ridder, Dick. The 6th IAPR International Conference on Pattern Recognition in Bioinformatics (PRIB), Nov 2011, Delft, Netherlands. Springer Berlin / Heidelberg, 7036, pp.272-283, 2011, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00603375
Contributeur : Noel Malod-Dognin <>
Soumis le : jeudi 30 juin 2011 - 15:38:58
Dernière modification le : jeudi 11 janvier 2018 - 16:19:58
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 09:21:16

Fichier

RR-7650.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00603375, version 1

Collections

Citation

Frédéric Cazals, Noël Malod-Dognin. Shape Matching by Localized Calculations of Quasi-isometric Subsets, with Applications to the Comparison of Protein Binding Patches. Loog, Marco and Wessels, Lodewyk and Reinders, Marcel and de Ridder, Dick. The 6th IAPR International Conference on Pattern Recognition in Bioinformatics (PRIB), Nov 2011, Delft, Netherlands. Springer Berlin / Heidelberg, 7036, pp.272-283, 2011, Lecture Notes in Computer Science. 〈inria-00603375〉

Partager

Métriques

Consultations de la notice

341

Téléchargements de fichiers

152