ABSTRACT
Although many electron density maps have been produced into the medium resolutions, it is still challenging to derive the atomic structure from such volumetric data. Current methods primarily rely on the availability of an existing atomic structure for fitting or a homologous template structure for modeling. In the process of developing a template-free, de novo, method, the topology of the secondary structure elements need to be resolved first. In this paper, we extend our previous algorithm of finding the optimal solution in the constraint graph problem. We illustrate an approach to obtain the top-K topologies by combining a dynamic programming algorithm with the K-shortest path algorithm. The effectiveness of the algorithms is demonstrated from the test using three datasets of different nature. The algorithm improves the accuracy, space and time of an existing method.
- Ludtke, S. J., Baldwin, P. R. and Chiu, W. EMAN: Semi-automated software for high resolution single particle reconstructions. Journal of Structural Biology, 128, 1 1999), 82--97.Google ScholarCross Ref
- Del Palu, A., He, J., Pontelli, E. and Lu, Y. Identification of Alpha-Helices from Low Resolution Protein Density Maps. Proceeding of Computational Systems Bioinformatics Conference(CSB)2006), 89--98.Google Scholar
- Chiu, W. and Schmid, M. F. Pushing back the limits of electron cryomicroscopy. Nature Struct. Biol., 41997), 331--333.Google Scholar
- 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 (May 5 2000), 877--880.Google Scholar
- Ludtke SJ, C. D., Song JL, Chuang DT, Chiu W. Seeing GroEL at 6 A resolution by single particle electron cryomicroscopy. Structure, 12, 7 (Jul 2004), 1129--1136.Google ScholarCross Ref
- 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 (Apr 2002), 263--269.Google ScholarCross Ref
- Yu, X., Jin, L. and Zhou, Z. H. 3.88A structure of cytoplasmic polyhedrosis virus by cryo-electron microscopy. Nature, 453, 7193 (05/15/print 2008), 415--419.Google Scholar
- Cong, Y., Baker, M. L., Jakana, J., Woolford, D., Miller, E. J., Reissmann, S., Kumar, R. N., Redding-Johanson, A. M., Batth, T. S., Mukhopadhyay, A., Ludtke, S. J., Frydman, J. and Chiu, W. 4.0-Å resolution cryo-EM structure of the mammalian chaperonin TRiC/CCT reveals its unique subunit arrangement. Proceedings of the National Academy of Sciences, 107, 11 (March 16, 2010 2010), 4967--4972.Google ScholarCross Ref
- 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 (April 2010 2010), 472--482.Google ScholarCross Ref
- Baker, M. L., Zhang, J., Ludtke, S. J. and Chiu, W. Cryo-EM of macromolecular assemblies at near-atomic resolution. Nat. Protocols, 5, 10 (09//print 2010), 1697--1708.Google Scholar
- 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 Research, 39, suppl 1 (January 1, 2011 2011), D456-D464.Google Scholar
- Henderson, R., Sali, A., Baker, Matthew L., Carragher, B., Devkota, B., Downing, Kenneth H., Egelman, Edward H., Feng, Z., Frank, J., Grigorieff, N., Jiang, W., Ludtke, Steven J., Medalia, O., Penczek, Pawel A., Rosenthal, Peter B., Rossmann, Michael G., Schmid, Michael F., Schröder, Gunnar F., Steven, Alasdair C., Stokes, David L., Westbrook, John D., Wriggers, W., Yang, H., Young, J., Berman, Helen M., Chiu, W., Kleywegt, Gerard J. and Lawson, Catherine L. Outcome of the First Electron Microscopy Validation Task Force Meeting. Structure, 20, 2 2012), 205--214.Google ScholarCross Ref
- 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, 972012), 698--708.Google Scholar
- Baker, M. L., Ju, T. and Chiu, W. Identification of secondary structure elements in intermediate-resolution density maps. Structure, 15, 1 (Jan 2007), 7--19.Google ScholarCross Ref
- 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 (May 2001), 1033--1044.Google ScholarCross Ref
- 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 (May 21 2004), 117--130.Google ScholarCross Ref
- 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. Journal of Structural Biology, 174, 2 2011), 360--373.Google ScholarCross Ref
- Al Nasr, K., Sun, W. and He, J. Structure prediction for the helical skeletons detected from the low resolution protein density map. BMC Bioinformatics, 11, Suppl 1 (January 2010 2010), S44.Google Scholar
- Lindert, S., Staritzbichler, R., Wötzel, N., Karakaş, M., Stewart, P. L. and Meiler, J. EM-Fold: De Novo Folding of α-Helical Proteins Guided by Intermediate-Resolution Electron Microscopy Density Maps. Structure, 17, 7 (July 2009 2009), 990--1003.Google ScholarCross Ref
- 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 2012), 464--478.Google ScholarCross Ref
- Jones, D. T. Protein secondary structure prediction based on position-specific scoring matrices. J Mol Biol, 292, 2 (Sep 1999), 195--202.Google ScholarCross Ref
- Cheng, J., Randall, A. Z., Sweredoski, M. J. and Baldi, P. SCRATCH: a protein structure and structural feature prediction server. Nucleic Acids Research, 33, suppl 2 (July 1, 2005 2005), W72-W76.Google Scholar
- Pollastri, G. and McLysaght, A. Porter: a new, accurate server for protein secondary structure prediction. Bioinformatics, 21, 8 (Apr 15 2005), 1719--1720. Google ScholarDigital Library
- Ward, J. J., McGuffin, L. J., Buxton, B. F. and Jones, D. T. Secondary structure prediction with support vector machines. Bioinformatics, 19, 13 (Sep 1 2003), 1650--1655.Google ScholarCross Ref
- Wu, Y., Chen, M., Lu, M., Wang, Q. and Ma, J. Determining protein topology from skeletons of secondary structures. J Mol Biol, 350, 3 (Jul 15 2005), 571--586.Google ScholarCross Ref
- Abeysinghe, S., Ju, T., Baker, M. L. and Chiu, W. Shape modeling and matching in identifying 3D protein structures. Computer-Aided Design, 40, 6 2008), 708--720. Google ScholarDigital Library
- Al Nasr, K., Ranjan, D., Zubair, M. and He, J. Ranking Valid Topologies of the Secondary Structure elements Using a constraint Graph. Journal of Bioinformatics and Computational Biology, 9, 3 2011), 415--430.Google ScholarCross Ref
- Bron, C. and Kerbosch, J. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16, 9 1973), 575--577. Google ScholarDigital Library
- Martins, E. d. Q. V., Pascoal, M. M. B. and Santos, J. L. E. d. Deviation Algorithms for Ranking Shortest Paths. International Journal of Foundation of Computer Science, 10, 3 1999), 247--263.Google Scholar
- Al Nasr, K., Liu, C., Rwebangira, M., Burge, L. and He, J. Intensity-based skeletonization of CryoEM grayscale images using a true segmentation-free algorithm. IEEE Transactions on Computational Biology and Bioinformatics 2013 (Under Review).Google Scholar
- Sun, W. and He, J. Native secondary structure topology has near minimum contact energy among all possible geometrically constrained topologies. Proteins: Structure, Function, and Bioinformatics, 77, 1 (October 2009 2009), 159--173.Google Scholar
Index Terms
A Constrained K-shortest Path Algorithm to Rank the Topologies of the Protein Secondary Structure Elements Detected in CryoEM Volume Maps
Recommendations
Solving the secondary structure matching problem in cryo-EM de novo modeling using a constrained K-shortest path graph algorithm
Electron cryomicroscopy is becoming a major experimental technique in solving the structures of large molecular assemblies. More and more three-dimensional images have been obtained at the medium resolutions between 5 and 10Å. At this resolution range, ...
Building the initial chain of the proteins through de novo modeling of the cryo-electron microscopy volume data at the medium resolutions
BCB '12: Proceedings of the ACM Conference on Bioinformatics, Computational Biology and BiomedicineCryo-electron Microscopy (cryoEM) is an advanced imaging technique that produces volume maps at different resolutions. This technique is capable of visualizing large molecular complexes such as viruses and ribosomes. At the medium resolutions, such as 5 ...
Construction of protein backbone pieces using segment-based FBCCD and Cryo-EM skeleton
BCB '14: Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health InformaticsCryo-Electron Microscopy is a biophysical technique that generates volumetric images of macromolecules. Although it is hard to distinguish the backbone from the density map at medium resolutions such as 5-10Å, the location of major secondary structure ...
Comments