Solving Maximum Clique Problem for Protein Structure Similarity
| Autor: | Malod-Dognin, Noël, Andonov, Rumen, Yanev, Nicola |
|---|---|
| Přispěvatelé: | Cazals, Frederic, Biological systems and models, bioinformatics and sequences (SYMBIOSE), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Department Probability, Operations Research and Statistics, Софийски университет = Sofia University, INRIA, Algorithms, Biology, Structure (ABS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, University of Sofia |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
Protein Structure Comparison
Maximum Clique [SDV.BIBS] Life Sciences [q-bio]/Quantitative Methods [q-bio.QM] protein structure alignment [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Quantitative Biology - Quantitative Methods [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM] FOS: Biological sciences Branch and Bound K-Partite Graphs Branch and bound [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM] maximum clique problems integer programming Integer Programming Quantitative Methods (q-bio.QM) [INFO.INFO-BI] Computer Science [cs]/Bioinformatics [q-bio.QM] |
| Zdroj: | [Research Report] RR-6818, INRIA. 2009, pp.12 Serdica Journal of Computing Serdica Journal of Computing, Institute of Mathematics and Informatics Bulgarian Academy of Sciences, 2010, 4 (1), pp.93--100 Serdica Journal of Computing, 2010, 4 (1), pp.93--100 |
| ISSN: | 1312-6555 1314-7897 |
| Popis: | * This work is supported by the ANR project PROTEUS "ANR-06-CIS6-008", by the Brittany Region and by the Bulgarian NSF project DO 02-359/2008. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|