DNA折纸术在一类特殊的整数规划问题中的应用

基于DNA折纸术设计并找出一类特殊的整数规划问题的最优解。将这类整数规划问题中的[n]个变量及对应的所有可能值设计成一条长链（脚手架链），通过添加相应的订书钉链形成发夹结构来映射出问题的解。当整数规划问题中有[n]个变量时，它的解可以映射成[n]个发夹结构（长链的长度为[l+nt]）。同时对于非解，通过添加订书钉链的方法来增加长链的发夹结构，从而使得长链的长度变长（超过[l+nt]），再通过凝胶电泳来排除这些非解，最后保留可行解。     

基于自组装模型的最大团问题DNA计算算法

DNA计算在解决NP完全问题时,有着传统图灵机无法比拟的优势.但是随着DNA计算研究的不断深入,传统DNA计算模型显现出杂交错误率和生化操作复杂性过高的缺点.如何提高DNA计算结果的准确性在DNA计算研究中日显重要.针对NP完全的最大团问题,引入DNA自组装模型,提出了一种求解最大团问题的DNA计算算法.算法通过减少实验的操作步骤数,以降低生化解的错误率,给出了DNA分子的编码方案及结果检测的实验方法.算法设计的tiles种类为(O)(n+|E|),生化操作复杂性为(o)(1),其中n为图的顶点数,|E|为边数.与求解最大团问题的其他DNA算法的对比分析表明,本算法不仅明显提高了生化解的准确性,且算法的生化实验复杂度低,具有良好的实验操作性.     

基于DNA计算自组装模型的Diffie-Hellman算法破译(英文)

DNA自组装计算模型是近年来引人关注的计算模型,已有基于自组装模型的二进制加法、乘法以及有限域中的加法和乘法的讨论．文中利用DNA自组装模型设计的模乘系统,实现了素数P的本原根g连续乘方后模p的数的排列,从而可以在线性时间内求解离散对数,为破译Diffie—Hellman密钥交换算法提供了新的生物方法．该模乘系统使用了Θ（p）种自组装类型,组装的时间复杂度为Θ（p-1）．系统最后组装结果提取出报告链后,经过PCR和凝胶电泳读取离散对数结果．该模型扩展了DNA自组装计算模型的应用,为求取离散对数提供了新思路．     

精确覆盖问题的O(1.414~n)链数DNA计算机算法

DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法.算法由初始解空间生成算法Init()、冗余解删除算法IllegalRemove()和并行搜索器ParallelSeacher()共3个子算法组成.与同类算法的性能比较分析表明:本算法在保持多项式生物操作复杂性的条件下,将求解n维精确覆盖问题的DNA链数从O(2n)减少至O(1.414n),从而将DNA计算机在试管内可求解的精确覆盖问题集合的基数从60提高到120,改进了相关文献的研究结果.     

子集和问题的O(1.414n)链数DNA计算机算法

随着DNA计算机研究的不断深入,如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重要内容之一.为设计可扩展的子集和问题DNA计算机算法,文中将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,通过设计DNA并行搜索器,提出一种求解子集和问题的DNA计算机模型和算法.与已有文献结论的对比分析表明:文中算法在保持多项式生物操作复杂性的条件下,将穷举算法中的DNA分子链数从O(2n)减少至O(1.414n),其中n为子集和问题的维数.因此,文中算法理论上在试管级生化反应条件下能将可破解子集和公钥的维数从60提高到120.     

DNA自组装技术的研究进展及难点(英文)

近年来,DNA自组装成为DNA计算及纳米材料科学等领域研究的热点,它关系着DNA计算机的发展．DNA分子如何组装已成为许多学者关注的焦点．为此,文中主要围绕着DNA分子组装成的初级元件的类型：一条长的DNA单链、多条短寡核苷酸链和自组装单元,重点从自组装的初级元件形成的一维、二维及三维结构上讨论DNA自组装技术与方法．文中讨论了这些技术的原理及应用的研究进展,并且分析了DNA自组装应用于DNA计算的主要难点及解决方案．首先,编码的好坏决定着实验是否能实施;其次,DNA单链之间组装的角度及初级原件之间的连接是影响自组装体产量的关键因素;从具体的实验操作上看,每条DNA单链的浓度比例及退火温度则决定着自组装的成败．随着学科之间的高度交叉,DNA自组装将是材料学、信息学、生物学等领域的重要研究方向,也是推动DNA计算机发展的重要手段．     

基于DNA折纸术求解可满足性问题的计算模型

DNA折纸术是一种全新的DNA自组装方法,具有可编程性、纳米可寻址性等优点,被广泛地应用于DNA计算中.利用DNA折纸术可折叠出特殊结构的特点,在DNA折纸基底上设计了一种求解可满足性问题的计算模型,该模型采用分子信标原理,通过观察荧光的明灭排除非解,从而找出可满足性问题的解.最后通过实例和模拟仿真表明了模型的可行性.     

一种实现三值逻辑电路的DNA计算模型

近年来,随着生物计算和量子计算研究的深入,多值逻辑电路的各种实现成为一个热门的研究方向.发夹结构是DNA分子一种特殊杂交方式的产物,具有结果稳定、特异性强的优点.本文首次提出了一种利用DNA分子来实现多值逻辑电路的方法,用DNA分子的多发夹结构来表示三值逻辑的值,并给出"与"运算和"或"运算的计算模型,该模型适合应用于大规模的多值逻辑电路.     

基于DNA Tiles自组装的布尔逻辑运算

大量研究工作表明,DNA tiles自组装现象是分子生物计算过程中一个很重要的计算方式.分子自组装的基本特点在于由许多小分子在一定机理的作用下,自动形成更大规模的超级分子结构的过程.自组装用于计算,在于这种组装模式可以抽象成一个自动化的系统,只需根据问题的需要设计好输入,再将其输入到运算系统,经过分子自组装过程,最后能生成问题的解.文中基于这样的运算机理,在DNA tiles自组装这个计算平台上,尝试做布尔逻辑运算,针对4变量4句子的布尔逻辑问题,提出一个DNA tiles自组装自动化运算系统.     

DNA折纸术在0-1背包问题中的应用

DNA折纸术因其反应的可编程性、纳米可寻址性等优点被广泛地应用于DNA计算中。利用DNA折纸术和杂交链式反应构建0-1背包问题的计算模型。以四个变量的0-1背包问题为例,首先将九种发夹结构和一种分子信标锚定在DNA折纸基底上并加入足量的辅助链;其次通过加入不同的引发链可以触发不同路径上的杂交链式反应,并得到问题的所有可能解;最后,通过荧光信号的数量确定可行解,从而找到问题的最优解。该模型不受权重过大或过小的影响,在折纸基底上可等比例的缩放权重。用Visual DSD软件对该模型进行仿真,模型显示出良好的可行性。     

简单0-1规划问题的动态DNA折纸计算模型

DNA折纸是一种全新的DNA自组装方法。将一个由DNA折纸卡槽、双态DNA机器、DNA行走机器人组装而成的动态折纸应用于求解0-1规划问题。其中DNA折纸卡槽由1条M13脚手架链和202条钉书钉链折叠而成。双态DNA机器分为不修饰和修饰金纳米颗粒两种情况,对应于0-1规划问题约束变量的取值为0或者1。DNA折纸卡槽和DNA双态机器组装成折纸基底。DNA行走机器人是7条单链折叠成的带有粘性末端的DNA折纸。在链的驱动下,DNA行走机器人在折纸基底上顺时针旋转行走,每步旋转120°。DNA行走机器人每走两步,与折纸基底上的DNA双态机器进行链置换,接收修饰的金纳米颗粒。当整个动态行走过程结束,根据透射电镜下DNA行走机器人接收的金纳米颗粒的大小和个数来判断约束变量的取值是否为可行解。该计算模型采用模块化结构,DNA折纸卡槽、双态DNA机器、DNA行走机器人等折纸均单独设计,且采用透射电镜读解,因而提高了模型实现的可行性。     

Convergence rates of Markov chains for some self-assembly and non-saturated Ising models

Algorithms based on Markov chains are ubiquitous across scientific disciplines as they provide a method for extracting statistical information about large, complicated systems. For some self-assembly models, Markov chains can be used to predict both equilibrium and non-equilibrium dynamics. In fact, the efficiency of these self-assembly algorithms can be related to the rate at which simple chains converge to their stationary distribution. We give an overview of the theory of Markov chains and show how many natural chains, including some relevant in the context of self-assembly, undergo a phase transition as a parameter representing temperature is varied in the model. We illustrate this behavior for the non-saturated Ising model in which there are two types of tiles that prefer to be next to other tiles of the same type. Unlike the standard Ising model, we also allow empty spaces that are not occupied by either type of tile. We prove that for a local Markov chain that allows tiles to attach and detach from the lattice, the rate of convergence is fast at high temperature and slow at low temperature.     

A constraint-based approach to the representation of software usage models

Software usage models are the basis for statistical testing. They derive their structure from specifications and their probabilities from evolving knowledge about the intended use of the software product. The evolving knowledge comes from developers, customers and testers of the software system in the form of relationships that should hold among the parameters of a model. When software usage models are encoded as Markov chains, their structure can be represented by a system of linear constraints, and many of the evolving relationships among model parameters can be represented by convex constraints. Given a Markov chain usage model as a system of convex constraints, mathematical programming can be used to generate the Markov chain transition probabilities that represent a specific software usage model.     

DNA计算中的数据与计算模型

对DNA计算的通用性及单链、双链、粘性末端、发夹、质粒、k-臂DNA分子等各种数据作了简单介绍,并对基于DNA分子结构特性和基于DNA计算机研制过程两个方面的DNA计算模型进行了分析对比。针对各种不同的DNA数据及特性,提出了混合DNA计算模型的研究思路,并从不同角度论述了混合DNA计算模型的可行性。     

Approximate Self-Assembly of the Sierpinski Triangle

The Tile Assembly Model is a Turing universal model that Winfree introduced in order to study the nanoscale self-assembly of complex DNA crystals. Winfree exhibited a self-assembly that tiles the first quadrant of the Cartesian plane with specially labeled tiles appearing at exactly the positions of points in the Sierpinski triangle. More recently, Lathrop, Lutz, and Summers proved that the Sierpinski triangle cannot self-assemble in the ??strict?? sense in which tiles are not allowed to appear at positions outside the target structure. Here we investigate the strict self-assembly of sets that approximate the Sierpinski triangle. We show that every set that does strictly self-assemble disagrees with the Sierpinski triangle on a set with fractal dimension at least that of the Sierpinski triangle (??1.585), and that no subset of the Sierpinski triangle with fractal dimension greater than 1 strictly self-assembles. We show that our bounds are tight, even when restricted to supersets of the Sierpinski triangle, by presenting a strict self-assembly that adds communication fibers to the fractal structure without disturbing it. To verify this strict self-assembly we develop a generalization of the local determinism method of Soloveichik and Winfree.     

Hairpin-based state machine and conformational addressing: Design and experiment

In this paper, we propose a new architecture for a multi-state DNA machine whose conformation of repeated hairpin structures changes sequentially in response to input oligomers. As an application of the machine, we also propose molecular memory in which the machine is used as a memory unit. Addressing in the memory is realized through state transitions of the machine. We then describe a method for designing DNA sequences of the machine, which exhaustively checks conformational changes of the machine by dividing its secondary structure into hairpin units. The method is based on the minimum free energy of the structure, the structure transition paths, and the total frequency of optimal and suboptimal structures. DNA sequences designed by the method were tested in a chemical experiment in which a machine consisting of two hairpins was actually constructed. As a result, we verified that the multi-state DNA machine realized the expected changes in its secondary structure.     

Migration of DNA molecules through entropic trap arrays: a dissipative particle dynamics study

Dissipative particle dynamics (DPD) simulations of worm-like chain bead-spring models are used to explore the electrophoresis migration of DNA molecules traveling through narrow constrictions. The DPD is a relatively new numerical approach that is able to fully incorporate hydrodynamic interactions. Two mechanisms are identified that cause the size-dependent trapping of DNA chains and thus mobility differences. First, small molecules are found to be trapped in the deep region due to higher Brownian mobility and crossing of electric field lines. Second longer chains have higher probability to form hernias at the entrance of the gap and can pass the entropic barrier more easily. Consequently, longer DNA molecules have higher mobility and travel faster than shorter chains. The present DPD simulations show good agreement with existing experimental data as well as published numerical data.