An Optimal Algorithm for the Maximum-Density Segment Problem
Authors:
- Hsueh-I LuHLHsueh-I Lu
Preprint
Abstract
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.
Keywords
All Related Versions
- Version 1, 2003-11-17, ArXiv
- Published version: SIAM Journal on Computing, 34 (2), 373.
This publication has 29 references indexed in Scilit:
- Linear-time algorithm for finding a maximum-density segment of a sequenceInformation Processing Letters, 2003
- Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysisJournal of Computer and System Sciences, 2002
- EMBOSS: The European Molecular Biology Open Software SuiteTrends in Genetics, 2000
- Optimal slope selection via cuttingsComputational Geometry, 1998
- Statistical analysis of vertebrate sequences reveals that long genes are scarce in GC-rich isochoresJournal of Molecular Evolution, 1995
- Optimal slope selection via expandersInformation Processing Letters, 1993
- Randomized optimal algorithm for slope selectionInformation Processing Letters, 1991
- Correlation between molecular clock ticking, codon usage, fidelity of DNA repair, chromosome banding and chromatin compactness in germline cellsFEBS Letters, 1987
- An approach to the organization of eukaryotic genomes at a macromolecular levelJournal of Molecular Biology, 1976
- A denaturation map of the λ phage DNA molecule determined by electron microscopyJournal of Molecular Biology, 1966