Development of Efficient Hybrid Sequence Design System for Constructing DNAmolecule Complexies

开发用于构建 DNA 分子复合物的高效杂交序列设计系统

• 批准号: 17500192
• 负责人: KOBAYASHI Satoshi
• 金额: $ 2.34万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17500192/
• 关键词: DNA Computing; Molecular Computing; Sequence Design; Self Assembly; 二次構造予測

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.

DNA计算是一种新的计算范式，我们利用沃森-克里克互补性构建预期的纳米尺度结构并计算一些东西。在这个研究项目中，我们设计了有效的分析算法来设计要组装成预期纳米级结构的序列，并开发了一个设计DNA序列的系统。研究结果有三个方面。第一个结果是一个简单的模型下，我们不考虑在试管中的序列浓度的序列评估一组的算法的发展。对于序列集是有限的情况，我们设计了一个O（n^）时间的有效算法<5>，其中n是定义给定有限序列集的自动机中的状态数。第二个结果是一个理论的算法的建议，用于评估一个更精确的模型下，我们认为浓度的序列集。感兴趣的问题可以在物理学方面被重新表述为计算反应系统的平衡态的问题。由于我们应该处理的反应系统，其所产生的复合物的数量是指数的输入序列的大小，这样的反应系统的平衡分析是计算上棘手的。在这个研究项目中，我们提出了一个新的理论计算平衡，克服了组合爆炸问题。在这个理论中，我们融合了图论和优化理论，以克服组合爆炸的结果复杂。最后，我们开发了一个用于设计一组序列的混合系统，其中我们使用了作者开发的一种流行的序列设计方法（称为模板法）以及本研究项目中提出的第一个评估算法。与以前的系统相比，我们可以有效地设计一组满足各种设计约束的序列。

项目成果

組合せ爆発を内包する化学反応系の平衡状態計算

包括组合爆炸在内的化学反应系统的平衡态计算

• 发表时间: 2007
• 作者: Satoshi;Kobayashi;Satoshi Kobayashi;小林聡
• 通讯作者: 小林聡

A New Approach to Computing Equilibrium State of Combinatorial Hybridization Reaction Systems

计算组合杂交反应系统平衡态的新方法

• 发表时间: 2007
• 期刊: Proc. of Workshop on Computing and Communications from Biological Systems: Theory and Applications CD-ROM
• 作者: Satoshi;Kobayashi;Symmetric;Enumeration;Method;Satoshi Kobayashi
• 通讯作者: Satoshi Kobayashi

Efficient Algorithms for Testing Structure Freeness of Finite Set of Biomolecular Sequences

测试生物分子序列有限集结构自由度的有效算法

• 发表时间: 2006
• 期刊: Proceedings of 11th International Meeting on DNA Computing LNCS 3892
• 作者: Satoshi;Kobayashi;Satoshi Kobayashi;Atsushi Kijima
• 通讯作者: Atsushi Kijima

A New Approach to Computing Equilibria

计算均衡的新方法

• 发表时间: 2008
• 期刊: Technical Report of Dept. of Computer Science, Univ. of Electro Communications CS08-01
• 作者: Satoshi;Kobayashi;Symmetric;Enumeration;Method
• 通讯作者: Method

A New Approach to Computing Equilibrium State of Combinatorial Chemical Reaction Systems

计算组合化学反应系统平衡态的新方法

• 发表时间: 2006
• 期刊: Technical Report of Dept. of Computer Science, Univ. of Electro Communications CS06-01
• 作者: Satoshi;Kobayashi;Satoshi Kobayashi;Atsushi Kijima;Satoshi Kobayashi
• 通讯作者: Satoshi Kobayashi