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 7 articles )
Showing results 1 to 7 of 7.
- Chauve, Cedric; Courtiel, Julien; Ponty, Yann: Counting, generating, analyzing and sampling tree alignments (2018)
- Chiu, Jimmy Ka Ho; Dillon, Tharam S.; Chen, Yi-Ping Phoebe: Large-scale frequent stem pattern mining in RNA families (2018)
- Berkemer, Sarah J.; Höner zu Siederdissen, Christian; Stadler, Peter F.: Algebraic dynamic programming on trees (2017)
- Chauve, Cedric; Courtiel, Julien; Ponty, Yann: Counting, generating and sampling tree alignments (2016)
- Giegerich, Robert; Touzet, Hélène: Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems (2014)
- 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)