Design and analysis of DNA strand displacement devices using probabilistic model checking

Matthew R. Lakin, David Parker, Luca Cardelli, Marta Kwiatkowska, Andrew PhillipsJournal of The Royal Society Interface 2012 · DOI

TL;DR

This paper introduces a novel approach to designing and verifying DNA strand displacement (DSD) circuits by integrating the DSD programming language with probabilistic model checking. This allows for the automated analysis of correctness, reliability, and performance of DSD devices, paving the way for more robust and predictable molecular computing.

What Problem Does This Paper Address?

Designing reliable DNA-based computing devices is a significant challenge due to the inherent complexity and potential for unwanted interactions between molecules. DNA strand displacement (DSD) offers a promising paradigm for building these devices, but ensuring their correct and robust operation, especially in the presence of numerous possible interference pathways, is difficult. Traditional simulation methods can be time-consuming and may not guarantee exhaustive analysis. This paper addresses the need for a formal, automated method to verify the design of DSD circuits, ensuring their correctness and quantifying their reliability and performance.

Methods

The authors leverage a combination of the DNA strand displacement (DSD) programming language and probabilistic model checking. The DSD language is used to formally describe DNA circuits, and a tool (Visual DSD) is extended to translate these designs into models suitable for the PRISM probabilistic model checker.

Key techniques include:

  • Formal Specification with DSD: The DSD language provides a textual syntax to represent DNA species and their interactions, enabling precise definition of circuit components.
  • Probabilistic Model Checking with PRISM: PRISM is used to analyze continuous-time Markov chains (CTMCs) derived from the DSD models. This allows for the verification of quantitative properties, such as probabilities of failure or expected execution times.
  • Temporal Logic for Property Specification: Properties of the DSD circuits are expressed using temporal logics (like CTL and CSL) to define desired behaviors (e.g., "always eventually terminate," "probability of failure is at most X").
  • Customized Verification Queries: The authors define specific PRISM queries to check for correctness (e.g., all desired outputs produced, no reactive gates/strands remaining) and to analyze performance (e.g., expected time to completion) and reliability (e.g., probability of error).
  • Abstraction Techniques: To handle the complexity of larger systems, the authors employ abstractions, such as declaring certain species as "constant" to represent high concentrations of fuels or waste products, thereby reducing the state space of the model.

Datasets

Not discussed in the paper. The authors create their own DSD models and analyze them using PRISM.

Key Insights and Ideas

  • Automated Debugging of DSD Designs: Probabilistic model checking can automatically identify subtle design flaws, such as crosstalk between components, that are difficult to detect through manual inspection or limited simulations.
  • Quantifying Reliability and Performance: Beyond simple correctness, the approach allows for rigorous quantification of a DSD circuit's reliability (e.g., probability of failure) and performance (e.g., expected execution time).
  • Design Space Exploration: The methods enable efficient evaluation of alternative design decisions, helping engineers choose the most robust and efficient implementations.
  • Scalability through Abstraction: By using abstractions like "constant" species, the authors demonstrate a path towards analyzing more complex DSD systems that would otherwise be computationally intractable.
  • Bridging Theory and Practice: The work connects theoretical formal verification techniques to the practical design and analysis of molecular computing systems.

Key Results

  • Bug Detection: The authors successfully identified a crosstalk bug in a transducer gate design that was not easily discoverable through traditional methods. Fixing this bug by adding a "new a" declaration in the DSD code resolved the issue.
  • Reliability Improvement with Parallelization: For a faulty transducer design, running multiple parallel copies (increasing N) significantly reduced the percentage of reactive (unsuccessfully executed) gates, demonstrating how redundancy can improve reliability.
  • Linear Time Complexity: For corrected transducer chains, the expected execution time was shown to increase linearly with the length of the chain, aligning with theoretical predictions.
  • Performance Impact of Garbage Collection: Catalyst gates without garbage collection showed a faster increase in expected completion time with increasing numbers of parallel copies compared to those with garbage collection, indicating that accumulating waste slows down the system.
  • Approximate Majority Voting Analysis: The authors successfully modeled and analyzed an approximate majority voting system, demonstrating the ability to predict consensus probabilities based on initial population sizes. For instance, when initial populations of X and Y were equal, the probability of reaching a consensus of X was 0.5.

Limitations and Future Work

  • Scalability Challenges: The primary limitation is the exponential growth of the state space with increasing numbers of molecules or complex reaction networks. This necessitates the use of abstractions, which can introduce approximations.
  • Extrapolation to Higher Molecule Counts: Extrapolating results from small-scale model checking to systems with significantly higher molecule numbers remains a challenge.
  • Future Work:
    • Developing more advanced abstraction techniques (e.g., sliding window abstractions, stochastic hybrid models) to improve scalability.
  • Investigating compositional model checking approaches for modular analysis of complex systems.
  • Exploring the application of these techniques to Turing-complete DNA computing systems, which require handling potentially unbounded reaction networks.
  • Experimental validation of the model checking predictions.

Summary updated

Abstract

Designing correct, robust DNA devices is difficult because of the many possibilities for unwanted interference between molecules in the system. DNA strand displacement has been proposed as a design paradigm for DNA devices, and the DNA strand displacement (DSD) programming language has been developed as a means of formally programming and analysing these devices to check for unwanted interference. We demonstrate, for the first time, the use of probabilistic verification techniques to analyse the correctness, reliability and performance of DNA devices during the design phase. We use the probabilistic model checker prism, in combination with the DSD language, to design and debug DNA strand displacement components and to investigate their kinetics. We show how our techniques can be used to identify design flaws and to evaluate the merits of contrasting design decisions, even on devices comprising relatively few inputs. We then demonstrate the use of these components to construct a DNA strand displacement device for approximate majority voting. Finally, we discuss some of the challenges and possible directions for applying these methods to more complex designs.
BibTeX
@article{lakin2012design,
  author = {Matthew R. Lakin and David Parker and Luca Cardelli and Marta Kwiatkowska and Andrew Phillips},
  title = {{Design and analysis of DNA strand displacement devices using probabilistic model checking}},
  journal = {Journal of The Royal Society Interface},
  year = {2012},
  doi = {10.1098/rsif.2011.0800},
}
Figure