Fast Algorithms for the Density Finding Problem Export

@article{citeulike:4119529, abstract = {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≤i≤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 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 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.}, author = {Lee, D. and Lin, Tien-Ching and Lu, Hsueh-I}, citeulike-article-id = {4119529}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/s00453-007-9023-8}, citeulike-linkout-1 = {http://www.springerlink.com/content/h2v4r7515j8k507g}, day = {1}, doi = {10.1007/s00453-007-9023-8}, journal = {Algorithmica}, keywords = {algorithms, biology, geometries}, month = {March}, number = {3}, pages = {298--313}, posted-at = {2009-03-02 14:53:28}, priority = {2}, title = {Fast Algorithms for the Density Finding Problem}, url = {http://dx.doi.org/10.1007/s00453-007-9023-8}, volume = {53}, year = {2009} }

TY - JOUR ID - citeulike:4119529 L3 - citeulike-article-id:4119529 N2 - 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≤i≤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 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 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. IS - 3 JF - Algorithmica EP - 313 TI - Fast Algorithms for the Density Finding Problem VL - 53 SP - 298 KW - algorithms KW - biology KW - geometries AU - Lee, D AU - Lin, Tien-Ching AU - Lu, Hsueh-I PY - 2009/03/01/ UR - http://dx.doi.org/10.1007/s00453-007-9023-8 ER -