DocumentCode :
952098
Title :
Optimal Algorithms for the Interval Location Problem with Range Constraints on Length and Average
Author :
Hsieh, Yong-Hsiang ; Yu, Chih-Chiang ; Wang, Biing-Feng
Author_Institution :
Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu
Volume :
5
Issue :
2
fYear :
2008
Firstpage :
281
Lastpage :
290
Abstract :
Let A be a sequence of n real numbers, L1 and L2 be two integers such that L1 les L2, and let R1 and R2 be two real numbers such that R1 les R2. An interval of A is feasible if its length is between L1 and L2, and its average is between R1 and R2. In this paper, we study the following problems: finding all feasible intervals of A, counting all feasible intervals of A, finding a maximum cardinality set of nonoverlapping feasible intervals of A, locating a longest feasible interval of A, and locating a shortest feasible interval of A. The problems are motivated from the problem of locating CpG islands in biomolecular sequences. In this paper, we first show that all the problems have an Omega (n log n)-time lower bound in the comparison model. Then, we use geometric approaches to design optimal algorithms for the problems. All the presented algorithms run in an online manner and use O(n) space.
Keywords :
DNA; biology computing; molecular biophysics; optimisation; CpG islands; biomolecular sequences; interval location problem; optimal algorithms; algorithms; analysis of algorithms; data structures; geometrical problems and computations; Algorithms; Base Composition; Computational Biology; CpG Islands; DNA; GC Rich Sequence; Models, Genetic; Sequence Analysis, DNA;
fLanguage :
English
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
Publisher :
ieee
ISSN :
1545-5963
Type :
jour
DOI :
10.1109/TCBB.2007.70217
Filename :
4359875
Link To Document :
بازگشت