Biology – Quantitative Biology – Biomolecules
Scientific paper
2008-02-07
Algorithms for Molecular Biology 2008, 3:10
Biology
Quantitative Biology
Biomolecules
16 pages, 10 figures
Scientific paper
10.1186/1748-7188-3-10
Background: It is of biological interest to make genome-wide predictions of the locations of DNA melting bubbles using statistical mechanics models. Computationally, this poses the challenge that a generic search through all combinations of bubble starts and ends is quadratic. Results: An efficient algorithm is described, which shows that the time complexity of the task is O(NlogN) rather than quadratic. The algorithm exploits that bubble lengths may be limited, but without a prior assumption of a maximal bubble length. No approximations, such as windowing, have been introduced to reduce the time complexity. More than just finding the bubbles, the algorithm produces a stitch profile, which is a probabilistic graphical model of bubbles and helical regions. The algorithm applies a probability peak finding method based on a hierarchical analysis of the energy barriers in the Poland-Scheraga model. Conclusions: Exact and fast computation of genomic stitch profiles is thus feasible. Sequences of several megabases have been computed, only limited by computer memory. Possible applications are the genome-wide comparisons of bubbles with promotors, TSS, viral integration sites, and other melting-related regions.
No associations
LandOfFree
A stitch in time: Efficient computation of genomic DNA melting bubbles 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 A stitch in time: Efficient computation of genomic DNA melting bubbles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A stitch in time: Efficient computation of genomic DNA melting bubbles will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-507882