Search Results

Documents authored by Jabbari, Hosna

Artifact
Software
DOI: 10.4230/artifacts.24328
Spark

Authors: Mateo Gray, Sebastian Will, and Hosna Jabbari

Abstract
Cite as

Mateo Gray, Sebastian Will, Hosna Jabbari. Spark (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24328,
   title = {{Spark}}, 
   author = {Gray, Mateo and Will, Sebastian and Jabbari, Hosna},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:2cb07371af448bb6254c05d23ac106800c590d39;origin=https://github.com/TheCOBRALab/Spark;visit=swh:1:snp:aeb39934d18efe24abf8aea90905fdbef5863e3f;anchor=swh:1:rev:51eaafa4fb54397a921a7c943d7747f4e226f5ba}{\texttt{swh:1:dir:2cb07371af448bb6254c05d23ac106800c590d39}} (visited on 2025-08-15)},
   url = {https://github.com/TheCOBRALab/Spark},
   doi = {10.4230/artifacts.24328},
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.13
Spark: Sparsified Hierarchical Energy Minimization of RNA Pseudoknots

Authors: Mateo Gray, Sebastian Will, and Hosna Jabbari

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Motivation. Determining RNA structure is essential for understanding RNA function and interaction networks. Although experimental techniques yield high‑accuracy structures, they are costly and time‑consuming; thus, computational approaches - especially minimum‑free‑energy (MFE) prediction algorithms - are indispensable. Accurately predicting pseudoknots, however, remains challenging because their inclusion usually leads to prohibitive computational complexity. Recent work demonstrated that sparsification can improve the efficiency of complex pseudoknot prediction algorithms such as Knotty. This finding suggests similar gains are possible for already efficient algorithms like HFold, which targets a complementary class of hierarchically constrained pseudoknots. Results. We introduce Spark, an exact, fully sparsified algorithm for predicting pseudoknotted RNA structures. Like its non‑sparsified predecessor HFold, Spark searches for the minimum‑energy structure under the HotKots 2.0 energy model, a pseudoknot extension of the Turner model. Because the sparsification is non‑heuristic, Spark preserves the asymptotic time‑ and space‑complexity guarantees of HFold while greatly reducing the constant factors. We benchmarked the performance of Spark against HFold and, as a pseudoknot‑free baseline, RNAfold. Compared with HFold, Spark substantially lowers both run time and memory usage, while achieving run‑time figures close to those of RNAfold. Across all tested sequence lengths, Spark used the least memory and consistently ran faster than HFold. Conclusion. By extending non‑heuristic sparsification to hierarchical pseudoknot prediction, Spark delivers an exceptionally fast and memory‑efficient tool accurate prediction of pseudoknotted RNA structures, enabling routine analysis of long sequences. The algorithm broadens the practical scope of computational RNA biology and provides a solid foundation for future advances in structure‑based functional annotation. Availability. Spark’s implementation and detailed results are available at https://github.com/TheCOBRALab/Spark.
Cite as

Mateo Gray, Sebastian Will, and Hosna Jabbari. Spark: Sparsified Hierarchical Energy Minimization of RNA Pseudoknots. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gray_et_al:LIPIcs.WABI.2025.13,
  author =	{Gray, Mateo and Will, Sebastian and Jabbari, Hosna},
  title =	{{Spark: Sparsified Hierarchical Energy Minimization of RNA Pseudoknots}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.13},
  URN =		{urn:nbn:de:0030-drops-239383},
  doi =		{10.4230/LIPIcs.WABI.2025.13},
  annote =	{Keywords: RNA, MFE, Secondary Structure Prediction, Pseudoknot, Sparsification, Space Complexity, Time Complexity}
}
Document
DOI: 10.4230/LIPIcs.WABI.2023.19
SparseRNAFolD: Sparse RNA Pseudoknot-Free Folding Including Dangles

Authors: Mateo Gray, Sebastian Will, and Hosna Jabbari

Published in: LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)

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³) time and O(n²) space for pseudoknot-free structures) for longer RNA sequences. Furthermore, accurate free energy calculations, including dangles 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 dangles 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 ability to be extended to pseudoknots.
Cite as

Mateo Gray, Sebastian Will, and Hosna Jabbari. SparseRNAFolD: Sparse RNA Pseudoknot-Free Folding Including Dangles. In 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 273, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gray_et_al:LIPIcs.WABI.2023.19,
  author =	{Gray, Mateo and Will, Sebastian and Jabbari, Hosna},
  title =	{{SparseRNAFolD: Sparse RNA Pseudoknot-Free Folding Including Dangles}},
  booktitle =	{23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-294-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{273},
  editor =	{Belazzougui, Djamal and Ouangraoua, A\"{i}da},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.19},
  URN =		{urn:nbn:de:0030-drops-186454},
  doi =		{10.4230/LIPIcs.WABI.2023.19},
  annote =	{Keywords: RNA, MFE, Secondary Structure Prediction, Dangle, Sparsification, Space Complexity, Time Complexity}
}
Document
DOI: 10.4230/LIPIcs.WABI.2017.12
Sparsification Enables Predicting Kissing Hairpin Pseudoknot Structures of Long RNAs in Practice

Authors: Hosna Jabbari, Ian Wark, Carlo Montemagno, and Sebastian Will

Published in: LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)

Abstract
While computational RNA secondary structure prediction is an important tool in RNA research, it is still fundamentally limited to pseudoknot-free structures (or at best very simple pseudoknots) in practice. Here, we make the prediction of complex pseudoknots - including kissing hairpin structures - practically applicable by reducing the originally high space consumption. For this aim, we apply the technique of sparsification and other space-saving modifications to the recurrences of the pseudoknot prediction algorithm by Chen, Condon and Jabbari (CCJ algorithm). Thus, the theoretical space complexity of free energy minimization is reduced to Theta(n^3+Z), in the sequence length n and the number of non-optimally decomposable fragments ("candidates") Z. The sparsified CCJ algorithm, sparseCCJ, is presented in detail. Moreover, we provide and compare three generations of CCJ implementations, which continuously improve the space requirements: the original CCJ implementation, our first modified implementation, and our final sparsified implementation. The two latest implementations implement the established HotKnots DP09 energy model. In our experiments, using 244GB of RAM, the original CCJ implementation failed to handle sequences longer than 195 bases; sparseCCJ handles our pseudoknot data set (up to about length 400 bases) in this space limit. All three CCJ implementations are available at https://github.com/HosnaJabbari/CCJ.
Cite as

Hosna Jabbari, Ian Wark, Carlo Montemagno, and Sebastian Will. Sparsification Enables Predicting Kissing Hairpin Pseudoknot Structures of Long RNAs in Practice. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jabbari_et_al:LIPIcs.WABI.2017.12,
  author =	{Jabbari, Hosna and Wark, Ian and Montemagno, Carlo and Will, Sebastian},
  title =	{{Sparsification Enables Predicting Kissing Hairpin Pseudoknot Structures of Long RNAs in Practice}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{12:1--12:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Schwartz, Russell and Reinert, Knut},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.12},
  URN =		{urn:nbn:de:0030-drops-76408},
  doi =		{10.4230/LIPIcs.WABI.2017.12},
  annote =	{Keywords: RNA, secondary structure prediction, pseudoknots, space efficiency, sparsification}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact