Abstract
Research in DNA computing was initiated by Leonard Adleman in 1994 when he solved an instance of an NP-complete problem solely by molecules. DNA code words arose in the attempt to avoid unwanted hybridizations of DNA strands for DNA based computations. Given a set of constraints, generating a large set of DNA strands that satisfy the constraints is an important problem in DNA computing. On the other hand, motivated by the non-determinism of molecular reactions, A. Ehrenfeucht and G. Rozenberg introduced forbidding and enforcing systems (fe-systems) as a model of computation that defines classes of languages based on two sets of constraints. We attempt to establish a connection between these two areas of research in natural computing by characterizing a variety of DNA codes that avoid certain types of cross hybridizations by fe-systems. We show that one fe-system can generate the entire class of DNA codes of a certain property, for example θ-k-codes, and confirm some properties of DNA codes through fe-systems. We generalize by fe-systems some known methods of generating good DNA code words which have been tested experimentally.
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.: Molecular computation of solutions to combinatorial problems. Science 266, 1021–1024 (1994)
Cavaliere, M., Jonoska, N.: Forbidding and enforcing in membrane computing. Natural Computing 2, 215–228 (2003)
Deaton, R., Murphy, R., Rose, J., Garzon, M., Franceschetti, D., Stevens Jr., S.: A DNA based implementation of an evolutionary search for good encodings for DNA computation. In: Proc. IEEE Conference on Evolutionary Computation ICEC 1997, pp. 267–271. Institute of Electrical and Electronics Engineers (1997)
Ehrenfeucht, A., Hoogeboom, H.J., Rozenberg, G., van Vugt, N.: Forbidding and enforcing. In: DNA Based Computers V, vol. 54, pp. 195–206. AMS DIMACS, Providence (2000)
Ehrenfeucht, A., Rozenberg, G.: Forbidding-enforcing systems. Theoretical Computer Science 292, 611–638 (2003)
Faulhammer, D., Cukras, A.R., Lipton, R.J., Landweber, L.F.: Molecular computation: RNA solutions to chess problems. Proceedings of the National Academy of Sciences, USA 97(4), 1385–1389 (2000)
Franco, G., Jonoska, N.: Forbidding and enforcing conditions in DNA self-assembly of graphs. In: Nanotechnology: Science and Computation. Natural Computing Series Part I, pp. 105–118 (2006)
Garzon, M.: On codeword design in metric spaces. Natural Computing 8(3), 571–588 (2009)
Genova, D.: Defining Languages by Forbidding-Enforcing Systems. In: Löwe, B., Normann, D., Soskov, I., Soskova, A. (eds.) CiE 2011. LNCS, vol. 6735, pp. 92–101. Springer, Heidelberg (2011)
Genova, D.: Forbidding Sets and Normal Forms for Language Forbidding-Enforcing Systems. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 289–300. Springer, Heidelberg (2012)
Genova, D., Jonoska, N.: Topological properties of forbidding-enforcing systems. Journal of Automata, Languages and Combinatorics 11(4), 375–397 (2006)
Genova, D., Jonoska, N.: Forbidding and enforcing on graphs. Theoretical Computer Science 429, 108–117 (2012)
Hussini, S., Kari, L., Konstantinidis, S.: Coding properties of DNA languages. Theoretical Computer Science 290, 1557–1579 (2003)
Jonoska, N., Mahalingam, K., Chen, J.: Involution codes: with application to DNA coded languages. Natural Computing 4, 141–162 (2005)
Kari, L., Konstantinidis, S., Losseva, E., Wozniak, G.: Sticky-free and overhang-free DNA languages. Acta Informatica 40, 119–157 (2003)
Kari, L., Mahalingam, K.: DNA Codes and Their Properties. In: Mao, C., Yokomori, T. (eds.) DNA12. LNCS, vol. 4287, pp. 127–142. Springer, Heidelberg (2006)
Liu, Q., Wang, L., Frutos, A.G., Condon, A., Corn, R.M., Smith, L.M.: DNA computing on surfaces. Nature 403, 175–179 (2000)
Marathe, A., Condon, A.E., Corn, R.M.: On combinatorial word design. Preliminary Preproceedings of the 5th International Meeting on DNA Based Computers, Boston, pp. 75–88 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Genova, D., Mahalingam, K. (2012). Generating DNA Code Words Using Forbidding and Enforcing Systems. In: Dediu, AH., Martín-Vide, C., Truthe, B. (eds) Theory and Practice of Natural Computing. TPNC 2012. Lecture Notes in Computer Science, vol 7505. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33860-1_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-33860-1_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33859-5
Online ISBN: 978-3-642-33860-1
eBook Packages: Computer ScienceComputer Science (R0)