Meta-Align

Meta-Align implements a hidden Markov model framework to align error-prone next-generation sequencing (NGS) reads in protein space while accounting for frameshifts and base quality scores.

Key Features:

• HMM-Based Framework: Uses a hidden Markov model to perform pairwise alignment in protein space rather than nucleotide space, accommodating frameshifts caused by insertions and deletions.
• Incorporation of Quality Scores: Integrates sequencing quality scores to better estimate sequencing errors and adjust alignment decisions.
• Dual Space Alignment: Operates across protein and DNA spaces via a pair HMM transducer combined with profile HMMs for all possible amino acid pairs, allowing consideration of translating frames and gap penalties.
• Optimal Alignment via Viterbi Algorithm: Applies the Viterbi algorithm to identify optimal alignments through the model that accounts for multiple translating frames and associated penalties.
• Computational Efficiency via Genetic Code Degeneracy: Exploits the degeneracy of the genetic code to reduce the number of HMM states and obtain a computationally feasible implementation.

Scientific Applications:

• Metagenomic read alignment: Aligns error-prone DNA sequences from metagenomic and other NGS datasets where insertion/deletion errors and frameshifts are prevalent.
• Improved downstream analyses: Produces more accurate alignments to increase the reliability of downstream genomic analyses and interpretations.
• Benchmarking and method comparison: Has been benchmarked on simulated reads based on BAliBASE and shown to outperform methods such as TBLASTX.

Methodology:

Constructs a pair HMM transducer alongside profile HMMs for amino acid pairs to enable alignment in protein space, incorporates sequencing quality scores, models and manages frameshifts and gap penalties across translating frames, applies the Viterbi algorithm for optimal alignment, and reduces state complexity by leveraging the degeneracy of the genetic code.