Local similarity in RNA secondary structures.

Höchsmann M, Töller T, Giegerich R, Kurtz S (2003)
Proc IEEE Comput Soc Bioinform Conf 2.

Journal Article | Published | English

No fulltext has been uploaded

Author
; ; ;
Abstract
We present a systematic treatment of alignment distance and local similarity algorithms on trees and forests. We build upon the tree alignment algorithm for ordered trees given by Jiang et. al (1995) and extend it to calculate local forest alignments, which is essential for finding local similar regions in RNA secondary structures. The time complexity of our algorithm is O(|F(1)| |F(2) deg(F(1)) deg(F(2)) (deg(F(1)) + deg(F(2))) where |F(i)| is the number of nodes in forest F(i) and deg (F(i)) is the degree of F(i). We provide carefully engineered dynamic programming implementations using dense, two-dimensional tables which considerably reduces the space requirement. We suggest a new representation of RNA secondary structures as forests that allow reasonable scoring of edit operations on RNA secondary structures. The comparison of RNA secondary structures is facilitated by a new visualization technique for RNA secondary structure alignments. Finally, we show how potential regulatory motifs can be discovered solely by their structural preservation, and independent of their sequence conservation and position.
Publishing Year
ISSN
PUB-ID

Cite this

Höchsmann M, Töller T, Giegerich R, Kurtz S. Local similarity in RNA secondary structures. Proc IEEE Comput Soc Bioinform Conf. 2003;2.
Höchsmann, M., Töller, T., Giegerich, R., & Kurtz, S. (2003). Local similarity in RNA secondary structures. Proc IEEE Comput Soc Bioinform Conf, 2.
Höchsmann, M., Töller, T., Giegerich, R., and Kurtz, S. (2003). Local similarity in RNA secondary structures. Proc IEEE Comput Soc Bioinform Conf 2.
Höchsmann, M., et al., 2003. Local similarity in RNA secondary structures. Proc IEEE Comput Soc Bioinform Conf, 2.
M. Höchsmann, et al., “Local similarity in RNA secondary structures.”, Proc IEEE Comput Soc Bioinform Conf, vol. 2, 2003.
Höchsmann, M., Töller, T., Giegerich, R., Kurtz, S.: Local similarity in RNA secondary structures. Proc IEEE Comput Soc Bioinform Conf. 2, (2003).
Höchsmann, Matthias, Töller, Thomas, Giegerich, Robert, and Kurtz, Stefan. “Local similarity in RNA secondary structures.”. Proc IEEE Comput Soc Bioinform Conf 2 (2003).
This data publication is cited in the following publications:
This publication cites the following data publications:

26 Citations in Europe PMC

Data provided by Europe PubMed Central.

Export

0 Marked Publications

Open Data PUB

Sources

PMID: 16452790
PubMed | Europe PMC

Search this title in

Google Scholar