Multiple sequence alignment (MSA) is the arrangement of three or more biological sequences so that corresponding residues occupy the same columns. The sequences may represent DNA, RNA, or proteins. Gaps are introduced where necessary to accommodate differences in sequence length. An alignment is therefore more than a display of similarity: it is an inferred correspondence among positions, usually intended to reflect descent from common ancestral positions or, in some applications, equivalent structural or functional roles.
MSA is a central method in bioinformatics. It supports the identification of conserved functional sites, the reconstruction of evolutionary relationships, the classification of sequence families, and the analysis of molecular structure. Its difficulty arises from the interaction of biological uncertainty and computational complexity. Different scoring systems, evolutionary assumptions, and algorithms can produce different alignments of the same sequences, especially when those sequences are distantly related or contain extensive insertions, deletions, and rearrangements.
Biological meaning and alignment representation
An alignment can be represented as a rectangular array with one sequence per row and one aligned position per column. Each entry is a residue symbol or a gap, conventionally written as a hyphen. Removing gaps from a row must recover the original input sequence in its original order. Standard alignments contain no columns consisting entirely of gaps, because such columns add no correspondence information. If there are sequences and alignment columns, the result is an array, although the input sequences may have different lengths.
The biological interpretation normally rests on homology, meaning common evolutionary origin. At the sequence level, homologous genes may be related through speciation, producing orthology, or through gene duplication, producing paralogy. Both kinds of relationship can be represented in an alignment, but they answer different biological questions. A family containing duplicated genes cannot automatically be treated as a set of one-to-one counterparts across species. Correctly aligning the residues does not, by itself, establish which duplication or speciation events produced the sequences.
Individual columns express positional hypotheses. Two residues in one column are proposed to correspond, even if their chemical identities differ. Identical residues do not necessarily establish correspondence: short repeated motifs may arise independently, and repetitive regions can admit several equally plausible placements. Conversely, a strongly diverged site may remain homologous despite having changed repeatedly. Percentage identity is consequently a property calculated from an alignment, not a definition of homology. Its value also depends on whether gap-containing positions and terminal overhangs are included in the denominator.
A gap represents an inferred absence relative to other sequences, rather than a directly observed evolutionary event. Without ancestral information, a gap cannot generally be identified as an insertion in one lineage rather than a deletion in another. Adjacent gaps may represent one event, several events, missing sequence, or an uncertain correspondence. A global alignment attempts to represent the full lengths of the sequences, whereas local or block-based alignments focus on selected corresponding regions. This distinction becomes especially important for proteins with different domain arrangements: forcing unrelated domains into a common rectangular alignment can create apparently precise but biologically unsupported columns.
Scoring systems and computational complexity
Most alignment algorithms search for an arrangement that maximizes an explicit score or approximates a probabilistic objective. A common criterion is the sum-of-pairs score, which adds contributions from all pairs of sequences:
Here, is the multiple alignment, is the score of the pairwise alignment induced by rows and , and is an optional weight. In the simplest formulation, residue-pair scores are added independently across columns, with separate treatment of gaps. Pair weights or sequence weights can reduce the dominance of densely sampled groups of nearly identical sequences.
For proteins, residue comparisons commonly use a substitution matrix, such as a member of the PAM or BLOSUM families. These matrices distinguish conservative replacements, such as leucine for isoleucine, from less frequently observed replacements between chemically dissimilar amino acids. Their entries are typically related to log odds: the probability of a residue pair in related sequences is compared with its probability under a background model. Nucleotide scoring may use simple match–mismatch rules or more differentiated models. The scoring scheme influences which correspondences are favored and is not a neutral formatting choice.
Gap penalties frequently distinguish opening a gap from extending it. Under one common convention, a gap of length has cost
where is the opening cost and the extension cost. This affine form favors one contiguous gap over many isolated gaps when the opening cost is larger. Terminal gaps may be penalized differently from internal gaps, reflecting the possibility that sequences are incomplete or represent different boundaries. In a multiple alignment, gap scoring is more complicated than in a pairwise alignment because a single block of gaps can induce different events in different sequence pairs.
Exact optimization becomes difficult as the number of sequences increases. Dynamic programming for sequences of comparable length uses a conceptual -dimensional lattice with roughly cells and up to predecessor configurations per cell in a basic formulation. Standard general formulations of optimal sum-of-pairs alignment are NP-hard. Exact methods are therefore mainly practical for small problems, sometimes aided by bounds or restricted search regions. Large-scale programs use heuristics, sacrificing a guarantee of finding the mathematical optimum. Even an exact optimum would remain conditional on its scoring system: the highest-scoring alignment need not be the most accurate reconstruction of evolutionary history.
Progressive alignment and guide trees
Progressive alignment builds a multiple alignment through a sequence of smaller alignment operations. Typically, the program first estimates similarities or distances among input sequences, constructs a guide tree, and then follows that tree from its leaves toward its root. Closely related sequences are aligned first. Existing alignments are subsequently combined through sequence-to-profile or profile-to-profile alignment, until all sequences belong to one result. A profile summarizes the residue and gap patterns at each column, allowing an entire aligned group to be compared with another sequence or group.
The approach became influential through work including Da-Fei Feng and Russell Doolittle’s 1987 description of progressive alignment. The Clustal family made such methods widely accessible; ClustalW, introduced by Julie Thompson, Desmond Higgins, and Toby Gibson in 1994, incorporated sequence weighting, position-sensitive gap penalties, and choices of substitution matrices related to sequence divergence. These developments addressed an important imbalance in biological databases: a large cluster of very similar sequences should not necessarily outweigh a smaller group representing a distinct evolutionary lineage.
The guide tree is an algorithmic ordering device, not automatically a defensible evolutionary tree. It may be built from approximate distances, word-sharing statistics, or preliminary pairwise alignments. Its branches determine when groups are merged, and therefore influence the final correspondence of residues. A poor early grouping can make later steps difficult, especially when a long or unusual sequence is aligned against a profile that does not adequately represent its relatives. Conversely, accurate early alignments of close relatives can provide a stable scaffold for incorporating more divergent sequences.
The main weakness of a purely progressive method is the persistence of early errors. Once residues have been placed together, later merging steps ordinarily preserve that correspondence. Existing gap columns may be extended, and new columns may be added, but previously aligned residues are not freely rearranged. This is often described as the “once a gap, always a gap” limitation, although actual implementations differ in their treatment of gaps and profiles. The important issue is the restriction on revisiting earlier decisions, not the literal permanence of every displayed gap character.
Progressive alignment remains useful because it converts an otherwise intractable joint search into manageable operations. Modern implementations may replace expensive all-against-all comparisons with approximate similarity searches or clustering. Clustal Omega, introduced in 2011, combines scalable guide-tree construction with profile hidden Markov model comparisons. Such developments preserve the progressive framework while improving its handling of large sequence sets and the information represented during profile alignment.
Iterative refinement and consistency-based methods
Iterative refinement addresses the inability of basic progressive alignment to correct early mistakes. Starting from an initial alignment, a program repeatedly divides the sequences into groups, removes gap-only columns within the resulting subalignments, and realigns the groups. A proposed change may be accepted if it improves an objective function or satisfies another algorithm-specific criterion. The split can be chosen randomly, derived from a tree, or targeted at poorly supported regions. Iteration allows residues that were initially placed together to acquire different partners.
The search remains heuristic. A locally improved score does not establish global optimality, and the outcome depends on the starting alignment, the allowed moves, and the stopping rule. Some methods refine the guide tree as well as the alignment, because the initial distance estimates may improve after more plausible correspondences have been established. This creates feedback between alignment and tree construction. It can improve practical performance, but neither product becomes independent evidence for the other merely because the two are updated repeatedly.
MUSCLE, introduced by Robert Edgar in 2004, became a prominent example of combining rapid initial alignment with subsequent improvement. Its original design used approximate distances for an initial draft, refined distance estimates and a revised tree, and then iterative refinement. MAFFT, first described by Kazutaka Katoh and colleagues in 2002, introduced fast Fourier transform techniques into sequence comparison and later developed multiple strategies with different speed–accuracy trade-offs. MAFFT’s L-INS-i, G-INS-i, and E-INS-i strategies incorporate different pairwise alignment assumptions and refinement procedures, suited to different patterns of conserved regions and intervening sequence.
Consistency-based methods use agreement among multiple pairwise relationships to evaluate proposed matches. If a residue in sequence A aligns to one in B, and that residue in B aligns to one in C, the indirect relationship provides evidence for aligning the residues in A and C. This evidence is not logically conclusive, because one of the pairwise matches may be wrong, but agreement across several routes can strengthen a correspondence. The information is often stored in a library of residue-pair constraints that guides subsequent alignment.
T-Coffee, introduced by Cédric Notredame, Desmond Higgins, and Jaap Heringa in 2000, combines pairwise alignment evidence through such a consistency framework. ProbCons, described in 2005, uses posterior match probabilities and probabilistic consistency transformations. These methods can be effective on difficult protein families, but storing and combining extensive pairwise evidence can be computationally demanding. Their characteristic strength is the use of information beyond the two profiles being merged at a particular step; their limitations include dependence on the quality of the initial evidence and the cost of representing it.
Profiles, probabilistic models, and joint evolutionary inference
A sequence profile summarizes variation across alignment columns. The simplest profile records residue frequencies, often adjusted by sequence weights and pseudocounts. Pseudocounts prevent a residue that happens not to appear in a small sample from being assigned an absolute probability of zero. More elaborate profiles represent the tendency to insert or delete sequence at different positions. This makes a profile more informative than a single consensus sequence, which usually retains only the most frequent residue at each column and discards much of the observed variation.
A profile hidden Markov model provides a probabilistic representation of a sequence family. Typical architectures contain match states corresponding to modeled alignment positions, insertion states that emit additional residues, and deletion states that bypass modeled positions without emitting a residue. Transition probabilities describe movement among these states, while emission probabilities describe residue preferences. The framework is based on the hidden Markov model, in which an observed sequence is generated through an unobserved path of states. Different state paths imply different alignments of a sequence to the model.
Profile models are particularly important for detecting remote relationships. A sequence may share no long, strikingly similar segment with any one family member yet fit the family’s position-specific pattern well. HMMER is a widely used software suite for profile-model searches and related operations. Pfam uses curated family models to classify protein domains. Aligning a new sequence to such a model places it relative to an established family framework, although this is not identical to freely realigning all family members. A model’s match columns embody prior decisions about which positions constitute the family’s conserved core.
Probabilistic methods also distinguish an optimal alignment from uncertainty over many alignments. A maximum-probability state path yields one solution, whereas posterior match probabilities estimate support for individual residue correspondences after considering alternative paths. Maximum expected accuracy methods can choose an alignment that maximizes expected correctly matched residues rather than the probability of the entire path. These objectives need not produce the same answer. A long sequence can have numerous individually plausible local alternatives even when one complete alignment receives the highest model probability.
More ambitious methods infer alignment and evolutionary history jointly. They place substitution and insertion–deletion processes on a tree and use procedures such as Markov chain Monte Carlo to sample possible alignments, trees, and model parameters. BAli-Phy is an example of this approach. Joint inference can propagate alignment uncertainty into evolutionary estimates rather than treating one alignment as fixed. Its computational demands are substantial, and its conclusions remain sensitive to the adequacy of the substitution, gap, and evolutionary models used.
Sequence type, molecular structure, and genomic organization
The appropriate alignment representation depends on the molecule and the biological question. For a protein-coding gene, direct nucleotide alignment can obscure correspondence when synonymous substitutions accumulate or when nucleotide-level similarity becomes weak. A common alternative translates the coding sequences, aligns the proteins, and projects the resulting gaps back onto the nucleotide sequences in groups of three. This codon-preserving alignment maintains the reading frame and connects nucleotide columns to codons. Frameshifts, premature stops, sequencing errors, and incorrectly predicted exon boundaries require separate attention because ordinary protein-guided projection cannot explain them automatically.
Protein alignment can draw on structural information because three-dimensional structure may remain recognizable after sequence similarity has become weak. A structural alignment compares spatial arrangements rather than residue strings alone. Structure-derived correspondences can guide an MSA or constrain selected positions. For example, residues forming the core of an alpha helix or a beta sheet may be aligned differently from residues in a flexible surface loop. Nevertheless, structural equivalence and common ancestry are not identical concepts, and flexible regions may lack a unique structural correspondence.
Functional sites provide another source of information. Catalytic residues in an enzyme, metal-binding residues, or a characteristic disulfide bond pattern may help distinguish plausible alignments from superficially high-scoring alternatives. These constraints must be interpreted in context: similar catalytic chemistry can evolve independently, and members of a homologous family can lose or alter a functional site. Domain organization is equally important. Proteins containing the same domains in different orders, or containing lineage-specific domain additions, may require separate domain alignments rather than one full-length global alignment.
Structured RNA introduces dependencies that ordinary column-independent scoring does not capture. In transfer RNA and ribosomal RNA, paired positions can change together while maintaining complementary base pairing. A substitution at one side of a stem may be compensated by another substitution at the opposite side. Covariance models incorporate such pairing relationships and are used in the Rfam resource to represent RNA families. Joint consideration of sequence and secondary structure can improve correspondence, although more elaborate structural models generally require greater computational effort.
Whole-genome comparison adds rearrangements, duplications, and repeated elements to the problem. A conventional MSA assumes that residue order is preserved within each row. Inversions, translocations, and changes in gene order violate a simple one-block representation. Genome alignment therefore often begins by identifying locally collinear homologous blocks and then aligning within those blocks. Tools such as progressiveMauve and Cactus address aspects of this larger problem. The resulting object may be a collection or graph of local correspondences rather than a single uncomplicated rectangle spanning every genome.
Evolutionary, functional, and structural applications
Multiple sequence alignments provide the character data for much of molecular phylogenetics. Each column can be treated as a set of observed states whose changes are modeled along a tree. Maximum likelihood and Bayesian methods evaluate these patterns under substitution models, often allowing evolutionary rates to vary among sites. The correspondence implied by the alignment is therefore foundational: if unrelated residues are placed in the same column, a phylogenetic analysis models a history for characters that do not share the assumed positional origin.
Conservation analysis uses aligned variation to identify positions that are unusually stable or restricted in their accepted residues. A simple measure is column entropy,
where is the estimated frequency of residue at column . Low entropy indicates limited observed variation, but its meaning depends on sample composition, sequence weighting, treatment of gaps, and evolutionary distances. A column conserved among ten nearly identical sequences provides different evidence from one conserved across a broad family. Sequence logos display position-specific residue preferences, commonly scaling the total column height by an information measure.
Conserved patterns can help identify binding sites, catalytic motifs, and family-specific features. In globins, alignments reveal correspondence among residues involved in heme binding and the surrounding structural framework despite divergence among family members such as hemoglobin and myoglobin. In protein kinases, conserved catalytic-domain motifs provide landmarks for family comparison. An alignment can support a functional hypothesis, but a conserved residue may reflect structural stability rather than direct catalytic activity. Experimental characterization and broader molecular context remain distinct sources of evidence.
Alignments also support estimates of selection in coding sequences. Comparisons of nonsynonymous and synonymous substitution rates use a codon alignment to distinguish changes that alter amino acids from those that do not. The ratio is interpreted within a specified evolutionary model, not as a direct count of observed differences. Misaligned codons, unrecognized paralogs, or recombination can distort these estimates. Natural selection is consequently inferred through a chain of assumptions that includes the correctness of positional correspondence.
Large protein alignments additionally reveal patterns of coevolution. Positions that change in a statistically dependent manner may participate in structural contacts or functional interactions. Direct-coupling methods attempt to distinguish direct statistical dependencies from indirect correlations, while accounting imperfectly for shared ancestry and uneven sampling. Such information has contributed to contact prediction and protein-structure modeling. AlphaFold2, described in 2021, uses MSA-derived information alongside other inputs in its principal architecture. However, an apparent correlation is not by itself proof of physical contact, and contact-related signals depend strongly on the diversity and quality of the aligned sequence set.
Accuracy assessment and alignment uncertainty
Alignment accuracy cannot generally be established by observing the true ancestral correspondence, because that history is unavailable for most real sequence families. Evaluation therefore uses several imperfect reference points: structure-derived alignments, simulated sequences with known histories, curated family alignments, and agreement among independent methods. Each tests a different aspect of performance. A method that performs well on compact, structurally characterized proteins may behave differently on fragmented sequences, long disordered regions, or proteins with complex domain architectures.
BAliBASE, first introduced in 1999, is a widely used benchmark organized around difficult protein-alignment cases and structurally informed reference information. Other benchmark resources include PREFAB and SABmark. Reference alignments commonly distinguish more reliable core regions from uncertain segments. Structural guidance is valuable, but it does not make every reference position unambiguous: different structural comparison methods may disagree, and flexible loops may be poorly resolved or support several reasonable correspondences. Benchmark composition can also favor methods whose assumptions resemble those used to construct the references.
Two common evaluation measures examine residue pairs and complete columns. A sum-of-pairs accuracy measure counts how many reference-aligned residue pairs are recovered by a test alignment, with details varying by implementation. A total-column score counts reference columns reproduced exactly. The latter is stricter: moving one residue can make an otherwise largely correct column fail the test. Benchmark sum-of-pairs accuracy must also be distinguished from a sum-of-pairs optimization score; one compares a result against a reference, whereas the other assigns a value to the alignment during construction.
Confidence assessment can instead focus on individual columns or residue pairs. Posterior probabilities quantify uncertainty within a probabilistic model. Perturbation-based approaches assess how correspondences change when guide trees, input order, or algorithmic conditions are altered. GUIDANCE and HoT are examples of methods that examine alignment robustness through perturbations. Agreement across runs is informative but not a guarantee of correctness, because multiple runs can share the same systematic error. Conversely, variation can reveal that a region has little information supporting one placement over another.
Filtering uncertain regions is common in downstream evolutionary analysis, but it changes the data and may introduce bias. Removing gap-rich or variable columns can eliminate errors while also preferentially discarding rapidly evolving, biologically informative positions. Tools such as Gblocks and trimAl implement explicit selection rules, whose effects depend on their settings and the dataset. A phylogenetic bootstrap measures sampling variation conditional on the supplied alignment; it does not automatically account for uncertainty in how that alignment was constructed. Repeating an analysis across plausible alternative alignments addresses a different source of variation from resampling columns within one fixed result.
Scale, data formats, and reproducibility
The computational burden of MSA depends on sequence number, sequence length, divergence, and the chosen algorithm. An alignment containing many short, similar sequences may be easier than a smaller set of long, distantly related multidomain proteins. Exhaustive pairwise comparison scales quadratically with sequence number before profile construction even begins. Consistency libraries, posterior-probability calculations, and repeated refinement can add substantial memory and runtime costs. Approximate distances, clustering, restricted searches, and parallel computing are therefore important in large-scale implementations.
Large datasets are often handled by separating representative alignment from sequence placement. A backbone alignment is constructed from a subset of sequences, and additional sequences are inserted relative to it. UPP, introduced in 2015, uses an ensemble of profile hidden Markov models derived from a backbone alignment and was designed to handle large datasets, including sequences of uneven length. MAFFT also provides modes for adding sequences or fragments to an existing alignment. Such approaches can preserve established correspondences, but the final result depends on whether the backbone adequately represents the diversity of the full dataset.
Aligned sequences are stored in several formats. Aligned FASTA is simple and widely supported, representing each sequence with an identifier followed by its gapped residue string. Clustal format arranges sequences into labeled blocks and may include a conservation line. Stockholm format can store sequence annotations and column annotations, making it useful for curated families and structural information. PHYLIP and NEXUS are common in evolutionary-analysis software, although specific implementations may impose restrictions on identifiers or formatting. Conversion can lose metadata even when all residue characters are preserved.
A3M is frequently used in protein-homology and structure-prediction workflows. It distinguishes match positions from insertions using uppercase and lowercase letters, with insertion-gap characters omitted. Consequently, the displayed character strings need not all have the same length, unlike rows of a conventional fully expanded alignment. Expanding A3M into a rectangular representation requires interpreting those conventions correctly. Confusing aligned positions with raw character offsets can corrupt residue numbering, contact maps, or the mapping of annotations back to an experimental structure.
Reproducibility requires more than retaining the final alignment file. Important provenance includes the original sequences, accession versions, sequence-selection criteria, program version, command-line settings, scoring choices, guide-tree or backbone information, and any manual edits. Random seeds matter for stochastic procedures, and software revisions can change results even when a program retains the same name. Downstream annotations also need explicit coordinate mapping: alignment column 150 may correspond to a different residue number in every sequence because of preceding gaps and insertions. Preserving these mappings allows functional sites, genomic coordinates, and structural residues to remain associated with the intended biological positions.