Making DNA Expressions Minimal

• Autorzy: van Vliet R. , Hoogeboom H.J.
• Języki publikacji: EN

Abstrakty

EN

DNA expressions constitute a formal notation for DNA molecules that may contain nicks and gaps. Different DNA expressions may denote the same DNA molecule. We describe an algorithm to rewrite a given DNA expression into a DNA expression of minimal length denoting the same molecule.

Słowa kluczowe

EN

DNA molecules; formal notation; minimal DNA expressions; algorithm; complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 2
• Strony: 199--226
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

van Vliet R.

• Leiden Institute of Advanced Computer Science, Leiden University Niels Bohrweg 1, 2333 CA Leiden, The Netherlands

autor

Hoogeboom H.J.

• Leiden Institute of Advanced Computer Science, Leiden University Niels Bohrweg 1, 2333 CA Leiden, The Netherlands

Bibliografia

• [1] L.M. Adleman: Molecular computation of solutions to combinatorial problems, Science 266, 1994, 1021–1024.
• [2] D. Boneh, C. Dunworth, R.J. Lipton: Breaking DES using a molecular computer, DNA Based Computers – Proceedings of a DIMACS Workshop, April 4, 1995, Princeton University (R.J. Lipton, E.B. Baum, Eds.), American Mathematical Society, Providence, RI, 1996, 37–66.
• [3] L. Cardelli, W. Shih (Eds.): DNA Computing and Molecular Programming – 17th International Conference, DNA 17, Pasadena, CA, USA, September 19–23, 2011 – Proceedings, LNCS 6937, Springer, Berlin, 2011.
• [4] J. Chen, N. Jonoska, G. Rozenberg (Eds.): Nanotechnology: Science and Computation, Natural Computing Series, Springer, Berlin, 2006.
• [5] T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introduction to Algorithms, The MIT Press, Cambridge and McGraw-Hill, New York, 1990.
• [6] A. Ehrenfeucht, T. Harju, I. Petre, D.M. Prescott, G. Rozenberg: Computation in Living Cells – Gene Assembly in Ciliates, Natural Computing Series, Springer, Berlin, 2004.
• [7] H. Gu, J. Chao, S.-J. Xiao, N.C. Seeman: A proximity-based programmable DNA nanoscale assembly line, Nature 465, 2010, 202–205.
• [8] T. Head: Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors, Bulletin of Mathematical Biology 49(6), 1987, 737–759.
• [9] L. Kari, S. Konstantinidis, P. Sos´ık: On properties of bond-free DNA languages, Theoretical Computer Science 334, 2005, 131–159.
• [10] Z. Li: Algebraic properties of DNA operations, Proceedings of the Fourth International Meeting on DNA Based Computers, University of Pennsylvania, Philadelphia, USA, June 15–19, 1998, BioSystems 52 (L. Kari, H. Rubin, D.H. Wood, Eds.), 1999, 55–61.
• [11] Gh. Păun, G. Rozenberg, A. Salomaa: DNA Computing – New Computing Paradigms, Springer, Berlin, 1998.
• [12] P.W.K. Rothemund: Folding DNA to create nanoscale shapes and patterns, Nature 440, 2006, 297–302.
• [13] Y. Sakakibara, Y. Mi (Eds.): DNA Computing and Molecular Programming – 16th International Conference, DNA 16, Hong Kong, China, June 14–17, 2010 – Revised Selected Papers, LNCS 6518, Springer, Berlin, 2011.
• [14] R. van Vliet: Combinatorial Aspects of Minimal DNA Expressions (ext.), Technical Report 2004-03, Leiden Institute of Advanced Computer Science, Leiden University, March 2004, see www.liacs.nl/home/rvvliet/dnaexpressions/
• [15] R. van Vliet: All about a Minimal Normal Form for DNA Expressions, Technical Report 2011-03, Leiden Institute of Advanced Computer Science, Leiden University, July 2011, see www.liacs.nl/home/rvvliet/dnaexpressions/
• [16] R. van Vliet, H.J. Hoogeboom: A minimal normal form for DNA expressions, Fundamenta Informaticae, 123(2), 2013, 227–243.
• [17] R. van Vliet, H.J. Hoogeboom, G. Rozenberg: Combinatorial aspects of minimal DNA expressions, DNA Computing – 10th InternationalWorkshop on DNA Computing, DNA10, Milan, Italy, June 7–10, 2004 – Revised Selected Papers (C. Ferretti, G. Mauri, C. Zandron, Eds.), LNCS 3384, Springer, Berlin, 2005, 375–388.
• [18] R. van Vliet, H.J. Hoogeboom, G. Rozenberg: The construction of minimal DNA expressions, Natural Computing 5, 2006, 127–149.
• [19] E. Winfree: DNA computing by self-assembly, The Bridge 33(4), 2003, 31–38.