Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs

Theis C, Janssen S, Giegerich R (2010)
In: Algorithms in Bioinformatics. 10th international workshop (WABI 2010), proceedings. Moulton V, Singh M (Eds); Lecture Notes in Bioinformatics, 6293. Berlin: Springer: 52-64.

Download
OA
Conference Paper | Published | English
Author
Editor
Moulton, Vincent ; Singh, Mona
Abstract
We present three heuristic strategies for folding RNA sequences into secondary structures including kissing hairpin motifs. The new idea is to construct a kissing hairpin motif from an overlay of two simple canonical pseudoknots. The difficulty is that the overlay does not satisfy Bellman's Principle of Optimality, and the kissing hairpin cannot simply be built from optimal pseudoknots. Our strategies have time/space complexities of O(n^4)/O(n^2), O(n^4)/O(n^3), and O(n^5)/O(n^2). All strategies have been implemented in the program pKiss and were evaluated against known structures. Surprisingly, our simplest strategy performs best. As it has the same complexity as the previous algorithm for simple pseudoknots, the overlay idea opens a way to construct a variety of practically useful algorithms for pseudoknots of higher topological complexity within O(n^4) time and O(n^2) space.
Publishing Year
Conference
10th International Workshop, WABI 2010
Location
Liverpool, UK
Conference Date
2010-09-06 – 2010-09-08
ISSN
PUB-ID

Cite this

Theis C, Janssen S, Giegerich R. Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs. In: Moulton V, Singh M, eds. Algorithms in Bioinformatics. 10th international workshop (WABI 2010), proceedings. Lecture Notes in Bioinformatics. Vol 6293. Berlin: Springer; 2010: 52-64.
Theis, C., Janssen, S., & Giegerich, R. (2010). Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs. In V. Moulton & M. Singh (Eds.), Lecture Notes in Bioinformatics: Vol. 6293. Algorithms in Bioinformatics. 10th international workshop (WABI 2010), proceedings (pp. 52-64). Berlin: Springer. doi:10.1007/978-3-642-15294-8_5
Theis, C., Janssen, S., and Giegerich, R. (2010). “Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs” in Algorithms in Bioinformatics. 10th international workshop (WABI 2010), proceedings, Moulton, V., and Singh, M. eds. Lecture Notes in Bioinformatics, vol. 6293, (Berlin: Springer), 52-64.
Theis, C., Janssen, S., & Giegerich, R., 2010. Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs. In V. Moulton & M. Singh, eds. Algorithms in Bioinformatics. 10th international workshop (WABI 2010), proceedings. Lecture Notes in Bioinformatics. no.6293 Berlin: Springer, pp. 52-64.
C. Theis, S. Janssen, and R. Giegerich, “Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs”, Algorithms in Bioinformatics. 10th international workshop (WABI 2010), proceedings, V. Moulton and M. Singh, eds., Lecture Notes in Bioinformatics, vol. 6293, Berlin: Springer, 2010, pp.52-64.
Theis, C., Janssen, S., Giegerich, R.: Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs. In: Moulton, V. and Singh, M. (eds.) Algorithms in Bioinformatics. 10th international workshop (WABI 2010), proceedings. Lecture Notes in Bioinformatics. 6293, p. 52-64. Springer, Berlin (2010).
Theis, Corinna, Janssen, Stefan, and Giegerich, Robert. “Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs”. Algorithms in Bioinformatics. 10th international workshop (WABI 2010), proceedings. Ed. Vincent Moulton and Mona Singh. Berlin: Springer, 2010.Vol. 6293. Lecture Notes in Bioinformatics. 52-64.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Last Uploaded
2017-06-07T09:20:47Z

This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Search this title in

Google Scholar
ISBN Search