Sorting permutations: games, genomes, and cycles

DOI10.1142/S179383091750063XzbMATH Open1386.05002arXiv1410.2353OpenAlexW2964003467MaRDI QIDQ4595252FDOQ4595252

Authors:

Publication date: 29 November 2017

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Abstract: Permutation sorting, one of the fundamental steps in pre-processing data for the efficient application of other algorithms, has a long history in mathematical research literature and has numerous applications. Two special-purpose sorting operations are considered in this paper: context directed swap, abbreviated cds, and context directed reversal, abbreviated cdr. These are special cases of sorting operations that were studied in prior work on permutation sorting. Moreover, cds and cdr have been postulated to model molecular sorting events that occur in the genome maintenance program of certain species of single-celled organisms called ciliates. This paper investigates mathematical aspects of these two sorting operations. The main result of this paper is a generalization of previously discovered characterizations of cds-sortability of a permutation. The combinatorial structure underlying this generalization suggests natural combinatorial two-player games. These games are the main mathematical innovation of this paper.

Full work available at URL: https://arxiv.org/abs/1410.2353

Recommendations

• Quantifying CDS sortability of permutations by strategic pile size
• scientific article; zbMATH DE number 1342319
• On combinatorial properties of elementary intramolecular operations
• Sorting a bridge hand
• Sorting with fixed-length reversals

zbMATH Keywords

permutation sortingmisere gamecontext directed block interchangescontext directed reversalsfixed point sorting gamenormal play game

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Problems related to evolution (92D15) Searching and sorting (68P10) Combinatorial games (91A46)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Combinatorics of genome rearrangements.
• On Hultman numbers
• Computation in living cells. Gene assembly in ciliates
• Template-guided recombination for IES elimination and unscrambling of genes in stichotrichous ciliates
• Sorting by Transpositions
• Transforming cabbage into turnip
• Characterizing the micronuclear gene patterns in ciliates
• A very elementary presentation of the Hannenhalli-Pevzner theory
• Sorting permutations by block-interchanges
• Reducibility of gene patterns in ciliates using the breakpoint graph.

Cited In (4)

• CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS
• A diagrammatic approach to information transmission in generalised switches
• On combinatorial properties of elementary intramolecular operations
• Quantifying CDS sortability of permutations by strategic pile size

Uses Software

• OEIS

This page was built for publication: Sorting permutations: games, genomes, and cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595252)