[{"dini_type":"doc-type:conferenceObject","abstract":[{"lang":"eng"}],"publication_status":"published","intvolume":" 4009","status":"public","dc":{"publisher":["Springer"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text"],"identifier":["https://pub.uni-bielefeld.de/record/1598249"],"description":["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."],"language":["eng"],"creator":["Rahmann, Sven","Lewenstein, Moshe"," Valiente, Gabriel"],"rights":["info:eu-repo/semantics/closedAccess"],"title":["Subsequence combinatorics and applications to microarray production, DNA sequencing and chaining algorithms"],"source":["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."],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1007/11780441_15","info:eu-repo/semantics/altIdentifier/isbn/978-3-540-35455-0","info:eu-repo/semantics/altIdentifier/wos/000239421700015"],"date":["2006"]},"place":"Berlin","creator":{"id":"67994","login":"riedel"},"uri_base":"https://pub.uni-bielefeld.de","user_id":"67994","date_created":"2010-04-28T12:19:18Z","message":"NEWISI20100428 NEW ISI record:\r\nDocument type: Proceedings Paper\r\nDepartments: Univ Bielefeld, Fac Technol, Algorithms & Stat Syst Biol Grp, D-33594 Bielefeld, Germany.\r\nISI Id: ISI:000239421700015 / Deleted rec-id, Dept., div. bibliographische Daten erg. (Rd, 13.3.19)","series_title":"Lecture Notes in Computer Science","type":"conference","isi":1,"_version":13,"_id":"1598249","date_updated":"2019-03-13T14:57:18Z","page":"153-164","external_id":{"isi":[]},"author":[{"last_name":"Rahmann","first_name":"Sven"}],"language":[{}],"editor":[{"last_name":"Lewenstein","first_name":"Moshe"},{"first_name":"Gabriel","last_name":" Valiente"}],"quality_controlled":"1","conference":{"location":"Barcelona, Spain","name":" CPM 2006","start_date":"2006-07-05","end_date":"2006-07-07"},"citation":{"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).","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.","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.","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","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.","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.

","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.","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.","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

","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.","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.

","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."},"volume":4009,"publication_identifier":{"isbn":[]},"department":[{"_id":"10036","tree":[{"_id":"10036"}]}],"publication":"Combinatorial Pattern Matching. 17th Annual Symposium, CPM 2006, Barcelona, Spain, July 5-7, 2006. Proceedings"}]