Solving Maximum Clique Problem for Protein Structure Similarity

Noël Malod-Dognin 1 Rumen Andonov 2 Nicola Yanev 3
1 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
2 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 weighted clique problems in specific k-partite graphs, referred here as alignment graphs. In this paper we present both a new integer programming formulation for solving such clique problems and a dedicated branch and bound algorithm for solving the maximum cardinality clique problem. Both approaches have been integrated in VAST, a software for aligning protein 3D struct ures largely used in the National Center for Biotechnology Information, an original clique solver which uses the well known Bron and Kerbosch algorithm (BK). Our computational results on real protein alignment instances show that our branch and bound algorithm is up to 116 times faster than BK.
Type de document :
Article dans une revue
Serdica Journal of Computing, Institute of Mathematics and Informatics Bulgarian Academy of Sciences, 2010, 4 (1), pp.93--100. 〈http://sci-gems.math.bas.bg/jspui/handle/10525/1583〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00849979
Contributeur : Frederic Cazals <>
Soumis le : vendredi 2 août 2013 - 09:11:06
Dernière modification le : jeudi 11 janvier 2018 - 16:22:40

Identifiants

  • HAL Id : hal-00849979, version 1

Collections

Citation

Noël Malod-Dognin, Rumen Andonov, Nicola Yanev. Solving Maximum Clique Problem for Protein Structure Similarity. Serdica Journal of Computing, Institute of Mathematics and Informatics Bulgarian Academy of Sciences, 2010, 4 (1), pp.93--100. 〈http://sci-gems.math.bas.bg/jspui/handle/10525/1583〉. 〈hal-00849979〉

Partager

Métriques

Consultations de la notice

151