skip to main content
10.1145/2506583.2506705acmconferencesArticle/Chapter ViewAbstractPublication PagesbcbConference Proceedingsconference-collections
tutorial

A Constrained K-shortest Path Algorithm to Rank the Topologies of the Protein Secondary Structure Elements Detected in CryoEM Volume Maps

Authors Info & Claims
Published:22 September 2013Publication History

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.

References

  1. 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 ScholarGoogle ScholarCross RefCross Ref
  2. 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 ScholarGoogle Scholar
  3. Chiu, W. and Schmid, M. F. Pushing back the limits of electron cryomicroscopy. Nature Struct. Biol., 41997), 331--333.Google ScholarGoogle Scholar
  4. 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 ScholarGoogle Scholar
  5. 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 ScholarGoogle ScholarCross RefCross Ref
  6. 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 ScholarGoogle ScholarCross RefCross Ref
  7. 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 ScholarGoogle Scholar
  8. 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 ScholarGoogle ScholarCross RefCross Ref
  9. 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 ScholarGoogle ScholarCross RefCross Ref
  10. 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 ScholarGoogle Scholar
  11. 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 ScholarGoogle Scholar
  12. 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 ScholarGoogle ScholarCross RefCross Ref
  13. 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 ScholarGoogle Scholar
  14. 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 ScholarGoogle ScholarCross RefCross Ref
  15. 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 ScholarGoogle ScholarCross RefCross Ref
  16. 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 ScholarGoogle ScholarCross RefCross Ref
  17. 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 ScholarGoogle ScholarCross RefCross Ref
  18. 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 ScholarGoogle Scholar
  19. 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 ScholarGoogle ScholarCross RefCross Ref
  20. 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 ScholarGoogle ScholarCross RefCross Ref
  21. Jones, D. T. Protein secondary structure prediction based on position-specific scoring matrices. J Mol Biol, 292, 2 (Sep 1999), 195--202.Google ScholarGoogle ScholarCross RefCross Ref
  22. 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 ScholarGoogle Scholar
  23. Pollastri, G. and McLysaght, A. Porter: a new, accurate server for protein secondary structure prediction. Bioinformatics, 21, 8 (Apr 15 2005), 1719--1720. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. 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 ScholarGoogle ScholarCross RefCross Ref
  25. 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 ScholarGoogle ScholarCross RefCross Ref
  26. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  27. 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 ScholarGoogle ScholarCross RefCross Ref
  28. Bron, C. and Kerbosch, J. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16, 9 1973), 575--577. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. 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 ScholarGoogle Scholar
  30. 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 ScholarGoogle Scholar
  31. 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 ScholarGoogle Scholar

Index Terms

  1. A Constrained K-shortest Path Algorithm to Rank the Topologies of the Protein Secondary Structure Elements Detected in CryoEM Volume Maps

              Recommendations

              Comments

              Login options

              Check if you have access through your login credentials or your institution to get full access on this article.

              Sign in
              • Published in

                cover image ACM Conferences
                BCB'13: Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics
                September 2013
                987 pages
                ISBN:9781450324342
                DOI:10.1145/2506583

                Copyright © 2013 ACM

                Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

                Publisher

                Association for Computing Machinery

                New York, NY, United States

                Publication History

                • Published: 22 September 2013

                Permissions

                Request permissions about this article.

                Request Permissions

                Check for updates

                Qualifiers

                • tutorial
                • Research
                • Refereed limited

                Acceptance Rates

                BCB'13 Paper Acceptance Rate43of148submissions,29%Overall Acceptance Rate254of885submissions,29%

              PDF Format

              View or Download as a PDF file.

              PDF

              eReader

              View online with eReader.

              eReader