On the range maximum-sum segment query problem
Resource
Discrete Applied Mathematics 155 (16): 2043-2052
Journal
Discrete Applied Mathematics
Journal Volume
155
Journal Issue
16
Pages
2043-2052
Date Issued
2007
Author(s)
Abstract
The range minimum query problem, RMQ for short, is to preprocess a sequence of real numbers A [1 ... n] for subsequent queries of the form: "Given indices i, j, what is the index of the minimum value of A [i ... j]?" This problem has been shown to be linearly equivalent to the LCA problem in which a tree is preprocessed for answering the lowest common ancestor of two nodes. It has also been shown that both the RMQ and LCA problems can be solved in linear preprocessing time and constant query time under the unit-cost RAM model. This paper studies a new query problem arising from the analysis of biological sequences. Specifically, we wish to answer queries of the form: "Given indices i and j, what is the maximum-sum segment of A [i ... j]?" We establish the linear equivalence relation between RMQ and this new problem. As a consequence, we can solve the new query problem in linear preprocessing time and constant query time under the unit-cost RAM model. We then present alternative linear-time solutions for two other biological sequence analysis problems to demonstrate the utilities of the techniques developed in this paper. © 2007 Elsevier B.V. All rights reserved.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
15.pdf
Size
250.89 KB
Format
Adobe PDF
Checksum
(MD5):73c657e254ca7037059f6bf127be157b