Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis
Authors: Lin Y-L.1; Jiang T.2; Chao K-M.3
Source: Journal of Computer and System Sciences, Volume 65, Number 3, November 2002 , pp. 570-586(17)
Publisher: Academic Press
- Free Content
- New Content
- Subscribed Content
- Free Trial Content
Abstract:
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 boundU, 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.
Language: English
Document Type: Research article
DOI: 10.1016/S0022-0000(02)00010-7
Affiliations: 1: Department of Computer Science and Information Management, Providence University, 200 Chung Chi Road, Shalu, Taichung County, 433 Taiwan 2: Department of Computer Science, University of California Riverside, Riverside, CA 92521-0144, USA 3: Department of Life Science, National Yang-Ming University, Taipei, 112 Taiwan
- Free Content
- New Content
- Subscribed Content
- Free Trial Content
Click here for Page Help