text: A binary string transmitted via a memoryless i.i.d. deletion channel is received as a subsequence of the original input. From this, one obtains a posterior distribution on the channel input, corresponding to a set of candidate supersequences weighted by the number of times the received subsequence can be embedded in them. In a previous work it is conjectured on the basis of experimental data that the entropy of the posterior is minimized and maximized by the constant and the alternating strings, respectively. In this work, we present an algorithm for counting the number of subsequence embeddings using a run-length encoding of strings. We then describe two different ways of clustering the space of supersequences and prove that their cardinality depends only on the length of the received subsequence and its Hamming weight, but not its exact form. Then, we consider supersequences that contain a single embedding of a fixed subsequence, referred to as singletons, and provide a closed form expression for enumerating them using the same run-length encoding. We prove an analogous result for the minimization and maximization of the number of singletons, by the alternating and the uniform strings, respectively. Next, we prove the original minimal entropy conjecture for the special cases of single and double deletions using similar clustering techniques and the same run-length encoding, which allow us to characterize the distribution of the number of subsequence embeddings in the space of compatible supersequences to demonstrate the effect of an entropy decreasing operation.
  @cite_18: Although the insertion deletion problem has been studied for more than fifty years, many results still remain elusive. The goal of this work is to present three novel theorems with a combinatorial flavor that shed further light on the structure and nature of insertions deletions. In particular, we give an exact result for the maximum number of common supersequences between two sequences, extending older work by Levenshtein. We then generalize this result for sequences that have different lengths. Finally, we compute the exact neighborhood size for the binary circular (alternating) string C n = 0101 … 01. In addition to furthering our understanding of the insertion deletion channel, these theorems can be used as building blocks in other applications. One such application is developing improved lower bounds on the sizes of insertion deletion-correcting codes.
  @cite_14: We take a graph theoretic view of deletion correcting codes. The problem of finding an n-bit s-deletion correcting code is equivalent to finding an independent set in a particular graph. We discuss the relationship between codes and colorings and demonstrate that the VT codes are optimal in a coloring sense. We describe a method of partitioning the set of bit strings by Hamming weight and finding codes within each partition. In the single deletion case, we find an optimal coloring of the constant Hamming weight induced subgraphs. We show that the resulting code is asymptotically optimal. We also prove a lower bound on size of codes constructed using these partitions for any number of deletions.
  @cite_8: Suppose a binary string x = x1 . . . xn is being broadcast repeatedly over a faulty communication channel. Each time, the channel delivers a fixed number m of the digits (m < n) with the lost digits chosen uniformly at random and the order of the surviving digits preserved. How large does m have to be to reconstruct the message?
  @cite_1: By using a run-length representation of sequences, ways to determine suband supersequences are discussed. This is then used in determining the number of sub- and supersequences of a sequence after double insertions or deletions. It is also used in creating subsequence supersequence books that are searched to find new double insertion deletion correcting code books with higher cardinalities than those already known.
  @cite_2: Synchronization channels, which can remove codeword symbols or introduce extraneous symbols, pose additional difficulties when compared to the commonly-studied substitution channel. A traditional problem in this area is to count the number of sequences formed when deleting a fixed number of symbols from a sequence. This work contains our first effort towards solving a similar, yet previously unexplored, problem: deriving bounds on the number of sequences obtained by deleting and inserting a fixed number of symbols.
  @cite_16: A synchronization error is said to occur when either a bit which does not belong appears, or is detected in a channel between bits which were transmitted; or a bit which was transmitted is lost or not detected. A model for such a channel will be proposed, and a lower and upper bound on the redundancy necessary to correct a given error rate will be derived. We will consider the case of single synchronization error correction in detail, and stronger bounds will be derived for that case. We will consider multiple adjacent synchronization errors as a special case, and show that the bounds can be tightened in this case as well.
  @cite_10: Motivated by the study of deletion channels, this paper presents improved bounds on the number of subsequences obtained from a binary string @math of length @math under @math deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string @math ; where a run is a maximal substring of the same character. Our improved bounds are obtained by a structural analysis of the family of @math -run strings @math , an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every @math , we present @math -run strings with the minimum (respectively maximum) number of subsequences under any @math deletions; we perform an exact analysis of the number of subsequences of these extremal strings; and show that this number can be calculated in polynomial time.
  @cite_17: The binary deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Input bits are deleted independently with probability d, and when they are not deleted, they are not affected by the channel. Despite significant effort, little is known about the capacity of this channel and even less about optimal coding schemes. In this paper, we develop a new systematic approach to this problem, by demonstrating that capacity can be computed in a series expansion for small deletion probability. We compute three leading terms of this expansion, and find an input distribution that achieves capacity up to this order. This constitutes the first optimal random coding result for the deletion channel. The key idea employed is the following: We understand perfectly the deletion channel with deletion probability d=0. It has capacity 1 and the optimal input distribution is iid Bernoulli (1 2). It is natural to expect that the channel with small deletion probabilities has a capacity that varies smoothly with d, and that the optimal input distribution is obtained by smoothly perturbing the iid Bernoulli (1 2) process. Our results show that this is indeed the case.
summary: In coding theory, and more specifically in the context of insertion and deletions channels, similar long-standing problems have been studied extensively, and yet many problems still remain elusive. This includes designing optimal coding schemes and determining the capacity of deletion channels, both of which incorporate the same underlying combinatorial problem addressed in the present work. Considering a finite number of insertions and deletions for designing correcting codes for synchronization errors @cite_16 @cite_1 @cite_17 and reconstructing the original string from a fixed subsequence @cite_8 represent two specific and related research areas. More recent work on the characterization of the number of subsequences obtained via the deletion channel @cite_2 @cite_18 @cite_10 , e.g., in terms of the number of runs in a string, shows great overlap with our work. A graph-theoretic approach for deletion correcting codes, closely related to our clustering analysis, including an alternative proof for the Hamming weight clustering given in Theorem based on a different approach, is given in @cite_14 .