Solving Maximum Clique Problem for Protein Structure Similarity

Noël Malod-Dognin 1, * Rumen Andonov 1 Nicola Yanev 2
* Auteur correspondant
1 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : A basic assumption of molecular biology is that proteins sharing close three-dimensional (3D) structures are likely to share a common function and in most cases derive from a same ancestor. Computing the similarity between two protein structures is therefore a crucial task and has been extensively investigated. Evaluating the similarity of two proteins can be done by finding an optimal one-to-one matching between their components, which is equivalent to identifying a maximum weighted clique in a specific ``alignment graph". In this paper we present a new integer programming formulation for solving such clique problems. The model has been implemented using the ILOG CPLEX Callable Library. In addition, we designed a dedicated branch and bound algorithm for solving the maximum cardinality clique problem. Both approaches have been integrated in VAST (Vector Alignment Search Tool) - a software for aligning protein 3D structures largely used in NCBI (National Center for Biotechnology Information). The original VAST clique solver uses the well known Bron and Kerbosh algorithm (BK). Our computational results on real life protein alignment instances show that our branch and bound algorithm is up to 116 times faster than BK for the largest proteins.
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00356816
Contributeur : Noel Malod-Dognin <>
Soumis le : mercredi 28 janvier 2009 - 17:11:07
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : jeudi 30 juin 2011 - 10:44:27

Fichiers

RR_6818.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00356816, version 1
  • ARXIV : 0901.4833

Citation

Noël Malod-Dognin, Rumen Andonov, Nicola Yanev. Solving Maximum Clique Problem for Protein Structure Similarity. [Research Report] RR-6818, INRIA. 2009, pp.12. 〈inria-00356816〉

Partager

Métriques

Consultations de la notice

471

Téléchargements de fichiers

265