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

We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A of pairs (a(i), w(i)) for i = 1,..., n and w(i) > 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) =Sigma(iless than or equal tokless than or equal tok)w(k), and the densith is (Sigma(iless than or equal tokless than or equal toj)a(k))/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(n log L)-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. (C) 2004 Elsevier Inc. All rights reserved.