Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

Abstract

We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A of pairs (ai,wi) for i=1,...,n and wi>0, a segment A(i,j) is a consecutive subsequence of A starting with index i and ending with index j. The width of A(i,j) is w(i,j)=∑i≤k≤jwk, and the density is (∑i≤k≤jak)/w(i,j). The maximum-density segment problem takes A and two values 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. When U is unbounded, we provide a relatively simple, O(n)-time algorithm, improving upon the O(nlogL)-time algorithm by Lin, Jiang and Chao. We then extend this result, providing an O(n)-time algorithm for the case when both L and U are specified.

Original languageEnglish (US)
Pages (from-to)128-144
Number of pages17
JournalJournal of Computer and System Sciences
Volume70
Issue number2
DOIs
StatePublished - Mar 2005

Keywords

  • Bioinformatics
  • Density
  • Sequences

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications'. Together they form a unique fingerprint.

Cite this