A characterization of the number of subsequences obtained via the deletion channel

2012/02/08 by Y. Liron, Liron, Y., Michael Langberg +1 · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.1202.1644

openalex publication_date 2012/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Motivated by the study of deletion channels, this work presents improved bounds on the number of subsequences obtained from a binary sting X of length n under t deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string X; where a run is a maximal sequence of the same character. Our improved bounds are obtained by a structural analysis of the family of r-run strings X, an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every r, we present r-run strings with the minimum (respectively maximum) number of subsequences under any t deletions; and perform an exact analysis of the number of subsequences of these extremal strings.

Cited by

• Sequence Reconstruction over the Deletion Channel
• An Improvement to Levenshtein's Upper Bound on the Cardinality of\n Deletion Correcting Codes
• On the Fixed-Length-Burst Levenshtein Ball with Unit Radius

Related

• From Clustering Supersequences to Entropy Minimizing Subsequences for Single and Double Deletions
• Average-case reconstruction for the deletion channel: subpolynomially many traces suffice
• Detecting Deletions and Insertions in Concatenated Strings with Optimal Redundancy
• Codes Correcting a Burst of Deletions or Insertions
• Beyond trace reconstruction: Population recovery from the deletion channel