Multiple sequence alignment

A multiple sequence alignment (MSA) arranges three or more biological sequences, usually proteins, DNA or RNA, in a grid so that residues placed in the same column are treated as descendants of the same position in a common ancestor. Gaps are inserted to absorb insertions and deletions. The alignment is not an end in itself: it is the input to almost everything else done with sequence data, including phylogenetic tree building, profile and motif construction, homology search, functional site annotation, and the detection of correlated mutations. Since 2021 it has also been the main evolutionary input to deep learning structure predictors, whose accuracy degrades as the input alignment gets shallower ^[29].

Computing an optimal alignment of many sequences at once is intractable in the general case, so essentially all practical MSA software is heuristic ^[4]. The field has therefore accumulated a long series of programs with different tradeoffs, from CLUSTAL in 1988 through MUSCLE, MAFFT and Clustal Omega to the GPU-accelerated search pipelines that feed AlphaFold and its open reproductions.

The alignment problem

Scoring

An alignment is only as meaningful as the objective it optimizes. The standard objective is the sum-of-pairs (SP) score: the alignment is scored by summing the scores of all induced pairwise alignments, where each aligned residue pair contributes a substitution matrix score and each gap contributes a penalty. Substitution matrices supply the per-pair scores. The PAM family derived them from an evolutionary rate model; BLOSUM, introduced by Steven and Jorja Henikoff in 1992, derived them instead from roughly 2,000 blocks of aligned segments covering more than 500 groups of related proteins, which the authors reported produced marked improvements in alignments and in database searches ^[27].

Gap handling matters as much as residue scoring. Real insertions and deletions are usually multi-residue events, so affine penalties (a large cost to open a gap plus a smaller cost per residue to extend it) fit biology better than a flat per-residue cost. Later programs made the penalties position dependent: CLUSTAL W reduced gap penalties in hydrophilic stretches, to push new gaps into loops rather than through secondary structure elements, and reduced them further at positions where a gap had already been opened ^[7].

Complexity

The pairwise case is solved exactly. Saul Needleman and Christian Wunsch published the dynamic programming recursion for global pairwise alignment in 1970 ^[1], and Temple Smith and Michael Waterman adapted it to local alignment in 1981 by allowing the score to reset to zero, so that the best-matching subsegments are recovered rather than the best end-to-end correspondence ^[2].

The direct generalization to k sequences fills a k-dimensional dynamic programming lattice, which costs on the order of n^k time and space for sequences of length n and becomes unusable past a handful of sequences. Humberto Carrillo and David Lipman showed in 1988 that the region of that lattice which can contain an optimal sum-of-pairs alignment is bounded by the pairwise alignment scores, which makes exact alignment feasible for small numbers of closely related sequences ^[3]. The general problem is harder than that bound suggests: Lusheng Wang and Tao Jiang proved in 1994 that multiple alignment with the SP score is NP-complete and that multiple tree alignment is MAX SNP-hard ^[4]. Every widely used aligner is therefore a heuristic, and different heuristics give different answers on the same input.

Progressive alignment and the CLUSTAL lineage

The dominant heuristic is progressive alignment. Da-Fei Feng and Russell Doolittle described it in 1987: estimate pairwise distances, build a guide tree, then align sequences and growing profiles in the order the tree suggests, starting with the most similar pairs. Their rule "once a gap, always a gap" fixes gaps introduced early in the process so that later steps cannot reopen them ^[5]. The method is fast and gives good results when the guide tree is roughly right, but it is greedy: an error made early is never revisited.

Desmond Higgins and Paul Sharp packaged the approach as CLUSTAL in 1988, explicitly targeting the microcomputers then available to biologists ^[6]. CLUSTAL W, published in 1994 by Julie Thompson, Higgins and Toby Gibson, made the progressive method substantially more sensitive on divergent proteins through four changes: individual sequence weights that down-weight near-duplicates and up-weight divergent sequences, substitution matrices varied by the divergence of the sequences being merged, residue-specific and locally reduced gap penalties, and reduced penalties at positions where gaps had already opened ^[7]. Clustal X added a graphical interface to the same program in 1997 ^[8], and both programs were completely rewritten in C++ as version 2.0 in 2007 ^[9].

Clustal Omega, released in 2011 by Fabian Sievers and colleagues, was the response to data sets of many thousands of sequences, which the authors described as becoming a bottleneck for progressive methods. It aligns very large protein sets quickly with accuracy comparable to slower high-quality aligners on small benchmarks, and it can add sequences to an existing alignment and exploit precomputed alignment information from resources such as Pfam ^[10].

Consistency, iteration and phylogeny awareness

Three lines of work attacked the greediness of the progressive heuristic from different directions.

Consistency-based methods precompute information about all pairs and use it to constrain the progressive merge. Cedric Notredame, Higgins and Jaap Heringa introduced T-Coffee in 2000, which builds a library of pairwise alignments (optionally mixing local and global alignments, different programs, or structural superpositions) and then aligns so that each intermediate step is consistent with how all the other sequences align to each other ^[11]. Chuong Do and colleagues formalized the idea probabilistically in ProbCons in 2005, scoring candidate alignments by probabilistic consistency and reporting statistically significant improvements over leading methods on the BAliBASE, SABmark and PREFAB benchmarks ^[16].

Iterative refinement instead repairs an initial alignment by repeatedly splitting it and realigning the parts. Robert Edgar's MUSCLE, published in 2004, combined k-mer distance estimation, a progressive pass using a profile score he called log-expectation, and refinement by tree-dependent restricted partitioning. He reported that MUSCLE ranked highest or joint highest for accuracy on BAliBASE, SABmark, SMART and the PREFAB benchmark he introduced with it, and that it aligned 5,000 sequences of average length 350 in seven minutes on a 2004 desktop ^[12]. Kazutaka Katoh's MAFFT, published in 2002, found homologous regions with a fast Fourier transform after converting each residue to volume and polarity values, and shipped both a progressive mode (FFT-NS-2) and an iterative refinement mode (FFT-NS-i) ^[14]. MAFFT version 7, described in 2013, added options for adding unaligned sequences to an existing alignment, adjusting strand direction in nucleotide alignment, constrained alignment, and parallel processing ^[15].

Phylogeny-aware alignment addresses a systematic bias rather than a search failure. Ari Loytynoja and Nick Goldman argued in 2008 that traditional aligners ignore the phylogenetic implications of the gap patterns they create, and consequently infer alignments with too many deletions and substitutions, too few insertions, and implausible histories of insertion and deletion events. Their method distinguishes insertions from deletions as separate evolutionary events, which they showed improves alignment quality and downstream analysis ^[17].

Edgar returned to the bias question in 2022 with Muscle5, which does not produce one alignment at all. It perturbs a hidden Markov model and permutes the guide tree to construct an ensemble of alignments with diverse biases, and confidence in a downstream inference is read off as the fraction of the ensemble that supports it. Applied to phylogenetics, Edgar reported that ensembles can resolve topologies that standard bootstrapping leaves uncertain and can show that some high-bootstrap topologies are wrong ^[13].

Profiles, hidden Markov models and homology search

Once an alignment exists, it can be summarized as a profile: per-column residue frequencies plus per-column insertion and deletion statistics. The probabilistic form of that summary is the profile hidden Markov model, introduced for protein modelling by Anders Krogh, Michael Brown, Saira Mian, Kimmen Sjolander and David Haussler in 1994 ^[18] and reviewed by Sean Eddy in 1998 ^[19]. Profile HMMs turn an alignment into a statistical model that can score arbitrary new sequences, which is the basis of the Pfam family database ^[35] and of the HMMER software. HMMER3, described by Eddy in 2011, made profile HMM search fast enough for routine use through a heuristic acceleration filter ^[20].

Search and alignment are circular in practice: better search finds more homologs, which deepens the alignment, which builds a better profile, which finds more homologs. PSI-BLAST, published by Stephen Altschul and colleagues in 1997, made that loop standard by iterating BLAST with a position-specific scoring matrix rebuilt from each round's hits ^[23]. Johannes Soding took the idea further in 2005 by comparing a query profile HMM against database profile HMMs rather than against plain sequences, which is more sensitive for remote homology ^[21]. Michael Remmert, Andreas Biegert, Andreas Hauser and Soding built HHblits on that basis in 2012: an iterative HMM-to-HMM search with a discretized-profile prefilter that they reported is faster than PSI-BLAST, 50 to 100 percent more sensitive, and produces more accurate alignments ^[22].

Throughput became the constraint once alignments were needed for millions of queries. Martin Steinegger and Soding released MMseqs2 in 2017 for sensitive protein search over massive data sets ^[24], and a GPU implementation followed in 2025: Felix Kallenborn and colleagues reported six times faster single-protein searches than CPU methods running on 2 x 64 cores, and a 31.8-fold acceleration of structure prediction with ColabFold relative to the standard AlphaFold2 pipeline ^[25].

MSAs in protein structure prediction

Why the alignment carries structural information

Columns in a deep MSA are not independent. If two residues are in contact in the folded protein, a mutation at one position tends to be compensated by a mutation at the other, so the two columns covary. Naive correlation statistics conflate direct and indirect coupling; direct-coupling analysis, applied at scale by Faruck Morcos and colleagues in 2011, separates them and recovers native residue contacts across many protein families from sequence alignments alone ^[31]. Contact prediction from coevolution was the bridge between alignment and structure that deep learning systems later absorbed into end-to-end models.

The AlphaFold 2 pipeline

AlphaFold 2 takes a query sequence and an MSA as input and processes both in its Evoformer trunk ^[29]. Producing that MSA is a substantial pipeline in its own right. The released code runs jackhmmer (the iterative HMMER search) against UniRef90 and against MGnify, and runs HHblits against the Big Fantastic Database (BFD) combined with UniRef30, formerly Uniclust30 ^[36]; a separate HHsearch pass against PDB70 supplies structural templates. The databases are large: the reference download script lists BFD at roughly 1.8 TB unpacked, and the full database set runs to several terabytes ^[30].

This is why MSA generation, not neural network inference, dominates the wall-clock cost of a single AlphaFold 2 prediction on a workstation. ColabFold, published by Milot Mirdita and colleagues in 2022, replaced the pipeline with an MMseqs2-based homology search and reported a 40 to 60 fold faster search, which together with optimized model use allowed close to 1,000 structures per day on a server with one GPU ^[26].

The AlphaFold 3 generation kept MSAs. The OpenFold consortium's OpenFold3 preview 2 technical report describes its standard pipeline as JackHMMER searches against UniRef90, UniProt and MGnify plus HHblits against an updated BFD, with a faster ColabFold and MMseqs2 route as an alternative ^[37]. NVIDIA ships the search step as a BioNeMo microservice, the MSA-Search NIM, which runs GPU-accelerated MMseqs2, offers both the AlphaFold 2 single-pass search style and the cascaded ColabFold style, and adds paired MSA search that pairs homologs by species across the chains of a complex so that cross-chain coevolutionary signal is preserved ^[38].

Alignment depth, pairing and quality

For structure prediction the useful measure of an MSA is not the raw number of rows but the effective number of independent sequences, since near-duplicates add little information. The retraining experiments behind OpenFold established how sensitive AlphaFold-class models are to their training and input distributions, and OpenProteinSet, the companion corpus released with it, published more than 16 million precomputed alignments precisely so that this dependence could be studied and so that models could be retrained rather than only run ^[33][34].

Complex prediction adds a pairing problem. For a heteromeric complex, the alignment for each chain must be paired so that rows come from the same organism, otherwise the coevolutionary signal across the interface is destroyed. The 2026 expansion of the AlphaFold Protein Structure Database to protein complexes illustrates both the scale and the shortcuts involved: MSAs for about 23 million homodimers were generated with GPU-accelerated MMseqs2 against UniRef100, restricted to the best hit per taxon as what the authors call a pragmatic orthology filter, while heterodimer alignments were formed by concatenating previously generated homodimer alignments without pairing ^[39].

Models that skip the alignment

Not every structure predictor needs an MSA. ESMFold, described by Zeming Lin and colleagues in 2023, replaces the alignment with the internal representations of a large protein language model and folds directly from a single sequence, which removes the search step entirely and makes prediction possible for sequences with no detectable homologs, such as designed proteins ^[32].

Benchmarks and the accuracy question

Alignment accuracy is normally measured against reference alignments built from superposed experimental structures, on the argument that structural equivalence is the closest available proxy for true homology. BAliBASE, released by Thompson, Frederic Plewniak and Olivier Poch in 1999, was the first widely adopted benchmark of this kind ^[28], and SABmark, SMART-derived sets and Edgar's PREFAB followed ^[12]. Benchmarks of this type have known weaknesses: reference sets are biased toward families with solved structures, structurally superposable does not always mean evolutionarily homologous, and scores on one benchmark do not always transfer to another. That is part of what motivated the ensemble framing of Muscle5, which treats alignment uncertainty as a quantity to be measured rather than a nuisance to be hidden behind a single output ^[13].

Limitations

An MSA is a hypothesis about homology, not an observation. Columns in poorly aligned regions are frequently wrong, and the errors propagate: phylogenetic branch lengths, selection tests and contact predictions all inherit them. Specific recurring problems include guide tree errors in progressive methods that cannot be undone later ^[5], systematic under-counting of insertions when gap placement ignores phylogeny ^[17], sensitivity of the result to program and parameter choice, and shallow alignments for orphan proteins and for designed sequences that have no natural relatives, which is exactly the regime in which structure predictors degrade ^[29][32].

See also

• AlphaFold
• AlphaFold 3
• AlphaFold-Multimer
• OpenFold
• ESMFold
• RoseTTAFold
• Boltz
• Protein folding
• Protein language model
• Hidden Markov Model
• Dynamic Programming
• Bioinformatics
• AI for Science
• AI Drug Discovery

References

1. ^Needleman, S. B. and Wunsch, C. D. "A general method applicable to the search for similarities in the amino acid sequence of two proteins." *Journal of Molecular Biology* 48, 443-453 (1970). doi.org/...0022-2836(70)90057-4
2. ^Smith, T. F. and Waterman, M. S. "Identification of common molecular subsequences." *Journal of Molecular Biology* 147, 195-197 (1981). doi.org/...0022-2836(81)90087-5
3. ^Carrillo, H. and Lipman, D. "The multiple sequence alignment problem in biology." *SIAM Journal on Applied Mathematics* 48, 1073-1082 (1988). doi.org/...0148063
4. ^1 ^2Wang, L. and Jiang, T. "On the complexity of multiple sequence alignment." *Journal of Computational Biology* 1, 337-348 (1994). doi.org/...cmb.1994.1.337
5. ^1 ^2Feng, D.-F. and Doolittle, R. F. "Progressive sequence alignment as a prerequisite to correct phylogenetic trees." *Journal of Molecular Evolution* 25, 351-360 (1987). doi.org/...BF02603120
6. ^1 ^2Higgins, D. G. and Sharp, P. M. "CLUSTAL: a package for performing multiple sequence alignment on a microcomputer." *Gene* 73, 237-244 (1988). doi.org/...0378-1119(88)90330-7
7. ^1 ^2 ^3Thompson, J. D., Higgins, D. G. and Gibson, T. J. "CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice." *Nucleic Acids Research* 22, 4673-4680 (1994). doi.org/...22.22.4673
8. ^Thompson, J. D., Gibson, T. J., Plewniak, F., Jeanmougin, F. and Higgins, D. G. "The CLUSTAL_X windows interface: flexible strategies for multiple sequence alignment aided by quality analysis tools." *Nucleic Acids Research* 25, 4876-4882 (1997). doi.org/...25.24.4876
9. ^Larkin, M. A. et al. "Clustal W and Clustal X version 2.0." *Bioinformatics* 23, 2947-2948 (2007). doi.org/...btm404
10. ^1 ^2Sievers, F. et al. "Fast, scalable generation of high-quality protein multiple sequence alignments using Clustal Omega." *Molecular Systems Biology* 7 (2011). doi.org/...msb.2011.75
11. ^Notredame, C., Higgins, D. G. and Heringa, J. "T-Coffee: a novel method for fast and accurate multiple sequence alignment." *Journal of Molecular Biology* 302, 205-217 (2000). doi.org/...jmbi.2000.4042
12. ^1 ^2 ^3Edgar, R. C. "MUSCLE: multiple sequence alignment with high accuracy and high throughput." *Nucleic Acids Research* 32, 1792-1797 (2004). doi.org/...gkh340
13. ^1 ^2 ^3Edgar, R. C. "Muscle5: high-accuracy alignment ensembles enable unbiased assessments of sequence homology and phylogeny." *Nature Communications* 13 (2022). doi.org/...s41467-022-34630-w
14. ^1 ^2Katoh, K. et al. "MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform." *Nucleic Acids Research* 30, 3059-3066 (2002). doi.org/...gkf436
15. ^Katoh, K. and Standley, D. M. "MAFFT multiple sequence alignment software version 7: improvements in performance and usability." *Molecular Biology and Evolution* 30, 772-780 (2013). doi.org/...mst010
16. ^1 ^2Do, C. B., Mahabhashyam, M. S. P., Brudno, M. and Batzoglou, S. "ProbCons: probabilistic consistency-based multiple sequence alignment." *Genome Research* 15, 330-340 (2005). doi.org/...gr.2821705
17. ^1 ^2 ^3Loytynoja, A. and Goldman, N. "Phylogeny-aware gap placement prevents errors in sequence alignment and evolutionary analysis." *Science* 320, 1632-1635 (2008). doi.org/...science.1158395
18. ^Krogh, A., Brown, M., Mian, I. S., Sjolander, K. and Haussler, D. "Hidden Markov models in computational biology: applications to protein modeling." *Journal of Molecular Biology* 235, 1501-1531 (1994). doi.org/...jmbi.1994.1104
19. ^Eddy, S. R. "Profile hidden Markov models." *Bioinformatics* 14, 755-763 (1998). doi.org/...14.9.755
20. ^Eddy, S. R. "Accelerated profile HMM searches." *PLoS Computational Biology* 7, e1002195 (2011). doi.org/...journal.pcbi.1002195
21. ^Soding, J. "Protein homology detection by HMM-HMM comparison." *Bioinformatics* 21, 951-960 (2005). doi.org/...bti125
22. ^Remmert, M., Biegert, A., Hauser, A. and Soding, J. "HHblits: lightning-fast iterative protein sequence searching by HMM-HMM alignment." *Nature Methods* 9, 173-175 (2012). doi.org/...nmeth.1818
23. ^Altschul, S. F. et al. "Gapped BLAST and PSI-BLAST: a new generation of protein database search programs." *Nucleic Acids Research* 25, 3389-3402 (1997). doi.org/...25.17.3389
24. ^Steinegger, M. and Soding, J. "MMseqs2 enables sensitive protein sequence searching for the analysis of massive data sets." *Nature Biotechnology* 35, 1026-1028 (2017). doi.org/...nbt.3988
25. ^Kallenborn, F. et al. "GPU-accelerated homology search with MMseqs2." *Nature Methods* 22, 2024-2027 (2025). doi.org/...s41592-025-02819-8
26. ^Mirdita, M. et al. "ColabFold: making protein folding accessible to all." *Nature Methods* 19, 679-682 (2022). doi.org/...s41592-022-01488-1
27. ^Henikoff, S. and Henikoff, J. G. "Amino acid substitution matrices from protein blocks." *Proceedings of the National Academy of Sciences* 89, 10915-10919 (1992). doi.org/...pnas.89.22.10915
28. ^Thompson, J. D., Plewniak, F. and Poch, O. "BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs." *Bioinformatics* 15, 87-88 (1999). doi.org/...15.1.87
29. ^1 ^2 ^3Jumper, J. et al. "Highly accurate protein structure prediction with AlphaFold." *Nature* 596, 583-589 (2021). doi.org/...s41586-021-03819-2
30. ^google-deepmind/alphafold, GitHub repository README and `alphafold/data/pipeline.py`. github.com/...alphafold. Accessed 2026-09-11.
31. ^Morcos, F. et al. "Direct-coupling analysis of residue coevolution captures native contacts across many protein families." *Proceedings of the National Academy of Sciences* 108 (2011). doi.org/...pnas.1111471108
32. ^1 ^2Lin, Z. et al. "Evolutionary-scale prediction of atomic-level protein structure with a language model." *Science* 379, 1123-1130 (2023). doi.org/...science.ade2574
33. ^Ahdritz, G. et al. "OpenFold: retraining AlphaFold2 yields new insights into its learning mechanisms and capacity for generalization." *Nature Methods* 21, 1514-1524 (2024). doi.org/...s41592-024-02272-z
34. ^Ahdritz, G. et al. "OpenProteinSet: training data for structural biology at scale." arXiv:2308.05326 (2023). arxiv.org/...2308.05326
35. ^Mistry, J. et al. "Pfam: the protein families database in 2021." *Nucleic Acids Research* 49, D412-D419 (2021). doi.org/...gkaa913
36. ^Mirdita, M. et al. "Uniclust databases of clustered and deeply annotated protein sequences and alignments." *Nucleic Acids Research* 45, D170-D176 (2017). doi.org/...gkw1081
37. ^The OpenFold3 Team. "OpenFold3-preview2 Technical Report." OpenFold portal (2026). portal.openfold.omsf.io/...p2_technical_report.pdf. Accessed 2026-09-11.
38. ^NVIDIA. "Overview." NVIDIA NIM for MSA Search documentation. docs.nvidia.com/...overview. Accessed 2026-09-11.
39. ^Han, Y., Tsenkov, M. I., Venanzi, N. A. E. et al. "AlphaFold Database expands to proteome-scale quaternary structures." *bioRxiv* preprint (2026), doi:10.64898/2026.03.27.714458. biorxiv.org/...2026.03.27.714458v1