×

zbMATH — the first resource for mathematics

Strand design for biomolecular computation. (English) Zbl 1061.68051
Summary: The design of DNA or RNA strands for DNA computations poses many new questions in algorithms and coding theory. DNA strand design also arises in use of molecular bar codes to manipulate and identify individual molecules in complex chemical libraries, and to attach molecules to DNA chips. We survey several formulations of the DNA strand design problem, along with results and open questions in this area.

MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
92C40 Biochemistry, molecular biology
Software:
ViennaRNA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adleman, L.M., Molecular computation of solutions to combinatorial problems, Science, 266, 11, 1021-1024, (1994)
[2] E.B. Baum, DNA sequences useful for computation, in: L.F. Landweber, E.B. Baum (Eds.), Proc. DNA Based Computers II, DIMACS, Workshop June 10-12, 1996, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 44, 1999, pp. 235-242. · Zbl 0919.68036
[3] A. Ben-Dor, R. Karp, B. Schwikowski, Z. Yakhini, Universal DNA tag systems: a combinatorial design scheme, Proc. RECOMB 2000, ACM, New York, pp. 65-75.
[4] R.S. Braich, C. Johnson, P.W.K. Rothemund, D. Hwang, N. Chelyapov, L.M. Adleman, Solution of a satisfiability problem on a gel-based DNA computer, Preliminary Proc. 6th Internat. Meeting on DNA Based Computers, Leiden, The Netherlands, June, 2000. · Zbl 0984.68660
[5] S. Brenner, Methods for sorting polynucleotides using oligonucleotide tags, US Patent Number 5,604,097, February 18, 1997.
[6] Brenner, S.; Lerner, R.A., Encoded combinatorial chemistry, Proc. natl. acad. sci. USA, 89, 5381-5383, (1992)
[7] Brenner, S.; Johnson, M.; Bridgham, J.; Golda, G.; Lloyd, D.H.; Johnson, D.; Luo, S.; McCurdy, S.; Foy, M.; Ewan, M,; Roth, R.; George, D.; Eletr, S.; Albrecht, G.; Vermaas, E.; Williams, S.R.; Moon, K.; Burcham, T.; Pallas, M.; DuBridge, R.B.; Kirchner, J.; Fearon, K.; Mao, J.; Corcoran, K., Gene expression analysis by massively parallel signature sequencing (MPSS) on microbead arrays, Nat. biotechnol., 18, 630-634, (2000)
[8] Breslauer, K.; Frank, R.; Blocker, H.; Marky, L., Predicting DNA duplex stability from the base sequence, Proc. natl. acad. sci. USA, 83, 3746-3750, (1986)
[9] Brouwer, A.E.; Shearer, J.B.; Sloane, N.J.A.; Smith, W.D., A new table of constant weight codes, IEEE trans. inform. theory, 36, 6, 1334-1380, (1990) · Zbl 0713.94017
[10] A.R. Cukras, D. Faulhammer, R.J. Lipton, L.F. Landweber, Chess games: a model for RNA based computation, Preliminary Proc. 4th Internat. DIMACS Meeting on DNA Based Computers, U. Pennsylvania, 1998, pp. 27-37.
[11] R. Deaton, R.C. Murphy, M. Garzon, D.R. Franceschetti, S.E. Stevens Jr., Good encodings for DNA-based solutions to combinatorial problems, in: L.F. Landweber, E.B. Baum (Eds.), Proc. DNA Based Computers II, DIMACS Workshop, June 10-12, 1996, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 44, 1999, pp. 247-258. · Zbl 0919.68044
[12] R. Deaton, M. Garzon, R.C. Murphy, J.A. Rose, D.R. Franceschetti, S.E. Stevens Jr., Genetic search of reliable encodings for DNA-based computation, in: Koza, R. John, Goldberg, E. David, Fogel, B. David, Riolo, L. Rick (Eds.), Proc. 1st Ann. Conf. on Genetic Programming, 1996.
[13] Eastman, W.L., On the construction of comma-free codes, IEEE trans. inform. theory, 11, 263-267, (1965) · Zbl 0138.15102
[14] El Gamal, A.A.; Hemachandra, L.A.; Shperling, I.; Wei, V.K., Using simulated annealing to design good codes, IEEE trans. inform. theory, IT-33, 1, (1987)
[15] T. Ericson, Bounds on the size of a code, in: L.H. Zetterberg, G.H. Einarsson (Eds.), Topics in Coding Theory, Lecture Notes in Control and Information Sciences, Vol. 128, Springer, Berlin, 1989.
[16] Faulhammer, D.; Cukras, A.R.; Lipton, R.J.; Landweber, L.F., Molecular computationrna solutions to chess problems, Proc. natl. acad. sci. USA, 97, 1385-1389, (2002)
[17] U. Feldkamp, W. Banzhaf, H. Rauhe, A DNA sequence compiler, Poster presented at the 6th Internat. Meeting on DNA Based Computers, Leiden, June, 2000. See also http://ls11-www.cs.uni-dortmund.de/molcomp/Publications/publications.html (visited November 11, 2000).
[18] Freier, S.M.; Kierzek, R.; Jaeger, J.A.; Sugimoto, N.; Caruthers, M.H.; Neilson, T.; Turner, D.H., Improved free-energy parameters for predictions of RNA duplex stability, Proc. natl. acad. sci. USA, 83, 9373-9377, (1986)
[19] Frutos, A.G.; Liu, Q.; Thiel, A.J.; Sanner, A.M.W.; 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)
[20] M. Garzon, R. Deaton, P. Neathery, D.R. Franceschetti, R.C. Murphy, A new metric for DNA computing, Proc. 2nd Genetic Programming Conference, Morgan Kaufman, Los Altos, CA, 1997, pp. 472-478.
[21] M. Garzon, R. Deaton, P. Neathery, D.R. Franceschetti, S.E. Stevens Jr., On the encoding problem for DNA computing, Preliminary Proc. 3rd DIMACS Workshop on DNA Based Computers, June 23-25, 1997, pp 230-237.
[22] M. Garzon, R. Deaton, L.F. Nino, S.E. Stevens Jr., M. Wittner, Encoding genomes for DNA computing, Proc. 3rd Genetic Programming Conference, Madison, WI, 1998.
[23] M. Garzon, R.J. Deaton, J.A. Rose, D.R. Franceschetti, Soft molecular computing, Preliminary Proc. 5th Internat. Meeting on DNA Based Computers, June 14-15, MIT Press, Cambridge, MA, 1999, pp. 89-98. · Zbl 0970.68064
[24] Golomb, S.W.; Gordon, B.; Welch, L.R., Comma-free codes, Canad. J. math., 10, 202-209, (1958) · Zbl 0081.14601
[25] A.J. Hartemink, D.K. Gifford, Thermodynamic simulation of deoxyoligonucleotide hybridization, Preliminary Proc. 3rd DIMACS Workshop on DNA Based Computers, June 23-27, 1997, U. Pennsylvania, pp. 15-25. · Zbl 0930.92010
[26] A.J. Hartemink, D.K. Gifford, J. Khodor, Automated constraint-based nucleotide sequence selection for DNA computation, Proc. 4th Annu. DIMACS Workshop on DNA-Based Computers, PA, Pennsylvania, June 1998.
[27] Hirao, I.; Nishimura, Y.; Tagawa, Y.; Watanabe, K.; Miura, K., Extraordinarily stable mini-hairpinselectrophoretical and thermal properties of the various sequence variants of d(GCGAAAGC) and their effect on DNA sequencing, Nucleic acids res., 20, 15, 3891-3896, (1992)
[28] I. Hofacker, RNA Folding Packages, 3 October, 2000. http://www.tbi.univie.ac.at/ ivo/RNA (3, October 2000).
[29] Hofacker, I.L.; Fontana, W.; Stadler, P.F.; Bonhoffer, S.; Tacker, M.; Schuster, P., Fast folding and comparison of RNA secondary structures, Monatsh. chemie, 125, 167-188, (1994)
[30] I.S. Honkala, P.R.J. Ostergard, Code design, in: E. Aarts J.K. Lenstra (Eds.), Local Search in Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, Chichester, 1997. · Zbl 1007.94029
[31] Klein, Y.; Litsyn, S.; Vardy, A., Two new bounds on the size of binary codes with a minimum distance of three, Designs codes cryptogr., 6, 219-227, (1995) · Zbl 0835.94029
[32] K. Komiya, K. Sakamoto, H. Gouzu, S. Yokoyama, M. Arita, A. Nishikawa, M. Hagiya, Successive state transitions with I/O interface by molecules, Preliminary Proc. 6th Internat. Meeting on DNA Based Computers, June, 2000, pp. 21-30. · Zbl 0984.68663
[33] Koschnick, K.-U., Some new constant weight codes, IEEE trans. inform. theory, 37, 2, 370-371, (1991) · Zbl 0721.94021
[34] Litsyn, S.; Vardy, A., The uniqueness of the best code, IEEE trans. inform. theory, 40, 5, 1693-1698, (1994) · Zbl 0818.94018
[35] R. Lyngsø, C. Pedersen, Pseudoknots in RNA secondary structures, Proc. 4th Annu. Internat. Conf. on Computational Molecular Biology (RECOMB00), 2000, pp. 201-209.
[36] MacWilliams, F.J.; Sloane, N.J.A., The theory of error-correcting codes, (1977), North-Holland Amsterdam · Zbl 0369.94008
[37] Mao, C.; LaBean, T.H.; Reif, J.H.; Seeman, N.C., Logical computation using algorithmic self-assembly of DNA triple crossover molecules, Nature, 407, 493-496, (2000)
[38] A. Marathe, A. Condon, R. Corn, On combinatorial DNA word design, Proc. 5th Internat. Meeting on DNA Based Computers, June 1999, J. Comput. Biol., to appear. · Zbl 0969.68070
[39] McCaskill, J.S., The equilibrium partition function and base pair binding probabilities for RNA secondary structure, Biopolymers, 29, 1105-1119, (1990)
[40] K.U. Mir, A restricted genetic alphabet for DNA computing, in: L.F. Landweber, E.B. Baum (Eds.), Proc. 2nd Annu. Workshop on DNA Based Computers, June 10-12, 1996, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 44, 1999, pp. 243-246. · Zbl 0936.68043
[41] Ooyang, Q.; Kaplan, P.; Liu, S.; Libchaber, A., DNA solution of the maximal clique problem, Science, 278, 446-449, (1997)
[42] Peyret, N.; Seneviratne, P.A.; Allawi, H.T.; SantaLucia, J., Nearest-neighbor thermodynamics and NMR of DNA sequences with internal A center dot A, C center dot C, G center dot G, and T center dot T mismatches, Biochemistry, 38, 12, 3468-3477, (1999)
[43] Programmable DNA web site, http://ls11-www.cs.uni-dortmund.de/molcomp/Downloads/downloads.html (visited November 11, 2000).
[44] Rivas, E.; Eddy, S., A dynamic programming algorithm for RNA structure prediction including pseudoknots, J. mol. biol., 285, 2053-2068, (1999)
[45] J.A. Rose, R.J. Deaton, The fidelity of annealing-ligation: a theoretical analysis, Preliminary Proc. 6th Internat. Meeting on DNA Based Computers, June, 2000, pp. 207-221. · Zbl 0984.68666
[46] J.A. Rose, R. Deaton, D.R. Franceschetti, M. Garzon, S.E. Stevens Jr., A statistical mechanical treatment of error in the annealing biostep of DNA computation, Special program in DNA and Molecular Computing at the Genetic and Evolutionary Computation Conference (GECCO-99), Orlando, FL, Morgan Kaufmann, Los Altos, CA, July 13-17, 1999.
[47] S. Roweis, E. Winfree, R. Burgoyne, N.V. Chelyapov, M.F. Goodman, P.W.K. Rothemund, L.M. Adleman, A sticker-based model for DNA computation, in: L.F. Landweber, E.B. Baum (Eds.), Proc. DNA Based Computers II, DIMACS Workshop, June 10-12, 1996, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 44, 1999, pp. 1-29. · Zbl 0919.68027
[48] Sakamoto, K.; Gouzu, H.; Komiya, K.; Kiga, D.; Yokoyama, S.; Yokomori, T.; Hagiya, M., Molecular computation by DNA hairpin formation, Science, 288, 1223-1226, (2000)
[49] SantaLucia, J., A unified view of polymer, dumbbell, and oligonucleotide DNA nearest-neighbor thermodynamics, Proc. natl acad sci USA, 95, 4, 1460-1465, (1998)
[50] Seeman, N.C., De novo design of sequences for nucleic acid structural engineering, J. biomol. struct. dyn., 8, 3, 573-581, (1990)
[51] N.C. Seeman, H. Wang, B. Liu, J. Qi, X. Li, X. Yang, F. Liu, W. Sun, Z. Shen, R. Sha, C. Mao, Y. Wang, S. Zhang, J. Chen, The perils of polynucleotides: the experimental gap between the design and assembly of unusual DNA structures, in: L.F. Landweber, E.B. Baum (Eds.), Proc. 2nd Annu. Workshop on DNA Based Computers, June 10-12, 1996, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 44, 1999, pp. 215-234. · Zbl 0919.68035
[52] Shoemaker, D.D.; Lashkari, D.A.; Morris, D.; Mittman, M.; Davis, R.W., Quantitative phenotypic analysis of yeast deletion mutants using a highly parallel molecular bar-coding strategy, Nat. genet., 16, 450-456, (1996)
[53] W.D. Smith, A. Schweitzer, DNA computers in vitro and in vivo, NECI Tech. Rep., March 20, 1995.
[54] Strachen, T.; Read, A.P., Human molecular genetics, (1996), Bios Scientific Publishers
[55] The PERMUTE program. Available at the PNAS web site http://www.pnas.org/cgi/content/full/97/4/1385/DC1 (visited November 22, 2000).
[56] Wetmur, J.G., DNA probes: applications of the principles of nucleic acid hybridization, Crit. rev. biochem. mol. biol., 26, 3/4, 227-259, (1991)
[57] E. Winfree, Algorithmic self-assembly of DNA, Ph.D. Thesis, California Institute of Technology, Oxford, August 1998, p. 110.
[58] Winfree, E.; Liu, F.; Wenzler, L.; Seeman, N., Design and self-assembly of 2D DNA crystals, Nature, 394, 539-544, (1998)
[59] E. Winfree, X. Yang, N. Seeman, Universal computation via self-assembly of DNA: some theory and experiments, in: L.F. Landweber, E.B. Baum (Eds.), Proc. 2nd Annu. Workshop on DNA Based Computers, June 10-12, 1996, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 44, 1999, pp. 191-214. · Zbl 0919.68034
[60] H. Yoshida, A. Suyama, Solution to 3-SAT by breadth first search, Proc. 5th Internat. Meeting on DNA Based Computers, MIT Press, Cambridge, MA, 1999, pp. 9-20. · Zbl 0971.68062
[61] Yurke, B.; Turberfield, A.J.; Mills, A.P.; Simmel, F.C.; Newmann, J.L., A DNA-fuelled molecular machine made of DNA, Nature, 406, 605-608, (2000)
[62] B.-T. Zhang, S.-Y. Shin, Molecular algorithms for efficient and reliable DNA computing, in: J.R. Koza, K. Deb, M. Doringo, D.B. Fogel, M. Garzon, H. Iba, R.L. Riolo (Eds.), Proc. 3rd Annu. Genetic Programming Conference, Morgan Kaufmann, Los Altos, CA, 1998, pp. 735-742.
[63] M. Zuker, Algorithms, thermodynamics, and databases for RNA secondary structure, 6 September 2000. http://www.ibc.wustl.edu/ zuker/rna/ (29, September 2000).
[64] M. Zuker, RNA folding form 18 August 1998. http://www.ibc.wustl.edu/ zuker/Bio-5495/RNAfold-html/ (29, September 2000).
[65] Zuker, M.; Stielger, P., Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information, Nucleic acids res., 9, 133-148, (1981)
[66] http://wwwchem.leidenuniv.nl/lic98/98high.htm (visited October 20, 2000).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.