Parameter Synthesis for Cardiac Cell Hybrid Models Using δ-Decisions

Bing Liu, Soonho Kong, Sicun Gao, Paolo Zuliani, Edmund M. Clarke

TL;DR

This paper introduces a novel framework for automatically finding parameter values in complex biological models that exhibit both continuous and discrete behaviors (hybrid models). By leveraging "δ-complete decision procedures," they overcome the inherent undecidability of analyzing such systems, enabling efficient parameter synthesis and model validation, particularly for cardiac cell dynamics.

What Problem Does This Paper Address?

Systems biology often relies on mathematical models to understand biological processes. A critical challenge is identifying the correct parameter values for these models so they accurately reflect observed biological behavior (e.g., time-series data). Many biological systems, like cell cycles or cardiac cell activity, exhibit distinct "modes" of operation, each with its own continuous dynamics. These are naturally modeled as "hybrid automata," which combine discrete states with continuous differential equations. However, analyzing hybrid automata, even with simple linear dynamics, is computationally undecidable. This undecidability makes it extremely difficult to synthesize parameters that satisfy desired behavioral constraints, especially when dealing with the nonlinear dynamics common in biological systems.

Methods

The core of the paper's contribution lies in its parameter synthesis framework, which sidesteps the undecidability problem by using δ-complete decision procedures. Instead of seeking exact answers, these procedures provide answers with a small, controllable error (δ).

Here's a breakdown of their approach:

  • LRF-Formulas: They use a first-order logic language (LRF) that can express complex relationships involving arbitrary computable real functions, including solutions to nonlinear Ordinary Differential Equations (ODEs).
  • δ-Weakening: To handle undecidability, they introduce a "δ-weakening" of formulas. This means replacing strict inequalities (e.g., t > 0) with slightly relaxed ones (e.g., t > -δ). This relaxation allows for decidable analysis.
  • δ-Decisions: The framework then performs "δ-decisions" on these weakened formulas. This means determining if a formula is definitively false (unsat) or potentially true (δ-sat) within the given error margin.
  • Hybrid Automata Encoding: They encode hybrid automata models into this LRF framework. This involves defining the states (modes), continuous dynamics (ODEs), jump conditions between modes, and invariants (conditions that must hold within a mode).
  • Bounded Model Checking: They adapt bounded model checking techniques to verify reachability properties of these hybrid automata. This involves checking if a specific state or region of the state space can be reached within a bounded number of discrete transitions.
  • Parameter Synthesis: The parameter synthesis problem is framed as a reachability question: "Does there exist a parameter combination for which the model reaches a goal state within k steps?" The δ-complete decision procedures are used to answer this. If a goal state is reachable (δ-sat), the tool can return a "witness" – a set of parameter values that satisfy the condition. If it's definitively unreachable (unsat), the model is deemed unfeasible for that property.

Datasets

Not discussed in the paper. The paper focuses on applying its method to existing, well-established models of cardiac cell dynamics.

Key Insights and Ideas

  • Bridging Undecidability with Controlled Approximation: The most significant insight is the successful application of δ-complete decision procedures to overcome the inherent undecidability of hybrid system analysis. This allows for practical, albeit approximate, verification and synthesis.
  • Parameter Synthesis as Reachability: Reframing parameter synthesis as a reachability problem for hybrid automata provides a powerful and unified approach.
  • Model Falsification for Biological Relevance: The framework can effectively "falsify" models. If a model cannot reproduce known biological behaviors (like specific action potential morphologies) for any reasonable parameter values, it can be ruled out, guiding the selection of more appropriate models.
  • Identifying Disease-Related Parameter Ranges: The method can pinpoint critical parameter ranges that lead to undesirable system behaviors, such as loss of cardiac cell excitability, which are directly relevant to understanding and potentially treating cardiac disorders.

Key Results

  • Successful Analysis of Nonlinear Cardiac Models: The paper demonstrates the framework's effectiveness on two highly nonlinear hybrid models of cardiac cell action potentials (BCF and FK models).
  • Model Falsification: The FK model was successfully falsified for its inability to reproduce the "spike-and-dome" action potential morphology observed in epicardial cells, while the BCF model could.
  • Robustness Verification: The models were shown to be robust to small stimulation amplitudes, meaning they wouldn't incorrectly trigger an action potential.
  • Identification of Disease Parameters: The framework identified critical parameter ranges for the BCF model that lead to a loss of cardiac cell excitability. Specifically, they found conditions like τo1 ∈ (0, 0.006) ∨ τo2 ∈ (0, 0.13) ∨ 6.2 · τso1 + τso2 ≥ 9.9 that can induce such disorders.
  • Efficiency: The authors report that their parameter synthesis framework is "convenient and efficient," with experimental runtimes typically in the order of seconds to minutes for the tested models.

Limitations and Future Work

  • Over-Approximation: The paper acknowledges that a "δ-sat" answer might be due to the over-approximation introduced by the δ-weakening. While this behavior aligns with safety requirements (an "unsat" is always correct), it means that a "δ-sat" result might not perfectly reflect the true system behavior.
  • Generalization to Other Formalisms: The authors suggest future work in extending their method to other model formalisms like SBML (Systems Biology Markup Language) and Ptolemy models.
  • Parameter Estimation from Experimental Data: A promising direction is applying the method for parameter estimation directly from noisy experimental data by encoding this data into logic formulas.
  • Complexity: While the framework is efficient for the tested cases, the paper notes that the complexity of the d-decision problem can increase with the number of quantifier alternations in the formulas.

Summary updated

Abstract

A central problem in systems biology is to identify parameter values such that a biological model satisfies some behavioral constraints (e.g., time series). In this paper we focus on parameter synthesis for hybrid (continuous/discrete) models, as many biological systems can possess multiple operational modes with specific continuous dynamics in each mode. These biological systems are naturally modeled as hybrid automata, most often with nonlinear continuous dynamics. However, hybrid automata are notoriously hard to analyze — even simple reachability for hybrid systems with linear differential dynamics is an undecidable problem. In this paper we present a parameter synthesis framework based on δ-complete decision procedures that sidesteps undecidability. We demonstrate our method on two highly nonlinear hybrid models of the cardiac cell action potential. The results show that our parameter synthesis framework is convenient and efficient, and it enabled us to select a suitable model to study and identify crucial parameter ranges related to cardiac disorders.
BibTeX
@inproceedings{liu2014parameter,
  author = {Bing Liu and Soonho Kong and Sicun Gao and Paolo Zuliani and Edmund M. Clarke},
  title = {{Parameter Synthesis for Cardiac Cell Hybrid Models Using δ-Decisions}},
  booktitle = {CMSB},
  year = {2014},
  url = {https://openreview.net/forum?id=fJBvWP-A1l},
}
Figure