Development of Efficient Hybrid Sequence Design System for Constructing DNAmolecule Complexies

DNA计算是一种新的计算范式，我们利用Watson-Crick互补性来构建预期的纳米级结构，并进行计算。在这个研究项目中，我们设计了高效的分析算法来设计要组装成预定纳米结构的序列，并开发了一个设计DNA序列的系统。研究结果有三个方面。第一个结果是开发了一种算法，用于在一个简单的模型下评估一组序列，在这个模型中，我们没有考虑试管中序列的浓度。对于序列集是有限的情况，我们设计了一个有效的算法O(n^&lt；5&gt；)时间，其中n是定义给定的有限序列集的自动机中的状态数。第二个结果是提出了在更精确的模型下评估序列集的算法理论，其中我们考虑了序列的集中度。这个有趣的问题可以用物理学的术语重新表述为计算反应体系的平衡态的问题。由于我们要处理的是一个反应系统，其生成的络合物的数目与输入序列的大小成指数关系，所以这种反应系统的平衡分析在计算上是困难的。在这个研究项目中，我们提出了一种新的计算均衡的理论，它克服了组合爆炸问题。在该理论中，我们融合了图论和最优化理论，以克服合成复合体的组合爆炸。最后，我们开发了一个用于设计一组序列的混合系统，其中我们使用了作者开发的一种流行的序列设计方法-模板方法，以及本研究项目中提出的第一个评估算法。与以前的系统相比，使用该系统可以有效地设计出满足各种设计约束的序列集。

DNA Computing is a new computing paradigm in which we construct intended nano-scale structures using Watson-Crick complementarity and compute something. In this research project, we devised efficient analysis algorithms for designing sequences to be assembled into an intended nano-scale structure and developed a system for designing DNA sequences. Research results are three-fold. The first result is the development of the algorithm for evaluating a set of sequences under a simple model where we do not consider concentration of sequences in a test tube. For the case that the sequence set is finite, we devised an efficient algorithm of O(n^<5>) time, where n is the number of states in the automaton defining the given finite set of sequences. The second result is the proposal of a theory of algorithms for evaluating a sequence set under a more precise model where we consider concentration of sequences. The problem of interest can be rephrased in terms of physics as a problem of computing equilibrium states of reaction systems. Since we should deal with a reaction system where the number of its resultant complexes is exponential with respect to the size of input sequences, the equilibria analysis of such reaction systems is computationally intractable. In this research project, we proposed a novel theory for computing equilibria which overcomes the combinatorial explosion problem. In this theory, we fuse graph theory and optimization theory in order to overcome the combinatorial explosion of resultant complexes. Finally, we developed a hybrid-system for designing a set of sequences, where we use a popular sequence design method, called template method, developed by the author, and the first evaluation algorithm proposed in this research project. With this system, we can efficiently design a set of sequences satisfying various design constraints compared to previous systems.