Abstract:
We consider various shuffling and unshuffling operations on languages and words, and examine their closure properties. Although the main goal is to provide some good and novel exercises and examples for undergraduate formal language theory classes, we also provide some new results and some open problems.

Abstract:
We consider a problem of shuffling a deck of cards with ordered labels. Namely we split the deck of N=k^tq cards (where t>=1 is maximal) into k equally sized stacks and then take the top card off of each stack and sort them by the order of their labels and add them to the shuffled stack. We show how to find stacks of cards invariant and periodic under the shuffling. We also show when gcd(q,k)=1 the possible periods of this shuffling are all divisors of order_k(N-q).

Abstract:
The number of ``carries'' when $n$ random integers are added forms a Markov chain [23]. We show that this Markov chain has the same transition matrix as the descent process when a deck of $n$ cards is repeatedly riffle shuffled. This gives new results for the statistics of carries and shuffling.

Abstract:
We have studied shuffling in genes that are conserved between distantly related species. Specifically, we estimated the incidence of gene shuffling in ten organisms from the three domains of life: eukaryotes, eubacteria, and archaea, considering only genes showing significant sequence similarity in pairwise genome comparisons. We found that successful gene shuffling is very rare among such conserved genes. For example, we could detect only 48 successful gene-shuffling events in the genome of the fruit fly Drosophila melanogaster which have occurred since its common ancestor with the worm Caenorhabditis elegans more than half a billion years ago.The incidence of gene shuffling is roughly an order of magnitude smaller than the incidence of single-gene duplication in eukaryotes, but it can approach or even exceed the gene-duplication rate in prokaryotes. If true in general, this pattern suggests that gene shuffling may not be a major force in reshaping the core genomes of eukaryotes. Our results also cast doubt on the notion that introns facilitate gene shuffling, both because prokaryotes show an appreciable incidence of gene shuffling despite their lack of introns and because we find no statistical association between exon-intron boundaries and recombined domains in the two multicellular genomes we studied.How do genes with new functions originate? This remains one of the most intriguing open questions in evolutionary genetics. Three principal mechanisms can create genes of novel function: point mutations and small insertions or deletions in existing genes; duplication of entire genes or domains within genes, in combination with mutations that cause functional divergence of the duplicates [1-3]; and recombination between dissimilar genes to create new recombinant genes (see, for example [4,5]). We here choose to call only this kind of recombination gene shuffling, excluding, for example, duplication of domains within a gene. In such a gene shuffling event, the parenta

Abstract:
In this paper we introduce and study a new property of infinite words: An infinite word $x\in A^\mathbb{N}$, with values in a finite set $A$, is said to be $k$-self-shuffling $(k\geq 2)$ if $x$ admits factorizations: $x=\prod_{i=0}^\infty U_i^{(1)}\cdots U_i^{(k)}=\prod_{i=0}^\infty U_i^{(1)}=\cdots =\prod_{i=0}^\infty U_i^{(k)}$. In other words, there exists a shuffle of $k$-copies of $x$ which produces $x$. We are particularly interested in the case $k=2$, in which case we say $x$ is self-shuffling. This property of infinite words is shown to be an intrinsic property of the word and not of its language (set of factors). For instance, every aperiodic word contains a non self-shuffling word in its shift orbit closure. While the property of being self-shuffling is a relatively strong condition, many important words arising in the area of symbolic dynamics are verified to be self-shuffling. They include for instance the Thue-Morse word and all Sturmian words of intercept $0<\rho <1$ (while those of intercept $\rho=0$ are not self-shuffling). Our characterization of self-shuffling Sturmian words can be interpreted arithmetically in terms of a dynamical embedding and defines an arithmetic process we call the {\it stepping stone model}. One important feature of self-shuffling words stems from its morphic invariance, which provides a useful tool for showing that one word is not the morphic image of another. The notion of self-shuffling has other unexpected applications particularly in the area of substitutive dynamical systems. For example, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic.

Abstract:
In this paper, we discuss a shuffling sequence problem: Given a DNA sequence, we generate a random sequence that preserves the frequencies of all mononucleotides, dinucleotides, trinucleotides or some high order base-compositions of the given sequence. Two quadratic running time algorithms, called Frequency-Counting algorithm and Decomposition- and-Reassemble algorithm, are presented for solving the problem. The first one is to count all frequencies of the mononucleotides, dinucleotides, trininucleotides, and any high order base-compositions in the given sequence. The second one is to generate a random DNA sequence that preserves the mononucleotides, dinucleotides, trinucleotides, or some high order base- compositions. The two algorithms are implemented into a program ShuffleSeq (in C) and is available at http://www.cs.iastate.edu/~ sqwu/ShuffleSeq.html.

Abstract:
We study the dynamics of a certain discrete model of interacting particles that comes from the so called shuffling algorithm for sampling a random tiling of an Aztec diamond. It turns out that the transition probabilities have a particularly convenient determinantal form. An analogous formula in a continuous setting has recently been obtained by Jon Warren studying certain model of interlacing Brownian motions which can be used to construct Dyson's non-intersecting Brownian motion. We conjecture that Warren's model can be recovered as a scaling limit of our discrete model and prove some partial results in this direction. As an application to one of these results we use it to rederive the known result that random tilings of an Aztec diamond, suitably rescaled near a turning point, converge to the GUE minor process.