Perspectives on molecular computing

In 1996, we began a research project on molecular computers under the new program “Research for the Future” funded by the Japan Society for the Promotion of Science. In this paper, we first summarize the research that has been completed in the field of DNA computing and the research problems that must be overcome. We also report some achievements of our research project in the first two years. We then propose a new direction in research towardsautonomous molecular computers, and describe the author’s work on the implementation of state machines using DNA molecules. We finally discuss the future perspectives on molecular computing based on our experiences. Masami Hagiya, Ph.D.: He received M.Sc. from University of Tokyo in 1982, and D.Sc. from Kyoto University in 1988. After the years in Research Institute for Mathematical Sciences, Kyoto University, he returned to University of Tokyo in 1992. He has been working on programming languages, verification and synthesis of programs, and automated deduction. In addition, he is interested in bio-computing since he was involved in the human genome project of Japan. He is currently organizing a project on molecular computing under the “Research for the Future” program of JSPS.     

Biomolecular realizations of a parallel architecture for solving combinatorial problems

A coherent approach to the problem of carrying out computations in aqueous solution is provided. The conceptual level of the presentation provides for many different molecular realizations to be explored in the future. Several possibilities are suggested. Our initial implementations have provided wet lab prototype computations for two of the classicalNP complete graph theoretic problems: the maximum independent set problem and the minimum dominating set problem. A wet lab prototype computation is in progress for the determination of the satisfiability of sets of disjunctive clauses. Tom Head, Ph.D.: He is Professor of Mathematical Sciences at Binghamton University. He received his B.S. and M.A. from the University of Oklahoma in 1954 & 55 and his Ph.D. from the University of Kansas in 1962. For each degree he majored in mathematics and minored in physics. His research has progressed from abstract algebra through formal language theory to biologically inspired algorithmic processes. His greatest professional satisfaction of the recent decade has been provided by his distinguished Ph.D. students: Natasa Jonoska, John Harrison, Arthur Weinberger, and Elizabeth Laun Goode. He wonders continually at the origin of life and its role in the cosmos. He expects to spend his late years meditating on the dimension of eternity.     

Models of molecular computing based on molecular reactions

We discuss two models of molecular computing. The first one is based on an abstract formulation of two sorts of molecular reactions: enforcing and forbidden. The enforcing reactions are reactions that may happen, and are allowed to happen, in a given molecular system, while the forbidden reactions are detrimental for the system (e.g., leading to “incorrect” computations) and thus must be avoided. Hence computations in such a forbidding-enforcing system are driven by enforcing conditions (describing the enforcing reactions), but they are restrained by forbidding conditions (describing the forbidden reactions). The second model, called molecular landscapes, is geared towards the display of solutions. It consists of organisms (computing agents) functioning in a common environment which plays the role of a common communication medium for the organisms. When a molecular landscapes system works on a specific computational problem, each organism is working on this problem. But as soon as an organismM will get its solution to the problem, it modifies the environment, which from this moment on supports only the organisms that get the same solution asM. This is done through a selection mechanism that relies on selective competition which “kills” the losers. Since this selection mechanism interacts with the solution mechanism from the moment that computations are initiated, it can drastically increase the density of good solutions (molecules). In this way the molecular landscapes system achieves the goal of displaying solutions. Grzegorz Rozenberg, Ph.D.: He is a Professor, the Head of the Theory Group at Leiden Institute of Advanced Computer Science, and the Director of Leiden Center for Natural Computing at Leiden University, The Netherlands. He is also an Adjoint Professor of Computer Science at the Department of Computer Science, University of Colorado at Boulder, USA. He received his Engineering and Master degrees in computer science in 1965 from the Technical University of Warsaw, Poland, and his Ph.D. in mathematics in 1968 from the Polish Academy of Sciences, Warsaw, Poland. He has published about 400 papers, 5 books and edited over 50 books in formal language and automata theory, concurrent systems, graph theory and graph rewriting, computer supported cooperative work, and molecular computing. He is a performing magician, and he is possessed by paintings by Hieronymus Bosch. In his words: “I have a wonderful family, I have written many papers, I have shuffled many decks of cards, I have studied many paintings by Bosch. Life has been good to me.”     

Large-scale DNA memory based on the nested PCR

A DNA Memory with over 10 million (16.8 M) addresses was achieved. The data embedded into a unique address was correctly extracted through an addressing processes based on nested PCR. The limitation of the scaling-up of the proposed DNA memory is discussed by using a theoretical model based on combinatorial optimization with some experimental restrictions. The results reveal that the size of the address space of the DNA memory presented here may be close to the theoretical limit. The high-capacity DNA memory can be also used in cryptography (steganography) or DNA ink. In decoding process, multiple data with different addresses can be also simultaneously accessed by using the mixture of some address primers. Electronic supplementary material  The online version of this article (doi: ) contains supplementary material, which is available to authorized users.     

计算智能融合应用研究

本文对神经网络（NN），进化算法（EA0，不确定理论（Uncertain Theory）混沌系统（Chaos System）、免疫算法（IA,Immune Algorithm）、DNA计算（DNA Coputing）等广义计算智能相互融合应用进行了总结和分析，重点介绍免疫算法、DNA计算等新型计算智能理论的相互融合应用，最后对计算智能理论的融合应用趋势进行探讨。     

DNA计算原理及系统分析

DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法,它开创了以化学反应作为计算工具的先例,具有广阔的应用前景。DNA计算的两个主要特点是计算的高度并行性和巨大的信息存储容量。该文简要介绍了DNA计算的原理及其数学计算的基本思想;对DNA计算的特点及其系统进行了分析。比较了DNA计算机与图灵机的异同;最后对DNA计算的发展前景进行展望。     

DNA计算原理、现状及展望

综述了DNA计算原理和特点,接着介绍了DNA计算的研究现状,指出了目前DNA计算的主要研究方向和DNA计算需要解决问题,最后对DNA计算的发展前景进行了展望.     

A Model in κ for DNA Addition

DNA computing is a hot research topic in recent years. Formalization and verification using theories(π-calculus, bioambients, κ-calculus and etc.) in Computer Science attract attention because it can help prove and predict to a certian degree various kinds of biological processes. Combining these two aspects, formal methods can be used to verify algorithms in DNA computing, including basic arithmetic operations if they are to be included in a DNA chip. In this paper, we first introduce a newly-designed algorithm for solving binary addition with DNA, which contributes to a unit in DNA computer processor, and then formalize the algorithm in κ-calculus(a formal method well suited for describing protein interactions) to show the correctness of it in a sense, and a sensible example is provided. Finally, some discussion on the described model is made, in addition to a few possible future improvement directions.     

DNA计算的原理及应用

DNA计算是一种新的计算模式,它具有高度的并行性.本文介绍了DNA计算的机理和应用,并重点讨论了DNA计算在解决NP-完全问题中的应用模型,最后讨论了DNA计算目前存在的问题和展望.     

End-user computing: The MIS managers' perspective

Despite the enthusiasm and its rapid growth, End-User Computing (EUC) is not well-managed. This article investigates EUC and its current practices. EUC experience at 31 organizations representing 12 industries was surveyed. Areas of study include: MIS/DP managers' perceptions and attitudes toward EUC, perceived benefits and difficulties of EUC applications and issues related to management and support of EUC activities. Implications of the survey findings for effective EUC applications are also discussed.