| Optimal algorithms for the interval location problem with range constraints on length and average. | |
| | |
MedLine Citation:
|
PMID: 18451437 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
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:
|
Yong-Hsiang Hsieh; Chih-Chiang Yu; Biing-Feng Wang |
Related Documents
:
|
10111297 - The clean restaurant. ii: employee hygiene. 9066767 - Chloropeptins, new anti-hiv antibiotics inhibiting gp120-cd4 binding from streptomyces ... 11527717 - Anti-aids agents. part 47: synthesis and anti-hiv activity of 3-substituted 3',4'-di-o-... 12217147 - Video-hypnosis--the provision of specialized therapy via videoconferencing. 22371717 - Short-term results of community-based interventions for improving physical activity: is... 3604997 - Terms of empowerment/exemplars of prevention: toward a theory for community psychology. |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't |
Journal Detail:
|
Title: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM Volume: 5 ISSN: 1545-5963 ISO Abbreviation: IEEE/ACM Trans Comput Biol Bioinform Publication Date: 2008 Apr-Jun |
Date Detail:
|
Created Date: 2008-05-02 Completed Date: 2008-07-18 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101196755 Medline TA: IEEE/ACM Trans Comput Biol Bioinform Country: United States |
Other Details:
|
Languages: eng Pagination: 281-90 Citation Subset: IM |
Affiliation:
|
Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30043, Taiwan. eric@cs.nthu.edu.tw |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Base Composition Computational Biology CpG Islands DNA / chemistry*, genetics* GC Rich Sequence Models, Genetic Sequence Analysis, DNA / statistics & numerical data |
| Chemical | |
Reg. No./Substance:
|
9007-49-2/DNA |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Nature reserve selection problem: a tight approximation algorithm.
Next Document: Prediction of R5, X4, and R5X4 HIV-1 coreceptor usage with evolved neural networks.