A genome alignment algorithm based on compression.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Traditional genome alignment methods, based on string edit distance, are computationally intensive and struggle with low-information regions.
• Existing methods lack a robust objective function for parameter optimization.
• Genomic sequences inherently contain genetic information that can be leveraged for alignment.

Purpose of the Study:

• To propose an information-theoretic approach for pairwise genome local alignment.
• To develop a novel method, XMAligner, that considers the information content of nucleotides.
• To address the limitations of conventional character-matching alignment algorithms.

Main Methods:

• XMAligner utilizes an information-theoretic framework for local genome alignment.
• It assesses nucleotide relationships based on significant mutual information within their context.
• Nucleotide information content is quantified using a lossless compression technique.

Main Results:

• XMAligner demonstrates superior performance compared to conventional methods, particularly for distantly related and statistically biased genomic data.
• The method efficiently aligns large eukaryotic genomes with moderate hardware.
• XMAligner incorporates an objective function that minimizes the need for manual parameter tuning.

Conclusions:

• The information-theoretic approach effectively overcomes the drawbacks of traditional alignment methods.
• Leveraging the information content of nucleotides enhances the accuracy and efficiency of genomic sequence alignment.