TY - JOUR

T1 - Computing and optimizing over all fixed-points of discrete systems on large networks

T2 - Computing and optimizing over all fixed-points of discrete systems on large networks

AU - Riehl, James R.

AU - Zimmerman, Maxwell I.

AU - Singh, Matthew F.

AU - Bowman, Gregory R.

AU - Ching, Shinung

N1 - Funding Information:
Data accessibility. Code used to implement the methods described in this paper are available at the following link: https://github.com/jrriehl/ FindEQ. Authors’ contributions. J.R.R. and S.C. conceived and developed the technical theory, simulations, performed the case studies, and prepared the manuscript. M.I.Z. and G.R.B. conceived and analysed the protein folding case study. M.F.S. prepared the data from the Human Connectome Project. All authors contributed to writing and editing the manuscript. Competing interests. The authors declare no competing interests. Funding. We are grateful to all the funders of this work, which was supported by grant 15RT0189 from the US Air Force Office of Scientific Research, grant nos 1537015, 1509342, 1653589 from the US National Science Foundation, and by the National Science Foundation CAREER Award MCB-1552471. S.C. and G.R.B. hold Career Awards at the Scientific Interface from the Burroughs-Wellcome Fund. M.I.Z. holds a Monsanto Graduate Fellowship and a Center for Biological Systems Engineering Fellowship. M.F.S. was partially supported by NSF-DGE-1143954.
Publisher Copyright:
© 2020 The Author(s).

PY - 2020/9/1

Y1 - 2020/9/1

N2 - Equilibria, or fixed points, play an important role in dynamical systems across various domains, yet finding them can be computationally challenging. Here, we show how to efficiently compute all equilibrium points of discrete-valued, discrete-time systems on sparse networks. Using graph partitioning, we recursively decompose the original problem into a set of smaller, simpler problems that are easy to compute, and whose solutions combine to yield the full equilibrium set. This makes it possible to find the fixed points of systems on arbitrarily large networks meeting certain criteria. This approach can also be used without computing the full equilibrium set, which may grow very large in some cases. For example, one can use this method to check the existence and total number of equilibria, or to find equilibria that are optimal with respect to a given cost function. We demonstrate the potential capabilities of this approach with examples in two scientific domains: computing the number of fixed points in brain networks and finding the minimal energy conformations of lattice-based protein folding models.

AB - Equilibria, or fixed points, play an important role in dynamical systems across various domains, yet finding them can be computationally challenging. Here, we show how to efficiently compute all equilibrium points of discrete-valued, discrete-time systems on sparse networks. Using graph partitioning, we recursively decompose the original problem into a set of smaller, simpler problems that are easy to compute, and whose solutions combine to yield the full equilibrium set. This makes it possible to find the fixed points of systems on arbitrarily large networks meeting certain criteria. This approach can also be used without computing the full equilibrium set, which may grow very large in some cases. For example, one can use this method to check the existence and total number of equilibria, or to find equilibria that are optimal with respect to a given cost function. We demonstrate the potential capabilities of this approach with examples in two scientific domains: computing the number of fixed points in brain networks and finding the minimal energy conformations of lattice-based protein folding models.

KW - brain networks

KW - energy landscapes

KW - fixed points

KW - graph partitioning

KW - optimization

KW - protein folding

UR - http://www.scopus.com/inward/record.url?scp=85090709679&partnerID=8YFLogxK

U2 - 10.1098/rsif.2020.0126

DO - 10.1098/rsif.2020.0126

M3 - Article

C2 - 32900299

AN - SCOPUS:85090709679

VL - 17

JO - Journal of the Royal Society Interface

JF - Journal of the Royal Society Interface

SN - 1742-5689

IS - 170

M1 - 20200126

ER -