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)}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>λ</mml:mi> </mml:mrow> <mml:mo>=</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>λ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> </mml:mrow> <mml:mrow> <mml:msub> <mml:mi>λ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>,</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>λ</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:mrow> </mml:math> is a partition of $${{\varvec{n}}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> which indicates the number of repeated regions or genes of different types ( $$\varvec{\lambda _i}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>λ</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> </mml:math> of type $${{\varvec{i}}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>i</mml:mi> </mml:mrow> </mml:math> with $${{\varvec{n}}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> total regions). A circular genome with $${{\varvec{n}}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> oriented regions determined by $$\varvec{\lambda }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>λ</mml:mi> </mml:mrow> </mml:math> can be identified with the double coset space $${\varvec{S}}_{\varvec{\lambda }} \backslash {\varvec{B}}_{\varvec{n}} / {\varvec{D}}_{\varvec{n}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mi>S</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>λ</mml:mi> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>\</mml:mo> </mml:mrow> <mml:msub> <mml:mrow> <mml:mi>B</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> <mml:mo>/</mml:mo> <mml:msub> <mml:mrow> <mml:mi>D</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> , where $$\varvec{B_n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>B</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:math> is the hyperoctahedral group, $$\varvec{D_n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>D</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:math> the dihedral group extended to $$\varvec{B_n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>B</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:math> , and $$\varvec{S_\lambda }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>S</mml:mi> <mml:mi>λ</mml:mi> </mml:msub> </mml:mrow> </mml:math>