Abstract
We introduce a geometric buildup approach to the distance geometry problem in protein modeling, and discuss the necessary and sufficient conditions on the distances for rigid or unique determination of a protein structure. We describe a new buildup algorithm for determining protein structures rigidly instead of uniquely. The algorithm requires even fewer distance constraints than the general buildup algorithm. We present the test results from applying the algorithm to determining the protein structures with varying degrees of availability of the distances, and show that the new development increases the modeling ability of the geometric buildup method even more while retaining much of the computational feasibility of the method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Wuthrich K. (1986). NMR of Proteins and Nucleic Acids. Wiley, London
Creighton T.E. (1993). Proteins: Structures and Molecular Properties, 2nd edn. Freeman and Company, San Francisco, USA
Cui F., Jernigan R. and Wu Z. (2005). Refinement of NMR-determined protein structures with database derived distance constraints. J. Bioinform. Comput. Biol. 3: 1315–1329
Wu D., Cui F., Jernigan R. and Wu Z. (2007). PIDD: A database for protein inter-atomic distance distributions. Nucleic Acids Res. 35: D202–D207
Wu, D., Jernigan, R., Wu, Z.: Refinement of NMR-determined protein structures with database derived mean-force potentials, Proteins: Structure, Function, Bioinformatics (2007). doi:10.1002/prot.21358
Crippen G.M. and Havel T.F. (1988). Distance Geometry and Molecular Conformation. Wiley, London
Hendrickson B.A. (1995). The molecule problem: Exploiting structure in global optimization. SIAM J. Optim. 5: 835–857
Havel, T.F.: Distance geometry: Theory, algorithms, and chemical applications, in Encyclopedia of Computational Chemistry, pp. 1–20. Wiley, London (1998)
Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proceedings of the 17th Allerton Conference in Communications, Control and Computing, pp. 480–489 (1979)
Dong Q. and Wu Z. (2002). A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances. J. Global Optim. 22: 365–375
Dong Q. and Wu Z. (2003). A geometric buildup algorithm for solving the molecular distance geometry problem with sparse distance data. J. Global Optim. 26: 321–333
Wu D. and Wu Z. (2007). An updated geometric buildup algorithm for solving the molecular distance geometry problem with sparse distance data. J. Global Optim. 37: 661–673
Blumenthal L.M. (1953). Theory and Applications of Distance Geometry. Oxford University Press, Oxford
Sippl M. and Scheraga H. (1985). Solution of the embedding problem and decomposition of symmetric matrices. Proc. Natl. Acad. Sci. USA 82: 2197–2201
Sippl M. and Scheraga H. (1986). Cayley–Menger coordinates. Proc. Natl. Acad. Sci. USA 83: 2283–2287
Huang H.X., Liang Z.A. and Pardalos P. (2003). Some properties for the Euclidean distance matrix and positive semi-definite matrix completion problems. J. Global Optim. 25: 3–21
Berman H.M., Westbrook J., Feng Z., Gilliland G., Bhat T.N., Weissig H., Shindyalov L.N. and Bourne P.E. (2000). The Protein Data Bank. Nucleic Acids Res. 28: 235–242
Wu, D.: Distance-Based Protein Structure Modeling, Ph.D. Thesis, Program on Bioinformatics and Computational Biology and Department of Mathematics, Iowa State University (2006)
Klepeis J.L., Floudas C.A., Morikis D. and Lambris J.D. (1999). Predicting peptide structures using NMR data and deterministic global Optimization. J. Comp. Chem. 20: 1354–1370
Klepeis J.L. and Floudas C.A. (2002). Prediction of beta-sheet topology and disulfide bridges in polypeptides. J. Comp. Chem. 24: 191–208
Floudas C.A., Fung H.K., McAllister S.R., Mönnigmann M. and Rajgaria R. (2006). Advances in protein structure prediction and de novo protein design: a review. Chem. Eng. Sci. 61: 966–988
Vicatos S., Reddy B.V. and Kaznessis Y. (2005). Prediction of distant residue contacts with the use of evolutionary information. Proteins 58: 935–949
Cheng J. and Baldi P. (2007). Improved residue contact prediction using support vector machines and a large feature set. BMC Bioinformatics 8: 113
Sit, A., Wu, Z., Yuan, Y.: A geometric buildup algorithm for the solution of the distance geometry problems using least-squares approximation (2007) (in preparation)
Schlick T. (2003). Molecular Modeling and Simulation: An Interdisciplinary Guide. Springer, Heidelberg
Bourne P.E. and Weissig H. (2003). Structural Bioinformatics. Wiley, London
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wu, D., Wu, Z. & Yuan, Y. Rigid versus unique determination of protein structures with geometric buildup. Optimization Letters 2, 319–331 (2008). https://doi.org/10.1007/s11590-007-0060-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-007-0060-7