Abstract Sequence alignment provides a formal framework for comparison of biological sequences through score maximization over matches, mismatches, and insertion–deletion events. Classical formulations distinguish between global alignment, which enforces end-to-end correspondence through fixed boundary conditions, and local alignment, which extracts high-scoring subsequences without global consistency. Both paradigms arise from the same dynamic programing (DP) recurrences, shaped by substitution matrices and gap-penalty models that approximate molecular evolution. Canonical algorithms such as Needleman–Wunsch and Smith–Waterman establish the foundations of exact alignment, while later extensions introduce affine and convex gap costs, statistical score distributions, and probabilistic significance models. Modern work builds on these principles through bit-parallel techniques, band-restricted computation, cache-aware layouts, single instruction, multiple data and graphics processing unit parallelism, hardware accelerators, and index-assisted heuristics that enable large-scale genomic analysis. Sequence alignment underpins applications ranging from whole-genome comparison and metagenomics to protein annotation, variant detection, human leukocyte antigen typing, and microbial surveillance. Persistent challenges include scalability to ultra-long sequences, faithful models of complex mutation processes, avoidance of parameter bias, and formal limits on exact subquadratic solutions. Emerging directions emphasize adaptive data-driven scoring, hybrid global–local formulations, privacy-preserving computation, and real-time or incremental alignment. These developments reaffirm sequence alignment as a closely related DP framework shaped primarily by boundary conditions rather than distinct paradigms.
Gagniuc et al. (Fri,) studied this question.