CoChat
Sign Up
Cited by 3,848Genome Rearrangement AlgorithmsGenomics and Phylogenetic StudiesChromosomal and Genetic Variations

progressiveMauve: Multiple Genome Alignment with Gene Gain, Loss and Rearrangement

Open access
Darling, Aaron E., Mau, Bob, Perna, Nicole T.·2010·PLoS ONE
DOI 10.1371/journal.pone.0011147PMC PMC2892488
Open this paper in CoChat — free accountOpen PDF

Abstract

BACKGROUND: Multiple genome alignment remains a challenging problem. Effects of recombination including rearrangement, segmental duplication, gain, and loss can create a mosaic pattern of homology even among closely related organisms. METHODOLOGY/PRINCIPAL FINDINGS: We describe a new method to align two or more genomes that have undergone rearrangements due to recombination and substantial amounts of segmental gain and loss (flux). We demonstrate that the new method can accurately align regions conserved in some, but not all, of the genomes, an important case not handled by our previous work. The method uses a novel alignment objective score called a sum-of-pairs breakpoint score, which facilitates accurate detection of rearrangement breakpoints when genomes have unequal gene content. We also apply a probabilistic alignment filtering method to remove erroneous alignments of unrelated sequences, which are commonly observed in other genome alignment methods. We describe new metrics for quantifying genome alignment accuracy which measure the quality of rearrangement breakpoint predictions and indel predictions. The new genome alignment algorithm demonstrates high accuracy in situations where genomes have undergone biologically feasible amounts of genome rearrangement, segmental gain and loss. We apply the new algorithm to a set of 23 genomes from the genera Escherichia, Shigella, and Salmonella. Analysis of whole-genome multiple alignments allows us to extend the previously defined concepts of core- and pan-genomes to include not only annotated genes, but also non-coding regions with potential regulatory roles. The 23 enterobacteria have an estimated core-genome of 2.46Mbp conserved among all taxa and a pan-genome of 15.2Mbp. We document substantial population-level variability among these organisms driven by segmental gain and loss. Interestingly, much variability lies in intergenic regions, suggesting that the Enterobacteriacae may exhibit regulatory divergence. CONCLUSIONS: The multiple genome alignments generated by our software provide a platform for comparative genomic and population genomic studies. Free, open-source software implementing the described genome alignment approach is available from http://gel.ahabs.wisc.edu/mauve.

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.1371/journal.pone.0011147

Cites

1 of 1 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?

  • Progressive alignment has been successfully applied to whole-genome alignment before, e.g., by progressiveMauve and TBA/MULTIZ.

    “Progressive alignment has been successfully applied to whole-genome alignment before—for example, by progressiveMauve21 and TBA/MULTIZ22.”

    From Progressive Cactus is a multiple-genome aligner for the thousand-genome era (2020) · cites this paper as [21]

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: 74

  1. [1]Kumar S Filipski A 2007 Multiple sequence alignment: In pursuit of homologous DNA positions. Genome Res 17 127 135 17272647
  2. [2]Lunter G 2007 Probabilistic whole-genome alignments reveal high indel rates in the human and mouse genomes. Bioinformatics 23 17646308
  3. [3]Prakash A Tompa M 2007 Measuring the accuracy of genome-size multiple alignments. Genome Biology 8 R124+ 17594489 PMC2394773
  4. [4]Dewey CN Pachter L 2006 Evolution at the nucleotide level: the problem of multiple whole-genome alignment. Hum Mol Genet 15 Suppl 1 16651369
  5. [5]Fitch WM 2000 Homology: a personal view on some of the problems. Trends Genet 16 227 231 10782117
  6. [6]Delcher AL Kasif S Fleischmann RD Peterson J White O 1999 Alignment of whole genomes. Nucleic Acids Res 27 2369 76 10325427 PMC148804
  7. [7]Delcher AL Phillippy A Carlton J Salzberg SL 2002 Fast algorithms for large-scale genome alignment and comparison. Nucleic acids research 30 2478 2483 12034836 PMC117189
  8. [8]Kurtz S Phillippy A Delcher AL Smoot M Shumway M 2004 Versatile and open software for comparing large genomes. Genome Biol 5 R12 14759262 PMC395750
  9. [9]Darling ACE Mau B Blattner FR Perna NT 2004 Mauve: multiple alignment of conserved genomic sequence with rearrangements. Genome Res 14 1394 403 15231754 PMC442156
  10. [10]Perna NT Plunkett G Burland V Mau B Glasner JD 2001 Genome sequence of enterohaemorrhagic Escherichia coli O157:H7. Nature 409 529 33 11206551
  11. [11]Welch RA Burland V Plunkett G Redford P Roesch P 2002 Extensive mosaic structure revealed by the complete genome sequence of uropathogenic Escherichia coli. Proc Natl Acad Sci U S A 99 17020 4 12471157 PMC139262
  12. [12]Hogg JS Hu FZ Janto B Boissy R Hayes J 2007 Characterization and modeling of the Haemophilus influenzae core- and supra-genomes based on the complete genomic sequences of Rd and 12 clinical nontypeable strains. Genome Biology 8 R103+ 17550610 PMC2394751
  13. [13]Hsiao WW Ung K Aeschliman D Bryan J Finlay BB 2005 Evidence of a large novel gene pool associated with prokaryotic genomic islands. PLoS Genetics 1 e62+ 16299586 PMC1285063
  14. [14]Tettelin H Masignani V Cieslewicz MJ Donati C Medini D 2005 Genome analysis of multiple pathogenic isolates of Streptococcus agalactiae: implications for the microbial “pan-genome”. Proc Natl Acad Sci U S A 102 13950 13955 16172379 PMC1216834
  15. [15]Vernikos GS Thomson NR Parkhill J 2007 Genetic flux over time in the Salmonella lineage. Genome Biology 8 R100+ 17547764 PMC2394748
  16. [16]Mau B Glasner JD Darling AE Perna NT 2006 Genome-wide detection and analysis of homologous recombination among sequenced strains of Escherichia coli. Genome Biology 7 R44+ 16737554 PMC1779527
  17. [17]Blanchette M Kent WJ Riemer C Elnitski L Smit AF 2004 Aligning multiple genomic sequences with the threaded blockset aligner. Genome Res 14 708 15 15060014 PMC383317
  18. [18]Bray N Pachter L 2003 MAVID multiple alignment server. Nucleic Acids Res 31 3525 6 12824358 PMC169029
  19. [19]Brudno M Do CB Cooper GM Kim MF Davydov E 2003 LAGAN and Multi-LAGAN: efficient tools for large-scale multiple alignment of genomic DNA. Genome Res 13 721 31 12654723 PMC430158
  20. [20]Hohl M Kurtz S Ohlebusch E 2002 Efficient multiple genome alignment. Bioinformatics 18 Suppl 1 S312 20 12169561
  21. [21]Ogurtsov AY Roytberg MA Shabalina SA Kondrashov AS 2002 Owen: aligning long collinear regions of genomes. Bioinformatics 18 1703 1704 12490463
  22. [22]Brudno M Steinkamp R Morgenstern B 2004 The chaos/dialign www server for multiple alignment of genomic sequences. Nucl Acids Res 32 W41 44 15215346 PMC441499
  23. [23]Chao KM Zhang J Ostell J Miller W 1995 A local alignment tool for very long dna sequences. Comput Appl Biosci 11 147 153 7620986
  24. [24]Li L Stoeckert CJ Roos DS 2003 OrthoMCL: identification of ortholog groups for eukaryotic genomes. Genome Res 13 2178 2189 12952885 PMC403725
  25. [25]Brudno M Malde S Poliakov A Do CB Couronne O 2003 Glocal alignment: finding rearrangements during alignment. Bioinformatics 19 Suppl 1 I54 I62 12855437
  26. [26]Swidan F Rocha EPC Shmoish M Pinter RY 2006 An integrative method for accurate comparative genome mapping. PLoS Comput Biol 2 PMC1526463 16933978
  27. [27]Vinh LS Varon A Wheeler WC 2006 Pairwise alignment with rearrangements. Genome Inform 17 141 151 17503387
  28. [28]Ovcharenko I Loots GG Giardine BM Hou M Ma J 2005 Mulan: Multiple-sequence local alignment and visualization for studying function and evolution. Genome Res 15 184 94 15590941 PMC540288
  29. [29]Phuong TM Do CB Edgar RC Batzoglou S 2006 Multiple alignment of protein sequences with repeats and rearrangements. Nucleic Acids Res 34 5932 42 17068081 PMC1635250
  30. [30]Raphael B Zhi D Tang H Pevzner P 2004 A novel method for multiple alignment of sequences with repeated and shuffled elements. Genome Res 14 2336 46 15520295 PMC525693
  31. [31]Treangen TJ Messeguer X 2006 M-GCAT: Interactively and efficiently constructing large-scale multiple genome comparison frameworks in closely related species. BMC Bioinformatics 7 433+ 17022809 PMC1629028
  32. [32]Dubchak I Poliakov A Kislyuk A Brudno M 2009 Multiple whole-genome alignments without a reference organism. Genome research 19 682 689 19176791 PMC2665786
  33. [33]Paten B Herrero J Beal K Fitzgerald S Birney E 2008 Enredo and pecan: genome-wide mammalian consistency-based multiple alignment with paralogs. Genome research 18 1814 1828 18849524 PMC2577869
  34. [34]Treangen TJ Darling AE Achaz G Ragan MA Messeguer X 2009 A novel heuristic for local multiple alignment of interspersed dna repeats. IEEE/ACM Transactions on Computational Biology and Bioinformatics 6 180 189 19407343
  35. [35]Zhang Y Waterman MS 2005 An eulerian path approach to local multiple alignment for dna sequences. Proceedings of the National Academy of Sciences of the United States of America 102 1285 1290 15668398 PMC547885
  36. [36]Darling AE Treangen TJ Zhang L Kuiken C Messeguer X 2006 Procrastination leads to efficient filtration for local multiple alignment. WABI 2006: Proceedings of the sixth annual Workshop on Algorithms in Bioinformatics Germany Springer Verlag 126 137 volume 4175
  37. [37]Ma B Tromp J Li M 2002 PatternHunter: faster and more sensitive homology search. Bioinformatics 18 440 5 11934743
  38. [38]Darling AE 2006 Computational Analysis of Genome Evolution. Ph.D. thesis, University of Wisconsin–Madison
  39. [39]Kucherov G Noe L Roytberg M 2005 Multiseed lossless filtration. IEEE/ACM Trans Comput Biol Bioinformatics 2 51 61 17044164
  40. [40]Chiaromonte F Yap VB Miller W 2002 Scoring pairwise genomic sequence alignments. Pac Symp Biocomput 115 126 11928468
  41. [41]Lippert RA Zhao X Florea L Mobarry C Istrail S 2004 Finding anchors for genomic sequence comparison. RECOMB '04: Proceedings of the eighth annual international conference on Resaerch in computational molecular biology New York, NY, USA ACM Press 233 241
  42. [42]Blanchette M Bourque G Sankoff D 1997 Breakpoint Phylogenies. Genome Inform Ser Workshop Genome Inform 8 25 34 11072302
  43. [43]Darling AE Mau B Blattner FR Perna NT 2004 GRIL: Genome rearrangement and inversion locator. Bioinformatics 20 122 124 14693819
  44. [44]Edgar RC 2004 MUSCLE: a multiple sequence alignment method with reduced time and space complexity. BMC Bioinformatics 5 113 15318951 PMC517706
  45. [45]Margulies EH Cooper GM Asimenos G Thomas DJ Dewey CN 2007 Analyses of deep mammalian sequence alignments and constraint predictions for 1% of the human genome. Genome Res 17 760 774 17567995 PMC1891336
  46. [46]Thompson JD Plewniak F Poch O 1999 A comprehensive comparison of multiple sequence alignment programs. Nucleic Acids Res 27 2682 90 10373585 PMC148477
  47. [47]Achaz G Coissac E Netter P Rocha EP 2003 Associations between inverted repeats and the structural evolution of bacterial genomes. Genetics 164 1279 1289 12930739 PMC1462642
  48. [48]Lunter G Rocco A Mimouni N Heger A Caldeira A 2008 Uncertainty in homology inferences: Assessing and improving genomic sequence alignment. Genome Res 18 298 309 18073381 PMC2203628
  49. [49]Dewey CN 2007 Aligning multiple whole genomes with mercator and mavid. Methods in molecular biology (Clifton, NJ) 395 221 236 17993677
  50. [50]Kent WJ Baertsch R Hinrichs A Miller W Haussler D 2003 Evolution's cauldron: duplication, deletion, and rearrangement in the mouse and human genomes. Proceedings of the National Academy of Sciences of the United States of America 100 11484 11489 14500911 PMC208784
  51. [51]Bradley RK Roberts A Smoot M Juvekar S Do J 2009 Fast statistical alignment. PLoS Computational Biology 5 e1000392+ 19478997 PMC2684580
  52. [52]Durbin R Eddy S Krogh A Mitchison G 1998 Biological Sequence Analysis Cambridge University Press 80 94 chapter 4
  53. [53]Pupo GM Lan R Reeves PR 2000 Multiple independent origins of Shigella clones of Escherichia coli and convergent evolution of many of their characteristics. Proc Natl Acad Sci U S A 97 10567 72 10954745 PMC27065
  54. [54]Yang J Nie H Chen L Zhang X Yang F 2007 Revisiting the molecular evolutionary history of Shigella spp. J Mol Evol 64 71 9 17160643
  55. [55]Didelot X Darling A Falush D 2009 Inferring genomic flux in bacteria. Genome research 19 306 317 19015321 PMC2652212
  56. [56]Rasko DA Rosovitz MJ Myers GS Mongodin EF Fricke WF 2008 The pangenome structure of Escherichia coli: comparative genomic analysis of E. coli commensal and pathogenic isolates. Journal of Bacteriology 190 6881 6893 18676672 PMC2566221
  57. [57]Hannenhalli S Pevzner PA 1995 Transforming men into mice (polynomial algorithm for genomic distance problem). FOCS '95: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95) Washington, DC, USA IEEE Computer Society 581 592
  58. [58]Tannier E Sagot MF 2004 Sorting by reversals in subquadratic time. Lecture Notes in Computer Science Springer-Verlag 1 13 volume 3109
  59. [59]Larget B Simon DL Kadane J 2002 On a Bayesian approach to phylogenetic inference from animal mitochondrial genome arrangements. Journal of the Royal Statistical Society B 64 681 693
  60. [60]Tang J Moret BM 2003 Scaling up accurate phylogenetic reconstruction from gene-order data. Bioinformatics 19 Suppl 1 i305 i312 12855474
  61. [61]Alekseyev MA 2008 Multi-break rearrangements and breakpoint re-uses: from linear to circular genomes. Journal of Computational Biology 15 1117 31 18788907
  62. [62]Bergeron A Mixtacki J Stoye J 2006 A unifying view of genome rearrangements. Bucher P Moret BME WABI '06: Proceedings of the Sixth International Workshop on Algorithms in Bioinformatics Springer 163 173 volume 4175 of Lecture Notes in Computer Science
  63. [63]Yancopoulos S Attie O Friedberg R 2005 Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21 3340 3346 15951307
  64. [64]Darling AE Miklós I Ragan MA 2008 Dynamics of genome rearrangement in bacterial populations. PLoS Genetics 4 e1000128 18650965 PMC2483231
  65. [65]Swidan F Ziv-Ukelson M Pinter RY 2006 On the repeat-annotated phylogenetic tree reconstruction problem. Journal of computational biology: a journal of computational molecular cell biology 13 1397 1418 17061918
  66. [66]Miller W Rosenbloom K Hardison RC Hou M Taylor J 2007 28-Way vertebrate alignment and conservation track in the UCSC Genome Browser. Genome Res gr.6761107+ PMC2099589 17984227
  67. [67]Mayor C Brudno M Schwartz JR Poliakov A Rubin EM 2000 Vista: visualizing global dna sequence alignments of arbitrary length. Bioinformatics (Oxford, England) 16 1046 1047 11159318
  68. [68]Oppenheim AB Rudd KE Mendelson I Teff D 1993 Integration host factor binds to a unique class of complex repetitive extragenic dna sequences in escherichia coli. Molecular microbiology 10 113 122 7968507
  69. [69]Langille MGI Eisen JA 2010 Biotorrents: A file sharing service for scientific data. PLoS ONE 5 e10071+ 20418944 PMC2854681
  70. [71]Didelot X Falush D 2007 Inference of bacterial microevolution using multilocus sequence data. Genetics 175 1251 1266 17151252 PMC1840087
  71. [72]Ma J Ratan A Raney BJ Suh BB Miller W 2008 The infinite sites model of genome evolution. Proceedings of the National Academy of Sciences of the United States of America 105 14254 14261 18787111 PMC2533685
  72. [73]Akerborg O Sennblad B Arvestad L Lagergren J 2009 Simultaneous bayesian gene tree reconstruction and reconciliation analysis. Proceedings of the National Academy of Sciences of the United States of America 106 5714 5719 19299507 PMC2667006
  73. [74]Fu Z Chen X Vacic V Nan P Zhong Y 2007 Msoar: A high-throughput ortholog assignment system based on genome rearrangement. Journal of Computational Biology 14 1160 1175 17990975
  74. [75]Do CB Mahabhashyam MS Brudno M Batzoglou S 2005 ProbCons: Probabilistic consistency-based multiple sequence alignment. Bioinformatics 15 330 340 PMC546535 15687296

Cited by

Sorted by citations

Authors
Darling, A. E., Mau, B., & Perna, N. T.
Affiliations
University of Wisconsin–Madison (US)
Corresponding author
Darling, Aaron E.
ORCID
Venue
PLoS ONE
Publisher
Public Library of Science (PLoS)
Published
2010-06-25
Volume
5
Issue
6
Pages
e11147
ISSN
1932-6203 (ISSN-L)
DOI
10.1371/journal.pone.0011147
PMC
PMC2892488
OpenAlex
W2041257508
Cited by
3,848
References
1
Citations by year
2026: 161 · 2025: 196 · 2024: 200 · 2023: 203 · 2022: 309 · 2021: 363 · 2020: 339 · 2019: 347 · 2018: 294 · 2017: 282 · 2016: 261 · 2015: 263 · 2014: 244 · 2013: 165 · 2012: 135
FWCI
63.43
Type
journal article
Language
en
Open access
Licence
Locations
  • PLoS ONE (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
  • Figshare (submittedVersion, cc-by)
  • UTS ePRESS (University of Technology Sydney) (submittedVersion)
  • OPUS - Open Publications of UTS Scholars (University of Technology Sydney) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (0630765)
  • U.S. Department of Health and Human Services
  • National Institutes of Health
  • U.S. Public Health Service (HHSN266200400040C)
  • National Institute of General Medical Sciences (R01GM062994)
  • National Institute of Allergy and Infectious Diseases
Topics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Genetics › Genome Rearrangement Algorithms
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
  • Life Sciences › Agricultural and Biological Sciences › Plant Science › Chromosomal and Genetic Variations
Keywords
multiple genome alignment, genome rearrangement, gene gain and loss, segmental duplication, recombination, core genome, pan-genome, Escherichia, Shigella, Salmonella, intergenic regions, regulatory divergence
MeSH terms
Algorithms, Models, Theoretical, Gene Rearrangement, Sequence Alignment, Genome, Bacterial

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