Synchronized shuffles
Maurice H. Ter Beek, Carlos Martín-Vide, Victor Mitrana
Genome shuffling Computer Science(all) Theoretical Computer Science Shuffles General Computer Science Synchronized shuffles Gene linkage
We extend the basic shuffle on words and languages, a well-known operation in theoretical computer science, by introducing three synchronized shuffles. These synchronized shuffles have some relevance to molecular biology since they may be viewed as the formal representations of various forms of gene linkage during genome shuffling. More precisely, each synchronized shuffle preserves the genetic backbone of the organisms, as well as the linked genes, by requiring the synchronization of some predefined genes while all other genes are arbitrarily shuffled. As for their mathematical properties, we prove that in a trio the closure under shuffle is equivalent to the closure under any of the synchronized shuffles studied here. Finally, based on this result, we present an algorithm for deciding whether a given regular language is synchronized shuffle closed.
Source: Theoretical computer science 341 (2005): 263–275. doi:10.1016/j.tcs.2005.04.007
Publisher: Elsevier, Lausanne ;, Paesi Bassi
[2] M.H. ter Beek, Team Automata-A Formal Approach to the Modeling of Collaboration Between System Components, Ph.D. Thesis, Leiden Institute of Advanced Computer Science, Leiden University, 2003.
[3] M.H. ter Beek, C.A. Ellis, J. Kleijn, G. Rozenberg, Synchronizations in team automata for groupware systems, Comput. Supported Cooperative Work-J. Collaborative Comput. 12 (1) (2003) 21-69.
[4] M.H. ter Beek, J. Kleijn, Team automata satisfying compositionality, in: K. Araki, S. Gnesi, D. Mandrioli (Eds.), Proc. of FME 2003: Formal Methods-the 12th Internat. Symp. on Formal Methods Europe, Pisa, Italy, Lecture Notes in Computer Science, Vol. 2805, Springer, Berlin, 2003, pp. 381-400.
[5] J.A. Bergstra, A. Ponse, S.A. Smolka (Eds.), Handbook of Process Algebra, Elsevier Science Publishers, Amsterdam, 2001.
[6] S.L. Bloom, Z. Ésik, Free shuffle algebras in language varieties, Theoret. Comput. Sci. 163 (1996) 55-98.
[7] P.C.Y. Chen, A computational model of a class of gene networks with positive and negative controls, BioSystems 73 (2004) 13-24.
[8] R. De Simone, Langages infinitaires et produit de mixage, Theoret. Comput. Sci. 31 (1984) 83-100.
[9] S. Eilenberg, Automata, Languages, and Machines, Vol. A. Academic Press, New York, 1974.
[10] S. Ginsburg, E.H. Spanier, Mappings of languages by two-tape devices, J. ACM 12 (3) (1965) 423-434.
[11] J.L. Gischer, Shuffle languages, Petri nets, and context sensitive grammars, Comm. ACM 24 (1981) 597-605.
[12] M. Jantzen, The power of synchronizing operations on strings, Theoret. Comput. Sci. 14 (1981) 127-154.
[13] T. Kimura, An algebraic system for process structuring and interprocess communication, in: Proc. of the 8th ACM SIGACT Symp. on Theory of Computing, Hershey, Pennsylvania, ACM Press, New York, 1976, pp. 92-100.
[14] J. Kleijn, Team automata for CSCW-a survey, in: H. Ehrig, W. Reisig, G. Rozenberg, H. Weber (Eds.), Petri Net Technology for Communication-Based Systems-Advances in Petri Nets, Lecture Notes in Computer Science, Vol. 2472, Springer, Berlin, 2003, pp. 295-320.
[15] M. Latteux, Y. Roos, Synchronized shuffle and regular languages, in: J. Karhumäki, H.A. Maurer, Gh. Pa˘un, G. Rozenberg (Eds.), Jewels are Forever-Contributions on Theoretical Computer Science in Honor of Arto Salomaa, Springer, Berlin, 1999, pp. 35-44.
[16] R. Milner, A Calculus of Communicating Systems, Lecture Notes in Computer Science, Vol. 92, Springer, Berlin, 1980.
[17] D. Park, On the semantics of fair parallelism, in: D. BjZrner (Ed.), Proc. of the Copenhagen Winter School on Abstract Software Specifications, Lecture Notes in Computer Science, Vol. 86, Springer, Berlin, 1979, pp. 504-526.
[18] A.W. Roscoe, The Theory and Practice of Concurrency, Prentice-Hall International Series in Computer Science, London, 1997.
[19] G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Springer, Berlin, 1997.
[20] R. Schaffrath, K. Sasnauskas, P.A. Meacock, Use of gene shuffles to study the cytoplasmic transcription system operating on Kluyveromyces lactis linear DNA plasmids, Enzyme Microbial Technol. 26 (9-10) (2000) 664-670.
[21] A.C. Shaw, Software descriptions with flow expressions, IEEE Trans. Software Engng. SE-4 (3) (1978) 242 -254.
[22] J. van de Snepscheut, Trace Theory and VLSI Design, Lecture Notes in Computer Science, Vol. 200, Springer, Berlin, 1985.
[23] W. Wechler, Universal Algebra for Computer Scientists, EATCS Monographs on Theoretical Computer Science, Vol. 25, Springer, Berlin, 1992.
[24] Y.-X. Zhang, K. Perry, V.A. Vinci, K. Powell, W.P.C. Stemmer, S.B. del Cardayré, Genome shuffling leads to rapid phenotypic improvement in bacteria, Nature 415 (2002) 644-646.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:43842,
title = {Synchronized shuffles},
author = {Maurice H. Ter Beek and Carlos Martín-Vide and Victor Mitrana},
publisher = {Elsevier, Lausanne ;, Paesi Bassi},
doi = {10.1016/j.tcs.2005.04.007},
journal = {Theoretical computer science},
volume = {341},
pages = {263–275},
year = {2005}
}
0000-0002-2930-6367
