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: Reducing the worst case running times of a family of RNA and CFG problems, using Valiant’s approach. | Zakov et al. Algorithms for Molecular Biology 2011 6 20 http content 6 1 20 AMR ALGORITHMS FOR MOLECULAR BIOLOGY RESEARCH Open Access Reducing the worst case running times of a family of RNA and CFG problems using Valiant s approach Shay Zakov Dekel Tsur and Michal Ziv-Ukelson Abstract Background RNA secondary structure prediction is a mainstream bioinformatic domain and is key to computational analysis of functional RNA. In more than 30 years much research has been devoted to defining different variants of RNA structure prediction problems and to developing techniques for improving prediction quality. Nevertheless most of the algorithms in this field follow a similar dynamic programming approach as that presented by Nussinov and Jacobson in the late 70 s which typically yields cubic worst case running time algorithms. Recently some algorithmic approaches were applied to improve the complexity of these algorithms motivated by new discoveries in the RNA domain and by the need to efficiently analyze the increasing amount of accumulated genome-wide data. Results We study Valiant s classical algorithm for Context Free Grammar recognition in sub-cubic time and extract features that are common to problems on which Valiant s approach can be applied. Based on this we describe several problem templates and formulate generic algorithms that use Valiant s technique and can be applied to all problems which abide by these templates including many problems within the world of RNA Secondary Structures and Context Free Grammars. Conclusions The algorithms presented in this paper improve the theoretical asymptotic worst case running time bounds for a large family of important problems. It is also possible that the suggested techniques could be applied to yield a practical speedup for these problems. For some of the problems such as computing the RNA partition function and base-pair binding probabilities the presented techniques are the only ones which are currently .
