Lin, Yaw-LingYaw-LingLinJiang, TaoTaoJiangKUN-MAO CHAO2011-04-182018-07-052011-04-182018-07-05200203029743http://ntur.lib.ntu.edu.tw//handle/246246/232975https://www.scopus.com/inward/record.uri?eid=2-s2.0-80052853127&doi=10.1007%2f3-540-45687-2_38&partnerID=40&md5=dbb41ae1e31542967cce434233a68d30We study two fundamental problems concerning the search for interesting regions in sequences: (i) given a sequence of real numbers of length n and an upper bound U, find a consecutive subsequence of length at most U with the maximum sum and (ii) given a sequence of real numbers of length n and a lower bound L, find a consecutive subsequence of length at least L with the maximum average. We present an O(n)- time algorithm for the first problem and an O(n log L)-time algorithm for the second. The algorithms have potential applications in several areas of biomolecular sequence analysis including locating GC-rich regions in a genomic DNA sequence, post-processing sequence alignments, annotating multiple sequence alignments, and computing length-constrained ungapped local alignment. Our preliminary tests on both simulated and real data demonstrate that the algorithms are very efficient and able to locate useful (such as GC-rich) regions. © Springer-Verlag Berlin Heidelberg 2002.en-USAlgorithm; Biomolecular sequence analysis; Efficiency; Length constraint; Maximum consecutive subsequence; Ungapped local alignmentconference paper10.1007/3-540-45687-2_382-s2.0-80052853127http://ntur.lib.ntu.edu.tw/bitstream/246246/232975/-1/16.pdf