LGSFAligner

LGSFAligner computes optimal local alignments between two RNA secondary structures represented as labeled ordered forests to identify similar substructures, including gapped subforests, for motif discovery.

Key Features:

• Local Alignment of Labeled Ordered Forests: Computes optimal local alignments between two labeled ordered forests that represent RNA secondary structures to detect similar substructures (motifs).
• Gapped Subforest Alignment: Generalizes closed subforest alignments to gapped subforests to enable alignment of structurally variant substructures.
• Algorithmic Efficiency: Implements a novel algorithm for optimal local gapped subforest alignments with improved time and space complexity compared to prior algorithms for closed subforest alignments.
• Application to Local Sequence-Structure Alignment (lssa): Provides a specialized modification of the core algorithm that addresses the local sequence-structure alignment (lssa) case much faster than previously proposed methods.

Scientific Applications:

• Motif Discovery: Identifies frequently occurring substructures within RNA secondary structures to infer functional similarities and evolutionary relationships.
• Structural Analysis: Enables detailed comparison of structural motifs across RNA sequences to analyze RNA function and interactions.
• Comparative Genomics: Supports comparative studies by aligning RNA secondary structures to explore genetic variation effects on structure and function.

Methodology:

Computes optimal local alignments between labeled ordered forests using an algorithm that generalizes closed subforests to gapped subforests and includes a modified, performance‑optimized variant for the lssa special case.