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_26: Abstract Let S be a finite sequence of length r whose terms come from the finite alphabet a . The subsequence number of S ( i = 0… r ) is the number of distinct t -long subsequences of S . We prove (1) for r and a fixed, the S simultaneously attain their maximum possible values if and only if S is a repeated permutation of a (meaning no letters appears twice in S without all of the other letters of a intervening): (2) the numbers S … S …… S , are logarithmically concave: and (3) over any central interval S … S …… S …( iSr − i). S , is least (through perhaps not uniquely). In addition, we show that for the generalized binomial coefficients c ( i.j.n ) defined by (1+ x +…+ x m −1 ) 1 = Σ c ( i . j . n ) x 1 , the sequence c ( i − 1.1. n ), c ( i −2.2 n )… is strongly logarithmically concave, thus extending a result of S.M. Tanny and M. Zuker. Logarithmic concavity is treated in the context of triangular arrays of numbers.
  @cite_22: This note describes an information theory problem that arose from some analysis of quantum key distribution protocols. The problem seems very natural and is very easy to state but has not to our knowledge been addressed before in the information theory literature: suppose that we have a random bit string y of length n and we reveal k bits at random positions, preserving the order but without revealing the positions, how much information about y is revealed? We show that while the cardinality of the set of compatible y strings depends only on n and k, the amount of leakage does depend on the exact revealed x string. We observe that the maximal leakage, measured as decrease in the Shannon entropy of the space of possible bit strings, corresponds to the x string being all zeros or all ones and that the minimum leakage corresponds to the alternating x strings. We derive a formula for the maximum leakage minimal entropy in terms of n and k. We discuss the relevance of other measures of information, in particular min-entropy, in a cryptographic context. Finally, we describe a simulation tool to explore these results.
  @cite_9: Abstract In this paper we investigate the complexity of finding various kinds of common super- and subsequences with respect to one or two given sets of strings. We show that Longest Minimal Common Supersequence, Shortest Maximal Common Subsequence, and Shortest Maximal Common Non-Supersequence are MAX SNP-hard over a binary alphabet. Moreover, we show that Shortest Common Supersequence, Longest Common Subsequence, Longest Common Non-Supersequence, Shortest Common Non-Subsequence, and Longest Minimal Common Non-Supersequence are MAX SNP-hard over a binary alphabet if the number of zeros is fixed (by the instance). We show how these problems can be related to finding sequences consistent with respect to two given sets of strings. This leads to a unified approach for characterizing the complexity of such problems.
  @cite_6: The problems of finding shortest common supersequences (SCS) and longest common subsequences (LCS) are two well-known NP -hard problems that have applications in many areas including computational molecular biology, data compression, robot motion planning and scheduling, text editing, etc. A lot of fruitless effort has been spent in searching for good approximation algorithms for these problems. In this paper, we show that these problems are inherently hard to approximate in the worst case. In particular, we prove that (i) SCS does not have a polynomial time linear approximation algorithm, unless P = NP ; (ii) There exists a constant @math such that, if SCS has a polynomial time approximation algorithm with ratio @math , where @math is the number of input sequences, then NP is contained in DTIME @math ; (iii) There exists a constant @math such that, if LCS has a polynomial time approximation algorithm with performance ratio @math , then P = NP . The proofs utilize the recent results of [Proc. 23rd IEEE Symposium on Foundations of Computer Science, 1992, pp. 14-23] on the complexity of approximation problems. In the second part of the paper, we introduce a new method for analyzing the average-case performance of algorithms for sequences, based on Kolmogorov complexity. Despite the above nonapproximability results, we show that near optimal solutions for both SCS and LCS can be found on the average. More precisely, consider a fixed alphabet @math and suppose that the input sequences are generated randomly according to the uniform probability distribution and are of the same length @math . Moreover, assume that the number of input sequences is polynomial in @math . Then, there are simple greedy algorithms which approximate SCS and LCS with expected additive errors @math and @math for any @math , respectively. Incidentally, our analyses also provide tight upper and lower bounds on the expected LCS and SCS lengths for a set of random sequences, solving a generalization of another well-known open question on the expected LCS length for two random sequences [K. Alexander, The rate of convergence of the mean length of the longest common subsequence, 1992, manuscript],[V. Chvatal and D. Sankoff, J. Appl. Probab., 12 (1975), pp. 306-315], [D. Sankoff and J. Kruskall, eds., Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, MA, 1983].
  @cite_3: We investigate combinatorial enumeration problems related to subsequences of strings; in contrast to substrings, subsequences need not be contiguous. For a finite alphabet E, the following three problems are solved. (1) Number of distinct subsequences: Given a sequence s ∈ Σ n and a nonnegative integer k ≤ n, how many distinct subsequences of length k does s contain? A previous result by Chase states that this number is maximized by choosing s as a repeated permutation of the alphabet. This has applications in DNA microarray production. (2) Number of ρ-restricted p-generated sequences: Given s ∈ Σ n and integers k ≥ 1 and p > 1, how many distinct sequences in Σ k contain no single nucleotide repeat longer than p and can be written as s[ r1 1 ... s rn n with 0 1, determine the number of sequences in E whose longest strictly increasing subsequence has length k, where 0 < k < K. This has applications to significance computations for chaining algorithms.
  @cite_24: A natural problem in extremal combinatorics is to maximize the number of distinct subsequences for any length- @math string over a finite alphabet @math ; this value grows exponentially, but slower than @math . We use the probabilistic method to determine the maximizing string, which is a cyclically repeating string. The number of distinct subsequences is exactly enumerated by a generating function, from which we also derive asymptotic estimates. For the alphabet @math , @math has the maximum number of distinct subsequences, namely @math . We also consider the same problem with sub strings in lieu of sub sequences . Here, we show that an appropriately truncated de Bruijn word attains the maximum. For both problems, we compare the performance of random strings with that of the optimal ones.
  @cite_0: Super- substring problems and super- subsequence problems are well-known problems in stringology that have applications in a variety of areas, such as manufacturing systems design and molecular biology. Here we investigate the complexity of a new type of such problem that forms a combination of a super- substring and a super- subsequence problem. Moreover we introduce different types of minimal superstring and maximal substring problems. In particular, we consider the following problems: given a set L of strings and a string S, (i) find a minimal superstring (or maximal substring) of L that is also a supersequence (or a subsequence) of S, (ii) find a minimal supersequence (or maximal subsequence) of L that is also a superstring (or a substring) of S. In addition some non-super- non-substring and non-super- nonsubsequence variants are studied. We obtain several NP-hardness or even MAX SNP-hardness results and also identify types of "weak minimal" superstrings and "weak maximal" substrings for which (i) is polynomial-time solvable.
  @cite_19: A subsequence is obtained from a string by deleting any number of characters; thus in contrast to a substring, a subsequence is not necessarily a contiguous part of the string. Counting subsequences under various constraints has become relevant to biological sequence analysis, to machine learning, to coding theory, to the analysis of categorical time series in the social sciences, and to the theory of word complexity. We present theorems that lead to efficient dynamic programming algorithms to count (1) distinct subsequences in a string, (2) distinct common subsequences of two strings, (3) matching joint embeddings in two strings, (4) distinct subsequences with a given minimum span, and (5) sequences generated by a string allowing characters to come in runs of a length that is bounded from above.
  @cite_5: The problem considered is that of determining the number of subsequences obtainable by deleting t symbols from a string of length n over an alphabet of size s. Recurrences are proven and solved for the maximum and average case values, and bounds on these values are exhibited.
  @cite_15: The problem considered is that of determining the number of subsequences obtain- able by deleting symbols from a string of length over an alphabet of size . Recurrences are proven and solved for the maximum and average case values, and bounds on these values are exhibited.
summary: Studies involving subsequences and supersequences encompass a wide variety of problems that arise in various contexts such as formal languages, coding theory, computer intrusion detection and DNA sequencing to name a few. Despite their prevalence in such a wide range of disciplines, they remain largely unexplored and still present a considerable wealth of unanswered questions. In the realm of stringology and formal languages, the problem of determining the number of distinct subsequences obtainable from a fixed number of deletions, and closely related problems, have been studied extensively in @cite_26 @cite_24 @cite_5 @cite_15 . Perhaps it is worth noting that the same entropy minimizing and maximizing strings conjectured in @cite_22 and characterized in the present work, have been shown to lead to the minimum and maximum number of distinct subsequences, respectively. The problems of finding shortest common supersequences (SCS) and longest common subsequences (LCS) represent two well-known NP-hard problems @cite_6 @cite_9 @cite_0 that involve subproblems similar to our work. Finally, devising efficient algorithms for subsequence combinatorics based on dynamic programming for counting the number of occurrences of a subsequence in DNA sequencing is yet another important and closely related line of research @cite_3 @cite_19 .