Multiple Sequence Comparison by Log-Expectation (MUSCLES) Algorithm

A Multiple Sequence Comparison by Log-Expectation (MUSCLES) Algorithm is a Sequence Alignment Algorithm that creates multiple alignments of amino acid or nucleotide sequences.

• AKA: MUSCLE Alignment Software, MUSCLE Algorithm.
• Context:
  • Source code and data available at: http://www.drive5.com/muscle
• Example(s):
  • muscle -in seqs.fa -out seqs.afa,
  • …
• Counter-Example(s):
  • T‐Coffee,
  • MAFFT,
  • CLUSTALW.
• See: BAliBASE, SABmark, SMART, Sequence Alignment Software, BMC Bioinformatics, Linux, MacOS, Microsoft Windows, IA-32, X86-64, Multiple Sequence Alignment, Public Domain, Software, Protein, Nucleotide, Software License.

---

---

References

2021a

• (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/MUSCLE_(alignment_software) Retrieved:2021-1-2.
  • MUltiple Sequence Comparison by Log-Expectation (MUSCLE) is computer software for multiple sequence alignment of protein and nucleotide sequences. It is licensed as public domain. The method was published by Robert C. Edgar in two papers in 2004. The first paper, published in Nucleic Acids Research, introduced the sequence alignment algorithm. The second paper, published in BMC Bioinformatics, presented more technical details.

    (...)

    The MUSCLE algorithm proceeds in three stages: the draft progressive, improved progressive, and refinement stages. In the draft progressive stage, the algorithm produces a draft multiple alignment, emphasising speed over accuracy. In the improved progressive stage, the Kimura distance is used to reestimate the binary tree to create the draft alignment, in turn producing a more accurate multiple alignment. The final refinement stage refines the improved alignment made in step two. Multiple alignments are available at the end of each stage. 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). MUSCLE is often used as a replacement for Clustal, since it usually (but not always) gives better sequence alignments, depending on the chosen options. Also, MUSCLE is significantly faster than Clustal, more so for larger alignments.

2021b

• (MUSCLE User Guide, 2021) ⇒ http://nebc.nerc.ac.uk/bioinformatics/documentation/muscle/muscle.html Retrieved:2021-1-2.
  • QUOTE: MUSCLE is a program for creating multiple alignments of amino acid or nucleotide sequences. A range of options is provided that give you the choice of optimizing accuracy, speed, or some compromise between the two. Default parameters are those that give the best average accuracy in our tests. Using versions current at the time of writing, my tests show that MUSCLE can achieve both better average accuracy and better speed than CLUSTALW or T‑Coffee, depending on the chosen options.

2004

• (Edgar, 2004) ⇒ Robert C. Edgar (2004), MUSCLE: multiple sequence alignment with high accuracy and high throughput". Nucleic Acids Research 32(5), 1792-97. DOI:10.1093/nar/gkh340.
  • QUOTE: We describe MUSCLE, a new computer program for creating multiple alignments of protein sequences. Elements of the algorithm include fast distance estimation using $k$ mer counting, progressive alignment using a new profile function we call the log‐expectation score, and refinement using tree‐dependent restricted partitioning.

---