{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T14:31:52Z","timestamp":1787236312555,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540369257","type":"print"},{"value":"9783540369264","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11809678_28","type":"book-chapter","created":{"date-parts":[[2006,8,15]],"date-time":"2006-08-15T09:41:33Z","timestamp":1155634893000},"page":"255-264","source":"Crossref","is-referenced-by-count":4,"title":["Computing Maximum-Scoring Segments in Almost Linear Time"],"prefix":"10.1007","author":[{"given":"Fredrik","family":"Bengtsson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"jingsen","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"4","key":"28_CR1","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1109\/TCBB.2004.43","volume":"1","author":"M. Cs\u0171r\u00f6s","year":"2004","unstructured":"Cs\u0171r\u00f6s, M.: Maximum-scoring segment sets. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a01(4), 139\u2013150 (2004)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"28_CR2","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1093\/bioinformatics\/btg023","volume":"19","author":"P. Fariselli","year":"2003","unstructured":"Fariselli, P., Finelli, M., Marchignoli, D., Martelli, P., Rossi, I., Casadio, R.: Maxsubseq: An algorithm for segment-length optimization. The case study of the transmembrane spanning segments. Bioinformatics\u00a019, 500\u2013505 (2003)","journal-title":"Bioinformatics"},{"key":"28_CR3","first-page":"219","volume":"10","author":"X. Huang","year":"1994","unstructured":"Huang, X.: An algorithm for identifying regions of a DNA sequence that satisfy a content requirement. Computer Applications in the Biosciences\u00a010, 219\u2013225 (1994)","journal-title":"Computer Applications in the Biosciences"},{"issue":"1","key":"28_CR4","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF02458835","volume":"51","author":"I.E. Auger","year":"1989","unstructured":"Auger, I.E., Lawrence, C.E.: Algorithms for the optimal identification of segment neighbourhoods. Bulletin of Mathematical Biology\u00a051(1), 39\u201354 (1989)","journal-title":"Bulletin of Mathematical Biology"},{"issue":"1","key":"28_CR5","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF02312495","volume":"9","author":"T.R. Bement","year":"1977","unstructured":"Bement, T.R., Waterman, M.S.: Locating maximum variance segments in sequential data. Mathematical Geology\u00a09(1), 55\u201361 (1977)","journal-title":"Mathematical Geology"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1145\/358234.381162","volume":"27","author":"J.L. Bentley","year":"1984","unstructured":"Bentley, J.L.: Programming pearls: Algorithm design techniques. Communications of the ACM\u00a027, 865\u2013871 (1984)","journal-title":"Communications of the ACM"},{"key":"28_CR7","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1145\/1968.381154","volume":"27","author":"J.L. Bentley","year":"1984","unstructured":"Bentley, J.L.: Programming pearls: Perspective on performance. Communications of the ACM\u00a027, 1087\u20131092 (1984)","journal-title":"Communications of the ACM"},{"key":"28_CR8","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0167-6423(87)90034-7","volume":"8","author":"D. Smith","year":"1987","unstructured":"Smith, D.: Applications of a strategy for designing divide-and-conquer algorithms. Science of Computer Programming\u00a08, 213\u2013229 (1987)","journal-title":"Science of Computer Programming"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Bae, S.E., Takaoka, T.: Algorithms for the problem of k maximum sums and a VLSI algorithm for the k maximum subarrays problem. In: Proceedings of the 7th International Symposium on Parallel Architectures, Algorithms and Networks, pp. 247\u2013253 (2004)","DOI":"10.1109\/ISPAN.2004.1300488"},{"key":"28_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/11533719_63","volume-title":"Computing and Combinatorics","author":"S.E. Bae","year":"2005","unstructured":"Bae, S.E., Takaoka, T.: Improved algorithms for the k-maximum subarray problem for small k. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 621\u2013631. Springer, Heidelberg (2005)"},{"key":"28_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/978-3-540-30551-4_14","volume-title":"Algorithms and Computation","author":"F. Bengtsson","year":"2004","unstructured":"Bengtsson, F., Chen, J.: Efficient algorithms for k maximum sums. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 137\u2013148. Springer, Heidelberg (2004); Revised version to appear in Algorithmica."},{"key":"28_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/11602613_52","volume-title":"Algorithms and Computation","author":"T.C. Lin","year":"2005","unstructured":"Lin, T.C., Lee, D.T.: Randomized algorithm for the sum selection problem. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 515\u2013523. Springer, Heidelberg (2005)"},{"key":"28_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1007\/11602613_72","volume-title":"Algorithms and Computation","author":"A. Bergkvist","year":"2005","unstructured":"Bergkvist, A., Damaschke, P.: Fast algorithms for finding disjoint subsequences with extremal densities. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 714\u2013723. Springer, Heidelberg (2005)"},{"key":"28_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/978-3-540-39658-1_15","volume-title":"Algorithms - ESA 2003","author":"K.M. Chung","year":"2003","unstructured":"Chung, K.M., Lu, H.I.: An optimal algorithm for the maximum-density segment problem. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 136\u2013147. Springer, Heidelberg (2003)"},{"key":"28_CR15","unstructured":"Ruzzo, W.L., Tompa, M.: A linear time algorithm for finding all maximal scoring subsequences. In: Proceedings of the 7th Annual International Conference on Intelligent Systems for Molecular Biology, pp. 234\u2013241 (1999)"},{"key":"28_CR16","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. The MIT Press, Cambridge (1990)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11809678_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T08:07:10Z","timestamp":1736496430000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11809678_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540369257","9783540369264"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11809678_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}