Finding Optimal Discretization Orders for Molecular Distance Geometry by Answer Set Programming

Abstract : The Molecular Distance Geometry Problem (MDGP) is the problem of finding the possible conformations of a molecule by exploiting available information about distances between some atom pairs. When particular assumptions are satisfied, the MDGP can be discretized, so that the search domain of the problem becomes a tree. This tree can be explored by using an interval Branch & Prune (iBP) algorithm. In this context, the order given to the atoms of the molecules plays an important role. In fact, the discretization assumptions are strongly dependent on the atomic ordering, which can also impact the computational cost of the iBP algorithm. In this work, we propose a new partial discretization order for protein backbones. This new atomic order optimizes a set of objectives, that aim at improving the iBP performances. The optimization of the objectives is performed by Answer Set Programming (ASP), a declarative programming language that allows to express our problem by a set of logical constraints. The comparison with previously proposed orders for protein backbones shows that this new discretization order makes iBP perform more efficiently.
Type de document :
Chapitre d'ouvrage
S. Fidanova. Studies in Computational Intelligence, 610, Springer, pp.1-15, 2015, Recent Advances in Computational Optimization
Liste complète des métadonnées

https://hal.inria.fr/hal-01196714
Contributeur : Antonio Mucherino <>
Soumis le : jeudi 10 septembre 2015 - 12:07:32
Dernière modification le : jeudi 15 novembre 2018 - 11:57:53

Identifiants

  • HAL Id : hal-01196714, version 1

Citation

Douglas S. Gonçalves, Jacques Nicolas, Antonio Mucherino, Carlile Lavor. Finding Optimal Discretization Orders for Molecular Distance Geometry by Answer Set Programming. S. Fidanova. Studies in Computational Intelligence, 610, Springer, pp.1-15, 2015, Recent Advances in Computational Optimization. 〈hal-01196714〉

Partager

Métriques

Consultations de la notice

374