CoChat
Sign Up
Cited by 444Genomics and Phylogenetic StudiesGenome Rearrangement AlgorithmsFractal and DNA sequence analysis

Mugsy: Fast multiple alignment of closely related whole genomes

Open access
Angiuoli, Samuel V., Salzberg, Steven L.·2011·Bioinformatics
DOI 10.1093/bioinformatics/btq665PMC PMC3031037
Open this paper in CoChat — free accountOpen PDF

Abstract

Motivation: The relative ease and low cost of current generation sequencing technologies has led to a dramatic increase in the number of sequenced genomes for species across the tree of life. This increasing volume of data requires tools that can quickly compare multiple whole-genome sequences, millions of base pairs in length, to aid in the study of populations, pan-genomes, and genome evolution. Results: We present a new multiple alignment tool for whole genomes named Mugsy. Mugsy is computationally efficient and can align 31 Streptococcus pneumoniae genomes in less than 2 hours producing alignments that compare favorably to other tools. Mugsy is also the fastest program evaluated for the multiple alignment of assembled human chromosome sequences from four individuals. Mugsy does not require a reference sequence, can align mixtures of assembled draft and completed genome data, and is robust in identifying a rich complement of genetic variation including duplications, rearrangements, and large-scale gain and loss of sequence. Availability: Mugsy is free, open-source software available from http://mugsy.sf.net. Contact: angiuoli@cs.umd.edu Supplementary information: Supplementary data are available at Bioinformatics online.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1093/bioinformatics/btq665

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Scalability in WGA algorithms is a critical characteristic, especially when dealing with larger and more complex genomes.

    “This is a critical characteristic, especially when dealing with larger and more complex genomes [46].”

    From Whole-Genome Alignment: Methods, Challenges, and Future Directions (2024) · cites this paper as [46]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 39

  1. Ahn SM The first Korean genome sequence and analysis: full genome sequencing for a socio-ethnic group Genome Res. 2009 19 1622 1629 19470904 PMC2752128
  2. Batzoglou S The many faces of sequence alignment Brief Bioinform. 2005 6 6 22 15826353
  3. Blanchette M Aligning multiple genomic sequences with the threaded blockset aligner Genome Res. 2004 14 708 715 15060014 PMC383317
  4. Bourque G Reconstructing the genomic architecture of ancestral mammals: lessons from human, mouse, and rat genomes Genome Res. 2004 14 507 516 15059991 PMC383294
  5. Bradley RK Fast statistical alignment PLoS Comput Biol. 2009 5 e1000392 19478997 PMC2684580
  6. Bray N AVID: A global alignment program Genome Res. 2003 13 97 102 12529311 PMC430967
  7. Chen X Tompa M Comparative assessment of methods for aligning multiple genome sequences Nat. Biotechnol. 2010 28 567 572 20495551
  8. Corel E A min-cut algorithm for the consistency problem in multiple sequence alignment Bioinformatics 2010 26 1015 1021 20189940
  9. Darling A Mauve: multiple alignment of conserved genomic sequence with rearrangements Genome Res. 2004 14 1394 1403 15231754 PMC442156
  10. Darling A progressiveMauve: multiple genome alignment with gene gain, loss and rearrangement PLoS ONE 2010 5 e11147 20593022 PMC2892488
  11. Deloger M A genomic distance based on MUM indicates discontinuity between most bacterial species and genera J. Bacteriol. 2009 191 91 99 18978054 PMC2612450
  12. Dewey CN Aligning multiple whole genomes with Mercator and MAVID Methods Mol. Biol. 2007 395 221 236 17993677
  13. Dewey CN Pachter L Evolution at the nucleotide level: the problem of multiple whole-genome alignment Hum. Mol. Genet. 2006 15 R51 R56 (Spec No. 1) 16651369
  14. Doring A SeqAn an efficient, generic C++ library for sequence analysis BMC Bioinformatics 2008 9 11 18184432 PMC2246154
  15. Dubchak I Multiple whole-genome alignments without a reference organism Genome Res. 2009 19 682 689 19176791 PMC2665786
  16. Edgar RC MUSCLE: multiple sequence alignment with high accuracy and high throughput Nucleic Acids Res. 2004 32 1792 1797 15034147 PMC390337
  17. Edmonds J Karp RM Theoretical improvements in algorithmic efficiency for network flow problems J. ACM 1972 19 248 264
  18. Elias I Settling the intractability of multiple alignment J. Comput. Biol. 2006 13 1323 1339 17037961
  19. Gusfield D Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. 1997 New York Cambridge University Press
  20. Hohl M Efficient multiple genome alignment Bioinformatics 2002 18 Suppl. 1 S312 S320 12169561
  21. IHGSC Initial sequencing and analysis of the human genome Nature 2001 409 860 921 11237011
  22. Jacobson G Vo K-P Heaviest increasing/common subsequence problems Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching 1992 Springer 52 66
  23. Kent WJ Evolution's cauldron: duplication, deletion, and rearrangement in the mouse and human genomes Proc. Natl Acad. Sci. USA 2003 100 11484 11489 14500911 PMC208784
  24. Kurtz S Versatile and open software for comparing large genomes Genome Biol. 2004 5 R12 14759262 PMC395750
  25. Margulies EH Analyses of deep mammalian sequence alignments and constraint predictions for 1% of the human genome Genome Res. 2007 17 760 774 17567995 PMC1891336
  26. Medini D The microbial pan-genome Curr. Opin. Genet. Dev. 2005 15 589 594 16185861
  27. Notredame C T-Coffee: a novel method for fast and accurate multiple sequence alignment J. Mol. Biol. 2000 302 205 217 10964570
  28. Paten B Sequence progressive alignment, a framework for practical large-scale probabilistic consistency alignment Bioinformatics 2009 25 295 301 19056777
  29. Paten B Enredo and Pecan: genome-wide mammalian consistency-based multiple alignment with paralogs Genome Res. 2008 18 1814 1828 18849524 PMC2577869
  30. Pevzner P Tesler G Genome rearrangements in mammalian evolution: lessons from human and mouse genomes Genome Res. 2003 13 37 45 12529304 PMC430962
  31. Raphael B A novel method for multiple alignment of sequences with repeated and shuffled elements Genome Res. 2004 14 2336 2346 15520295 PMC525693
  32. Rausch T Segment-based multiple sequence alignment Bioinformatics 2008 24 i187 i192 18689823
  33. Rosenbloom KR ENCODE whole-genome data in the UCSC Genome Browser Nucleic Acids Res. 2009 38 Database issue D620 D625 19920125 PMC2808953
  34. Schwartz S Human-mouse alignments with BLASTZ Genome Res. 2003 13 103 107 12529312 PMC430961
  35. Sherry ST dbSNP: the NCBI database of genetic variation Nucleic Acids Res. 2001 29 308 311 11125122 PMC29783
  36. Thompson JD CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice Nucleic Acids Res. 1994 22 4673 4680 7984417 PMC308517
  37. Treangen TJ Messeguer X M-GCAT: interactively and efficiently constructing large-scale multiple genome comparison frameworks in closely related species BMC Bioinformatics 2006 7 433 17022809 PMC1629028
  38. Wheeler DL Database resources of the National Center for Biotechnology Information Nucleic Acids Res. 2008 36 Database issue D13 D21 18045790 PMC2238880
  39. Zhang Y Waterman MS An Eulerian path approach to local multiple alignment for DNA sequences Proc. Natl Acad. Sci. USA 2005 102 1285 1290 15668398 PMC547885

Cited by

Sorted by citations

Authors
Angiuoli, S. V., & Salzberg, S. L.
Affiliations
University of Maryland, College Park (US)
Corresponding author
Angiuoli, Samuel V.
ORCID
Venue
Bioinformatics
Publisher
Oxford University Press (OUP)
Published
2010-12-09
Volume
27
Issue
3
Pages
334-342
ISSN
  • 1367-4803 (ISSN-L)
  • 1367-4811
DOI
10.1093/bioinformatics/btq665
PMC
PMC3031037
OpenAlex
W2164786886
Cited by
444
References
3
Citations by year
2026: 5 · 2025: 18 · 2024: 14 · 2023: 14 · 2022: 38 · 2021: 33 · 2020: 26 · 2019: 30 · 2018: 43 · 2017: 44 · 2016: 41 · 2015: 42 · 2014: 46 · 2013: 20 · 2012: 19
FWCI
6.07
Type
journal article
Language
en
Open access
Licence
Locations
  • Bioinformatics (publishedVersion, cc-by-nc)
  • PubMed Central (publishedVersion, cc-by-nc)
  • PubMed (publishedVersion)
Funders
  • National Institutes of Health
  • National Institute of General Medical Sciences (R01GM083873)
  • U.S. National Library of Medicine (R01LM006845)
Topics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Genetics › Genome Rearrangement Algorithms
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
Keywords
multiple genome alignment, whole-genome alignment, closely related genomes, pan-genome, genome evolution, Streptococcus pneumoniae, comparative genomics, genetic variation
MeSH terms
Algorithms, Humans, Software, Streptococcus pneumoniae, Sequence Alignment, Genome, Bacterial, Genomics

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review