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

Rahmann S (2006)
In: Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings. Lewenstein M, Valiente G (Eds); Lecture Notes in Computer Science, 4009. Berlin: Springer: 153-164.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Konferenzbeitrag | Veröffentlicht | Englisch
Autor
Herausgeber
;
Abstract / Bemerkung
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 <= 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 rho-restricted rho-generated sequences: Given s is an element of Sigma(n) and integers 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 <= r(i) <= rho for all i? For rho = infinity, the question becomes how many length-k sequences match the regular expression s(1)*s(2)*... s(n)*. These considerations allow a detailed analysis of a new DNA sequencing technology ("454 sequencing"). (3) Exact length distribution of the longest increasing subsequence: Given Sigma = {1, ..., K} and an integer n >= 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.
Erscheinungsjahr
Titel des Konferenzbandes
Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings
Band
4009
Seite(n)
153-164
Konferenz
CPM 2006
Konferenzort
Barcelona, Spain
Konferenzdatum
2006-07-05 – 2006-07-07
PUB-ID

Zitieren

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.
Rahmann, S. (2006). Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms. In M. Lewenstein & G. Valiente (Eds.), Lecture Notes in Computer Science: Vol. 4009. Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings (pp. 153-164). Berlin: Springer. doi:10.1007/11780441_15
Rahmann, S. (2006). “Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms” in Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings, Lewenstein, M., and Valiente, G. eds. Lecture Notes in Computer Science, vol. 4009, (Berlin: Springer), 153-164.
Rahmann, S., 2006. Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms. In M. Lewenstein & G. Valiente, eds. Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings. Lecture Notes in Computer Science. no.4009 Berlin: Springer, pp. 153-164.
S. Rahmann, “Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms”, Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings, M. Lewenstein and G. Valiente, eds., Lecture Notes in Computer Science, vol. 4009, Berlin: Springer, 2006, pp.153-164.
Rahmann, S.: Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms. In: Lewenstein, M. and Valiente, G. (eds.) Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings. Lecture Notes in Computer Science. 4009, p. 153-164. Springer, Berlin (2006).
Rahmann, Sven. “Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms”. Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings. Ed. Moshe Lewenstein and Gabriel Valiente. Berlin: Springer, 2006.Vol. 4009. Lecture Notes in Computer Science. 153-164.