Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis
✍ Scribed by Yaw-Ling Lin; Tao Jiang; Kun-Mao Chao
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 306 KB
- Volume
- 65
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
We 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.