An Improved Algorithm for the Location of Heaviest Segments in Genomic Sequences

The location of heaviest segments in genomic sequences has been effective in the search for diverse groups of regions containing features of interest. Several algorithms have been developed and published to identify either the globally highest scoring segment or all segments scoring the highest in their local environments, some running in time linear with the size of the sequence. In this paper we present a new linear-time variant of the algorithm for locating all highest scoring segments in a given sequence, which we believe is better structured, easier to prove correct, and at least as efficient as these previously published.