2012/11/16 by Daniel Cullina, Cullina, Daniel, Ankur A. Kulkarni +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced biosensing and bioanalysis techniques #Combinatorics (math.CO) #DNA and Biological Computing #DNA and Nucleic Acid Chemistry #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #cs.DM #cs.IT #math.CO #math.IT
paper · pdf · doi:10.48550/arxiv.1211.4056
arxiv created 2012/11/16 · openalex publication_date 2012/11/16 · arxiv updated 2012/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of constructing deletion correcting codes over a binary alphabet and take a graph theoretic view. An n-bit s-deletion correcting code is an independent set in a particular graph. We propose constructing such a code by taking the union of many constant Hamming weight codes. This results in codes that have additional structure. Searching for codes in constant Hamming weight induced subgraphs is computationally easier than searching the original graph. We prove a lower bound on size of a codebook constructed this way for any number of deletions and show that it is only a small factor below the corresponding lower bound on unrestricted codes. In the single deletion case, we find optimal colorings of the constant Hamming weight induced subgraphs. We show that the resulting code is asymptotically optimal. We discuss the relationship between codes and colorings and observe that the VT codes are optimal in a coloring sense. We prove a new lower bound on the chromatic number of the deletion channel graphs. Colorings of the deletion channel graphs that match this bound do not necessarily produce asymptotically optimal codes.