Fast algorithms for large-scale genome alignment and comparison
Open accessAbstract
We describe a suffix-tree algorithm that can align the entire genome sequences of eukaryotic and prokaryotic organisms with minimal use of computer time and memory. The new system, MUMmer 2, runs three times faster while using one-third as much memory as the original MUMmer system. It has been used successfully to align the entire human and mouse genomes to each other, and to align numerous smaller eukaryotic and prokaryotic genomes. A new module permits the alignment of multiple DNA sequence fragments, which has proven valuable in the comparison of incomplete genome sequences. We also describe a method to align more distantly related genomes by detecting protein sequence homology. This extension to MUMmer aligns two genomes after translating the sequence in all six reading frames, extracts all matching protein sequences and then clusters together matches. This method has been applied to both incomplete and complete genome sequences in order to detect regions of conserved synteny, in which multiple proteins from one organism are found in the same order and orientation in another. The system code is being made freely available by the authors.
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.
Integrity signals
Registry
Cites
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.
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?
MUMmer 2.1 required less memory and ran the four steps faster than the previous version.
“For that reason, the authors proposed a new method that required less memory and ran the four steps faster [13].”
From Whole-Genome Alignment: Methods, Challenges, and Future Directions (2024) · cites this paper as [13]
The Algorithmic Improvements section (page not provided) reports that MUMmer 2 used less memory and aligned the same genomes faster than MUMmer 1.0. The copy does not establish that each of four steps ran faster or identify the improved system specifically as version 2.1. (LLM, conf=0.85)
Experimental — accuracy not yet measured
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
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669 · see citing works
Flagged first, then by citations
Research works printed but not linked: 2
- Pearson,W.R. (2000) Flexible sequence similarity searching with the FASTA3 program package. Methods Mol. Biol., 132, 185-219.
- Gusfield,D. (1997) Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York.
Cited by
Sorted by citations
STAR: ultrafast universal RNA-seq aligner
Dobin, A., Davis, C. A., Schlesinger, F., Drenkow, J., Zaleski, C., Jha, S., Batut, P., Chaisson, M., & Gingeras, T. R. (2013) · Bioinformatics · doi:10.1093/bioinformatics/bts635 · Cited by 51,709 · see citing works
Genome sequence of the human malaria parasite Plasmodium falciparum
Gardner, M. J., Hall, N., Fung, E., White, O., Berriman, M., Hyman, R. W., Carlton, J. M., Pain, A., Nelson, K. E., Bowman, S., et al. (2002) · Nature · doi:10.1038/nature01097 · Cited by 4,407 · see citing works
Self-citationThe complete sequence of a human genome
Nurk, S., Koren, S., Rhie, A., Rautiainen, M., Bzikadze, A. V., Mikheenko, A., Vollger, M. R., Altemose, N., Uralsky, L., Gershman, A., et al. (2022) · Science · doi:10.1126/science.abj6987 · Cited by 3,136 · see citing works
Biogeography and individuality shape function in the human skin metagenome
Program, N. C. S., Oh, J., Byrd, A. L., Deming, C., Conlan, S., Kong, H. H., & Segre, J. A. (2014) · Nature · doi:10.1038/nature13786 · Cited by 1,148 · see citing works
Snitkin, E. S., Zelazny, A. M., Thomas, P. J., Stock, F., Program, N. C. S., Henderson, D. K., Palmore, T. N., & Segre, J. A. (2012) · Science Translational Medicine · doi:10.1126/scitranslmed.3004129 · Cited by 863 · see citing works
<i>Clostridium ljungdahlii</i> represents a microbial production platform based on syngas
Köpke, M., Held, C., Hujer, S., Liesegang, H., Wiezer, A., Wollherr, A., Ehrenreich, A., Liebl, W., Gottschalk, G., & Dürre, P. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1004716107 · Cited by 660 · see citing works
Charbonneau, M. R., O’Donnell, D., Blanton, L. V., Totten, S. M., Davis, J. C. C., Barratt, M. J., Cheng, J., Guruge, J., Talcott, M., Bain, J. R., et al. (2016) · Cell · doi:10.1016/j.cell.2016.01.024 · Cited by 606 · see citing works
Olm, M. R., Crits-Christoph, A., Bouma-Gregson, K., Firek, B. A., Morowitz, M. J., & Banfield, J. F. (2021) · Nature Biotechnology · doi:10.1038/s41587-020-00797-0 · Cited by 537 · see citing works
Ovcharenko, I., Nobrega, M. A., Loots, G. G., & Stubbs, L. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh355 · Cited by 519 · see citing works
Case, J. B., Rothlauf, P. W., Chen, R. E., Liu, Z., Zhao, H., Kim, A. S., Bloyet, L.-M., Zeng, Q., Tahan, S., Droit, L., et al. (2020) · Cell Host & Microbe · doi:10.1016/j.chom.2020.06.021 · Cited by 410 · see citing works
Supply, P., Marceau, M., Mangenot, S., Roche, D., Rouanet, C., Khanna, V., Majlessi, L., Criscuolo, A., Tap, J., Pawlik, A., et al. (2013) · Nature Genetics · doi:10.1038/ng.2517 · Cited by 305 · see citing works
Delmont, T. O., Gaia, M., Hinsinger, D. D., Frémont, P., Vanni, C., Fernandez-Guerra, A., Eren, A. M., Kourlaiev, A., d'Agata, L., Clayssen, Q., et al. (2022) · Cell Genomics · doi:10.1016/j.xgen.2022.100123 · Cited by 173 · see citing works
Dumas, E., Christina Boritsch, E., Vandenbogaert, M., Rodríguez de la Vega, R. C., Thiberge, J.-M., Caro, V., Gaillard, J.-L., Heym, B., Girard-Misguich, F., Brosch, R., et al. (2016) · Genome Biology and Evolution · doi:10.1093/gbe/evw001 · Cited by 112 · see citing works
Forche, A., Cromie, G., Gerstein, A. C., Solis, N. V., Pisithkul, T., Srifa, W., Jeffery, E., Abbey, D., Filler, S. G., Dudley, A. M., et al. (2018) · Genetics · doi:10.1534/genetics.118.301019 · Cited by 94 · see citing works
Computational discovery of internal micro-exons
Volfovsky, N., Haas, B. J., & Salzberg, S. L. (2003) · Genome Research · doi:10.1101/gr.677503 · Cited by 87 · see citing works
Self-citationKim, J.-H., Dilthey, A. T., Nagaraja, R., Lee, H.-S., Koren, S., Dudekula, D., Wood III, W. H., Piao, Y., Ogurtsov, A. Y., Utani, K., et al. (2018) · Nucleic Acids Research · doi:10.1093/nar/gky442 · Cited by 86 · see citing works
Self-citationGaps and complex structurally variant loci in phased genome assemblies
Porubsky, D., Vollger, M. R., Harvey, W. T., Rozanski, A. N., Ebert, P., Hickey, G., Hasenfeld, P., Sanders, A. D., Stober, C., Human Pangenome Reference Consortium, et al. (2023) · Genome Research · doi:10.1101/gr.277334.122 · Cited by 58 · see citing works
Ouwerkerk, J. P., Tytgat, H. L. P., Elzinga, J., Koehorst, J., Van den Abbeele, P., Henrissat, B., Gueimonde, M., Cani, P. D., Van de Wiele, T., Belzer, C., et al. (2022) · Microorganisms · doi:10.3390/microorganisms10081605 · Cited by 23 · see citing works
Whole-Genome Alignment: Methods, Challenges, and Future Directions
Saada, B., Zhang, T., Siga, E., Zhang, J., & Magalhães Muniz, M. M. (2024) · Applied Sciences · doi:10.3390/app14114837 · Cited by 15 · see citing works
- Authors
- Delcher, A. L.
- Affiliations
- Loyola University Maryland (US)
- Corresponding author
- Delcher, A. L.
- Venue
- Nucleic Acids Research
- Publisher
- Oxford University Press (OUP)
- Published
- 2002-06-01
- Volume
- 30
- Issue
- 11
- Pages
- 2478-2483
- ISSN
- 0305-1048 (ISSN-L)
- 1362-4962
- PMC
- PMC117189
- OpenAlex
- W2095685450
- Cited by
- 1,036
- References
- 1
- Citations by year
- 2026: 16 · 2025: 23 · 2024: 44 · 2023: 35 · 2022: 44 · 2021: 53 · 2020: 74 · 2019: 48 · 2018: 48 · 2017: 79 · 2016: 54 · 2015: 51 · 2014: 53 · 2013: 41 · 2012: 28
- FWCI
- 13.34
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Nucleic Acids Research (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- Funders
- National Science Foundation
- National Institutes of Health
- U.S. Public Health Service (R01-A142243)
- National Institute of Allergy and Infectious Diseases
- 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
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Keywords
- genome alignment, comparative genomics, multiple sequence alignment, protein homology, conserved synteny, human genome, mouse genome, eukaryotic genomes, prokaryotic genomes, memory-efficient alignment
- MeSH terms
- Algorithms, Animals, Computers, Humans, Plasmodium, Software, Time Factors, Genome, Human, Sequence Alignment, Genome, Genome, Bacterial, Genome, Protozoan, Computational Biology, Contig Mapping, 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
