Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: A stitch in time: Efficient computation of genomic DNA melting bubbles. | Algorithms for Molecular Biology BioMed Central Research A stitch in time Efficient computation of genomic DNA melting bubbles Eivind Tostesen1 2 Open Access Address Department of Tumor Biology Norwegian Radium Hospital N-0310 Oslo Norway and 2Department of Mathematics University of Oslo N-0316 Oslo Norway Email Eivind Tostesen - eivindto@ Published 17 July 2008 Received 1 February 2008 Algorithms for Molecular Biology 2008 3 10 doi 1748-7188-3-10 Accepted 17 July 2008 This article is available from http content 3 1 10 2008 Tostesen licensee BioMed Central Ltd. This is an Open Access article distributed under the terms of the Creative Commons Attribution License http licenses by which permits unrestricted use distribution and reproduction in any medium provided the original work is properly cited. 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
