DiagAF

DiagAF computes a novel lower bound for edit distance using shift Hamming masks to serve as a pre-alignment filter that improves the accuracy and efficiency of sequence alignment.

Key Features:

• Novel lower bound of edit distance: DiagAF computes a new lower bound using shift Hamming masks, requiring fewer masks than SHD and MAGNET and incorporating information from the exchange of edit distance paths.
• Handling unequal length sequences: DiagAF supports alignment filtering for sequence pairs with unequal lengths.
• Early termination for true alignments: The algorithm includes an early-termination mechanism that halts computation when true alignments are detected.
• Demonstrated performance: Experimental comparisons reported lower error rates and reduced processing time relative to existing methods.

Scientific Applications:

• Comparative genomics: DiagAF's pre-alignment filtering can accelerate and improve pairwise sequence comparisons in comparative genomics.
• Phylogenetic studies: The filter can reduce computational burden while preserving alignment accuracy for phylogenetic analyses.
• Large-scale sequence analysis: DiagAF is applicable to workflows requiring many pairwise alignments by reducing verification costs.

Methodology:

DiagAF uses shift Hamming masks to establish a new lower bound for edit distance, optimizes the number of masks used, integrates path-exchange information, supports unequal-length sequence pairs, and applies early termination when true alignments are found.