Regular PaperNo Access

BOND-FREE LANGUAGES: FORMALIZATIONS, MAXIMALITY AND CONSTRUCTION METHODS

LILA KARI

Department of Computer Science, The University of Western Ontario, London, Ontario, N6A 5B7, Canada

Search for more papers by this author

STAVROS KONSTANTINIDIS

Department of Mathematics and Computing Science, Saint Mary's University, Halifax, Nova Scotia, B3H 3C3, Canada

Corresponding author.

Search for more papers by this author

, and

PETR SOSÍK

Department of Computer Science, The University of Western Ontario, London, Ontario, N6A 5B7, Canada

Institute of Computer Science, Silesian University, 74601 Opava, Czech Republic

Search for more papers by this author

https://doi.org/10.1142/S0129054105003467Cited by:9 (Source: Crossref)

Abstract

The problem of negative design of DNA languages is addressed, that is, properties and construction methods of large sets of words that prevent undesired bonds when used in DNA computations. We recall a few existing formalizations of the problem and then define the property of sim-bond-freedom, where sim is a similarity relation between words. We show that this property is decidable for context-free languages and polynomial-time decidable for regular languages. The maximality of this property also turns out to be decidable for regular languages and polynomial-time decidable for an important case of the Hamming similarity. Then we consider various construction methods for Hamming bond-free languages, including the recently introduced method of templates, and obtain a complete structural characterization of all maximal Hamming bond-free languages. This result is applicable to the θ-k-code property introduced by Jonoska and Mahalingam.

A short version (without proofs) of this work will appear in the proceedings volume of "Tenth International Meeting on DNA Computing, Milan, June 7-10, 2004."

Keywords:

References

M. Andronescu, D. Dees, L. Slaybaugh, Y. Zhao, A. Condon, B. Cohen, S. Skiena, "Algorithms for testing that sets of DNA words concatenate without secondary structure," in [9], pp. 182-195 . Google Scholar
M. Arita and S. Kobayashi, New Generation Computing 20, 263 (2002). Crossref, Web of Science, Google Scholar
E. Baum, DNA sequences useful for computation, Proc. 2nd DIMACS Workshop on DNA-based computers pp. 122–127. Google Scholar
J. Chen and J. Reif (eds.) , Pre-proceedings 9th International Workshop on DNA-Based Computers, LNCS 2943 ( 2004 ) . Google Scholar
M. Domaratzki, "Deletion Along Trajectories," Tech. report 464-2003, School of Computing, Queen's University, 2003 . Google Scholar
A. Ehrenfeucht and G. Rozenberg, RAIRO Inform. Ther. Appl. 20, 89 (1985). Crossref, Web of Science, Google Scholar
U. Feldkamp, S. Saghafi, H. Rauhe, "DNASequenceGenerator - A program for the construction of DNA sequences," in [14], pp. 179–189 . Google Scholar
M. Garzonet al., A new metric for DNA computing, Proc. 2nd Annual Genetic Programming Conference, eds. J. R. Kozaet al. (1997) pp. 472–478. Google Scholar
M. Hagiya and A. Ohuchi (eds.) , Proc. 8th Workshop on DNA-Based Computers, LNCS 2568 ( 2002 ) . Google Scholar
T. Head, Finite Versus Infinite: Contributions to an Eternal Dilemma, eds. C. S. Calude and G. Pănn (Springer-Verlag, London, 2000) pp. 175–186. Crossref, Google Scholar
J. E. Hopcroft , R. Motwani and J. D. Ullman , Introduction to Automata Theory, Languages, and Computation ( Addison-Wesley , Boston , 2001 ) . Google Scholar
S. Hussini, L. Kari, S. Konstantinidis, "Coding properties of DNA languages," in [14], pp. 107-118 . Google Scholar
N. Jonoska and K. Mahalingam, Languages of DNA based code words, Preproceedings of DNA9, eds. J. Chen and J. Reif pp. 58–68. Google Scholar
N. Jonoska and N. C. Seeman (eds.) , Proc. 7th Workshop on DNA-Based Computers, LNCS 2340 ( 2002 ) . Google Scholar
H. Jürgensen, S. Konstantinidis, "Codes," in [30], pp. 511–607 . Google Scholar
L. Kari, "On insertion and deletion in formal languages," Ph. D. Thesis, University of Turku, Finland, 1991 . Google Scholar
L. Kari, Theoretical Computer Science 132, 129 (1994). Crossref, Web of Science, Google Scholar
L. Kari, R. Kitto and G. Thierrin, Lecture Notes in Computer Science 2300, eds. W. Braueret al. (2002) pp. 376–393. Google Scholar
L. Kari, S. Konstantinidis, "Language equations, maximality and error detection," Journal of Computer and System Sciences (to appear) . Google Scholar
L. Kariet al., Acta Informatica 40, 119 (2003). Crossref, Web of Science, Google Scholar
L. Kari, S. Konstantinidis, P. Sosík, "On properties of bond-free DNA languages," Tech. report 609, Univ. Western Ontario, Dept. Computer Science, 2003 . Google Scholar
L. Kari, S. Konstantinidis, P. Sosík "Bond-free languages: formalizations, maximality and construction methods," Tech. report 2004-01, Dept. Mathematics and Computing Science, Saint Mary's University, Halifax, 2004. Electronic form available at http://www.stmarys.ca/academic/science/compsci/ A short version of this work will appear in the proceedings volume of the Tenth International Meeting on DNA Computing, Milan, June 7-10, 2004 . Google Scholar
L. Kari, P. Sosík, "Language deletion on trajectories," Tech. report 606, Dept. of Computer Science, University of Western Ontario, London, 2003 . Google Scholar
S. Konstantinidis, J. Universal Comp. Science 8, 278 (2002). Web of Science, Google Scholar
A. E. Condon, R. M. Corn and A. Marathe, J. Computational Biology 8, 201 (2001). Web of Science, Google Scholar
A. Mateescu, G. Rozenberg, A. Salomaa, "Shuffle on trajectories: syntactic constraints," Tech. report 41, Turku Centre for Computer Science, 1996, and Theoretical Computer Science 197 (1998), 1–56 . Google Scholar
G. Mauri, C. Ferretti, "Word Design for Molecular Computing: A Survey," in [4], pp. 37–46 . Google Scholar
G. Păun , G. Rozenberg and A. Salomaa , DNA Computing. New Computing Paradigms ( Springer-Verlag , Berlin , 1998 ) . Google Scholar
J. H. Reif, T. H. LaBean, M. Pirrung, V. S. Rana, B. Guo, C. Kingsford, G. S. Wickham, "Experimental construction of very large scale DNA databases with associative search capability" in [14], pp. 231–247 . Google Scholar
G. Rozenberg and A. Salomaa (eds.) , Handbook of Formal Languages I ( Springer , Berlin , 1997 ) . Crossref, Google Scholar
A. Salomaa , Formal Languages ( Academic press , London , 1973 ) . Google Scholar
F. Tanaka, M. Nakatsugawa, M. Yamamoto, T. Shiba, A. Ohuchi, "Developing support system for sequence design in DNA computing," in [14], pp. 129–137 . Google Scholar
D. C. Tulpan, H. H. Hoos, A. E. Condon, "Stochastic Local Search Algorithms for DNA Word Design," in [9], pp. 229–241 . Google Scholar
D. Wood , Theory of Computation ( Harper & Row , New York , 1987 ) . Google Scholar
S. Yu, "Regular languages," in [30], pp. 41–110 . Google Scholar