{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:16:58Z","timestamp":1792156618350,"version":"4.4.0"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>\n                    We address a fundamental problem arising from analysis of biomolecular sequences. The input consists of two numbers w\n                    <jats:sub>min<\/jats:sub>\n                    and w\n                    <jats:sub>max<\/jats:sub>\n                    and a sequence S of n number pairs (a\n                    <jats:sub>i<\/jats:sub>\n                    ,w\n                    <jats:sub>i<\/jats:sub>\n                    ) with w\n                    <jats:sub>i<\/jats:sub>\n                    &gt; 0. Let segmentS (i,j) of S be the consecutive subsequence of S between indices i and j. The density of S(i,j) is d(i,j) = (a\n                    <jats:sub>i<\/jats:sub>\n                    + a\n                    <jats:sub>i<\/jats:sub>\n                    + 1 + \\cdots + a\n                    <jats:sub>j<\/jats:sub>\n                    )\/(w\n                    <jats:sub>i<\/jats:sub>\n                    + w\n                    <jats:sub>i<\/jats:sub>\n                    + 1 + \\cdots + w\n                    <jats:sub>j<\/jats:sub>\n                    )$. The maximum-density segment problem is to find a maximum-density segment over all segments S(i,j) with w\n                    <jats:sub>min<\/jats:sub>\n                    \\leq w\n                    <jats:sub>i<\/jats:sub>\n                    + w\n                    <jats:sub>i<\/jats:sub>\n                    + 1 + \\cdots + w\n                    <jats:sub>j<\/jats:sub>\n                    \\leq w\n                    <jats:sub>max<\/jats:sub>\n                    . The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu [Proceedings of the Second International Workshop on Algorithms in Bioinformatics, R. Guig\u00f3 and D. Gusfield, eds., Lecture Notes in Comput. Sci. 2452, Springer-Verlag, New York, 2002, pp. 157--171], runs in O(n log(w\n                    <jats:sub>max<\/jats:sub>\n                    - w\n                    <jats:sub>min<\/jats:sub>\n                    +1)) time. In the present paper, we solve the problem in O(n) time. Our approach bypasses the complicated right-skew decomposition, introduced by Lin, Jiang, and Chao [J. Comput. System Sci., 65 (2002), pp. 570--586]. As a result, our algorithm has the capability to process the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences. Moreover, for a type of input sequences S representable in O(m) space, we show how to exploit the sparsity of S and solve the maximum-density segment problem for S in O(m) time.\n                  <\/jats:p>","DOI":"10.1137\/s0097539704440430","type":"journal-article","created":{"date-parts":[[2004,12,9]],"date-time":"2004-12-09T21:00:32Z","timestamp":1102626032000},"page":"373-387","source":"Crossref","is-referenced-by-count":42,"title":["An Optimal Algorithm for the Maximum-Density Segment Problem"],"prefix":"10.1137","volume":"34","author":[{"given":"Kai-min","family":"Chung","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hsueh-I","family":"Lu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":"N. N. Alexandrov and V. V. Solovyev,\n                      Statistical significance of ungapped sequence alignments\n                      , in Proceedings of the Pacific Symposium on Biocomputing, Maui, HI, 1998, World Scientific, River Edge, NJ, Vol. 3, pp. 461\u2013470."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-1119(99)00485-0"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02099946"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00025-4"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0960-9822(94)00045-X"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0218055"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF00163235"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/20.7.1497"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1098\/rspb.1993.0071"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0014-5793(87)80660-9"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1038\/21804"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.molbev.a003886"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. H. Goldwasser, M.\u2010Y. Kao, and H.\u2010I. Lu,\n                      Fast algorithms for finding maximum\u2010density segments of a sequence with applications to bioinformatics\n                      , in Proceedings of the Second International Workshop on Algorithms in Bioinformatics (Rome, Italy, 2002), R. Guig\u00f3 and D. Gusfield, eds., Lecture Notes in Comput. Sci. 2452, Springer\u2010Verlag, New York, 2002, pp. 157\u2013171.","DOI":"10.1007\/3-540-45784-4_12"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.08.001"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053907"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/26.6.1548"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/25.19.3957"},{"key":"R18","first-page":"17","volume":"51","author":"Holmquist G. P.","year":"1992","journal-title":"Am. J. Hum. Genet.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9297","issn-type":"print"},{"key":"R19","first-page":"219","volume":"10","author":"Huang X.","year":"1994","journal-title":"Comput. Appl. Biosci."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/24.21.4249"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(66)80037-2"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1038\/79189"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1093\/emboj\/16.14.4456"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90234-Z"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00225-4"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/19.1.151"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00010-7"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(76)80105-2"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1074\/jbc.272.47.29842"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90177-J"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1177\/002215540104901112"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1101\/gr.153400"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.suppl_1.S199"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9525(00)02024-2"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1128\/MCB.13.6.3588"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/S0092-8240(84)80055-5"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1098\/rstb.1995.0108"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.80.7.1816"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/27.19.3899"},{"key":"R40","first-page":"1816","volume":"80","author":"Sueoka N.","year":"1988","journal-title":"Proc. Natl. Acad. Sci. USA","ISSN":"https:\/\/id.crossref.org\/issn\/0027-8424","issn-type":"print"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1074\/jbc.M110006200"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1038\/337283a0"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/27.15.e9"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1016\/0378-1119(96)00393-9"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539704440430","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:19Z","timestamp":1787336299000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539704440430"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539704440430"],"URL":"https:\/\/doi.org\/10.1137\/s0097539704440430","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}