SparseRNAfolD: optimized sparse RNA pseudoknot-free folding with dangle consideration
Abstract Motivation Computational RNA secondary structure prediction by free energy minimization is indispensable for analyzing structural RNAs and their interactions. These methods find the structure with the minimum free energy (MFE) among exponentially many possible structures and have a restrict...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2024-03-01
|
| Series: | Algorithms for Molecular Biology |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s13015-024-00256-4 |
| _version_ | 1797275872850345984 |
|---|---|
| author | Mateo Gray Sebastian Will Hosna Jabbari |
| author_facet | Mateo Gray Sebastian Will Hosna Jabbari |
| author_sort | Mateo Gray |
| collection | DOAJ |
| description | Abstract Motivation Computational RNA secondary structure prediction by free energy minimization is indispensable for analyzing structural RNAs and their interactions. These methods find the structure with the minimum free energy (MFE) among exponentially many possible structures and have a restrictive time and space complexity ( $$O(n^3)$$ O ( n 3 ) time and $$O(n^2)$$ O ( n 2 ) space for pseudoknot-free structures) for longer RNA sequences. Furthermore, accurate free energy calculations, including dangle contributions can be difficult and costly to implement, particularly when optimizing for time and space requirements. Results Here we introduce a fast and efficient sparsified MFE pseudoknot-free structure prediction algorithm, SparseRNAFolD, that utilizes an accurate energy model that accounts for dangle contributions. While the sparsification technique was previously employed to improve the time and space complexity of a pseudoknot-free structure prediction method with a realistic energy model, SparseMFEFold, it was not extended to include dangle contributions due to the complexity of computation. This may come at the cost of prediction accuracy. In this work, we compare three different sparsified implementations for dangle contributions and provide pros and cons of each method. As well, we compare our algorithm to LinearFold, a linear time and space algorithm, where we find that in practice, SparseRNAFolD has lower memory consumption across all lengths of sequence and a faster time for lengths up to 1000 bases. Conclusion Our SparseRNAFolD algorithm is an MFE-based algorithm that guarantees optimality of result and employs the most general energy model, including dangle contributions. We provide a basis for applying dangles to sparsified recursion in a pseudoknot-free model that has the potential to be extended to pseudoknots. |
| first_indexed | 2024-03-07T15:20:15Z |
| format | Article |
| id | doaj.art-b64d56fc4ef845ecb03400afccd55427 |
| institution | Directory Open Access Journal |
| issn | 1748-7188 |
| language | English |
| last_indexed | 2024-03-07T15:20:15Z |
| publishDate | 2024-03-01 |
| publisher | BMC |
| record_format | Article |
| series | Algorithms for Molecular Biology |
| spelling | doaj.art-b64d56fc4ef845ecb03400afccd554272024-03-05T17:41:31ZengBMCAlgorithms for Molecular Biology1748-71882024-03-0119111610.1186/s13015-024-00256-4SparseRNAfolD: optimized sparse RNA pseudoknot-free folding with dangle considerationMateo Gray0Sebastian Will1Hosna Jabbari2Department of Biomedical Engineering, University of AlbertaDepartment of Computer Science CNRS/LIX (UMR 7161), Institut Polytechnique de ParisDepartment of Biomedical Engineering, University of AlbertaAbstract Motivation Computational RNA secondary structure prediction by free energy minimization is indispensable for analyzing structural RNAs and their interactions. These methods find the structure with the minimum free energy (MFE) among exponentially many possible structures and have a restrictive time and space complexity ( $$O(n^3)$$ O ( n 3 ) time and $$O(n^2)$$ O ( n 2 ) space for pseudoknot-free structures) for longer RNA sequences. Furthermore, accurate free energy calculations, including dangle contributions can be difficult and costly to implement, particularly when optimizing for time and space requirements. Results Here we introduce a fast and efficient sparsified MFE pseudoknot-free structure prediction algorithm, SparseRNAFolD, that utilizes an accurate energy model that accounts for dangle contributions. While the sparsification technique was previously employed to improve the time and space complexity of a pseudoknot-free structure prediction method with a realistic energy model, SparseMFEFold, it was not extended to include dangle contributions due to the complexity of computation. This may come at the cost of prediction accuracy. In this work, we compare three different sparsified implementations for dangle contributions and provide pros and cons of each method. As well, we compare our algorithm to LinearFold, a linear time and space algorithm, where we find that in practice, SparseRNAFolD has lower memory consumption across all lengths of sequence and a faster time for lengths up to 1000 bases. Conclusion Our SparseRNAFolD algorithm is an MFE-based algorithm that guarantees optimality of result and employs the most general energy model, including dangle contributions. We provide a basis for applying dangles to sparsified recursion in a pseudoknot-free model that has the potential to be extended to pseudoknots.https://doi.org/10.1186/s13015-024-00256-4RNAMFESecondary structure predictionDangleSparsificationSpace complexity |
| spellingShingle | Mateo Gray Sebastian Will Hosna Jabbari SparseRNAfolD: optimized sparse RNA pseudoknot-free folding with dangle consideration Algorithms for Molecular Biology RNA MFE Secondary structure prediction Dangle Sparsification Space complexity |
| title | SparseRNAfolD: optimized sparse RNA pseudoknot-free folding with dangle consideration |
| title_full | SparseRNAfolD: optimized sparse RNA pseudoknot-free folding with dangle consideration |
| title_fullStr | SparseRNAfolD: optimized sparse RNA pseudoknot-free folding with dangle consideration |
| title_full_unstemmed | SparseRNAfolD: optimized sparse RNA pseudoknot-free folding with dangle consideration |
| title_short | SparseRNAfolD: optimized sparse RNA pseudoknot-free folding with dangle consideration |
| title_sort | sparsernafold optimized sparse rna pseudoknot free folding with dangle consideration |
| topic | RNA MFE Secondary structure prediction Dangle Sparsification Space complexity |
| url | https://doi.org/10.1186/s13015-024-00256-4 |
| work_keys_str_mv | AT mateogray sparsernafoldoptimizedsparsernapseudoknotfreefoldingwithdangleconsideration AT sebastianwill sparsernafoldoptimizedsparsernapseudoknotfreefoldingwithdangleconsideration AT hosnajabbari sparsernafoldoptimizedsparsernapseudoknotfreefoldingwithdangleconsideration |