Hostname: page-component-8448b6f56d-cfpbc Total loading time: 0 Render date: 2024-04-20T00:22:57.908Z Has data issue: false hasContentIssue false
  • English
  • Français

Calculating a linear-time solution to the densest-segment problem

Part of: JFP Research Articles

Published online by Cambridge University Press:  14 December 2015

SHARON CURTIS  and
SHIN-CHENG MU
SHARON CURTIS
Affiliation:
Oxford University, UK (e-mail: sharon.curtis@ndph.ox.ac.uk)
SHIN-CHENG MU
Affiliation:
Academia Sinica, Taiwan (e-mail: scm@iis.sinica.edu.tw)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The problem of finding a densest segment of a list is similar to the well-known maximum segment sum problem, but its solution is surprisingly challenging. We give a general specification of such problems, and formally develop a linear-time online solution, using a sliding-window style algorithm. The development highlights some elegant properties of densities, involving partitions that are decreasing and all right-skew.

Type
Articles
Information
Journal of Functional Programming , Volume 25 , 2015 , e22
Copyright
Copyright © Cambridge University Press 2015 

References

Bird, R. S. (1987) An introduction to the theory of lists. In Logic of Programming and Calculi of Discrete Design, Broy, M. (ed), NATO ASI Series F, vol. 36. Springer-Verlag, pp. 342.Google Scholar
Bird, R. S. & de Moor, O. (1997) The Algebra of Programming. Prentice Hall.Google Scholar
Chung, K.-M. (2010) Personal communication.Google Scholar
Chung, K.-M. & Lu, H.-I. (2003) An optimal algorithm for the maximum-density segment problem. In Annual European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 2832, pp. 136–147, Springer-Verlag.Google Scholar
Chung, K.-M. & Lu, H.-I. (2004) An optimal algorithm for the maximum-density segment problem. SIAM J. Comput. 34 (2), 373–387.CrossRefGoogle Scholar
Curtis, S. & Mu, S.-C. (2014) Calculating a linear-time solution to the densest segment problem (paper and supplement materials). Available at: http://www.iis.sinica.edu.tw/~scm/2014/mds/. Last accessed: November 23rd, 2015.Google Scholar
Goldwasser, M. H., Kao, M.-Y. & Lu, H.-I. (2002) Fast algorithms for finding maximum-density segments of a sequence with applications to bioinformatics. In Proceedings of the 2nd Workshop on Algorithms in Bioinformatics (WABI 2002), Springer, Berlin, pp. 157–171.Google Scholar
Goldwasser, M. H., Kao, M.-Y. & Lu, H.-I. (2005) Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications. J. Comput. Syst. Sci. 70 (2), 128–144.CrossRefGoogle Scholar
Han, L. & Zhao, Z. (2009) CpG islands or CpG clusters: How to identify functional gc-rich regions in a genome? BMC Bioinformatics 10 (65), doi: 10.1186/1471-2105-10-65.CrossRefGoogle ScholarPubMed
Hinze, R. & Paterson, R. (2006) Finger trees: A simple general-purpose data structure. J. Funct. Program. 16 (2), 197–217.CrossRefGoogle Scholar
Huang, X. (1994) An algorithm for identifying regions of a DNA sequence that satisfy a content requirement. Comput. Appl. Biosci. 10 (3), 219–225.Google ScholarPubMed
Jeuring, J. T. (1993) Theories for Algorithm Calculation. Ph.D. thesis, Utrecht University.Google Scholar
Jeuring, J. T. & Meertens, L. (1989) The least-effort cabinet formation. Squiggolist 1 (2), 12–16.Google Scholar
Kaldewaij, A. (1990) Programming: The Derivation of Algorithms. Prentice Hall.Google Scholar
Lin, Y.-L., Jiang, T. & Chao, K.-M. (2002) Efficient algorithms for locating the length-constrained heaviest segments, with applications to biomolecular sequence analysis. In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Springer-Verlag, Berlin, vol. 2420, pp. 459–470.Google Scholar
Malcolm, G. R. (1990) Algebraic Data Types and Program Transformation. Ph.D. thesis, Groningen University, the Netherlands.Google Scholar
Mu, S.-C., Ko, H.-S. & Jansson, P. (2009) Algebra of programming in Agda: Dependent types for relational program derivation. J. Funct. Program. 19 (5), 545–579.CrossRefGoogle Scholar
Norell, U. (2007) Towards a Practical Programming Language Based on Dependent Type Theory. Ph.D. thesis, Chalmers University of Technology.Google Scholar
Okasaki, C. (1999) Purely Functional Data Structures. Cambridge University Press.Google Scholar
Rem, M. (1988) Small programming exercises 20. Sci. Comput. Program. 10 (1), 99–105.CrossRefGoogle Scholar
Swierstra, S. D. & de Moor, O. (1993) Virtual data structures. In IFIP TC2/WG2.1 State-of-the-Art Report on Formal Program Development, Bernhard, M., Helmut, P. & Steve, S. (eds), Lecture Notes in Computer Science, pp. 355–371, Springer.CrossRefGoogle Scholar
Van Den Eijnde, J. P. H. W. (1990) Left-bottom and right-top segments. Sci. Comput. Program. 15 (1), 79–94.CrossRefGoogle Scholar
Zantema, H. (1992) Longest segment problems. Sci. Comput. Program. 18 (1), 39–66.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.