Predicting RNA secondary structures: One-grammar-fits-all solution

Menglu Li; Micheal Cheng; Yongtao Ye; Wk Hon; Hf Ting; Tw Lam; Cy Tang; Thomas Wong; Sm Yiu

doi:10.1007/978-3-319-19048-8_18

Predicting RNA secondary structures: One-grammar-fits-all solution

Menglu Li, Micheal Cheng, Yongtao Ye, Wk Hon, Hf Ting, Tw Lam, Cy Tang, Thomas Wong, Sm Yiu^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

1 Citation (Scopus)

Abstract

RNA secondary structures are known to be important in many biological processes. Many available programs have been developed for RNA secondary structure prediction. Based on our knowledge, however, there still exist secondary structures of known RNA sequences which cannot be covered by these algorithms. In this paper, we provide an efficient algorithm that can handle all RNA secondary structures found in Rfam database. We designed a new stochastic context-free grammar named Rectangle Tree Grammar (RTG) which significantly expands the classes of structures that can be modelled. Our algorithm runs in O(n⁶) time and the accuracy is reasonably high, with average PPV and sensitivity over 75%. In addition, the structures that RTG predicts are very similar to the real ones.

Original language	English
Title of host publication	Bioinformatics Research and Applications - 11th International Symposium, ISBRA 2015, Proceedings
Editors	Ion Măndoiu, Yaohang Li, Robert Harrison
Publisher	Springer Verlag
Pages	211-222
Number of pages	12
ISBN (Print)	9783319190471
DOIs	https://doi.org/10.1007/978-3-319-19048-8_18
Publication status	Published - 2015
Event	11th International Symposium on Bioinformatics Research and Applications, ISBRA 2015 - Norfolk, United States Duration: 7 Jun 2015 → 10 Jun 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9096
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Symposium on Bioinformatics Research and Applications, ISBRA 2015
Country/Territory	United States
City	Norfolk
Period	7/06/15 → 10/06/15

Access to Document

10.1007/978-3-319-19048-8_18

Cite this

Li, M., Cheng, M., Ye, Y., Hon, W., Ting, H., Lam, T., Tang, C., Wong, T., & Yiu, S. (2015). Predicting RNA secondary structures: One-grammar-fits-all solution. In I. Măndoiu, Y. Li, & R. Harrison (Eds.), Bioinformatics Research and Applications - 11th International Symposium, ISBRA 2015, Proceedings (pp. 211-222). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9096). Springer Verlag. https://doi.org/10.1007/978-3-319-19048-8_18

Li, Menglu ; Cheng, Micheal ; Ye, Yongtao et al. / Predicting RNA secondary structures : One-grammar-fits-all solution. Bioinformatics Research and Applications - 11th International Symposium, ISBRA 2015, Proceedings. editor / Ion Măndoiu ; Yaohang Li ; Robert Harrison. Springer Verlag, 2015. pp. 211-222 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{cddaa53ca7b84232b5e2764cb6fe4798,

title = "Predicting RNA secondary structures: One-grammar-fits-all solution",

abstract = "RNA secondary structures are known to be important in many biological processes. Many available programs have been developed for RNA secondary structure prediction. Based on our knowledge, however, there still exist secondary structures of known RNA sequences which cannot be covered by these algorithms. In this paper, we provide an efficient algorithm that can handle all RNA secondary structures found in Rfam database. We designed a new stochastic context-free grammar named Rectangle Tree Grammar (RTG) which significantly expands the classes of structures that can be modelled. Our algorithm runs in O(n6) time and the accuracy is reasonably high, with average PPV and sensitivity over 75\%. In addition, the structures that RTG predicts are very similar to the real ones.",

author = "Menglu Li and Micheal Cheng and Yongtao Ye and Wk Hon and Hf Ting and Tw Lam and Cy Tang and Thomas Wong and Sm Yiu",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 11th International Symposium on Bioinformatics Research and Applications, ISBRA 2015 ; Conference date: 07-06-2015 Through 10-06-2015",

year = "2015",

doi = "10.1007/978-3-319-19048-8\_18",

language = "English",

isbn = "9783319190471",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "211--222",

editor = "Ion M{\u a}ndoiu and Yaohang Li and Robert Harrison",

booktitle = "Bioinformatics Research and Applications - 11th International Symposium, ISBRA 2015, Proceedings",

address = "Germany",

}

Li, M, Cheng, M, Ye, Y, Hon, W, Ting, H, Lam, T, Tang, C, Wong, T & Yiu, S 2015, Predicting RNA secondary structures: One-grammar-fits-all solution. in I Măndoiu, Y Li & R Harrison (eds), Bioinformatics Research and Applications - 11th International Symposium, ISBRA 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9096, Springer Verlag, pp. 211-222, 11th International Symposium on Bioinformatics Research and Applications, ISBRA 2015, Norfolk, United States, 7/06/15. https://doi.org/10.1007/978-3-319-19048-8_18

Predicting RNA secondary structures: One-grammar-fits-all solution. / Li, Menglu; Cheng, Micheal; Ye, Yongtao et al.
Bioinformatics Research and Applications - 11th International Symposium, ISBRA 2015, Proceedings. ed. / Ion Măndoiu; Yaohang Li; Robert Harrison. Springer Verlag, 2015. p. 211-222 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9096).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

TY - GEN

T1 - Predicting RNA secondary structures

T2 - 11th International Symposium on Bioinformatics Research and Applications, ISBRA 2015

AU - Li, Menglu

AU - Cheng, Micheal

AU - Ye, Yongtao

AU - Hon, Wk

AU - Ting, Hf

AU - Lam, Tw

AU - Tang, Cy

AU - Wong, Thomas

AU - Yiu, Sm

PY - 2015

Y1 - 2015

N2 - RNA secondary structures are known to be important in many biological processes. Many available programs have been developed for RNA secondary structure prediction. Based on our knowledge, however, there still exist secondary structures of known RNA sequences which cannot be covered by these algorithms. In this paper, we provide an efficient algorithm that can handle all RNA secondary structures found in Rfam database. We designed a new stochastic context-free grammar named Rectangle Tree Grammar (RTG) which significantly expands the classes of structures that can be modelled. Our algorithm runs in O(n6) time and the accuracy is reasonably high, with average PPV and sensitivity over 75%. In addition, the structures that RTG predicts are very similar to the real ones.

AB - RNA secondary structures are known to be important in many biological processes. Many available programs have been developed for RNA secondary structure prediction. Based on our knowledge, however, there still exist secondary structures of known RNA sequences which cannot be covered by these algorithms. In this paper, we provide an efficient algorithm that can handle all RNA secondary structures found in Rfam database. We designed a new stochastic context-free grammar named Rectangle Tree Grammar (RTG) which significantly expands the classes of structures that can be modelled. Our algorithm runs in O(n6) time and the accuracy is reasonably high, with average PPV and sensitivity over 75%. In addition, the structures that RTG predicts are very similar to the real ones.

UR - https://www.scopus.com/pages/publications/84944527480

U2 - 10.1007/978-3-319-19048-8_18

DO - 10.1007/978-3-319-19048-8_18

M3 - Conference Paper

AN - SCOPUS:84944527480

SN - 9783319190471

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 211

EP - 222

BT - Bioinformatics Research and Applications - 11th International Symposium, ISBRA 2015, Proceedings

A2 - Măndoiu, Ion

A2 - Li, Yaohang

A2 - Harrison, Robert

PB - Springer Verlag

Y2 - 7 June 2015 through 10 June 2015

ER -

Li M, Cheng M, Ye Y, Hon W, Ting H, Lam T et al. Predicting RNA secondary structures: One-grammar-fits-all solution. In Măndoiu I, Li Y, Harrison R, editors, Bioinformatics Research and Applications - 11th International Symposium, ISBRA 2015, Proceedings. Springer Verlag. 2015. p. 211-222. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-19048-8_18

Predicting RNA secondary structures: One-grammar-fits-all solution

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this