Spectral clustering of Markov chain transition matrices with complex eigenvalues. (English) Zbl 07866504
Summary: The Robust Perron Cluster Analysis (PCCA+) has become a popular spectral clustering algorithm for coarse-graining transition matrices of nearly decomposable Markov chains with transition states. Originally developed for reversible Markov chains, the algorithm only worked for transition matrices with real eigenvalues. In this paper, we therefore extend the theoretical framework of PCCA+ to Markov chains with a complex eigen-decomposition. We show that by replacing a complex conjugate pair of eigenvectors by their real and imaginary components, a real representation of the same subspace is obtained, which is suitable for the cluster analysis. We show that our approach leads to the same results as the generalized PCCA+ (GPCCA), which replaces the complex eigen-decomposition by a conceptually more difficult real Schur decomposition. We apply the method on non-reversible Markov chains, including circular chains, and demonstrate its efficiency compared to GPCCA. The experiments are performed in the Matlab programming language and codes are provided.
Keywords:
spectral cluster analysis; complex eigen-decomposition; invariant sub-space condition; discrete-time Markov chains; stochastic matrices; Markov state modelReferences:
| [1] | Frank, A. S.; Röblitz, S., cPCCA: Robust perron cluster analysis for stochastic matrices with complex eigenvalues, (2022), GitHub, Available online at https://https://github.com/sroeblitz/cPCCA/tree/v1.0.0 |
| [2] | Reuter, B., GPCCA: Generalized perron cluster cluster analysis program to coarse-grain reversible and non-reversible Markov state models, (2018), GitHub, Available online at https://github.com/msmdev/gpcca |
| [3] | Reuter, B.; Fackeldey, K.; Weber, M., Generalized Markov modeling of nonreversible molecular kinetics, J. Chem. Phys., 150, 17, Article 174103 pp., (2019) |
| [4] | Chu, B. K.; Tse, M. J.; Sato, R. R.; Read, E. L., Markov state models of gene regulatory networks, BMC Syst. Biol., 11, 14, 1-17, (2017) |
| [5] | Tse, M. J.; Chu, B. K.; Gallivan, C. P.; Read, E. L., Rare-event sampling of epigenetic landscapes and phenotype transitions, PLoS Comput. Biol., 14, 8, Article e1006336 pp., (2018) |
| [6] | Swope, W. C.; Pitera, J. W.; Suits, F.; Pitman, M.; Eleftheriou, M.; Fitch, B. G.; Germain, R. S.; Rayshubski, A.; Ward, T. J.C.; Zhestkov, Y.; Zhou, R., Describing protein folding kinetics by molecular dynamics simulations. 2. Example applications to alanine dipeptide and a \(\beta \)-hairpin peptide, J. Phys. Chem. B, 108, 21, 6582-6594, (2004) |
| [7] | Noé, F.; Schütte, C.; Vanden-Eijnden, E.; Reich, L.; Weikl, T. R., Constructing the equilibrium ensemble of folding pathways from short off-equilibrium simulations, Proc. Natl. Acad. Sci. USA, 106, 45, 19011-19016, (2009) · Zbl 1254.92001 |
| [8] | Fersht, A. R., Characterizing transition states in protein folding: an essential step in the puzzle, Curr. Opin. Struct. Biol., 5, 1, 79-84, (1995) |
| [9] | Chodera, J. D.; Noé, F., Markov state models of biomolecular conformational dynamics, Curr. Opin. Struct. Biol., 25, 135-144, (2014) |
| [10] | Burke, P. E.P.; Campos, C. B.d. L.; Costa, L.d. F.; Quiles, M. G., A biochemical network modeling of a whole-cell, Sci. Rep., 10, 13303, 1-14, (2020) |
| [11] | Reuter, B.; Weber, M.; Fackeldey, K.; Röblitz, S.; Garcia, M. E., Generalized Markov state modeling method for nonequilibrium biomolecular dynamics: Exemplified on amyloid \(\beta\) conformational dynamics driven by an oscillating electric field, J. Chem. Theory Comput., 14, 7, 3579-3594, (2018) |
| [12] | Pande, V. S.; Beauchamp, K.; Bowman, G. R., Everything you wanted to know about Markov state models but were afraid to ask, Methods, 52, 1, 99-105, (2010) |
| [13] | Röblitz, S.; Weber, M., Fuzzy spectral clustering by PCCA+: application to Markov state models and data classification, Adv. Data Anal. Classif., 7, 2, 147-179, (2013) · Zbl 1273.62145 |
| [14] | Andrilli, S.; Hecker, D., Chapter 8 - additional applications, (Elementary Linear Algebra, (2010), Academic Press: Academic Press Boston), 491-585 |
| [15] | Husic, B. E.; Pande, V. S., Markov state models: From an art to a science, J. Am. Chem. Soc., 140, 7, 2386-2396, (2018) |
| [16] | Fackeldey, K.; Sikorski, A.; Weber, M., Spectral clustering for non-reversible Markov chains, Comp. Appl. Math., 37, 5, 6376-6391, (2018) · Zbl 1413.62082 |
| [17] | Weber, M.; Fackeldey, K., G-PCCA: Spectral Clustering for Non-reversible Markov ChainsTechnical Repor 15-35, (2015), ZIB, Available online at https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/5550 |
| [18] | Brandts, J. H., Matlab code for sorting real Schur forms, Numer. Linear Algebra Appl., 9, 3, 249-261, (2002) · Zbl 1071.65500 |
| [19] | Weber, M., Implications of PCCA+ in molecular simulation, Comput, 6, 1, 20, (2018) |
| [20] | Deuflhard, P.; Weber, M., Robust perron cluster analysis in conformation dynamics, Linear Algebra Appl., 398, 161-184, (2005) · Zbl 1070.15019 |
| [21] | Fackeldey, K.; Sikorski, A.; Weber, M., Spectral Clustering for Non-reversible Markov ChainsTechnical Report 18-48, (2018), ZIB, Available online at https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7021. (Accessed 14 June 2022) · Zbl 1413.62082 |
| [22] | Frank, A. S.; Larripa, K.; Ryu, H.; Snodgrass, R. G.; Röblitz, S., Bifurcation and sensitivity analysis reveal key drivers of multistability in a model of macrophage polarization, J. Theoret. Biol., 509, 110511, (2021) · Zbl 1457.92050 |
| [23] | Gupta, P. B.; Fillmore, C. M.; Jiang, G.; Shapira, S. D.; Tao, K.; Kuperwasser, C.; Lander, E. S., Stochastic state transitions give rise to phenotypic equilibrium in populations of cancer cells, Cell, 146, 4, 633-644, (2011) |
| [24] | Ferrell, J. E.; Tsai, T. Y.; Yang, Q., Modeling the cell cycle: Why do certain circuits oscillate?, Cell, 144, 6, 874-885, (2011) |
| [25] | Chhimwal, M.; Agrawal, S.; Kumar, G., Markovian approach to evaluate circularity in supply chain of non ferrous metal industry, Resour. Policy, 80, Article 103260 pp., (2023) |
| [26] | Weber, M., Eigenvalues of non-reversible Markov chains - A case studyTechnical Report 17-13, (2017), ZIB, Available online at https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/6219. (Accessed on 14 June 2022) |
| [27] | Reuter, B.; Klein, M.; Lange, M., pyGPCCA - Python GPCCA: Generalized perron cluster cluster analysis package to coarse-grain reversible and non-reversible Markov state models, (2021), GitHub, Available online at https://github.com/msmdev/pyGPCCA |
| [28] | Sikorski, A.; Sechi, R.; Helfmann, L., Cmdtools: Python implementation of severals tools for the analysis of dynamical systems from the transfer operator perspective, (2021), GitHub, Available online at https://github.com/zib-cmd/cmdtools/tree/v1.0.1 |
| [29] | Stewart, G. W., A krylov-Schur algorithm for large eigenproblems, SIAM J. Matrix Anal. Appl., 23, 3, 601-614, (2001) · Zbl 1003.65045 |
| [30] | Hernández, V.; Román, J. E.; Tomás, A.; Vidal, V., Krylov-Schur methods in SLEPcTechnical Report STR-7, (2007), Scalable Library for Eigenvalue Problem Computations: Scalable Library for Eigenvalue Problem Computations Universitat Polytécnica de Valéncia, Available online at https://slepc.upv.es/documentation/reports/str7.pdf |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
