Synchronized shuffles

Ter Beek M. H., Martín-Vide C., Mitrana V.

Shuffles; Synchronized shuffles; Gene linkage; Genome shuffling 

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, vol. 341 (issue 1-3), pp. 263-275