Sequence Alignment

Sequence alignment is the process of arranging two or more sequences—of DNA, RNA or proteins—to identify regions of similarity, inserting “gaps” where needed so that equivalent positions line up. Those similar regions can reveal functional, structural or evolutionary relationships between the sequences. It is a central task of bioinformatics.

Types

Two main approaches are distinguished. Global alignment aligns the full sequences end to end, and is useful when they are similar and of comparable length. Local alignment looks for the most similar subregions within sequences that, overall, may be very different, and serves to locate conserved domains or motifs. Alignment can also be pairwise (two sequences) or multiple (three or more at once).

Algorithms

The classic algorithms are based on dynamic programming: the Needleman-Wunsch algorithm (1970) for global alignment and the Smith-Waterman algorithm (1981) for local, both with scores that reward matches and penalize gaps. To compare against huge databases, where exhaustive dynamic programming is infeasible, faster, approximate heuristics such as BLAST and FASTA are used.

Its relation to AI

Sequence alignment is a canonical example of dynamic programming, and today it has a direct connection to AI: deep-learning methods that predict protein structure, such as AlphaFold, use multiple sequence alignments as input, from which they extract the patterns of coevolution between residues. Moreover, aligning biological sequences is, at bottom, the same problem as comparing text strings via edit distance.