Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs

Theis, Corinna; Janssen, Stefan; Giegerich, Robert

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.

Konferenzbeitrag | Veröffentlicht | Englisch

Download

TheisJanssenGiegerich2010_pkiss

DOI

https://doi.org/10.1007/978-3-642-15294-8_5

URN

urn:nbn:de:0070-bipr-46297

Autor*in

Theis, Corinna; Janssen, Stefan^UniBi ; Giegerich, Robert^UniBi

Herausgeber*in

Moulton, Vincent; Singh, Mona

Einrichtung

Centrum für Biotechnologie > Institut für Bioinformatik
Centrum für Biotechnologie > Arbeitsgruppe R. Giegerich
Technische Fakultät > AG Praktische Informatik

Abstract / Bemerkung

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.

Erscheinungsjahr

2010

Titel des Konferenzbandes

Algorithms in Bioinformatics. 10th international workshop (WABI 2010), proceedings

Serien- oder Zeitschriftentitel

Lecture Notes in Bioinformatics

Band

6293

Seite(n)

52-64

Konferenz

10th International Workshop, WABI 2010

Konferenzort

Liverpool, UK

Konferenzdatum

2010-09-06 – 2010-09-08

ISBN

978-3-642-15293-1, 978-3-642-15294-8

ISSN

0302-9743

Page URI

https://pub.uni-bielefeld.de/record/1894008

Zitieren

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. https://doi.org/10.1007/978-3-642-15294-8_5

Theis, Corinna, Janssen, Stefan, and Giegerich, Robert. 2010. “Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs”. In Algorithms in Bioinformatics. 10th international workshop (WABI 2010), proceedings, ed. Vincent Moulton and Mona Singh, 6293:52-64. Lecture Notes in Bioinformatics. Berlin: Springer.

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.

Alle Dateien verfügbar unter der/den folgenden Lizenz(en):

Copyright Statement: