Abstract
Given a sequence A of n real numbers and two positive integers l and k, where \(k \leq \frac{n}{l}\), the problem is to locate k disjoint segments of A, each has length at least l, such that their sum of densities is maximized. The best previously known algorithm, due to Bergkvist and Damaschke [1], runs in O(nl+k 2 l 2) time. In this paper, we give an O(n+k 2 llogl)-time algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bergkvist, A., Damaschke, P.: Fast Algorithms for Finding Disjoint Subsequences with Extremal Densities. In: Proceedings of the 16th Annual International Symposium on Algorithms and Computation, pp. 714–723 (2005)
Chen, Y.H., Lu, H.-I., Tang, C.Y.: Disjoint Segments with Maximum Density. In: Proceedings of the 5th Annual International Conference on Computational Science, pp. 845–850 (2005)
Chung, K.-M., Lu, H.-I.: An Optimal Algorithm for the Maximum-Density Segment Problem. SIAM Journal on Computing 34, 373–387 (2004)
Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T.: Mining Optimized Association Rules for Numeric Attributes. Journal of Computer and System Sciences 58, 1–12 (1999)
Goldwasser, M., Kao, M.-Y., Lu, H.-I.: Linear-Time Algorithms for Computing Maximum-Density Sequence Segments with Bioinformatics Applications. Journal of Computer and System Sciences 70, 128–144 (2005)
Huang, X.: An Algorithm for Identifying Regions of a DNA Sequence that Satisfy a Content Requirement. Computer Applications in the Biosciences 10, 219–225 (1994)
Kim, S.K.: Linear-Time Algorithm for Finding a Maximum-Density Segment of a Sequence. Information Processing Letters 86, 339–342 (2003)
Lin, Y.-L., Huang, X., Jiang, T., Chao, K.-M.: MAVG: Locating Non-Overlapping Maximum Average Segments in a Given Sequence. Bioinformatics 19, 151–152 (2003)
Lin, Y.-L., Jiang, T., Chao, K.-M.: Efficient Algorithms for Locating the Length-Constrained Heaviest Segments with Applications to Biomolecular Sequence Analysis. Journal of Computer and System Sciences 65, 570–586 (2002)
Liu, H.-F., Chao, K.-M.: An Optimal Algorithm for Iteratively Locating Non-Overlapping Maximum Density Segments. Information Processing Letters (submitted)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, HF., Chao, KM. (2006). On Locating Disjoint Segments with Maximum Sum of Densities. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_31
Download citation
DOI: https://doi.org/10.1007/11940128_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)