Document Open Access Logo

Maxent-Stress Optimization of 3D Biomolecular Models

Authors Michael Wegner, Oskar Taubert, Alexander Schug, Henning Meyerhenke

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.70.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Michael Wegner
Oskar Taubert
Alexander Schug
Henning Meyerhenke

Cite As Get BibTex

Michael Wegner, Oskar Taubert, Alexander Schug, and Henning Meyerhenke. Maxent-Stress Optimization of 3D Biomolecular Models. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 70:1-70:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.70

Abstract

Knowing a biomolecule's structure is inherently linked to and a prerequisite for any detailed understanding of its function. Significant effort has gone into developing technologies for structural characterization. These technologies do not directly provide 3D structures; instead they typically yield noisy and erroneous distance information between specific entities such as atoms or residues, which have to be translated into consistent 3D models.

Here we present an approach for this translation process based on maxent-stress optimization. Our new approach extends the original graph drawing method for the new application's specifics by introducing additional constraints and confidence values as well as algorithmic components. Extensive experiments demonstrate that our approach infers structural models (i.e., sensible 3D coordinates for the molecule's atoms) that correspond well to the distance information, can handle noisy and error-prone data, and is considerably faster than established tools. Our results promise to allow domain scientists nearly-interactive structural modeling based on distance constraints.

Subject Classification

Keywords
  • Distance geometry
  • protein structure determination
  • 3D graph drawing
  • maxent-stress optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Le Thi Hoai An. Solving large scale molecular distance geometry problems by a smoothing technique via the gaussian transform and d.c. programming. Journal of Global Optimization, 27(4):375-397, 2003. URL: http://dx.doi.org/10.1023/a:1026016804633.
  2. Le Thi Hoai An and Pham Dinh Tao. Large-scale molecular optimization from distance matrices by a d.c. optimization approach. SIAM Journal on Optimization, 14(1):77-114, jan 2003. URL: http://dx.doi.org/10.1137/s1052623498342794.
  3. Elisabetta Bergamini, Michael Wegner, Dimitar Lukarski, and Henning Meyerhenke. Estimating current-flow closeness centrality with a multigrid laplacian solver. In Proc. 7th SIAM Workshop on Combinatorial Scientific Computing, CSC 2016, pages 1-12. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974690.ch1.
  4. Helen M. Berman, John Westbrook, Zukang Feng, Gary Gilliland, Talapady N. Bhat, Helge Weissig, Ilya N. Shindyalov, and Philip E. Bourne. The protein data bank. Nucleic Acids Research, 28(1):235-242, Jan 2000. URL: http://dx.doi.org/10.1093/nar/28.1.235.
  5. Pratik Biswas, Kim-Chuan Toh, and Yinyu Ye. A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation. SIAM Journal on Scientific Computing, 30(3):1251-1277, jan 2008. URL: http://dx.doi.org/10.1137/05062754x.
  6. Leonard M. Blumenthal. Theory and Applications of Distance Geometry, volume 347. Oxford, 1953. Google Scholar
  7. Ulrik Brandes and Christian Pich. Eigensolver methods for progressive multidimensional scaling of large data. In Graph Drawing, pages 42-53. Springer Science + Business Media, 2007. URL: http://dx.doi.org/10.1007/978-3-540-70904-6_6.
  8. Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM, 42(1):67-90, jan 1995. URL: http://dx.doi.org/10.1145/200836.200853.
  9. Gordon M. Crippen, Timothy F. Havel, et al. Distance Geometry and Molecular Conformation, volume 74. Research Studies Press Taunton, UK, 1988. Google Scholar
  10. Angel E. Dago, Alexander Schug, Andrea Procaccini, James A. Hoch, Martin Weigt, and Hendrik Szurmant. Structural basis of histidine kinase autophosphorylation deduced by integrating genomics, molecular dynamics, and mutagenesis. Proceedings of the National Academy of Sciences, 109(26):E1733-E1742, 2012. Google Scholar
  11. Eleonora De Leonardis, Benjamin Lutz, Sebastian Ratz, Simona Cocco, Rémi Monasson, Alexander Schug, and Martin Weigt. Direct-coupling analysis of nucleotide coevolution facilitates rna secondary and tertiary structure prediction. Nucleic acids research, 43(21):10444-10455, 2015. Google Scholar
  12. Qunfeng Dong and Zhijun Wu. A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances. Journal of Global Optimization, 22(1/4):365-375, 2002. URL: http://dx.doi.org/10.1023/a:1013857218127.
  13. Peter Eades. A heuristic for graph drawing. Congressus Numerantium, 42:146-160, 1984. Google Scholar
  14. Xingyuan Fang and Kim-Chuan Toh. Using a distributed SDP approach to solve simulated protein molecular conformation problems. In Distance Geometry, pages 351-376. Springer Science + Business Media, nov 2012. URL: http://dx.doi.org/10.1007/978-1-4614-5128-0_17.
  15. Thomas M. J. Fruchterman and Edward M. Reingold. Graph drawing by force-directed placement. Software: Practice and Experience, 21(11):1129-1164, Nov 1991. URL: http://dx.doi.org/10.1002/spe.4380211102.
  16. Emden R. Gansner, Yifan Hu, and Stephen North. A maxent-stress model for graph layout. IEEE Transactions on Visualization and Computer Graphics, 19(6):927-940, jun 2013. URL: http://dx.doi.org/10.1109/tvcg.2012.299.
  17. Oliver F. Lange, Nils-Alexander Lakomek, Christophe Farès, Gunnar F. Schröder, Korvin F. A. Walter, Stefan Becker, Jens Meiler, Helmut Grubmüller, Christian Griesinger, and Bert L. De Groot. Recognition dynamics up to microseconds revealed from an rdc-derived ubiquitin ensemble in solution. science, 320(5882):1471-1475, 2008. Google Scholar
  18. Ngai-Hang Z. Leung and Kim-Chuan Toh. An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization. SIAM Journal on Scientific Computing, 31(6):4351-4372, jan 2010. URL: http://dx.doi.org/10.1137/080733103.
  19. Leo Liberti, Carlile Lavor, Nelson Maculan, and Fabrizio Marinelli. Double variable neighbourhood search with smoothing for the molecular distance geometry problem. Journal of Global Optimization, 43(2-3):207-218, aug 2009. URL: http://dx.doi.org/10.1007/s10898-007-9218-1.
  20. Leo Liberti, Carlile Lavor, Nelson Maculan, and Antonio Mucherino. Euclidean distance geometry and applications. SIAM Review, 56(1):3-69, jan 2014. URL: http://dx.doi.org/10.1137/120875909.
  21. Fabian Lipp, Alexander Wolff, and Johannes Zink. Faster force-directed graph drawing with the well-separated pair decomposition. In Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers, volume 9411 of LNCS, pages 52-59. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-27261-0_5.
  22. Oren E. Livne and Achi Brandt. Lean algebraic multigrid (LAMG): Fast graph laplacian linear solver. SIAM Journal on Scientific Computing, 34(4):B499-B522, Jan 2012. URL: http://dx.doi.org/10.1137/110843563.
  23. Jeffrey W. Martin, Anthony K. Yan, Chris Bailey-Kellogg, Pei Zhou, and Bruce R. Donald. A geometric arrangement algorithm for structure determination of symmetric protein homo-oligomers from noes and rdcs. Journal of Computational Biology, 18(11):1507-1523, 2011. Google Scholar
  24. Henning Meyerhenke, Martin Nöllenburg, and Christian Schulz. Drawing large graphs by multilevel maxent-stress optimization. In Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers, volume 9411 of LNCS, pages 30-43. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-27261-0_3.
  25. Jorge J. Moré and Zhijun Wu. Global continuation for distance geometry problems. SIAM Journal on Optimization, 7(3):814-836, aug 1997. URL: http://dx.doi.org/10.1137/s1052623495283024.
  26. Jorge J. Moré and Zhijun Wu. Distance geometry optimization for protein structures. Journal of Global Optimization, 15(3):219-234, 1999. Google Scholar
  27. Antonio Mucherino, Carlile Lavor, Leo Liberti, and Nelson Maculan, editors. Distance Geometry: Theory, Methods, and Applications. Springer Science + Business Media, 2013. URL: http://dx.doi.org/10.1007/978-1-4614-5128-0.
  28. Jeffre K. Noel, Paul C. Whitford, and Onuchic Jose N. The shadow map: A general contact definition for capturing the dynamics of biomolecular folding and function. J Phys Chem B, 116(29):8692-8702, 2013. URL: http://dx.doi.org/10.1021/jp300852d.
  29. Sergey Ovchinnikov, Hahnbeom Park, Neha Varghese, Po-Ssu Huang, Georgios A. Pavlopoulos, David E. Kim, Hetunandan Kamisetty, Nikos C. Kyrpides, and David Baker. Protein structure determination using metagenome sequence data. Science, 355(6322):294-298, 2017. Google Scholar
  30. Carol A. Rohl, Charlie E. M. Strauss, Kira M. S. Misura, and David Baker. Protein structure prediction using rosetta. Methods in enzymology, 383:66-93, 2004. Google Scholar
  31. Peter W. Rose, Andreas Prlić, Chunxiao Bi, Wolfgang F. Bluhm, Cole H. Christie, Shuchismita Dutta, Rachel Kramer Green, David S. Goodsell, John D. Westbrook, Jesse Woo, Jasmine Young, Christine Zardecki, Helen M. Berman, Philip E. Bourne, and Stephen K. Burley. The rcsb protein data bank: views of structural biology for basic and applied research and education. Nucleic Acids Research, 43(D1):D345, 2015. URL: http://dx.doi.org/10.1093/nar/gku1214.
  32. James B. Saxe. Embeddability of weighted graphs in k-space is strongly NP-hard. Carnegie-Mellon University, Department of Computer Science, 1980. Google Scholar
  33. A. Schug, T. Herges, and W. Wenzel. Reproducible protein folding with the stochastic tunneling method. Physical review letters, 91(15):158102, 2003. Google Scholar
  34. Alexander Schug and José N. Onuchic. From protein folding to protein function and biomolecular binding by energy landscape theory. Current opinion in pharmacology, 10(6):709-714, 2010. Google Scholar
  35. Alexander Schug, Martin Weigt, José N. Onuchic, Terence Hwa, and Hendrik Szurmant. High-resolution protein complexes from integrating genomic information with molecular simulation. Proceedings of the National Academy of Sciences, 106(52):22124-22129, 2009. Google Scholar
  36. Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. Networkit: A tool suite for large-scale complex network analysis. Network Science, 4(4):508-530, Dec 2016. Google Scholar
  37. J. B. Stothers. Carbon-13 NMR Spectroscopy: Organic Chemistry, A Series of Monographs, volume 24. Elsevier, 2012. Google Scholar
  38. El-Ghazali Talbi. Metaheuristics: From Design to Implementation. Wiley Publishing, 2009. Google Scholar
  39. Guido Uguzzoni, Shalini John Lovis, Francesco Oteri, Alexander Schug, Hendrik Szurmant, and Martin Weigt. Large-scale identification of coevolution signals across homo-oligomeric protein interfaces by direct coupling analysis. Proceedings of the National Academy of Sciences, 114(13):E2662-E2671, 2017. Google Scholar
  40. D. Voet and J. G. Voet. Biochemistry, 4th Edition. John Wiley &Sons, 2010. Google Scholar
  41. Michael Wegner, Oskar Taubert, Alexander Schug, and Henning Meyerhenke. Maxent-stress optimization of 3D biomolecular models. arXiv preprint arXiv:1706.06805, Jun 2017. URL: https://arxiv.org/abs/1706.06805.
  42. Kurt Wüthrich. Protein structure determination in solution by nmr spectroscopy. Journal of Biological Chemistry, 265(36):22059-22062, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact