title: Optimal algorithms for the interval location problem with range constraints on length and average.
abstract: Let A be a sequence of n real numbers, L(1) and L(2) be two integers such that L(1) < or = L(2) , and R(1) and R(2) be two real numbers such that R(1) < or = R(2). An interval of A is feasible if its length is between L(1) and L(2) and its average is between R(1) and R(2). 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 non-overlapping 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 firstly show that all the problems have 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 on-line manner and use O(n) space.
authors.affiliation: Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, Taiwan. eric@cs.nthu.edu.tw
authors.forename: Yong-Hsiang
authors.initials: YH
authors.lastname: Hsieh
authors.forename: Chih-Chiang
authors.initials: CC
authors.lastname: Yu
authors.forename: Biing-Feng
authors.initials: BF
authors.lastname: Wang
mesh_terms: D000465:Algorithms; D001482:Base Composition; D019295:Computational Biology; D018899:CpG Islands; D004247:DNA / Q000737:chemistry* / Q000235:genetics*; D020862:GC Rich Sequence; D008957:Models, Genetic; D017422:Sequence Analysis, DNA / Q000706:statistics & numerical data
chemical_list: D004247:DNA