| Reducing the worst case running times of a family of RNA and CFG problems, using Valiant's approach. | |
| | |
MedLine Citation:
|
PMID: 21851589 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
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 known for reducing the asymptotic running time bounds of the standard algorithms. |
| | |
Authors:
|
Shay Zakov; Dekel Tsur; Michal Ziv-Ukelson |
Related Documents
:
|
10560759 - Sequential ram-based neural networks: learnability, generalisation, knowledge extractio... 21608319 - Tech helps facility slash hais by 22%. 21604899 - Interpersonal subtypes and change of interpersonal problems in the treatment of patient... 22250269 - New technique for medial canthoplasty that incorporates modified v-w epicanthoplasty. 22057819 - Shared decision-making in orthopaedic surgery. 22190449 - Towards quantitative computer-aided studies of enzymatic enantioselectivity: the case o... 1460159 - Problem solving and suicidality among prison inmates: another look at state versus trait. 1160789 - The tole of towing services at motor vehicle crashes. 18156319 - Changes in bacterial communities of the marine sponge mycale laxissima on transfer into... |
Publication Detail:
|
Type: JOURNAL ARTICLE Date: 2011-8-18 |
Journal Detail:
|
Title: Algorithms for molecular biology : AMB Volume: 6 ISSN: 1748-7188 ISO Abbreviation: - Publication Date: 2011 Aug |
Date Detail:
|
Created Date: 2011-8-19 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101265088 Medline TA: Algorithms Mol Biol Country: - |
Other Details:
|
Languages: ENG Pagination: 20 Citation Subset: - |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Genome-wide copy number variation (CNV) in patients with autoimmune Addison's disease.
Next Document: A phospho-proteomic screen identifies substrates of the checkpoint kinase Chk1.