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.

References in zbMATH (referenced in 1 article )

Showing result 1 of 1.
Sorted by year (citations)

  1. Schirmer, Stefanie; Giegerich, Robert: Forest alignment with affine gaps and anchors (2011)