請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38188
標題: Fast Algorithms for the Density Finding Problem
作者: D.T.Lee
T.C.Lin
H.I.Lu
關鍵字: Maximum-density segment problem · Density finding problem · Slope selection problem ·Convex hull · Computational geometry · GC content · DNA sequence ·Bioinformatics
出版社: Springer-Verlag New York, Inc. Secaucus, NJ, USA
摘要: 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 $d(i^{*},j^{*})=\sum_{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\{\lfloor\frac{u-\ell}{w_{\mathrm{min}}}\rfloor,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.
URI: http://hdl.handle.net/11455/38188
ISSN: 0178-4617
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。