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

Michael H. Goldwasser, Ming-Yang Kao, Hsueh I. Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Citations (Scopus)

Abstract

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.

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings
EditorsRoderic Guigo, Dan Gusfield
PublisherSpringer Verlag
Pages157-171
Number of pages15
ISBN (Print)3540442111, 9783540442110
StatePublished - Jan 1 2002
Event2nd International Workshop on Algorithms in Bioinformatics, WABI 2002 - Rome, Italy
Duration: Sep 17 2002Sep 21 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2452
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Workshop on Algorithms in Bioinformatics, WABI 2002
CountryItaly
CityRome
Period9/17/029/21/02

Fingerprint

Bioinformatics
Fast Algorithm
Sequence Analysis
Subsequence
Consecutive
Optimization Problem
Integer
Arbitrary

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Goldwasser, M. H., Kao, M-Y., & Lu, H. I. (2002). Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics. In R. Guigo, & D. Gusfield (Eds.), Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings (pp. 157-171). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2452). Springer Verlag.
Goldwasser, Michael H. ; Kao, Ming-Yang ; Lu, Hsueh I. / Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics. Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings. editor / Roderic Guigo ; Dan Gusfield. Springer Verlag, 2002. pp. 157-171 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{6c58d9623da14e428eff17cf52e71a96,
title = "Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics",
abstract = "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.",
author = "Goldwasser, {Michael H.} and Ming-Yang Kao and Lu, {Hsueh I.}",
year = "2002",
month = "1",
day = "1",
language = "English (US)",
isbn = "3540442111",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "157--171",
editor = "Roderic Guigo and Dan Gusfield",
booktitle = "Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings",
address = "Germany",

}

Goldwasser, MH, Kao, M-Y & Lu, HI 2002, Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics. in R Guigo & D Gusfield (eds), Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2452, Springer Verlag, pp. 157-171, 2nd International Workshop on Algorithms in Bioinformatics, WABI 2002, Rome, Italy, 9/17/02.

Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics. / Goldwasser, Michael H.; Kao, Ming-Yang; Lu, Hsueh I.

Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings. ed. / Roderic Guigo; Dan Gusfield. Springer Verlag, 2002. p. 157-171 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2452).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

PY - 2002/1/1

Y1 - 2002/1/1

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

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

ER -

Goldwasser MH, Kao M-Y, Lu HI. Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics. In Guigo R, Gusfield D, editors, Algorithms in Bioinformatics - 2nd International Workshop,WABI 2002, Proceedings. Springer Verlag. 2002. p. 157-171. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).