Sparsification of RNA structure prediction including pseudoknots
Abstract Background Although many RNA molecules contain pseudoknots, computational prediction of pseudoknotted RNA structure is still in its infancy due to high running time and space consumption implied by the dynamic programming formulations of the problem. Results In this paper, we introduce spar...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
BioMed Central Ltd
2011
|
| Online Access: | http://hdl.handle.net/1721.1/63116 |
| _version_ | 1811093690793328640 |
|---|---|
| author | Mohl, Mathias Salari, Raheleh Will, Sebastian Backofen, Rolf Sahinalp, S. Cenk |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Mohl, Mathias Salari, Raheleh Will, Sebastian Backofen, Rolf Sahinalp, S. Cenk |
| author_sort | Mohl, Mathias |
| collection | MIT |
| description | Abstract Background Although many RNA molecules contain pseudoknots, computational prediction of pseudoknotted RNA structure is still in its infancy due to high running time and space consumption implied by the dynamic programming formulations of the problem. Results In this paper, we introduce sparsification to significantly speedup the dynamic programming approaches for pseudoknotted RNA structure prediction, which also lower the space requirements. Although sparsification has been applied to a number of RNA-related structure prediction problems in the past few years, we provide the first application of sparsification to pseudoknotted RNA structure prediction specifically and to handling gapped fragments more generally - which has a much more complex recursive structure than other problems to which sparsification has been applied. We analyse how to sparsify four pseudoknot structure prediction algorithms, among those the most general method available (the Rivas-Eddy algorithm) and the fastest one (Reeder-Giegerich algorithm). In all algorithms the number of "candidate" substructures to be considered is reduced. Conclusions Our experimental results on the sparsified Reeder-Giegerich algorithm suggest a linear speedup over the unsparsified implementation. |
| first_indexed | 2024-09-23T15:49:10Z |
| format | Article |
| id | mit-1721.1/63116 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:49:10Z |
| publishDate | 2011 |
| publisher | BioMed Central Ltd |
| record_format | dspace |
| spelling | mit-1721.1/631162022-09-29T16:19:27Z Sparsification of RNA structure prediction including pseudoknots Mohl, Mathias Salari, Raheleh Will, Sebastian Backofen, Rolf Sahinalp, S. Cenk Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Will, Sebastian Will, Sebastian Abstract Background Although many RNA molecules contain pseudoknots, computational prediction of pseudoknotted RNA structure is still in its infancy due to high running time and space consumption implied by the dynamic programming formulations of the problem. Results In this paper, we introduce sparsification to significantly speedup the dynamic programming approaches for pseudoknotted RNA structure prediction, which also lower the space requirements. Although sparsification has been applied to a number of RNA-related structure prediction problems in the past few years, we provide the first application of sparsification to pseudoknotted RNA structure prediction specifically and to handling gapped fragments more generally - which has a much more complex recursive structure than other problems to which sparsification has been applied. We analyse how to sparsify four pseudoknot structure prediction algorithms, among those the most general method available (the Rivas-Eddy algorithm) and the fastest one (Reeder-Giegerich algorithm). In all algorithms the number of "candidate" substructures to be considered is reduced. Conclusions Our experimental results on the sparsified Reeder-Giegerich algorithm suggest a linear speedup over the unsparsified implementation. Semiconductor Research Corporation. Focus Center Research Program (Contract 2003-CT-888) 2011-05-25T18:29:41Z 2011-05-25T18:29:41Z 2010-12 2010-10 2011-05-09T18:32:06Z Article http://purl.org/eprint/type/JournalArticle 1748-7188 http://hdl.handle.net/1721.1/63116 Mohl, Mathias et al. “Sparsification of RNA Structure Prediction Including Pseudoknots.” Algorithms for Molecular Biology 5.1 (2010) : 39. en http://dx.doi.org/10.1186/1748-7188-5-39 Algorithms for Molecular Biology Creative Commons Attribution Mohl et al.; licensee BioMed Central Ltd. application/pdf BioMed Central Ltd BioMed Central Ltd |
| spellingShingle | Mohl, Mathias Salari, Raheleh Will, Sebastian Backofen, Rolf Sahinalp, S. Cenk Sparsification of RNA structure prediction including pseudoknots |
| title | Sparsification of RNA structure prediction including pseudoknots |
| title_full | Sparsification of RNA structure prediction including pseudoknots |
| title_fullStr | Sparsification of RNA structure prediction including pseudoknots |
| title_full_unstemmed | Sparsification of RNA structure prediction including pseudoknots |
| title_short | Sparsification of RNA structure prediction including pseudoknots |
| title_sort | sparsification of rna structure prediction including pseudoknots |
| url | http://hdl.handle.net/1721.1/63116 |
| work_keys_str_mv | AT mohlmathias sparsificationofrnastructurepredictionincludingpseudoknots AT salariraheleh sparsificationofrnastructurepredictionincludingpseudoknots AT willsebastian sparsificationofrnastructurepredictionincludingpseudoknots AT backofenrolf sparsificationofrnastructurepredictionincludingpseudoknots AT sahinalpscenk sparsificationofrnastructurepredictionincludingpseudoknots |