ASPRAlign

ASPRAlign aligns and compares RNA secondary structures, including pseudoknots, by converting structures into algebraic tree representations to quantify structural similarity.

Key Features:

• Algebraic RNA Trees: Constructs Algebraic RNA Trees that abstract structural relationships from the primary nucleotide sequence to represent RNA secondary structure including pseudoknots.
• Structural RNA Trees: Generates Structural RNA Trees as an alternative abstraction for comparing RNA secondary structures.
• ASPRA Distance Calculation: Computes the ASPRA distance, a metric that quantifies dissimilarity between two RNA structures, including complex topologies with pseudoknots.
• Efficient Algorithm: Employs an alignment algorithm with worst-case time complexity O(n^2), where n is the number of nucleotides in the longer RNA structure.
• Java Implementation: Implemented in Java for integration within computational workflows.

Scientific Applications:

• Viral RNA analysis: Enables comparison of viral RNAs that commonly contain pseudoknots to study structural determinants of function.
• Ribosomal RNA analysis: Supports analysis of ribosomal RNAs with complex secondary structures for structural and functional investigations.
• Regulatory and catalytic RNA study: Facilitates investigation of RNAs involved in regulatory processes and catalytic functions by comparing structural architectures.
• Comparative structural genomics: Provides quantitative measures (ASPRA distance) to assess evolutionary relationships, functional conservation, and to aid identification of novel RNA motifs.

Methodology:

Converts RNA secondary structures into algebraic tree representations and compares them using a specialized alignment algorithm to compute the ASPRA distance, operating with worst-case time complexity O(n^2) and focusing on structural rather than sequence information.