lara

lara performs sequence-structure alignment of RNA by integrating sequence and secondary-structure information using a graph-based integer linear programming formulation to improve alignments for low-homology RNAs.

Key Features:

• Graph-Based Representation: LARA represents sequence-structure alignments as a graph and formulates the alignment problem as an integer linear program (ILP) to integrate sequence and structural information.
• Integer Linear Programming (ILP): The alignment problem is expressed as an ILP to enable precise modeling of sequence-structure constraints.
• Combinatorial Optimization Techniques: LARA applies combinatorial optimization methods to compute optimal or near-optimal solutions to the ILP, enabling handling of multiple input sequences.
• Low-Homology Alignment Focus: The method is targeted at improving alignments for low-homology RNAs by explicitly incorporating structural information.
• Benchmark Performance: LARA has been evaluated on a recently published RNA alignment benchmark set and shows superior alignment quality that increases with the number of input sequences.

Scientific Applications:

• Functional non-coding RNA analysis: Produces improved sequence-structure alignments for studies of functional non-coding RNAs.
• RNA function and interaction inference: Supports elucidation of RNA functions and interactions through more accurate alignments.
• Comparative RNA alignment studies: Facilitates comparative analyses across multiple RNA sequences, with scalability as sequence count increases.

Methodology:

Uses a graph-based representation formulated as an integer linear program (ILP) and solves the ILP with combinatorial optimization methods; performance was evaluated on a published RNA alignment benchmark set.