---
_id: '1598249'
abstract:
- lang: eng
text: '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.'
author:
- first_name: Sven
full_name: Rahmann, Sven
last_name: Rahmann
citation:
ama: '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.'
angewandte-chemie: 'S. Rahmann, in *Combinatorial Pattern Matching. 17th Annual
Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings* (Eds.:
M. Lewenstein, G. Valiente), Springer, Berlin, **2006**, p. 153-164.'
apa: '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'
apa_indent: '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

'
bio1: '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, Valiente G (Eds); Lecture Notes in Computer Science, 4009. Berlin:
Springer: 153-164.'
chicago: 'Rahmann,
Sven. 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*,
ed. Moshe Lewenstein and Gabriel Valiente, 4009:153-164. Lecture Notes in Computer
Science. Berlin: Springer.

'
default: '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.'
dgps: 'Rahmann,
S. (2006). Subsequence combinatorics and applications to microarray production,
DNA sequencing and chaining algorithms (Lecture Notes in Computer Science). In
M. Lewenstein & G. Valiente (Hrsg.), *Combinatorial Pattern Matching.
17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings*
(S. 153-164). Gehalten auf der CPM 2006, Berlin: Springer. doi:10.1007/11780441_15.

'
frontiers: '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.'
harvard1: '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.'
ieee: ' 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.'
lncs: ' 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).'
mla: '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.'
wels: 'Rahmann, S. (2006): Subsequence combinatorics and applications to microarray
production, DNA sequencing and chaining algorithms. In: Moshe Lewenstein; Gabriel Valiente
(Hrsg.): Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona,
Spain, July 5-7, 2006. Proceedings. Berlin: Springer. (Lecture Notes in Computer
Science, 4009). S. 153-164.'
conference:
end_date: 2006-07-07
location: Barcelona, Spain
name: ' CPM 2006'
start_date: 2006-07-05
date_created: 2010-04-28T12:19:18Z
date_updated: 2019-03-13T14:57:18Z
department:
- _id: '10036'
doi: 10.1007/11780441_15
editor:
- first_name: Moshe
full_name: Lewenstein, Moshe
last_name: Lewenstein
- first_name: Gabriel
full_name: ' Valiente, Gabriel'
last_name: ' Valiente'
external_id:
isi:
- '000239421700015'
intvolume: ' 4009'
isi: 1
language:
- iso: eng
page: 153-164
place: Berlin
publication: Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona,
Spain, July 5-7, 2006. Proceedings
publication_identifier:
isbn:
- 978-3-540-35455-0
publication_status: published
publisher: Springer
quality_controlled: '1'
series_title: Lecture Notes in Computer Science
status: public
title: Subsequence combinatorics and applications to microarray production, DNA sequencing
and chaining algorithms
type: conference
user_id: '67994'
volume: 4009
year: '2006'
...