Abstract
In this paper, we present a concentration control method that may become a new framework of DNA computing. In this method, the concentration of each DNA is used as input and output data. By encoding the numeric data into concentrations of DNAs, a shortest path problem, which is a combinatorial optimization problem, can be solved. The method also enables local search among all candidate solutions instead of a exhaustive search. Furthermore, we can reduce the costs of some experimental operations in detecting process of DNA computing, because we have only to extract and analyze relatively intensive bands. Solutions of a shortest path problem by using a simulator and by laboratory experiments are presented to show the effectiveness of the concentration control method.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
L. Adleman: “Molecular Computation of Solutions to Combinatorial Problems,” Science, vol. 266, pp. 1021–1024, 1994.
R. J. Lipton: “DNA Solution of Hard Computational Problems,” Science, vol. 268, pp. 542–545, 1995.
Q. Ouyang, P. Kaplan, S. Lir, and A. Libchaber: “DNA Solution of the Maximal Clique Problem,” Science, vol. 278, pp. 446–449, 1997.
J. Chen, A. Eugene, B. Lemieux, W. Cedeno and D. H. Wood: “In vitro Selection for a Max 1s DNA Genetic Algorithm,” Preliminary Proceedings of Fifth International Meeting on DNA Based Computers, pp. 23–37, 1999.
K. Sakamoto, H. Gouzu, K. Komiya, D. Kiga, S. Yokoyama, T. Yokomori, and M. Hagiya: “Molecular Computation by DNA Hairpin Formation,” Science, vol. 288, pp. 1223–1226, 2000.
T. Head, M. Yamamura, and S. Gal: “Aqueous Computing: writing on molecules,” Proc. Congress on Evolutionary Computation 1999, IEEE Service Center, Piscataway NJ, pp. 1006–1010, 1999.
J. Oliver: “Computation With DNA: Matrix Multiplication,” DNA Based Computers 2, DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 44, pp. 113–122, 1999.
M. Yamamoto, J. Yamashita, T. Shiba, T. Hirayama, S. Takiya, K. Suzuki, M. Munekata, and A. Ohuchi: “A Study on the Hybridization Process in DNA Computing,” DNA Based Computers 5, DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 54, pp. 101–110, 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yamamoto, M., Matsuura, N., Shiba, T., Kawazoe, Y., Ohuchi, A. (2002). Solutions of Shortest Path Problems by Concentration Control. In: Jonoska, N., Seeman, N.C. (eds) DNA Computing. DNA 2001. Lecture Notes in Computer Science, vol 2340. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48017-X_19
Download citation
DOI: https://doi.org/10.1007/3-540-48017-X_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43775-8
Online ISBN: 978-3-540-48017-4
eBook Packages: Springer Book Archive