Geodesic
Solving Maximum Clique Problem for Protein Structure Similarity
Serdica Journal of Computing, Tome 4 (2010) no. 1, pp. 93-100.

Voir la notice de l'article provenant de la source Bulgarian Digital Mathematics Library

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 structures 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.
Keywords: Protein Structure Comparison, Maximum Clique, K-Partite Graphs, Integer Programming, Branch and Bound 
@article{SJC_2010_4_1_a8,
     author = {Malod-Dognin, No\"el and Andonov, Rumen and Yanev, Nicola},
     title = {Solving {Maximum} {Clique} {Problem} for {Protein} {Structure} {Similarity}},
     journal = {Serdica Journal of Computing},
     pages = {93--100},
     publisher = {mathdoc},
     volume = {4},
     number = {1},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2010_4_1_a8/}
}
TY  - JOUR
AU  - Malod-Dognin, Noël
AU  - Andonov, Rumen
AU  - Yanev, Nicola
TI  - Solving Maximum Clique Problem for Protein Structure Similarity
JO  - Serdica Journal of Computing
PY  - 2010
SP  - 93
EP  - 100
VL  - 4
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJC_2010_4_1_a8/
LA  - en
ID  - SJC_2010_4_1_a8
ER  - 
%0 Journal Article
%A Malod-Dognin, Noël
%A Andonov, Rumen
%A Yanev, Nicola
%T Solving Maximum Clique Problem for Protein Structure Similarity
%J Serdica Journal of Computing
%D 2010
%P 93-100
%V 4
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJC_2010_4_1_a8/
%G en
%F SJC_2010_4_1_a8
Malod-Dognin, Noël; Andonov, Rumen; Yanev, Nicola. Solving Maximum Clique Problem for Protein Structure Similarity. Serdica Journal of Computing, Tome 4 (2010) no. 1, pp. 93-100. http://geodesic.mathdoc.fr/item/SJC_2010_4_1_a8/