Computer Science – Data Structures and Algorithms
Scientific paper
2003-11-17
SIAM Journal on Computing, 34(2):373-387, 2004
Computer Science
Data Structures and Algorithms
15 pages, 12 figures, an early version of this paper was presented at 11th Annual European Symposium on Algorithms (ESA 2003),
Scientific paper
10.1137/S0097539704440430
We address a fundamental problem arising from analysis of biomolecular sequences. The input consists of two numbers $w_{\min}$ and $w_{\max}$ and a sequence $S$ of $n$ number pairs $(a_i,w_i)$ with $w_i>0$. Let {\em segment} $S(i,j)$ of $S$ be the consecutive subsequence of $S$ between indices $i$ and $j$. The {\em density} of $S(i,j)$ is $d(i,j)=(a_i+a_{i+1}+...+a_j)/(w_i+w_{i+1}+...+w_j)$. The {\em maximum-density segment problem} is to find a maximum-density segment over all segments $S(i,j)$ with $w_{\min}\leq w_i+w_{i+1}+...+w_j \leq w_{\max}$. The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu, runs in $O(n\log(w_{\max}-w_{\min}+1))$ time. In the present paper, we solve the problem in O(n) time. Our approach bypasses the complicated {\em right-skew decomposition}, introduced by Lin, Jiang, and Chao. As a result, our algorithm has the capability to process the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences. Moreover, for a type of input sequences $S$ representable in $O(m)$ space, we show how to exploit the sparsity of $S$ and solve the maximum-density segment problem for $S$ in $O(m)$ time.
Chung Kai-Min
Lu Hsueh-I
No associations
LandOfFree
An Optimal Algorithm for the Maximum-Density Segment Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Optimal Algorithm for the Maximum-Density Segment Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Optimal Algorithm for the Maximum-Density Segment Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-605277