Genome rearrangements as double coset Markov chains

Abstract Permutation groups provide a natural framework for modeling genomes and their rearrangement events, which is crucial for understanding evolutionary relationships. Double cosets can be used to model objects arising from multiple symmetries, such as circular genomes with repeated genes. Suppose $${\varvec{\lambda } = \varvec{( \lambda _1,}\varvec{\lambda _2,} \varvec{\dots , \lambda _k)}}$$ λ = ( λ 1 , λ 2 , ⋯ , λ k ) is a partition of $${{\varvec{n}}}$$ n which indicates the number of repeated regions or genes of different types ( $$\varvec{\lambda _i}$$ λ i of type $${{\varvec{i}}}$$ i with $${{\varvec{n}}}$$ n total regions). A circular genome with $${{\varvec{n}}}$$ n oriented regions determined by $$\varvec{\lambda }$$ λ can be identified with the double coset space $${\varvec{S}}_{\varvec{\lambda }} \backslash {\varvec{B}}_{\varvec{n}} / {\varvec{D}}_{\varvec{n}}$$ S λ \ B n / D n , where $$\varvec{B_n}$$ B n is the hyperoctahedral group, $$\varvec{D_n}$$ D n the dihedral group extended to $$\varvec{B_n}$$ B n , and $$\varvec{S_\lambda }$$ S λ the Young subgroup extended to $$\varvec{B_n}$$ B n . This paper develops this correspondence and derives formulas for the sizes of double cosets and the number of double cosets in special cases. The size of double cosets gives the induced probability distribution on genomes from uniformly sampling $$\varvec{B_n}$$ B n . The representation is utilized to define Markov chains which capture the processes of inversions, transpositions, and translocations.