Robert C. Edgar

Edgar graduated in 1982 from University College London, BSc in Physics, PhD in Particle physics.^[4] He pursued software development post-graduation and founded his own company, Parity Software, in 1988.^[4] In 2001, he began working with coding algorithms after attending a seminar at the University of California, Berkeley.^[5] From 2001-present day Edgar has contributed to or been the sole creator of multiple software programs, including MUSCLE and USEARCH.^[4] He has written a total of 96 papers in the field of computational biology from 2002-present, with his most recent paper being Discovery and Validation of Alternatives to VSV-G for Pseudotyping of Lentiviral Vectors for In Vivo Delivery of Anti-Tumor Transgenes. As of April, 2025, his work has been cited over 143,126 times.^[6] The two originally published MUSCLE papers have been cited more than 58,979 times combined. The paper “MUSCLE: multiple sequence alignment with high accuracy and high throughput”^[1] has received more than 49,052 citations,^[6] while “MUSCLE: a multiple sequence alignment method with reduced time and space complexity”^[2] has been cited over 9,936 times.^[6]

Muscle Versions History

Overview

In late 2021, Edgar released Muscle5 (also referred to as Muscle v5), an updated version of the MUSCLE software. It introduces several innovations aimed at improving alignment accuracy and reducing bias found in other MSA algorithms. Traditional tools such as Clustal Omega, MAFFT, and earlier versions of MUSCLE rely on progressive alignment strategies that produce a single alignment. Muscle5, in contrast, generates an ensemble of high-accuracy alignments by perturbing a hidden Markov model and permuting its guide tree. At its core, the algorithm is a parallelized reimplementation of ProbCons, and is designed to scale efficiently to large datasets. Muscle5 has demonstrated improved benchmark performance compared to leading MSA methods across several datasets, including BAliBASE, BRAliBASE, and PREFAB.^[3]

Ensembles

A key innovation in Muscle5 is the use of alignment ensembles, which provide unbiased metrics of confidence in alignments. Each individual MSA (replicate) in the ensemble uses fixed but independently chosen parameters for the hidden Markov model and guide tree, allowing results to be averaged over a diverse set of replicates. This enables biologists to assess how sensitive their downstream analyses are to alignment uncertainty by comparing results across the ensemble.^[3]

Stage 1: Draft Progressive

In this first stage, the algorithm produces a multiple alignment, emphasizing speed over accuracy. This step begins by computing the k-mer distance for every pair of input sequences to create a distance matrix. UPGMA clusters the distance matrix to produce a binary tree. From this tree a progressive alignment is constructed, beginning with the creation of profiles for each leaf of the tree. For every node in the tree, a pairwise alignment is constructed of the two child profiles, creating a new profile to be assigned to that node. This continues until there is a multiple sequence alignment of all input sequences at the root of the tree.

Given ${\displaystyle N}$ input sequences and ${\displaystyle L}$ as the average sequence length, the time complexity of the draft progressive stage is

${\displaystyle O(N^{2}\cdot L+N\cdot L^{2})}$.

Here, the pairwise ${\displaystyle k}$-mer distance calculation is computed as ${\displaystyle O(N^{2}\cdot L)}$, and the progressive alignment steps take ${\displaystyle O(N\cdot L^{2})}$, where ${\displaystyle O}$ denotes the asymptotic upper bound. The space complexity is ${\displaystyle O(N\cdot L)}$ as the algorithm maintains profiles and alignments for each sequence across the tree.^[1]

Stage 2: Improved Progressive

This stage focuses on obtaining a more optimal tree by calculating the Kimura distance for each pair of input sequences using the multiple sequence alignment obtained in Stage one, and creates a second distance matrix. UPGMA clusters this distance matrix to obtain a second binary tree. A progressive alignment is performed to obtain a multiple sequence alignment like in Stage one, but it is optimized by only computing alignments in subtrees whose branching orders have changed from the first binary tree, resulting in a more accurate alignment.

Refined alignments are made in the second stage by recalculating a more accurate tree via the Kimura distance. Thus, the algorithm analysis involves the initial subprocedures of pairwise distance calculations and progressive alignment; however, optimizations in computation are made by limiting re-alignment to only those subtrees with altered branching orders. The optimization is thus given as

${\displaystyle O(N^{2}\cdot L+m\cdot L^{2})}$,

where the variable ${\displaystyle m}$ denotes the number of subtree realignments. Similarly, the space complexity is

${\displaystyle O(N\cdot L)}$,

as profiles and alignments for the input sequences are stored for the progressive alignment process.^[1]

Stage 3: Refinement

In this final stage, an edge is chosen from the second tree, with edges being visited in decreasing distance from the root. The chosen edge is deleted, dividing the tree into two subtrees. The profile of the multiple alignment is then computed for each subtree. A new multiple sequence alignment is produced by re-aligning the subtree profiles. If the SP score is improved, the new alignment is kept, otherwise, it is discarded. The process of deleting an edge and aligning is repeated until convergence, or until a user-defined limit is reached.

The time complexity of the refinement stage is given as ${\displaystyle O(k\cdot L^{2})}$. Here, ${\displaystyle k}$ denotes the number of edge deletions and ${\displaystyle L}$ denotes the average sequence length, where re-alignment of the subtree profiles is still the dominant cost per iteration. The space complexity remains the same as given in Stage one and two: ${\displaystyle O(N\cdot L)}$. Since the same iterative refinement process occurs, the asymptotic complexity remains polynomial as the dominant term grows linearly with respect to the number of refinement steps.

In comparison, the CLUSTALW algorithm includes an optimized iterative refinement step such that selective re-alignment of the tree occurs in order to maximize alignment accuracy without repeating the entire process. The time and space complexity, however, do not change for this optimized iterative refinement step. The time complexity is ${\displaystyle O(k\cdot L^{2})}$, where ${\displaystyle k}$ is the number of refinement steps and ${\displaystyle L}$ is the average alignment length. The space complexity is given as ${\displaystyle O(N\cdot L)}$, again, for alignment profiles and sequence data for all ${\displaystyle N}$ input sequences.^[1][2]

Comparison of Space Complexity and Alignment Accuracy

Feature	CLUSTALW	MUSCLE v3 Version
Time Complexity	${\displaystyle O(k\cdot L^{2})}$	${\displaystyle O(k\cdot L^{2})}$
Alignment Accuracy	Moderate	Higher, due to iterative refinement improving SP score

Algorithm Flowchart

Complexity and Comparison

In the first two stages of the algorithm, the time complexity is O(N²L + NL²), the space complexity is O(N² + NL + L²). The refinement stage adds to the time complexity another term, O(N³L).^[1] MUSCLE is often used as a replacement for Clustal, since it usually (but not always) gives better sequence alignments. Depending on the chosen options, MUSCLE is significantly faster than Clustal, more so for larger alignments.^[1][2]

Most modern multiple sequence alignment programs are generally accepted when presenting aligned sequences but there are few differences amongst them. The main difference between programs is the method used to align the sequences. For instance, T-COFFEE and Clustal use the progressive method while MUSCLE and MAFFT perform using the iterative method of alignment.^[9] These two methods differ in their ability to handle low similarity sequences with the iterative method providing more accurate results. The other way methods differ is with their computational needs.

Originally MUSCLE had middling CPU demands in comparison to other programs but was definitely higher than the progressive methods.^[1] Comparisons with modern versions of MSA programs reveal that many are quite similar in capabilities. The alignments were assessed based on their sum of pairs (SP), correctly matching two nucleotides/amino acids across two sequences, and their total columns (TC), matching columns divided by the total columns. In these cases, MUSCLE was average in its ability to maximize matching pairs and columns, being slightly worse than the ProbCons, T-Coffee, Probalign and MAFFT.^[10] Outside the alignment scores, MUSCLE was less computationally demanding in both time to execute the alignment and the memory demand.