Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T07:06:00.714Z Has data issue: false hasContentIssue false
  • English
  • Français

Constrained cyclic coordinate descent for cryo-EM images at medium resolutions: beyond the protein loop closure problem

Published online by Cambridge University Press:  19 May 2016

Kamal Al Nasr  and
Jing He
Kamal Al Nasr
Affiliation:
Department of Computer Science, Tennessee State University, Nashville, TN 37209, USA
Jing He*
Affiliation:
Department of Computer Science, Old Dominion University, Norfolk, VA 23525, USA
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

The cyclic coordinate descent (CCD) method is a popular loop closure method in protein structure modeling. It is a robotics algorithm originally developed for inverse kinematic applications. We demonstrate an effective method of building the backbone of protein structure models using the principle of CCD and a guiding trace. For medium-resolution 3-dimensional (3D) images derived using cryo-electron microscopy (cryo-EM), it is possible to obtain guiding traces of secondary structures and their skeleton connections. Our new method, constrained cyclic coordinate descent (CCCD), builds α-helices, β-strands, and loops quickly and fairly accurately along predefined traces. We show that it is possible to build the entire backbone of a protein fairly accurately when the guiding traces are accurate. In a test of 10 proteins, the models constructed using CCCD show an average of 3.91 Å of backbone root mean square deviation (RMSD). When the CCCD method is incorporated in a simulated annealing framework to sample possible shift, translation, and rotation freedom, the models built with the true topology were ranked high on the list, with an average backbone RMSD100 of 3.76 Å. CCCD is an effective method for modeling atomic structures after secondary structure traces and skeletons are extracted from 3D cryo-EM images.

Keywords

Inverse kinematicsCryo-electron microscopyImageSkeletonProtein structureLoop modelingCyclic coordinate descent
Type
Articles
Information
Robotica , Volume 34 , Issue 8 , August 2016 , pp. 1777 - 1790
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Wang, C., Bradley, P. and Baker, D., “Protein-protein docking with backbone flexibility,” J. Mol. Biol. 373 (2), 503–519 (2007).CrossRefGoogle ScholarPubMed
2. Mandell, D. J., Coutsias, E. A. and Kortemme, T., “Sub-angstrom accuracy in protein loop reconstruction by robotics-inspired conformational sampling,” Nature Methods 6 (8), 551–552 (2009).CrossRefGoogle ScholarPubMed
3. Liu, P., Zhu, F., Rassokhin, D. N. and Agrafiotis, D. K., “A self-organizing algorithm for modeling protein loops,” PLoS Comput. Biol. 5 (8), e1000478 (2009).CrossRefGoogle ScholarPubMed
4. Canutescu, A. A. and Dunbrack, R. L. Jr., “Cyclic coordinate descent: A robotics algorithm for protein loop closure,” Protein Sci. 12 (5), 963–972 (2003).CrossRefGoogle ScholarPubMed
5. Kavraki, L. E., Svestka, P., Latombe, J. C. and Overmars, M. H., “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom. 12 (4), 566–580 (1996).CrossRefGoogle Scholar
6. Dawen, X. and Amato, N. M., “A Kinematics-Based Probabilistic Roadmap Method for High DOF Closed Chain Systems,” Proceedings of the IEEE International Conference on. Robotics and Automation, 2004, New Orleans, LA. ICRA'04 2004. pp. 473–478.CrossRefGoogle Scholar
7. Cortes, J., Simeon, T. and Laumond, J. P., “A Random Loop Generator for Planning the Motions of Closed Kinematic Chains using PRM Methods,” Proceedings of the IEEE International Conference on. Robotics and Automation, 2002. ICRA '02. Washington, DC, 2002. pp. 2141–2146.Google Scholar
8. Cortés, J., Siméon, T., Remaud-Siméon, M. and Tran, V., “Geometric algorithms for the conformational analysis of long protein loops,” J. Comput. Chem. 25 (7), 956–967 (2004).CrossRefGoogle ScholarPubMed
9. Yakey, J. H., LaValle, S. M. and Kavraki, L. E., “Randomized path planning for linkages with closed kinematic chains,” IEEE Trans. Robot. Autom. 17 (6), 951–958 (2001).CrossRefGoogle Scholar
10. Wedemeyer, W. J. and Scheraga, H. A., “Exact analytical loop closure in proteins using polynomial equations,” J. Comput. Chem. 20, 819–844 (1999).3.0.CO;2-Y>CrossRefGoogle ScholarPubMed
11. Shehu, A., Clementi, C. and Kavraki, L. E., “Modeling protein conformational ensembles: From missing loops to equilibrium fluctuations,” Proteins: Struct., Functions, Bioinformatics 65 (1), 164–179 (2006).CrossRefGoogle ScholarPubMed
12. Coutsias, E. A., Seok, C., Jacobson, M. P. and Dill, K. A., “A kinematic view of loop closure,” J. Comput. Chem. 25, 510–528 (2004).CrossRefGoogle ScholarPubMed
13. Fine, R. M., Wang, H., Shenkin, P. S., Yarmush, D. L. and Levinthal, C., “Predicting antibody hypervariable loop conformations. II: Minimization and molecular dynamics studies of MCPC603 from many randomly generated loop conformations,” Proteins 1 (4), 342–362 (1986).CrossRefGoogle ScholarPubMed
14. Shenkin, P. S., Yarmush, D. L., Fine, R. M., Wang, H. J. and Levinthal, C., “Predicting antibody hypervariable loop conformation. 1. ensembles of random conformations for ring-like structure,” Biopolymers 26, 2053–2085 (1987).CrossRefGoogle Scholar
15. Wang, L. T. and Chen, C. C., “A combined optimization method for solving the inverse kinematics problem of mechanical manipulators,” IEEE Trans. Robot. Autom. 7, 489–499 (1991).CrossRefGoogle Scholar
16. Ring, C. S., Kneller, D. G., Langridge, R. and Cohen, F. E., “Taxonomy and conformational analysis of loops in proteins,” J. Mol. Biol. 224, 685–699 (1992).CrossRefGoogle ScholarPubMed
17. Xiang, Z., Soto, C. S. and Honig, B., “Evaluating conformational free energies: The colony energy and its application to the problem of loop prediction,” Proc. Natl. Acad. Sci. USA (PNAS) 99 (11), 7432–7437 (2002).CrossRefGoogle Scholar
18. Chen, D. H., Ludtke, S. J., Song, J. L., Chuang, D. T., and Chiu, W., “Seeing GroEL at 6 A resolution by single particle electron cryomicroscopy,” Structure 12 (7), 1129–1136 (2004).Google Scholar
19. Chiu, W. and Schmid, M. F., “Pushing back the limits of electron cryomicroscopy,” Nature Struct. Biol. 4, 331–333 (1997).CrossRefGoogle ScholarPubMed
20. Chiu, W., Baker, M. L., Jiang, W. and Zhou, Z. H., “Deriving folds of macromolecular complexes through electron cryomicroscopy and bioinformatics approaches,” Curr. Opin. Struct. Biol. 12 (2), 263–269 (2002).CrossRefGoogle ScholarPubMed
21. Zhou, Z. H., Dougherty, M., Jakana, J., He, J., Rixon, F. J. and Chiu, W., “Seeing the herpesvirus capsid at 8.5 A,” Science 288(5467), 877–880 (2000).CrossRefGoogle Scholar
22. Zhang, X., Jin, L., Fang, Q., Hui, W. H. and Zhou, Z. H., “3.3 Å Cryo-EM structure of a nonenveloped virus reveals a priming mechanism for cell entry,” Cell 141 (3), 472–482 (2010).CrossRefGoogle ScholarPubMed
23. Cheng, L., Sun, J., Zhang, K., Mou, Z., Huang, X., Ji, G., Sun, F., Zhang, J. and Zhu, P., “Atomic model of a cypovirus built from cryo-EM structure provides insight into the mechanism of mRNA capping,” Proc. Natl. Acad. Sci. 108 (4), 1373–1378 (2011).CrossRefGoogle ScholarPubMed
24. Gonen, T., Sliz, P., Kistler, J., Cheng, Y. and Walz, T., “Aquaporin-0 membrane junctions reveal the structure of a closed water pore,” Nature 429(6988), 193–197 (2004).CrossRefGoogle Scholar
25. Brown, A., Amunts, A., Bai, X.-C., Sugimoto, Y., Edwards, P. C., Murshudov, G., Scheres, S. H. W. and Ramakrishnan, V., “Structure of the large ribosomal subunit from human mitochondria,” Science 346(6210), 718–722 (2014).CrossRefGoogle Scholar
26. Hussain, T., Llácer, J. L., Fernández, I. S., Munoz, A., Martin-Marcos, P., Savva, C. G., Lorsch, J. R., Hinnebusch, A. G. and Ramakrishnan, V., “Structural changes enable start codon recognition by the eukaryotic translation initiation complex,” Cell 159 (3), 597–607 (2014).CrossRefGoogle ScholarPubMed
27. Lawson, C. L., Baker, M. L., Best, C., Bi, C., Dougherty, M., Feng, P., van Ginkel, G., Devkota, B., Lagerstedt, I., Ludtke, S. J., Newman, R. H., Oldfield, T. J., Rees, I., Sahni, G., Sala, R., Velankar, S., Warren, J., Westbrook, J. D., Henrick, K., Kleywegt, G. J., Berman, H. M. and Chiu, W., “EMDataBank.org: unified data resource for CryoEM,” Nucleic Acids Res. 39(Database issue), D456–464 (2011).CrossRefGoogle ScholarPubMed
28. Pintilie, G. D., Zhang, J., Goddard, T. D., Chiu, W. and Gossard, D. C., “Quantitative analysis of cryo-EM density map segmentation by watershed and scale-space filtering, and fitting of structures by alignment to regions,” J. Struct. Biol. 170 (3), 427–438 (2010).CrossRefGoogle ScholarPubMed
29. Topf, M., Lasker, K., Webb, B., Wolfson, H., Chiu, W. and Sali, A., “Protein structure fitting and refinement guided by cryo-EM density,” Structure 16 (2), 295–307 (2008).CrossRefGoogle ScholarPubMed
30. Tama, F., Miyashita, O. and Brooks, C. L., “Normal mode based flexible fitting of high-resolution structure into low-resolution experimental data from cryo-EM,” J. Struct. Biol. 147 (3), 315–326 (2004).CrossRefGoogle ScholarPubMed
31. Pandurangan, A. P. and Topf, M., “Finding rigid bodies in protein structures: Application to flexible fitting into cryoEM maps,” J. Struct. Biol. 177 (2), 520–531 (2012).CrossRefGoogle ScholarPubMed
32. Suhre, K., Navazab, J. and Sanejouand, Y.-H., “NORMA: A tool for flexible fitting of high-resolution protein structures into low-resolution electron-microscopy-derived density maps,” Acta Crystallogr.. Section D, Biol. Crystallogr. 62 (Pt 9), 1098–1100 (2006).CrossRefGoogle Scholar
33. Velazquez-Muriel, J. A. and Carazo, J. M., “Flexible fitting in 3D-EM with incomplete data on superfamily variability,” J. Struct. Biol. 158 (2), 165–181 (2007).CrossRefGoogle ScholarPubMed
34. Chacón, P. and Wriggers, W., “Multi-resolution contour-based fitting of macromolecular structures,” J. Mol. Biol. 317 (3), 375–384 (2002).CrossRefGoogle ScholarPubMed
35. Wriggers, W. and Birmanns, S., “Using situs for flexible and rigid-body fitting of multiresolution single-molecule data,” J. Struct. Biol. 133 (2–3), 193–202 (2001).CrossRefGoogle ScholarPubMed
36. Wriggers, W., “Using Situs for the integration of multi-resolution structures,” Biophys. Rev. 2 (1), 21–27 (2010).CrossRefGoogle ScholarPubMed
37. Topf, M., Baker, M. L., Marti-Renom, M. A., Chiu, W. and Sali, A., “Refinement of protein structures by iterative comparative modeling and CryoEM density fitting,” J. Mol. Biol. 357 (5), 1655–1668 (2006).CrossRefGoogle ScholarPubMed
38. Baker, M. L., Ju, T. and Chiu, W., “Identification of secondary structure elements in intermediate-resolution density maps,” Structure 15 (1), 7–19 (2007).CrossRefGoogle ScholarPubMed
39. Si, D. and He, J., “Tracing beta strands using strandTwister from Cryo-EM density maps at medium resolutions,” Structure 22 (11), 1665–1676 (2014).CrossRefGoogle ScholarPubMed
40. Si, D., Ji, S., Al Nasr, K. and He, J., “A machine learning approach for the identification of protein secondary structure elements from cryoEM density maps,” Biopolymers 97, 698–708 (2012).CrossRefGoogle Scholar
41. Baker, M. L., Abeysinghe, S. S., Schuh, S., Coleman, R. A., Abrams, A., Marsh, M. P., Hryc, C. F., Ruths, T., Chiu, W. and Ju, T., “Modeling protein structure at near atomic resolutions with Gorgon,” J. Struct. Biol. 174 (2), 360–373 (2011).CrossRefGoogle ScholarPubMed
42. Al Nasr, K., Ranjan, D., Zubair, M. and He, J., “Ranking valid topologies of the secondary structure elements using a constraint graph,” J. Bioinformatics Comput. Biol. 9 (3), 415–430 (2011).CrossRefGoogle ScholarPubMed
43. Al Nasr, K., Ranjan, D., Zubair, M., Chen, L. and He, J., “Solving the secondary structure matching problem in Cryo-EM De novo modeling using a constrained K-Shortest path graph algorithm,” IEEE/ACM Trans. Comput. Biol. Bioinformatics, 11 (2), 419–430 (2014).CrossRefGoogle ScholarPubMed
44. Ju, T., Baker, M. L. and Chiu, W., “Computing a family of skeletons of volumetric models for shape description,” Comput.-Aided Des. 39 (5), 352–360 (2007).CrossRefGoogle ScholarPubMed
45. Biswas, A., Si, D., Al Nasr, K., Ranjan, D., Zubair, M. and He, J., “Improved efficiency in Cryo-EM secondasy structure topology determination from inaccurate data,” J. Bioinformatics Comput. Biol. 10 (03), 1242006 (2012).CrossRefGoogle ScholarPubMed
46. Biswas, A., Ranjan, D., Zubair, M. and He, J., “A dynamic programming algorithm for finding the optimal placement of a secondary structure topology in Cryo-EM data,” J. Comput. Biol., (2015).CrossRefGoogle Scholar
47. Biswas, A., Ranjan, D., Zubair, M. and He, J., “A novel computational method for deriving protein secondary structure topologies using Cryo-EM density maps and multiple secondary structure predictions,” LNCS, Bioinformatics Res. Appl., 9096, 60–71 (2015).CrossRefGoogle Scholar
48. Al Nasr, K., Chen, L., Si, D., Ranjan, D., Zubair, M. and He, J., “Building the Initial Chain of the Proteins Through de novo Modeling of the Cryo-Electron Microscopy Volume Data at the Medium Resolutions,” Proceedings of the ACM Conference on Bioinformatics, Computational Biology and Biomedicine, Orlando, Florida, (2012) pp. 490–497.Google Scholar
49. Jiang, W., Baker, M. L., Ludtke, S. J. and Chiu, W., “Bridging the information gap: Computational tools for intermediate resolution structure interpretation,” J. Mol. Biol. 308 (5), 1033–1044 (2001).CrossRefGoogle ScholarPubMed
50. Dal Palu, A., He, J., Pontelli, E. and Lu, Y., “Identification of Alpha-Helices from Low Resolution Protein Density Maps,” Proceeding of the Computational Systems Bioinformatics Conference(CSB), Stanford University, CA (2006) pp. 89–98.Google Scholar
51. Rusu, M. and Wriggers, W., “Evolutionary bidirectional expansion for the tracing of alpha helices in cryo-electron microscopy reconstructions,” J. Struct. Biol. 177 (2), 410–419 (2012).CrossRefGoogle ScholarPubMed
52. Kong, Y. and Ma, J., “A structural-informatics approach for mining beta-sheets: Locating sheets in intermediate-resolution density maps,” J. Mol. Biol. 332 (2), 399–413 (2003).CrossRefGoogle ScholarPubMed
53. Kong, Y., Zhang, X., Baker, T. S. and Ma, J., “A Structural-informatics approach for tracing beta-sheets: Building pseudo-C(alpha) traces for beta-strands in intermediate-resolution density maps,” J. Mol. Biol. 339 (1), 117–130 (2004).CrossRefGoogle ScholarPubMed
54. Bajaj, C., Goswami, S. and Zhang, Q., “Detection of secondary and supersecondary structures of proteins from cryo-electron microscopy,” J. Struct. Biol. 177 (2), 367–381 (2012).CrossRefGoogle ScholarPubMed
55. Si, D. and He, J., “Beta-sheet Detection and Representation from Medium Resolution Cryo-EM Density Maps,” BCB'13: Proceedings of ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, Washington, D.C. (Sep. 22–25, 2013) pp. 764–770.CrossRefGoogle Scholar
56. Abeysinghe, S. S., Baker, M., Wah, C. and Tao, J., “Segmentation-Free Skeletonization of Grayscale Volumes for Shape Understanding,” IEEE International Conference on Shape Modeling and Applications, SMI, Stony Brook, NY (2008) pp. 63–71.Google Scholar
57. Al Nasr, K., Liu, C., Rwebangira, M., Burge, L. and He, J., “Intensity-based Skeletonization of CryoEM gray-scale images using a true segmentation-free algorithm,” IEEE/ACM Trans. Comput. Biol. Bioinformatics 10 (5), 1289–1298 (2013).CrossRefGoogle ScholarPubMed
58. Cuff, J. A., Clamp, M. E., Siddiqui, A. S., Finlay, M. and Barton, G. J., “JPred: A consensus secondary structure prediction server,” Bioinformatics 14 (10), 892–893 (1998).CrossRefGoogle ScholarPubMed
59. Pollastri, G. and McLysaght, A., “Porter: A new, accurate server for protein secondary structure prediction,” Bioinformatics 21 (8), 1719–1720 (2005).CrossRefGoogle Scholar
60. Jones, D. T., “Protein secondary structure prediction based on position-specific scoring matrices,” J. Mol. Biol. 292 (2), 195–202 (1999).CrossRefGoogle ScholarPubMed
61. Abeysinghe, S., Ju, T., Baker, M. L. and Chiu, W., “Shape modeling and matching in identifying 3D protein structures,” Comput.-Aided Des. 40 (6), 708–720 (2008).CrossRefGoogle Scholar
62. Ginalski, K., “Comparative modeling for protein structure prediction,” Curr. Opin. Struct. Biol. 16 (2), 172–177 (2006).CrossRefGoogle ScholarPubMed
63. Fiser, A. and Šali, A., “Modeller: Generation and refinement of homology-based protein structure models,” Methods Enzymology 374, 461–491 (2003).CrossRefGoogle ScholarPubMed
64. Simons, K. T., Kooperberg, C., Huang, E. and Baker, D., “Assembly of protein tertiary structures from fragments with similar local sequences using simulated annealing and Bayesian scoring functions,” J. Mol. Biol. 268 (1), 209–225 (1997).CrossRefGoogle ScholarPubMed
65. Rohl, C. A., Strauss, C. E., Misura, K. M. and Baker, D., “Protein structure prediction using Rosetta,” Methods Enzymol 383, 66–93 (2004).CrossRefGoogle ScholarPubMed
66. Lindert, S., Alexander, N., Wötzel, N., Karaka, M., Stewart, Phoebe L. and Meiler, J., “EM-Fold: De novo atomic-detail protein structure determination from medium-resolution density maps,” Structure 20 (3), 464–478 (2012).CrossRefGoogle ScholarPubMed
67. Lindert, S., Staritzbichler, R., Wötzel, N., Karakas, M., Stewart, P. L. and Meiler, J., “EM-fold: De novo folding of alpha-helical proteins guided by intermediate-resolution electron microscopy density maps,” Structure 17 (7), 990–1003 (2009).CrossRefGoogle ScholarPubMed
68. Baker, M. R., Rees, I., Ludtke, S. J., Chiu, W. and Baker, M. L., “Constructing and validating initial Cα models from ubnanometer resolution density maps with Pathwalking,” Structure 20 (3), 450–463 (2012).CrossRefGoogle ScholarPubMed
69. Lotan, I., Van Den Bedem, H., Deacon, A. M. and Latombe, J.-C., “Computing protein structures from electron density maps: The missing fragment problem algorithmic foundations of robotics VI,” Springer Tracts Adv. Robot. 17, 345–360 (2005).CrossRefGoogle Scholar
70. Lu, Y., He, J., and Strauss, C. E., “Deriving Topology and Sequence Alignment for the Helix Skeleton in Low Resolution Protein Density Maps,” J Bioinformatics Comput. Biol., 6 (1), 183–201 (2008).CrossRefGoogle ScholarPubMed
71. Al Nasr, K. and He, J., “An effective convergence independent loop closure method using forward-backward cyclic coordinate descent,” Int. J. Data Mining Bioinformatics 3 (3), 346–361 (2009).CrossRefGoogle ScholarPubMed
72. Al Nasr, K. and He, J., “Deriving protein backbone using traces extracted from density maps at medium resolutions,” LNCS, Bioinformatics Res. Appl., 9096, 1–11 (2015).CrossRefGoogle Scholar
73. Ludtke, S. J., Baldwin, P. R. and Chiu, W., “EMAN: Semi-automated software for high resolution single particle reconstructions,” J. Struct. Biol. 128 (1), 82–97 (1999).CrossRefGoogle Scholar
74. Xie, W. and Sahinidis, N. V., “Residue-rotamer-reduction algorithm for the protein side-chain conformation problem,” Bioinformatics 22 (2), 188–194 (2006).CrossRefGoogle ScholarPubMed
75. Sun, W. and He, J., “Native secondary structure topology has near minimum contact energy among all possible geometrically constrained topologies,” Proteins 77 (1), 159–173 (2009).CrossRefGoogle ScholarPubMed
76. Pettersen, E. F., Goddard, T. D., Huang, C. C., Couch, G. S., Greenblatt, D. M., Meng, E. C. and Ferrin, T. E., “UCSF Chimera–-A visualization system for exploratory research and analysis,” J. Comput. Chem. 25 (13), 1605–1612 (2004).CrossRefGoogle ScholarPubMed