Bioinformatický seminár

Tue 16 Apr. 2013, 17:20

Title: Zakov et al. (2011) Reducing the worst case running times of a family of RNA and CFG problems, using Valiant's approach
Speaker: Lucia Simanová

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
known for reducing the asymptotic running time bounds of the standard algorithms.