Forest alignment with affine gaps and anchors. We present two enhancements to T. Jiang et al.’s tree alignment algorithm [Theor. Comput. Sci. 143, No. 1, 137–148 (1995; Zbl 0873.68150)], 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 also argue that tree alignment should be parameterized by a user-described set of edit operations, generalizing over the traditional, atomic edit operations.
Keywords for this software
References in zbMATH (referenced in 3 articles )
Showing results 1 to 3 of 3.
- Chauve, Cedric; Courtiel, Julien; Ponty, Yann: Counting, generating and sampling tree alignments (2016)
- Schirmer, Stefanie; Giegerich, Robert: Forest alignment with affine gaps and anchors, applied in RNA structure comparison (2013)
- Schirmer, Stefanie; Giegerich, Robert: Forest alignment with affine gaps and anchors (2011)