An Optimal Algorithm for the Maximum-Density Segment Problem
Authors:
- Kai-Min ChungKCKai-Min Chung
- Hsueh-I LuHLHsueh-I Lu
- 1 January 2005
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 34 (2) , 373-387
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 segmentS (i,j) of S be the consecutive subsequence of S between indices i and j. The density of S(i,j) is d(i,j) = (a i + a i + 1 + \cdots + a j )/(w i + w i + 1 + \cdots + w j )$. The 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 + \cdots + w j \leq w max . The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu [Proceedings of the Second International Workshop on Algorithms in Bioinformatics, R. Guigó and D. Gusfield, eds., Lecture Notes in Comput. Sci. 2452, Springer-Verlag, New York, 2002, pp. 157--171], 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 right-skew decomposition, introduced by Lin, Jiang, and Chao [J. Comput. System Sci., 65 (2002), pp. 570--586]. 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
This publication has 42 references indexed in Scilit:
- Isochores and the evolutionary genomics of vertebratesGene, 2000
- Isochores result from mutation not selectionNature, 1999
- 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
- Genetic Recombination: Patterns in the genomeCurrent Biology, 1994
- Recombination and mammalian genome evolutionProceedings Of The Royal Society B-Biological Sciences, 1993
- Evidence that both G + C rich and G + C poor isochores are replicated early and late in the cell cycleNucleic Acids Research, 1992
- An Optimal-Time Algorithm for Slope SelectionSIAM Journal on Computing, 1989
- Correlation between molecular clock ticking, codon usage, fidelity of DNA repair, chromosome banding and chromatin compactness in germline cellsFEBS Letters, 1987
- Compositional constraints and genome evolutionJournal of Molecular Evolution, 1986