File MaximumSegments.h

↰ Parent directory (ADS/algorithm)

The segments (subarrays) of largest sum and their variants, chapter 2 of the notes: the gains of a stock as the differences of its quotations, and the regions of a DNA sequence rich in C and G.

Definition (ADS/algorithm/MaximumSegments.h)

Detailed Description

  • maxSumSegmentCubic() and maxSumSegmentQuadratic() are Algorithms 2.1 and 2.2, all the pairs ( b , s ), the sum recomputed or extended, :math:` Theta( n^3 ) ` and :math:` Theta( n^2 ) `.

  • maxSumSegment() is Algorithm 2.3, the scan of Kadane with the positions: a prefix of negative sum is dropped, since no optimum starts after a segment of positive sum nor has a prefix of negative sum (Properties 1 and 2), O( n ) time, one pass, :math:` lceil n / B rceil ` I/Os whatever B (cache oblivious). maxSubarraySum() of File Subsequences.h is the same scan for the value only, the empty segment allowed; here the segment is not empty, so that an array of negative numbers gives its largest one.

  • maxSumSegmentPrefix() is Algorithm 2.4: with the prefix sums P, the best segment ending in s is :math:` P[ s ] - min_{b < s} P[ b ] `, the minimum carried along the scan.

  • maxSumSegmentLength() bounds the length to :math:` [ L , U ] `: the minimum of P over the window of the admissible starts, by a deque of increasing prefix sums (the sliding minimum), O( n ), the algorithm of Lin, Jiang and Chao.

  • longestSegmentAtLeast() is the algorithm of section 2.5 for the longest segment of sum at least t: at step i only the starts left of :math:` L_i = i - ell ` can beat the current length :math:` ell , and among them only the chain of leftmost minima :math: C_1 = LMin[ L_i ] , C_2 = LMin[ C_1 ] , ldots , whose prefix sums increase (Fact 2.2); the chain is walked while the sum stays at least t, and every step past the first lengthens the solution, hence O( n ) amortized. longestSegmentAverageAtLeast() reduces the longest segment of average at least p / q to it, by :math: q D[ k ] - p `.

  • maxDensitySegment() is the segment of largest average among those of length at least L: the average of D[ x .. i ) is the slope from :math:` ( x , P[ x ] ) ` to :math:` ( i , P[ i ] ) , and the best x for i lies on the lower convex hull of the points :math: x leq i - L , kept by the monotone chain as i grows, the tangent found by a binary search, :math: O( n log n ) `. Goldwasser, Kao and Lu, and Chung and Lu, reach O( n ) by walking the hull with a pointer that moves only forward under a further argument (and also handle an upper bound on the length); the binary search keeps the code short and exact on integers.

  • gcIndicator() maps a DNA sequence to 1 for C and G and 0 otherwise, the input of the two biological measures of the notes: :math:` x - p ell ` (a segment sum of the scores :math:` 1 - p ` and :math:` -p , e.g., q D[ k ] - p for p / q) and the density :math: x / ell `.

A Segment holds the sum of D[ first .. first + length ), length 0 for none. The contracts [see File Contract.h]: D not empty where a segment must exist, :math:` 1 leq L leq U , :math: L leq n `, q > 0; the sum of a segment is that of its items, and maxSumSegment() agrees with maxSubarraySum() when its sum is not negative, audits. The sums of the segments and of the prefixes of D must fit in T, which is not checked (an item of T alone may be its largest or its smallest value). The functions are defined in MaximumSegments.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 2

  1. Bentley, Programming pearls: algorithm design techniques, Communications of the ACM 27(9), 865-873, 1984, doi:10.1145/358234.381162

Y.-L. Lin, T. Jiang, K.-M. Chao, Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis, Journal of Computer and System Sciences 65(3), 570-586, 2002, doi:10.1016/S0022-0000(02)00010-7

    1. Goldwasser, M.-Y. Kao, H.-I. Lu, Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications, Journal of Computer and System Sciences 70(2), 128-144, 2005, doi:10.1016/j.jcss.2004.08.001

K.-M. Chung, H.-I. Lu, An optimal algorithm for the maximum-density segment problem, SIAM Journal on Computing 34(2), 373-387, 2004, doi:10.1137/S0097539704440430

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions