Istituto di Scienza e Tecnologie dell'Informazione     
Ter Beek M. H., Martin-Vide C., Mitrana V. Synchronized Shuffles. In: Theoretical Computer Science, vol. 341 (1-3) pp. 263 - 275. Elsevier Science Publishers, Amsterdam, 2005.
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.
URL: http://dx.doi.org/doi:10.1016/j.tcs.2005.04.007
Subject Shuffles
Synchronized shuffles
Gene linkage
Genome shuffling
F.4.3 Formal Languages. Operations on languages
G.2.1 Combinatorics. Permutations and combinations

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional