PUMA
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.
 
 
Abstract
(English)
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