TY - GEN

T1 - Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics

AU - Goldwasser, Michael H.

AU - Kao, Ming-Yang

AU - Lu, Hsueh I.

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2002

Y1 - 2002

N2 - We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A = (equation found) of real numbers, a segment S is a consecutive subsequence (equation found). The width of S is j − i + 1, while the density is (equation found). The maximum-density segment problem takes A and two integers L and U as input and asks for a segment of A with the largest possible density among those of width at least L and at most U. If U = n (or equivalently, U = 2L − 1), we can solve the problem in O(n) time, improving upon the O(n log L)-time algorithm by Lin, Jiang and Chao for a general sequence A. Furthermore, if U and L are arbitrary, we solve the problem in O(n + n log(U − L + 1)) time. There has been no nontrivial result for this case previously. Both results also hold for a weighted variant of the maximum-density segment problem.

AB - We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A = (equation found) of real numbers, a segment S is a consecutive subsequence (equation found). The width of S is j − i + 1, while the density is (equation found). The maximum-density segment problem takes A and two integers L and U as input and asks for a segment of A with the largest possible density among those of width at least L and at most U. If U = n (or equivalently, U = 2L − 1), we can solve the problem in O(n) time, improving upon the O(n log L)-time algorithm by Lin, Jiang and Chao for a general sequence A. Furthermore, if U and L are arbitrary, we solve the problem in O(n + n log(U − L + 1)) time. There has been no nontrivial result for this case previously. Both results also hold for a weighted variant of the maximum-density segment problem.

UR - http://www.scopus.com/inward/record.url?scp=84957034248&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957034248&partnerID=8YFLogxK

U2 - 10.1007/3-540-45784-4_12

DO - 10.1007/3-540-45784-4_12

M3 - Conference contribution

AN - SCOPUS:84957034248

SN - 3540442111

SN - 9783540442110

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 157

EP - 171

BT - Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings

A2 - Guigo, Roderic

A2 - Gusfield, Dan

PB - Springer Verlag

T2 - 2nd International Workshop on Algorithms in Bioinformatics, WABI 2002

Y2 - 17 September 2002 through 21 September 2002

ER -