Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms

Rahmann S. Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms. In: Lewenstein M, Valiente G, eds. Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings. Lecture Notes in Computer Science. Vol 4009. Berlin: Springer; 2006: 153-164.We investigate combinatorial enumeration problems related to subsequences of strings; in contrast to substrings, subsequences need not be contiguous. For a finite alphabet Sigma, the following three problems are solved. (1) Number of distinct subsequences: Given a sequence s is an element of Sigma(n) and a nonnegative integer k = 1 and rho >= 1, how many distinct sequences in Sigma(k) contain no single nucleotide repeat longer than rho and can be written as s(1)(r1)... s(n)(rn) with 0 = 1, determine the number of sequences in Sigma(n) whose longest strictly increasing subsequence has length k, where 0 <= k <= K. This has applications to significance computations for chaining algorithms