2025/09/08 by Mladen Kovačević, Kovačević, Mladen, Keshav Goyal +3
Biochemistry, Genetics and Molecular Biology · Engineering · #Genome Rearrangement Algorithms #graph theory and CDMA systems #DNA and Biological Computing
paper · pdf · doi:10.48550/arxiv.2509.06692
The problem of correcting transpositions (or swaps) of consecutive symbols in q -ary strings is studied. Lower bounds on asymptotically achievable rates of codes correcting t = τn transpositions are derived. The first bound is obtained by analyzing the average cardinality of ``transposition balls'' and evaluating the appropriate version of the generalized Gilbert--Varshamov bound, while the second bound follows from a construction of codes correcting an arbitrary number of transpositions (i.e., zero-error codes). Asymptotic bounds on the cardinality of optimal codes correcting t = \textrmconst transpositions are also derived.