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