Abstract
The time is approaching when information can be written into DNA. This tutorial work surveys the methods for designing code words using DNA, and proposes a simple code that avoids unwanted hybridization in the presence of shift and concatenation of DNA words and their complements.
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.
Similar content being viewed by others
References
Adleman, L.M.: Molecular Computation of Solutions to Combinatorial Problems. Science 266(5187), 1021–1024 (1994)
Brenner, S., Lerner, R.A.: Encoded Combinatorial Chemistry. Proc. Nation. Acad. Sci. USA 89(12), 5381–5383 (1992)
Brenner, S., Williams, S.R., Vermaas, E.H., Storck, T., Moon, K., McCollum, C., Mao, J.I., Luo, S., Kirchner, J.J., Eletr, S., DuBridge, R.B., Burcham, T., Albrecht, G.: In Vitro Cloning of Complex Mixtures of DNA on Microbeads: physical separation of differentially expressed cDNAs. Proc. Nation. Acad. Sci. USA 97(4), 1665–1670 (2000)
Ben-Dor, A., Karp, R., Schwikowski, B., Yakhini, Z.: Universal DNA Tag Systems: a combinatorial design scheme. J. Comput. Biol. 7(3-4), 503–519 (2000)
Wong, P.C., Wong, K.-K., Foote, H.: Organic Data Memory Using the DNA Approach. Comm. of ACM 46(1), 95–98 (2003)
Allawi, H.T., SantaLucia Jr., J.: Nearest-neighbor Thermodynamics of Internal AC Mismatches in DNA: sequence dependence and pH effects. Biochemistry 37(26), 9435–9444 (1998)
Golomb, S.W., Gordon, B., Welch, L.R.: Comma-Free Codes. Canadian J. of Math. 10, 202–209 (1958)
Tang, B., Golomb, S.W., Graham, R.L.: A New Result on Comma-Free Codes of Even Word-Length. Canadian J. of Math. 39(3), 513–526 (1987)
Judson, H.F.: The Eighth Day of Creation: Makers of the Revolution in Biology. Cold Spring Harbor Laboratory (Original 1979; Expanded Edition 1996)
Stiffler, J.J.: Comma-Free Error-Correcting Codes. IEEE Trans. on Inform. Theor. IT-11, 107–112 (1965)
Stiffler, J.J.: Theory of Synchronous Communication. Prentice-Hall Inc., Englewood Cliffs (1971)
Breslauer, K.J., Frank, R., Blocker, H., Marky, L.A.: Predicting DNA Duplex Stability from the Base Sequence. Proc. Nation. Acad. Sci. USA 83(11), 3746–3750 (1986)
Arita, M., Kobayashi, S.: DNA Sequence Design Using Templates. New Generation Comput. 20(3), 263–277 (2002), Available as a sample paper at http://www.ohmsha.co.jp/ngc/index.htm
Zuker, M., Steigler, P.: Optimal Computer Folding of Large RNA Sequences Using Thermodynamics and Auxiliary Information. Nucleic Acids Res. 9, 133–148 (1981)
Faulhammer, D., Cukras, A.R., Lipton, R.J., Landweber, L.F.: Molecular Computation: RNA Solutions to Chess Problems. Proc. Nation. Acad. Sci. USA 97(4), 1385–1389 (2000)
Frutos, A.G., Liu, Q., Thiel, A.J., Sanner, A.M., Condon, A.E., Smith, L.M., Corn, R.M.: Demonstration of a Word Design Strategy for DNA Computing on Surfaces. Nucleic Acids Res. 25(23), 4748–4757 (1997)
Winfree, E., Yang, X., Seeman, N.C.: Universal Computation Via Self-assembly of DNA: some theory and experiments. In: DNA Based Computers II. DIMACS Series in Discr. Math. and Theor. Comput. Sci, vol. 44, pp. 191–213 (1998)
Benenson, Y., Paz-Elizur, T., Adar, R., Keinan, E., Livneh, Z., Shapiro, E.: Programmable and Autonomous Computing Machine Made of Biomolecules. Nature 414, 430–434 (2001)
Li, M., Lee, H.J., Condon, A.E., Corn, R.M.: DNA Word Design Strategy for Creating Sets of Non-interacting Oligonucleotides for DNA Microarrays. Langmuir 18(3), 805–812 (2002)
Cattell, K., Ruskey, F., Sawada, J., Serra, M.: Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials over GF(2). J. Algorithms 37, 267–282 (2000)
Deaton, R., Murphy, R.C., Garzon, M., Franceschetti, D.R., Stevens Jr., S.E.: Good Encodings for DNA-based Solution to Combinatorial Problems. In: DNA Based Computers II. DIMACS Series in Discr. Math. and Theor. Comput. Sci., vol. 44, pp. 247–258 (1998)
Garzon, M., Neathery, P., Deaton, R., Franceschetti, D.R., Stevens Jr., S.E.: Encoding Genomes for DNA Computing. In: Proc. 3rd Annual Genet. Program. Conf., pp. 684–690. Morgan Kaufmann, San Francisco (1998)
Braich, R.S., Chelyapov, N., Johnson, C., Rothemund, R.W., Adleman, L.: Solution of a 20-Variable 3-SAT Problem on a DNA Computer. Science 296(5567), 499–502 (2002)
Komiya, K., Sakamoto, K., Gouzu, H., Yokoyama, S., Arita, M., Nishikawa, A., Hagiya, M.: Successive State Transitions with I/O Interface by Molecules. In: Condon, A., Rozenberg, G. (eds.) DNA 2000. LNCS, vol. 2054, pp. 17–26. Springer, Heidelberg (2001)
Tulpan, D.C., Hoos, H., Condon, A.: Stochastic Local Search ALgorithms for DNAWord Design. In: Proc. 8th Intern. Meeting on DNA-Based Computers, Sapporo, Japan, pp. 311–323 (2002)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland, New York (1983) (2nd reprint)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Arita, M. (2003). Writing Information into DNA. In: Jonoska, N., Păun, G., Rozenberg, G. (eds) Aspects of Molecular Computing. Lecture Notes in Computer Science, vol 2950. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24635-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-24635-0_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20781-8
Online ISBN: 978-3-540-24635-0
eBook Packages: Springer Book Archive