Locating regions in a sequence under density constraints

Details Locating regions in a sequence under density constraints Locating regions in a sequence under density constraints

2011-04-05

arxiv.org/abs/1104.0919v1

Computer Science

Data Structures and Algorithms

15 pages, 8 figures

Scientific paper

Several biological problems require the identification of regions in a sequence where some feature occurs within a target density range: examples including the location of GC-rich regions, identification of CpG islands, and sequence matching. Mathematically, this corresponds to searching a string of 0s and 1s for a substring whose relative proportion of 1s lies between given lower and upper bounds. We consider the algorithmic problem of locating the longest such substring, as well as other related problems (such as finding the shortest substring or a maximal set of disjoint substrings). For locating the longest such substring, we develop an algorithm that runs in O(n) time, improving upon the previous best-known O(n log n) result. For the related problems we likewise improve time complexities and remove significant overhead from the prior state of the art. Practical testing verifies that our new algorithms enjoy significantly smaller time and memory footprints, and can process sequences that are orders of magnitude longer as a result.

Affiliated with

Also associated with

No associations

Rating

Locating regions in a sequence under density constraints does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Locating regions in a sequence under density constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Locating regions in a sequence under density constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-321907