Involution Solid and Join codes

• Autorzy: Jonoska N. , Kari L. , Mahalingam K.
• Języki publikacji: EN

Abstrakty

EN

In this paper we study a generalization of the classical notions of solid codes and comma-free codes: involution solid codes (q-solid) and involution join codes (q-join). These notions are motivated by DNA strand design where Watson-Crick complementarity can be formalized as an antimorphic involution. We investigate closure properties of these codes, as well as necessary conditions for q-solid codes to be maximal. We show how the concept of q-join can be utilized such that codes that are not themselves q-comma free can be split into a union of subcodes that are q-comma free.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 86, nr 1-2
• Strony: 127--142
• Opis fizyczny: bibliogr. 25 poz.

Twórcy

autor

Jonoska N.

autor

Kari L.

autor

Mahalingam K.

• 355 Middlesex College, Department of Computer Science, University of Western Ontario, London, Ontario, Canada-N6A5B7, Canada,

Bibliografia

• [1] J. Berstel and D. Perrin, Theory of Codes, Academic Press, Inc. Orlando Florida, 1985.
• [2] R.Deaton, J.Chen, H.Bi, M.Garzon, H.Rubin and D.F.Wood, A PCR based protocol for in vitro selection of non-crosshybridizing oligonucleotides, DNA Computing: Proceedings of the 8th International Meeting on DNA Based Computers (M.Hagiya, A.Ohuchi editors), LNCS 2568 (2003) 196-204.
• [3] R.Deaton, J.Chen, M.Garzon, J.Kim, D.Wood, H.Bi, D.Carpenter and Y.Wang, Characterization of Non-Crosshybridizing DNA Oligonucleotides Manufactured in Vitro, DNA computing: Preliminary Proceedings of the 10th International Meeting on DNA Based Computers, (C.Ferretti, G.Mauri, C.Zandron editors) LNCS 3384 (2005) 50-61.
• [4] R. Deaton et al, A DNA based implementation of an evolutionary search for good encodings for DNA computation, Proc. IEEE Conference on Evolutionary Computation ICEC-97 (1997) 267-271.
• [5] D. Faulhammer, A. R. Cukras, R. J. Lipton and L. F.Landweber, Molecular computation: RNA solutions to chess problems, Proceedings of the National Academy of Sciences, USA, 97-4 (2000) 1385-1389.
• [6] C. Ferreti and G.Mauri, Remarks on Relativisations and DNA encodings, Aspects ofMolecular Computing, (N.Jonoska, G.Paun, G.Rozenberg editors), LNCS 2950 (2004) 132-138.
• [7] M. Garzon, R. Deaton and D. Reanult, Virtual test tubes: a new methodology for computing, Proc. 7th. Int. Symposium on String Processing and Information retrieval, A Coru˘na, Spain. IEEE Computing Society Press (2000) 116-121.
• [8] T.Head, Unique decipherability relative to a language, Tamkang J. Math, 11 (1980) 59-66.
• [9] T. Head, Relativized code concepts and multi-tube DNA dictionaries, Finite vs Infinite, (C.S. Calude and G. Paun editors), (2000): 175-186.
• [10] S. Hussini, L. Kari and S. Konstantinidis, Coding properties of DNA languages, DNA Computing: Proceedings of the 7th InternationalMeeting on DNA Based Computers, (N. Jonoska, N.C. Seeman editors), LNCS 2340 (2002) 57-69.
• [11] N.Jonoska, L.Kari and K.Mahalingam, Involution solid and join codes, Proceedings of the 10th International Meeting on Developments in Language Theory, (Oscar H. Ibarra, Zhe Dang editors) LNCS 4036 (2006), 192-202.
• [12] N.Jonoska, K.Mahalingamand J.Chen, Involution codes: with application to DNA coded languages,Natural Computing, Vol 4-2 (2005) 141-162.
• [13] H.Jürgensen and S.S.Yu, Solid Codes, Journal of Information Processing Cybernetics, EIK 26 (1990) 10, 563-574.
• [14] H.Jürgensen and S.Konstantinidis, Codes, Handbook of Formal Languages, Vol 1, (G.Rozenberg and A.Salomaa editors), Springer Verlag (1997) 511-608.
• [15] H.Jürgensen, M.Katsura and S.Konstantinidis, Maximal solid codes, Journal of Automata, Languages and Combinatorics 6(1) (2001) 25-50.
• [16] L.Kari, S.Konstantinidis, E.Losseva and G.Wozniak, Sticky-free and overhang-free DNA languages, Acta Informatica 40 (2003) 119-157.
• [17] L.Kari and K.Mahalingam, DNA Codes and their properties, Proceedings of the 12th InternationalMeeting on DNA Computing, (C. Mao, T.Yokomori, B.T. Zhang, Editors), LNCS 4287 (2006), 127-142.
• [18] L.Kari, S.Konstantinidis and P.Sosik, Bond-free languages: formalizations, maximality and construction methods, Proceedings of the 10th International Meeting on DNA Computing, (C.Ferreti, G.Mauri, C.Zandron editors) LNCS 3384 (2005) 169-181.
• [19] L.Kari, S.Konstantinidis and P.Sosik, Preventing undesirable bonds between DNA codewords, Proceedings of the 10th InternationalMeeting on DNA Computing, LNCS 3384 (2005) 182-191.
• [20] K.Mahalingam, InvolutionCodes: With Application to DNA StrandDesign Ph.d. Thesis, University of South Florida, Tampa, FL, 2004.
• [21] A.Marathe, A.E. Condon and R.M. Corn, On combinatorial word design, Journal of Computational Biology 8:3 (2001) 201-220.
• [22] G.Mauri and C.Ferretti, Word design for molecular computing: a survey, DNA Computing: Proceedings of the 9th International Meeting on DNA Based Computers, (J.Chen, J.H.Reif editors), LNCS 2943 (2004) 37-47.
• [23] H.J, Shyr and S.S.Yu , Solid codes and disjunctive domains, Semigroup Forum 41 (1990) 23-37.
• [24] H.J.Shyr, G.Thierrin and S.S.Yu, Monogenic e-closed languages and dipolar words, Discrete Mathematics 126 (1994) 339-348.
• [25] H.J.Shyr, Free Monoids and Languages, Hon Min Book Company 2001.