%0 Journal Article
%T Reducing the worst case running times of a family of RNA and CFG problems, using Valiant's approach
%A Shay Zakov
%A Dekel Tsur
%A Michal Ziv-Ukelson
%J Algorithms for Molecular Biology
%D 2011
%I BioMed Central
%R 10.1186/1748-7188-6-20
%X 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.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 known for reducing the asymptotic running time bounds of the standard algorithms.RNA research is one of the classical domains in bioinformatics, receiving increasing attention in recent years due to discoveries regarding RNA's role in regulation of genes and as a catalyst in many cellular processes [1,2]. It is well-known that the function of an RNA molecule is heavily dependent on its structure [3]. However, due to the difficulty of physically determining RNA structure via wet-lab techniques, computational prediction of RNA structures serves as the basis of many approaches related to RNA functional analysis [4]. Most computational tools for RNA structural prediction focus on RNA secondary structures - a reduced structural representation of RNA molecules which describes a set of paired nucleotides, through hydrogen bonds, in an RNA sequence. RNA secondary structures can be relatively well predicted computationally in polynomial time (as opposed to three-dimensional structures). This computational feasibility, combined with the fact that RNA secondary structures still reveal importan
%U http://www.almob.org/content/6/1/20