{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T09:34:20Z","timestamp":1790760860775,"version":"4.1.0"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>Trajectory- or mesh-based methods for analyzing the dynamical behavior of large molecules tend to be impractical due to the curse of dimensionality---their computational cost increases exponentially with the size of the molecule. We propose a method to break the curse by a novel square root approximation of transition rates, Monte Carlo quadrature and a discretization approach based on solving linear programs. With randomly sampled points on the molecular energy landscape and randomly generated discretizations of the molecular configuration space as our initial data, we construct a matrix describing the transition rates between adjacent discretization regions. This transition rate matrix yields a Markov state model of the molecular dynamics. We use Perron cluster analysis and coarse-graining techniques in order to identify metastable sets in configuration space and approximate the transition rates between the metastable sets. Application of our method to a simple energy landscape on a two-dimensional configuration space provides proof of concept and an example for which we compare the performance of different discretizations. We show that the computational cost of our method grows only polynomially with the size of the molecule. However, finding discretizations of higher-dimensional configuration spaces in which metastable sets can be identified remains a challenge.<\/jats:p>","DOI":"10.1137\/120899959","type":"journal-article","created":{"date-parts":[[2013,6,14]],"date-time":"2013-06-14T15:01:35Z","timestamp":1371222095000},"page":"738-756","source":"Crossref","is-referenced-by-count":33,"title":["A Square Root Approximation of Transition Rates for a Markov State Model"],"prefix":"10.1137","volume":"34","author":[{"given":"Han Cheng","family":"Lie","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Konstantin","family":"Fackeldey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcus","family":"Weber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,6,13]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu,\n                      Spatial tessellations: Concepts and applications of Voronoi diagrams\n                      , 2nd ed., Wiley Ser. Probab. Stat., Wiley, New York, 2000.","DOI":"10.1002\/9780470317013"},{"key":"atypb2","unstructured":"R. Bellman,\n                      Dynamic programming\n                      , Princeton University Press, Princeton, NJ, 1972."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"A. Bovier,\n                      Metastability: A potential theoretic approach\n                      , Proceedings of the International Congress of Mathematicians (ICM), Madrid, Spain, 2006. Volume III: Invited Lectures. European Mathematical Society, Zurich, pp. 499-518.","DOI":"10.4171\/022-3\/26"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.2307\/3215235"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"atypb6","first-page":"191","author":"Sch\u00fctte C.","year":"2001","journal-title":"New York"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"P. Deuflhard and M. Weber,\n                      Robust Perron Cluster Analysis in Conformation Dynamics\n                      , Technical report ZIB 03-19, Zuse Institut Berlin, 2005.","DOI":"10.1016\/j.laa.2004.10.026"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmb.2004.06.063"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1003962107"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.4.369"},{"key":"atypb12","unstructured":"W. Huisinga,\n                      Metastability of Markovian Systems: A Transfer Operator Based Approach in Application to Molecular Dynamics\n                      , Ph.D. thesis, Department of Mathematics and Computer Science, Freie Universit\u00e4t, Berlin, 2001."},{"key":"atypb13","first-page":"167","author":"Huisinga W.","year":"2006","journal-title":"Berlin"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1063\/1.2714538"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1063\/1.3565032"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1021\/ct300077q"},{"key":"atypb17","unstructured":"J. E. Goodman and J. O'Rourke (eds.),\n                      Handbook of Discrete and Computational Geometry\n                      , CRC Press, Boca Raton, FL, 1997."},{"key":"atypb18","unstructured":"K. Fackeldey, S. Roeblitz, O. Scharkoi, and M. Weber,\n                      Soft Versus Hard Metastable Conformations in Molecular Simulations\n                      , ZIB Report 02-12, Zuse Institut Berlin, 2011."},{"key":"atypb19","first-page":"191","volume":"20","author":"Khachiyan L. G.","year":"1979","journal-title":"Soviet Math. Dokl."},{"key":"atypb20","unstructured":"S. Kube and P. Deuflhard,\n                      Errata on Robust Perron Cluster Analysis in Conformation Dynamics\n                      , Technical report ZIB 03-19, Zuse Institut Berlin, 2006."},{"key":"atypb21","unstructured":"S. Kube and M. Weber,\n                      Coarse Grained Molecular Kinetics\n                      , ZIB Report 06-35, Zuse Institut Berlin, 2006."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1063\/1.2404953"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars,\n                      Computational Geometry: Algorithms and Applications\n                      , 3rd ed., Springer-Verlag, Berlin, 2008.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/090764049"},{"key":"atypb25","unstructured":"J. Matousek and B. G\u00e4rtner,\n                      Understanding and Using Linear Programming\n                      , Springer, 2007."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/100798910"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"J. R. Norris,\n                      Markov Chains\n                      , Cambridge University Press, Cambridge, UK, 1997.","DOI":"10.1017\/CBO9780511810633"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(00)00095-1"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1063\/1.2335447"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/004\/40"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1063\/1.1570396"},{"key":"atypb33","unstructured":"S. Rakovic, P. Grieder, and C. Jones,\n                      Computation of Voronoi Diagrams and Delaunay Triangulation via Parametric Linear Programming\n                      , Tech. report, http:\/\/infoscience.epfl.ch\/record\/169767\/files\/cued\\textunderscore control\\textunderscore 779.pdf (2004)."},{"key":"atypb34","unstructured":"C. Sch\u00fctte,\n                      Conformational Dynamics: Modelling, Theory, Algorithm, and Application to Biomolecules\n                      , Thesis, Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, 1999."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.2307\/1909285"},{"key":"atypb36","unstructured":"T. Hiroshima, Y. Miyamoto, and K. Sugihara,\n                      Another Proof of Polynomial-Time Recognizability of Delaunay Graphs\n                      , IEICE Trans. Fund., E83-A (2000), pp. 627-638."},{"key":"atypb37","unstructured":"M. Weber,\n                      Meshless Methods in Conformation Dynamics\n                      , Ph.D. thesis, Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, 2006."},{"key":"atypb38","unstructured":"M. Weber,\n                      A Subspace Approach to Molecular Markov State Models via an Infinitesimal Generator\n                      , Thesis, Department of Mathematics and Computer Science, Freie Universit\u00e4t Berlin, 2010."}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120899959","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:59:47Z","timestamp":1787331587000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120899959"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120899959"],"URL":"https:\/\/doi.org\/10.1137\/120899959","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}