Protein structure determination via an efficient geometric build-up algorithm

Davis, Robert T.; Ernst, Claus; Di Wu
January 2010
BMC Structural Biology;2010 Supplement 1, Vol. 10, Special section p1
Academic Journal
Background: A protein structure can be determined by solving a so-called distance geometry problem whenever a set of inter-atomic distances is available and sufficient. However, the problem is intractable in general and has proved to be a NP hard problem. An updated geometric build-up algorithm (UGB) has been developed recently that controls numerical errors and is efficient in protein structure determination for cases where only sparse exact distance data is available. In this paper, the UGB method has been improved and revised with aims at solving distance geometry problems more efficiently and effectively. Methods: An efficient algorithm (called the revised updated geometric build-up algorithm (RUGB)) to build up a protein structure from atomic distance data is presented and provides an effective way of determining a protein structure with sparse exact distance data. In the algorithm, the condition to determine an unpositioned atom iteratively is relaxed (when compared with the UGB algorithm) and data structure techniques are used to make the algorithm more efficient and effective. The algorithm is tested on a set of proteins selected randomly from the Protein Structure Database-PDB. Results: We test a set of proteins selected randomly from the Protein Structure Database-PDB. We show that the numerical errors produced by the new RUGB algorithm are smaller when compared with the errors of the UGB algorithm and that the novel RUGB algorithm has a significantly smaller runtime than the UGB algorithm. Conclusions: The RUGB algorithm relaxes the condition for updating and incorporates the data structure for accessing neighbours of an atom. The revisions result in an improvement over the UGB algorithm in two important areas: a reduction on the overall runtime and decrease of the numeric error.


Related Articles

  • An updated geometric build-up algorithm for solving the molecular distance geometry problems with sparse distance data. Di Wu; Zhijun Wu // Journal of Global Optimization;Apr2007, Vol. 37 Issue 4, p661 

    Abstract??An updated geometric build-up algorithm is developed for solving the molecular distance geometry problem with a sparse set of inter-atomic distances. Different from the general geometric build-up algorithm, the updated algorithm re-computes the coordinates of the base atoms whenever...

  • Solving the molecular distance geometry problem with inaccurate distance data. Souza, Michael; Lavor, Carlile; Muritiba, Albert; Maculan, Nelson // BMC Bioinformatics;2013, Vol. 14 Issue Suppl 9, p1 

    We present a new iterative algorithm for the molecular distance geometry problem with inaccurate and sparse data, which is based on the solution of linear systems, maximum cliques, and a minimization of nonlinear leastsquares function. Computational results with real protein structures are...

  • A Geometric Buildup Algorithm for the Solution of the Distance Geometry Problem Using Least-Squares Approximation. Sit, Atilla; Zhijun Wu; Yaxiang Yuan // Bulletin of Mathematical Biology;Nov2009, Vol. 71 Issue 8, p1914 

    We propose a new geometric buildup algorithm for the solution of the distance geometry problem in protein modeling, which can prevent the accumulation of the rounding errors in the buildup calculations successfully and also tolerate small errors in given distances. In this algorithm, we use all...

  • The difficulty of protein structure alignment under the RMSD. Shuai Cheng Li // Algorithms for Molecular Biology;2013, Vol. 8 Issue 1, p1 

    Background: Protein structure alignment is often modeled as the largest common point set (LCP) problem based on the Root Mean Square Deviation (RMSD), a measure commonly used to evaluate structural similarity. In the problem, each residue is represented by the coordinate of the Ca atom, and a...

  • A New Algorithm for Reconstruction a Protein 3D Structure from Contact Map. Al-Fawareh, Hamed J. // Journal of Computational Intelligence in Bioinformatics;2011, Vol. 4 Issue 1, p95 

    Reconstruction a protein 3D structure using its contact map is not less than revolutionizes molecular biology. Recently, there are many research efforts that provide guidelines for protein contact map prediction; these efforts used machine learning approaches such as neural network and distance...

  • Computation of Molecular Surface Using Euclidean Voronoi Diagram. Joonghyun Ryu; Donguk Kim; Youngsong Cho; Rhohun Park; Deok-Soo Kim // Computer-Aided Design & Applications (Computer-Aided Design & Ap;2005, Vol. 2 Issue 1-4, p439 

    Given a protein, analyzing the geometric structure of protein is fundamental for the study of a protein folding, docking, interactions between proteins, and so on. One of the important geometric analyses is computing the molecular surface of protein. Discussed in this paper is an efficient...

  • Algorithm for backrub motions in protein design. Ivelin Georgiev; Daniel Keedy; Jane S. Richardson; David C. Richardson; Bruce R. Donald // Bioinformatics;Jul2008, Vol. 24 Issue 13, pi196 

    Motivation: The Backrub is a small but kinematically efficient side-chain-coupled local backbone motion frequently observed in atomic-resolution crystal structures of proteins. A backrub shifts the Cα–Cβ orientation of a given side-chain by rigid-body dipeptide rotation plus smaller...

  • e-PROPAINOR: A Web-Server for Fast Prediction of Cα Structure & Likely Functional Sites of a Protein Sequence. Joshi, Rajani R.; Jyothish, N. T. // Open Bioinformatics Journal;2010, Vol. 4 Issue 2010, p11 

    e-PROPAINOR (www.math.iitb.ac.in/epropainor/) is a web-server based on extension of PROPAINOR for prediction and computational function elucidation of 3-D structure of proteins. It predicts the Cα structure of a given protein sequence. Computational efficiency and reliability are key features...

  • HAAD: A Quick Algorithm for Accurate Prediction of Hydrogen Atoms in Protein Structures. Yunqi Li; Roy, Ambrish; Yang Zhang // PLoS ONE;2009, Vol. 4 Issue 8, p1 

    Hydrogen constitutes nearly half of all atoms in proteins and their positions are essential for analyzing hydrogen-bonding interactions and refining atomic-level structures. However, most protein structures determined by experiments or computer prediction lack hydrogen coordinates. We present a...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics