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 Scopus citations

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
DOIs
StatePublished - 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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics'. Together they form a unique fingerprint.

Cite this