1 Search Results for "Montemagno, Carlo"

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-dev.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}
}
  • Refine by Author
  • 1 Jabbari, Hosna
  • 1 Montemagno, Carlo
  • 1 Wark, Ian
  • 1 Will, Sebastian

  • Refine by Classification

  • Refine by Keyword
  • 1 RNA
  • 1 pseudoknots
  • 1 secondary structure prediction
  • 1 space efficiency
  • 1 sparsification

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact