Fast algorithms for the density finding problem
Journal
Algorithmica (New York)
Journal Volume
53
Journal Issue
3
Pages
298-313
Date Issued
2009
Author(s)
Lee, D.T.
Lin, T.-C.
HSUEH-I LU
Abstract
We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a 1,w 1),(a 2,w 2), (a n, w n ) of n ordered pairs (a i, w i ) of numbers a i and width w i >0 for each 1 ≤ n, two nonnegative numbers δ, u with ≥ u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i *,j *) over all O(n 2) consecutive subsequences A(i,j) with width constraint satisfying ≥ w(i,j)=≤ r=i j w r ≤u such that its density d(i *},j *)=∑r=i *j *a-r/w(i *},j *) is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog∈n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog∈n) time and O(nlog∈n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog∈ 2 m) time and O(n+mlog∈m) space, where m=min[⌊ u-ℓ/w min⌋,n and w min=min∈ r=1 n w r. As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem. © 2007 Springer Science+Business Media, LLC.
Type
journal article