A strand graph semantics for DNA-based computation

作     者：Petersen, Rasmus L. Lakin, Matthew R. Phillips, Andrew 

作者机构：Microsoft Res Cambridge England Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2016年第632卷

页      面：43-73页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation [1027877, 1028238, 1318833] New Mexico Cancer Nanoscience and Microsystems Training Center (NIH/NCI grant) [5R25CA153825] Direct For Computer & Info Scie & Enginr Division of Computing and Communication Foundations Funding Source: National Science Foundation Directorate For Engineering Div Of Chem, Bioeng, Env, & Transp Sys Funding Source: National Science Foundation 

主　　题：Strand graph Site graph Process calculus Programming language DNA computing Molecular programming Biological computation 

摘      要：DNA nanotechnology is a promising approach for engineering computation at the nanoscale, with potential applications in biofabrication and intelligent nanomedicine. DNA strand displacement is a general strategy for implementing a broad range of nanoscale computations, including any computation that can be expressed as a chemical reaction network. Modelling and analysis of DNA strand displacement systems is an important part of the design process, prior to experimental realisation. As experimental techniques improve, it is important for modelling languages to keep pace with the complexity of structures that can be realised experimentally. In this paper we present a process calculus for modelling DNA strand displacement computations involving rich secondary structures, including DNA branches and loops. We prove that our calculus is also sufficiently expressive to model previous work on non-branching structures, and propose a mapping from our calculus to a canonical strand graph representation, in which vertices represent DNA strands, ordered sites represent domains, and edges between sites represent bonds between domains. We define interactions between strands by means of strand graph rewriting, and prove the correspondence between the process calculus and strand graph behaviours. Finally, we propose a mapping from strand graphs to an efficient implementation, which we use to perform modelling and simulation of DNA strand displacement systems with rich secondary structure. (C) 2015 Elsevier B.V. All rights reserved.