Development of Efficient Hybrid Sequence Design System for Constructing DNAmolecule Complexies

点击翻译按钮获取中文摘要

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.