Research

A stitch in time: Efficient computation of genomic DNA melting bubbles

Eivind Tøstesen^1,2

¹  Department of Tumor Biology, Norwegian Radium Hospital, N-0310, Oslo, Norway

²  Department of Mathematics, University of Oslo, N-0316, Oslo, Norway

author email corresponding author email

Algorithms for Molecular Biology 2008, 3:10doi:10.1186/1748-7188-3-10

Published:	17 July 2008

Abstract

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.

Conclusion

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.