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.

Synchronized shuffles

ter Beek M. H.;
2005

Abstract

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.
2005
Istituto di Scienza e Tecnologie dell'Informazione "Alessandro Faedo" - ISTI
Shuffles; Synchronized shuffles; Gene linkage; Genome shuffling
File in questo prodotto:
File Dimensione Formato  
prod_43842-doc_2993.pdf

solo utenti autorizzati

Descrizione: tcs05.pdf
Tipologia: Versione Editoriale (PDF)
Dimensione 220.31 kB
Formato Adobe PDF
220.31 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/37408
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 7
social impact