Extending the geometric build-up algorithm for the molecular distance geometry problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)One of the most important problems in computational biology is the determination of the three-dimensional structure of a protein using the amino acid sequence that generates it. This task can be experimentally performed by using NMR techniques. However, NMR data usually provide only a sparse set of distances between atoms of a molecule. In this case, the aim is to determine its three-dimensional structure using a set of distances for only some pairs of atoms. This problem is known as the Molecular Distance Geometry Problem (MDGP). This work extends the Geometric Build-up Algorithm (GBA) by Dong and Wu, proposed to solve instances of the MDGP. Computational results show that the presented approach, the Extended Geometric Build-up Algorithm (EGBA), is capable of dealing with instances not previously solved by the GBA. (C) 2008 Elsevier B.V. All rights reserved.1084234237Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ)Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP