Maximum Cliques in Protein Structure Comparison

Noël Malod-Dognin 1, 2 Rumen Andonov 3, * Nicola Yanev 4
* Auteur correspondant
1 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
3 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Computing the similarity between two protein structures is a crucial task in molecular biology, and has been extensively investigated. Many protein structure comparison methods can be modeled as maximum clique problems in specific k-partite graphs, referred here as alignment graphs. In this paper, we propose a new protein structure comparison method based on internal distances (DAST), which main characteristic is that it generates alignments having RMSD smaller than any previously given threshold. DAST is posed as a maximum clique problem in an alignment graph, and in order to compute DAST's alignments, we also design an algorithm (ACF) for solving such maximum clique problems. We compare ACF with one of the fastest clique finder, recently conceived by Österg˙ard. On a popular benchmark (the Skolnick set) we observe that ACF is about 20 times faster in average than the Österg˙ard's algorithm. We then successfully use DAST's alignments to obtain automatic classification in very good agreement with SCOP.
Type de document :
Communication dans un congrès
Paola Festa. SEA 2010 9th International Symposium on Experimental Algorithms, May 2010, Naples, Italy. Springer, 6049, pp.106-117, 2010, 〈http://link.springer.com/chapter/10.1007%2F978-3-642-13193-6_10〉. 〈10.1007/978-3-642-13193-6_10〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00536700
Contributeur : Rumen Andonov <>
Soumis le : mardi 23 novembre 2010 - 13:52:06
Dernière modification le : mercredi 11 avril 2018 - 01:56:59
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:37:10

Fichier

Cliques_2010.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Noël Malod-Dognin, Rumen Andonov, Nicola Yanev. Maximum Cliques in Protein Structure Comparison. Paola Festa. SEA 2010 9th International Symposium on Experimental Algorithms, May 2010, Naples, Italy. Springer, 6049, pp.106-117, 2010, 〈http://link.springer.com/chapter/10.1007%2F978-3-642-13193-6_10〉. 〈10.1007/978-3-642-13193-6_10〉. 〈inria-00536700〉

Partager

Métriques

Consultations de la notice

406

Téléchargements de fichiers

138