Forest alignment with affine gaps and anchors, applied in RNA structure comparison

Schirmer S, Giegerich R (2013)
Theoretical Computer Science 483: 51-67.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Abstract / Bemerkung
We present two enhancements to Jiang's tree alignment algorithm, motivated by experience with its use for RNA structure alignment. One enhancement is the introduction of an affine gap model, which can be accommodated with a runtime increase by a constant factor. The second enhancement is a speed-up of the alignment algorithm when certain nodes in the trees are pre-aligned by a so-called anchoring. Both enhancements are included in a new implementation of the tool RNAFORESTER. We evaluate the new algorithm with two applications related to RNA secondary structure analysis. Based on our experience, we suggest a new formulation of the tree alignment model, based on regular tree languages and rewrite rules. (C) 2012 Elsevier B.V. All rights reserved.
Stichworte
Forest alignment; Affine gap costs; alignment; Anchored; RNA structure alignment
Erscheinungsjahr
2013
Zeitschriftentitel
Theoretical Computer Science
Band
483
Seite(n)
51-67
ISSN
0304-3975
Page URI
https://pub.uni-bielefeld.de/record/2607289

Zitieren

Schirmer S, Giegerich R. Forest alignment with affine gaps and anchors, applied in RNA structure comparison. Theoretical Computer Science. 2013;483:51-67.
Schirmer, S., & Giegerich, R. (2013). Forest alignment with affine gaps and anchors, applied in RNA structure comparison. Theoretical Computer Science, 483, 51-67. doi:10.1016/j.tcs.2012.07.040
Schirmer, S., and Giegerich, R. (2013). Forest alignment with affine gaps and anchors, applied in RNA structure comparison. Theoretical Computer Science 483, 51-67.
Schirmer, S., & Giegerich, R., 2013. Forest alignment with affine gaps and anchors, applied in RNA structure comparison. Theoretical Computer Science, 483, p 51-67.
S. Schirmer and R. Giegerich, “Forest alignment with affine gaps and anchors, applied in RNA structure comparison”, Theoretical Computer Science, vol. 483, 2013, pp. 51-67.
Schirmer, S., Giegerich, R.: Forest alignment with affine gaps and anchors, applied in RNA structure comparison. Theoretical Computer Science. 483, 51-67 (2013).
Schirmer, Stefanie, and Giegerich, Robert. “Forest alignment with affine gaps and anchors, applied in RNA structure comparison”. Theoretical Computer Science 483 (2013): 51-67.