BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2010 >
Volume 4 Number 1 >

Please use this identifier to cite or link to this item:

Title: Solving Maximum Clique Problem for Protein Structure Similarity
Authors: Malod-Dognin, Noël
Andonov, Rumen
Yanev, Nicola
Keywords: Protein Structure Comparison
Maximum Clique
K-Partite Graphs
Integer Programming
Branch and Bound
Issue Date: 2010
Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation: Serdica Journal of Computing, Vol. 4, No 1, (2010), 93p-100p
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 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.
ISSN: 1312-6555
Appears in Collections:Volume 4 Number 1

Files in This Item:

File Description SizeFormat
sjc118-vol4-num1-2010.pdf151.09 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License