|
|||||
|
|
On the range maximum-sum segment query problem |
|
| Authors: | Kuan-Yu Chen |
| Affiliation: | a Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan b Graduate Institute of Biomedical Electronics and Bioinformatics, National Taiwan University, Taipei 106, Taiwan c Graduate Institute of Networking and Multimedia, National Taiwan University, Taipei 106, Taiwan |
| 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. |
| Keywords: | Range minimum query Least common ancestor Maximum-sum segment |
| 本文献已被 ScienceDirect 等数据库收录！ | |