The discretizable molecular distance geometry problem |
| |
Authors: | Carlile Lavor Leo Liberti Nelson Maculan Antonio Mucherino |
| |
Institution: | 1. Department of Applied Mathematics (IMECC-UNICAMP), State University of Campinas, 13081-970, Campinas, SP, Brazil 2. LIX, ??cole Polytechnique, 91128, Palaiseau, France 3. Federal University of Rio de Janeiro (COPPE?CUFRJ), C.P. 68511, 21945-970, Rio de Janeiro, RJ, Brazil 4. CERFACS, Toulouse, France
|
| |
Abstract: | Given a simple weighted undirected graph G=(V,E,d) with d:E???+, the Molecular Distance Geometry Problem (MDGP) consists in finding an embedding x:V???3 such that ??x u ?x v ??=d uv for each {u,v}??E. We show that under a few assumptions usually satisfied in proteins, the MDGP can be formulated as a search in a discrete space. We call this MDGP subclass the Discretizable MDGP (DMDGP). We show that the DMDGP is NP-hard and we propose a solution algorithm called Branch-and-Prune (BP). The BP algorithm performs remarkably well in practice in terms of speed and solution accuracy, and can be easily modified to find all incongruent solutions to a given DMDGP instance. We show computational results on several artificial and real-life instances. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|