On the maximum number of non-confusable strings evolving under short tandem duplications

DOI10.1134/S0032946022020028MaRDI QIDQ6173451zbMATH OpenFDO

Authors

Publication date 21 July 2023

Published in Problems of Information Transmission (Search for Journal in Brave)

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

zbMATH Keywords

constrained codeDNA storageduplication errorerror correctionrepetition errorsquare-free stringsticky insertiontandem duplicationtandem repeatzero-error capacity

Mathematics Subject Classification ID

Combinatorics on words (68R15) Protein sequences, DNA sequences (92D20) Channel models (including quantum) in information and communication theory (94A40) Combinatorial codes (94B25) Synchronization error-correcting codes (94B50)

Abstract: The set of all $q$-ary strings that do not contain repeated substrings of length $leqslant!3$ (i.e., that do not contain substrings of the form $aa$, $abab$, and $abcabc$) constitutes a code correcting an arbitrary number of tandem-duplication mutations of length $leqslant!3$. In other words, any two such strings are non-confusable in the sense that they cannot produce the same string while evolving under tandem duplications of length $leqslant!3$. We demonstrate that this code is asymptotically optimal in terms of rate, meaning that it represents the largest set of non-confusable strings up to subexponential factors. This result settles the zero-error capacity problem for the last remaining case of tandem-duplication channels satisfying the "root-uniqueness" property.

Recommendations

• Deciding the confusability of words under tandem repeats in linear time
• On duplication-free codes for disjoint or equal-length errors
• Duplication-correcting codes
• Uniformly bounded duplication codes
• Improved Lower Bounds for the Capacity of i.i.d. Deletion and Duplication Channels

Cites work

• Capacity and Expressiveness of Genomic Tandem Duplication
• Deciding the confusability of words under tandem repeats in linear time
• Duplication-Correcting Codes for Data Storage in the DNA of Living Organisms
• Efficient Encoding/Decoding of GC-Balanced Codes Correcting Tandem Duplications
• The Capacity of String-Duplication Systems
• Uniformly bounded duplication languages

Cited in

(1)

• On duplication-free codes for disjoint or equal-length errors

This page was built for publication: On the maximum number of non-confusable strings evolving under short tandem duplications

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