GS-Aligner

GS-Aligner aligns genomic sequences using bit-level operations to enable efficient comparison of very long sequences and to detect complex genomic rearrangements such as translocations and inversions.

Key Features:

• Bit-Level Coding: Represents and manipulates sequences at the bit level to reduce memory footprint and accelerate operations.
• Efficiency and Scalability: Optimizes time and space usage for aligning very long genomic sequences common in large-scale genomic studies.
• Alignment Anchors: Searches for matching segments between sequences to establish reliable alignment anchors.
• Longest Increasing Subsequence (LIS): Applies the LIS algorithm to identify and optimize the longest consistent chain of matches.
• Optimal Local Alignment: Computes high-quality local alignments focused on optimal matching regions within sequences.
• Divergent Sequence Alignment: Handles fairly divergent sequences, including comparisons between species such as human and mouse.
• Detection of Complex Rearrangements: Identifies genomic rearrangements including translocations and inversions.
• Empirical Performance on Divergent Genomes: Reported to outperform existing methods when aligning relatively divergent sequences, including comparisons across different mammalian orders and between a mammal and a nonmammalian vertebrate.

Scientific Applications:

• Comparative Genomics: Alignment of genomic sequences between species (e.g., human and mouse) for evolutionary and functional analyses.
• Structural Variation Analysis: Detection and characterization of translocations and inversions in genome assemblies.
• Large-Scale Genome Alignment: Alignment tasks in large-scale genomic studies that require handling of very long sequences.

Methodology:

Uses bit-level coding, searches for matching segments to establish alignment anchors, applies the Longest Increasing Subsequence (LIS) algorithm to optimize chains of matches, and computes optimal local alignments.