Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA self-assembly and DNA computing. Previous work has extended results from coding theory to obtain bounds on code size for new biologically motivated constraints and has applied heuristic local search and genetic algorithm techniques for code design. This article proposes a natural optimization formulation of the DNA code design problem in which the goal is to design n strings that satisfy a given set of constraints while minimizing the length of the strings. For multiple sets of constraints, we provide simple randomized algorithms that run in time polynomial in n and any given constraint parameters, and output strings of length within a constant factor of the optimal with high probability. To the best of our knowledge, this work is the first to consider this type of optimization problem in the context of DNA code design.

REFERENCES

• 1: Leonard M. Adleman, Molecular computation of solutions to combinatorial problems, Science, v.266 n.11, p.1021-1024, Nov. 1994
• 2: Gagan Aggarwal , Michael H. Goldwasser , Ming-Yang Kao , Robert T. Schweller, Complexities for generalized models of self-assembly, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 3: Amir Ben-Dor , Richard Karp , Benno Schwikowski , Zohar Yakhini, Universal DNA tag systems: a combinatorial design scheme, Proceedings of the fourth annual international conference on Computational molecular biology, p.65-75, April 2000, Tokyo, Japan [doi>10.1145/332306.332346]
• 4: Ravinderjit S. Braich , Cliff Johnson , Paul W. K. Rothemund , Darryl Hwang , Nickolas V. Chelyapov , Leonard M. Adleman, Solution of a Satisfiability Problem on a Gel-Based DNA Computer, Revised Papers from the 6th International Workshop on DNA-Based Computers: DNA Computing, p.27-42, June 13-17, 2000
• 5: Arwen Brenneman , Anne Condon, Strand design for biomolecular computation, Theoretical Computer Science, v.287 n.1, p.39-58, 25 September 2002 [doi>10.1016/S0304-3975(02)00135-4]
• 6: Brenner, S. 1997. Methods for sorting polynucleotides using oligonucleotide tags. US Patent Number 5,604,097.
• 7: Brenner, S., and Lerner, R. A. 1992. Encoded combinatorial chemistry. Proc. Nat. Acad. Sci. 89. 5381--5383.
• 8: Breslauer, K. J., Frank, R., Blocker, H., and Marky, L. A. 1986. Predicting DNA duplex stability from the base sequence. Proc. Nat. Acad. Sci. 83, 3746--3750.
• 9: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 10: Deaton, R., Garzon, M., Murphy, R., Franceschetti, D., and Stevens, S. 1996. Genetic search of reliable encodings for DNA based computation. In Proceedings of the 1st Annual Conference on Genetic Programming. 9--15.
• 11: Frutos, A. G., Liu, Q., Thiel, A. J., Sanner, A. M. W., Condon, A. E., Smith, L. M., and Corn, R. M. 1997. Demonstration of a word design strategy for DNA computing on surfaces. Nucleic Acids Res. 25, 4748--4757.
• 12: Philippe Gaborit , Oliver D. King, Linear constructions for DNA codes, Theoretical Computer Science, v.334 n.1-3, p.99-113, 11 April 2005 [doi>10.1016/j.tcs.2004.11.004]
• 13: Garzon, M., Deaton, R., Neathery, P., Franceschetti, D., and Murphy, R. 1997. A new metric for DNA computing. In Proceedings of the 2nd Genetic Programming Conference. 472--278.
• 14: Garzon, M. H., Phan, V., and Neel, A. J. 2009. Optimal DNA codes for computing and self-assembly. J. Nanotechnol. Molec. Comput. 1, 1, 1--17.
• 15: Kao, M.-Y., Sanghi, M., and Schweller, R. 2006. Flexible word design and graph labeling. In Proceedings of the 17th International Symposium on Algorithms and Computation. 48--60.
• 16: King, O. D. 2003. Bounds for DNA codes with constant gc-content. J. Combinatorics 10, 13.
• 17: Marathe, A., Condon, A., and Corn, R. M. 2001. On combinatorial DNA word design. J. Comput. Biol. 8, 3, 201--219.
• 18: Vinhthuy Phan , Max H. Garzon, On codeword design in metric DNA spaces, Natural Computing: an international journal, v.8 n.3, p.571-588, September 2009 [doi>10.1007/s11047-008-9088-6]
• 19: Shoemaker, D. D., Lashkari, D. A., Morris, D., Mittmann, M., and Davis, R. W. 1996. Quantitative phenotypic analysis of yeast deletion mutants using a highly parallel molecular bar-coding strategy. Nature 16, 450--456.
• 20: Tsaftaris, S. A. 2004. DNA computing from a signal processing viewpoint. IEEE Signal Proces. Mag. 21, 100--106.
• 21: Tulpan, D. C., and Hoos, H. H. 2003. Hybrid randomised neighbourhoods improve stochastic local search for DNA code design. In Proceedings of the 16th Conference of the Canadian Society for Computational Studies of Intelligence, Y. Xiang and B. Chaib-draa, Eds. Lecture Notes in Computer Science, vol. 2671. Springer-Verlag, New York, 418--433.
• 22: Dan C. Tulpan , Holger H. Hoos , Anne Condon, Stochastic Local Search Algorithms for DNA Word Design, Revised Papers from the 8th International Workshop on DNA Based Computers: DNA Computing, p.229-241, June 10-13, 2002
• 23: Winfree, E., Liu, F., Wenzler, L., and Seeman, N. 1998. Design and self-assembly of two-dimensional DNA crystals. Nature 394, 539--544.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms

Keywords:
DNA code design, randomized algorithms