💻 computer science

SMT with Uninterpreted Functions and Monotonicity Constraints in Systems Biology

This paper presents an SMT-based approach for inferring biological models using uninterpreted functions with monotonicity constraints, demonstrating through extensive benchmarks that its lazy instantiation strategy significantly outperforms both naive quantified encodings and state-of-the-art domain-specific tools like Bonesis and AEON.

Original authors: Ondřej Huvar, Martin Jonáš, Samuel Pastva

Published 2026-04-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ondřej Huvar, Martin Jonáš, Samuel Pastva

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery in a complex city. The city is a biological system (like a cell), and the "citizens" are genes or proteins. These citizens talk to each other, passing notes that tell them to turn "on" (produce a chemical) or "off" (stop producing it).

Your job is to figure out exactly how they talk. You know the rules of the city (the network of connections), and you have seen the city in a few specific "frozen moments" where everything stays the same (these are called fixed points). But you don't know the specific instructions each citizen follows to decide what to do next.

This paper is about building a super-smart computer detective to solve this mystery.

The Problem: The "Black Box" Rules

In biology, we often know that Gene A influences Gene B, but we don't know the exact formula.

The "Uninterpreted Function": Think of this as a Black Box. You put numbers in (the state of the neighbors), and a number comes out (the next state of the gene). We don't know what's inside the box, but we know it exists.
The "Monotonicity" Rule: In the real world, biology usually follows a simple rule: Cause and Effect are consistent.
- If a "Good Guy" (an activator) sends a stronger signal, the result should be more "Good" (or at least not less).
- If a "Bad Guy" (an inhibitor) sends a stronger signal, the result should be less "Good".
- It rarely happens that a stronger signal from a Good Guy suddenly makes the result worse. This consistency is called Monotonicity.

The challenge is: How do we teach a computer to find the secret rules inside those Black Boxes, knowing that they must follow these "Good Guy/Bad Guy" consistency rules?

The Old Way: Asking Too Many Questions (The "Naive" Approach)

Imagine trying to guess the rules of the Black Box by asking the computer: "For every possible combination of inputs, is the rule consistent?"

The computer tries to write a giant list of questions like: "If input A is 1 and B is 2, is the output higher than if A is 1 and B is 3?"

The Problem: If you have a gene with 10 neighbors, the number of combinations is astronomical. The computer gets overwhelmed, like a student trying to read every book in a library to find one sentence. It gets stuck and gives up. This is what the paper calls the "Quantified Encoding."

The New Way: The "Lazy" Detective (The "Instantiation" Approach)

The authors realized you don't need to ask every possible question. You only need to ask the questions that actually matter for the specific clues you have.

They developed a smarter strategy called "Lazy Instantiation."

The Analogy: Imagine you are trying to find a suspect in a crowd.
- The Old Way: You check every single person in the city against your description, one by one, even if they are clearly not the suspect.
- The New Way (Lazy): You look at the crowd. You see someone who looks a bit like the suspect. You ask, "Is this person the suspect?" If the answer is "No, they are too short," you move on. You only ask the hard questions when the clues actually point to a problem.
How it works: The computer starts by guessing a set of rules. It checks if those rules fit the "frozen moments" (fixed points) you observed. If the rules break the "Monotonicity" law (e.g., the Good Guy gets stronger but the result gets worse), the computer says, "Aha! I found a mistake!" and adds just one specific rule to fix that specific mistake. It keeps doing this only when necessary.

The Results: Why This Matters

The authors tested this new detective method against the old ones and against other famous biology tools (like Bonesis and AEON).

Speed: The "Lazy" method was incredibly fast. While the old "Ask Everything" method got stuck on complex problems, the new method solved them in seconds.
Scale: It could handle cities with hundreds of citizens (genes) and complex connections. The old tools crashed when the connections got too complicated.
Versatility: Most existing tools only work for simple "On/Off" (Boolean) switches. This new method works for multi-level systems (like a dimmer switch that can be 0, 1, 2, or 3), which is much closer to how real biology works.

The Bottom Line

This paper is like upgrading from a brute-force search (checking every single possibility) to a smart, targeted investigation.

By realizing that biology follows simple, consistent rules (monotonicity), the authors taught the computer to stop wasting time on impossible scenarios and focus only on the clues that matter. This allows scientists to reverse-engineer complex biological systems much faster and more accurately than ever before, helping us understand how life works at a fundamental level.

1. Problem Statement

The paper addresses the model inference problem in systems biology, specifically for logic-based discrete models (Boolean and multi-valued/Thomas networks). The goal is to reconstruct the unknown update functions of a biological system given:

Empirical Observations: Typically steady states (fixed points) observed in the system.
Mechanistic Assumptions: Constraints derived from biological knowledge, specifically:
- Influence Graph: Which variables regulate others.
- Monotonicity: Whether a regulator has a consistently positive (monotone) or negative (anti-monotone) effect on the target.
- Essentiality: Whether a regulator actually influences the target (i.e., changing the regulator changes the output).

The core challenge is to encode these constraints into a Satisfiability Modulo Theories (SMT) framework. While Uninterpreted Functions (UF) are ideal for modeling unknown update functions, enforcing monotonicity constraints on these functions within SMT solvers is computationally difficult. Naive approaches using universal quantifiers often fail to scale, especially with high-arity functions (many inputs) and complex instances.

2. Methodology

The authors propose an SMT-based approach that encodes the inference problem using Uninterpreted Functions (UF) subject to monotonicity constraints. They compare three distinct encoding strategies:

A. Naive Quantified Encoding

This approach translates monotonicity directly into universally quantified formulas (e.g., $\forall x, y. x \le y \implies f(x) \le f(y)$ ).

Limitation: Most SMT solvers struggle with quantified formulas, leading to undecidability or severe performance degradation, particularly when function arities are high.

B. Eager Quantifier Instantiation

Based on the theoretical work of Sofronie-Stokkermans et al., this method relies on the fact that a finite set of quantifier-free monotonicity lemmas is sufficient to encode monotonicity for a specific input formula.

Mechanism: It generates all necessary instances of the monotonicity axiom for every pair of function applications found in the input formula before solving.
Complexity: The number of lemmas is quadratic ( $O(|\phi|^2)$ ) relative to the formula size. While it avoids quantifiers, it can generate a massive number of constraints upfront.

C. Lazy Quantifier Instantiation (Proposed Innovation)

The authors introduce a lazy variant of the instantiation approach.

Mechanism: The solver starts with the base formula $\phi$ $ϕ$ and no monotonicity lemmas. It iteratively:
1. Checks for satisfiability.
2. If a model is found, it checks if the model violates any monotonicity constraints.
3. If a violation is detected, it adds the specific violated lemma to the formula and repeats.
Advantage: This avoids generating unnecessary constraints for lemmas that are not required to prove unsatisfiability or find a valid model, significantly reducing the problem size for complex instances.

3. Key Contributions

Formalization: The paper formally maps the logic-based model inference problem to SMT with Uninterpreted Functions and monotonicity constraints, handling both Boolean and integer-valued (multi-valued) domains.
Algorithmic Comparison: It provides a rigorous comparison between naive quantified encodings and instantiation-based approaches (both eager and lazy).
Lazy Instantiation Algorithm: The introduction of the lazy algorithm (Algorithm 1) which dynamically adds monotonicity lemmas only when violated, offering a scalable solution for dense networks.
Integer Support: Unlike many existing tools restricted to Boolean domains, this approach natively supports multi-valued (integer) networks, which are crucial for modeling biological systems with more than two concentration levels.

4. Experimental Results

The authors evaluated their approach on 8,990 instances derived from three benchmark sets:

bbm-boolean: 8,381 instances from curated Boolean models.
bma-integer: 465 instances from multi-valued (integer) models.
omnipath: 144 real-world, data-driven instances with high function arity (up to 76 inputs) and dense influence graphs.

Key Findings:

Performance vs. Quantified Encodings: Instantiation-based methods (Eager and Lazy) significantly outperformed naive quantified encodings. Quantified methods failed on nearly all high-arity integer instances and struggled with Boolean instances where function arity exceeded 11–12.
Eager vs. Lazy:
- On Boolean benchmarks, both instantiation methods solved all instances quickly.
- On Integer benchmarks, Eager was the only method to solve all 465 instances (within 4 minutes), while Lazy solved 417.
- On Omnipath (high-arity, dense) benchmarks, Lazy outperformed Eager, solving all 144 instances in under 5 seconds. This suggests that for dense networks, the eager generation of all $O(n^2)$ lemmas is inefficient, and the lazy approach avoids unnecessary overhead.
Comparison with State-of-the-Art Tools:
- Bonesis (ASP-based): Restricted to Boolean models and Disjunctive Normal Form (DNF) encodings. It failed on high-arity instances or required restricting the search space (trading completeness for speed). The SMT approach solved 100% of the Boolean instances Bonesis could not.
- AEON (BDD-based): Also restricted to Boolean models. It failed completely on instances with function arity > 5 due to exponential blowup in BDD size. The SMT approach solved all such instances.
- Conclusion: The SMT approach is orders of magnitude faster and more scalable than existing domain-specific tools, particularly for high-arity and non-Boolean models.

5. Significance

Scalability: The paper demonstrates that SMT with uninterpreted functions, when combined with lazy quantifier instantiation, is a viable and superior method for inferring complex biological models that were previously intractable for automated reasoning tools.
Generality: By supporting integer domains and arbitrary monotonicity constraints, the approach bridges the gap between simple Boolean models and more realistic multi-valued biological models.
Practical Impact: The ability to handle dense influence graphs (like those found in real gene regulatory networks) and high-arity functions makes this tool applicable to real-world systems biology problems, such as the Omnipath dataset used in the evaluation.
Future Directions: The framework opens the door for incorporating additional biological constraints (e.g., trap spaces) and handling uncertain observations via optimization-based SMT.

In summary, the paper establishes that lazy instantiation of monotonicity lemmas is the key to unlocking the power of SMT solvers for systems biology, outperforming both traditional quantified encodings and specialized tools like Bonesis and AEON.