Cited by 611Genomics and Phylogenetic StudiesGenome Rearrangement AlgorithmsChromosomal and Genetic Variations

The DOI matches its Crossref record; 66 of the 66 references it cites were found in a registry or an index; 40 of the 49 sources its claims cite were checked for support.

Progressive Cactus is a multiple-genome aligner for the thousand-genome era

Open access

Abstract

New genome assemblies have been arriving at a rapidly increasing pace, thanks to decreases in sequencing costs and improvements in third-generation sequencing technologies 1–3 . For example, the number of vertebrate genome assemblies currently in the NCBI (National Center for Biotechnology Information) database 4 increased by more than 50% to 1,485 assemblies in the year from July 2018 to July 2019. In addition to this influx of assemblies from different species, new human de novo assemblies 5 are being produced, which enable the analysis of not only small polymorphisms, but also complex, large-scale structural differences between human individuals and haplotypes. This coming era and its unprecedented amount of data offer the opportunity to uncover many insights into genome evolution but also present challenges in how to adapt current analysis methods to meet the increased scale. Cactus 6 , a reference-free multiple genome alignment program, has been shown to be highly accurate, but the existing implementation scales poorly with increasing numbers of genomes, and struggles in regions of highly duplicated sequences. Here we describe progressive extensions to Cactus to create Progressive Cactus, which enables the reference-free alignment of tens to thousands of large vertebrate genomes while maintaining high alignment quality. We describe results from an alignment of more than 600 amniote genomes, which is to our knowledge the largest multiple vertebrate genome alignment created so far.

Overview

AI snapshot

Written from the paper’s full text.

TL;DR

Progressive Cactus extends the reference-free Cactus aligner with a progressive strategy that scales linearly with genome number while retaining high accuracy and ancestral reconstruction. The authors demonstrate it on simulated data, guide-tree and assembly-quality tests, and a 605-genome amniote alignment spanning more than 1 trillion bases.

Key findings

  • Progressive Cactus achieved higher Alignathon accuracy than any participating aligner, with F1 scores of 0.989 for simulated primates and 0.795 for simulated mammals. In simulated catarrhine alignments, progressive mode reduced runtime by 15% for 10 species and 48% for 20 species versus a star-tree strategy.
  • Guide-tree choice had limited impact: across four alignments of 48 avian species on chromosome 1, an average of 98.5% of aligned pairs were identical between any two alignments, and pairwise species F1 scores between Jarvis- and Prum-based trees were at least 0.955.
  • The 600-way amniote alignment combined 242 Zoonomia mammals and 363 B10K avians, totaling 605 genomes and 1.07 trillion bases, using 73,692 instance-hours and 2.1 million core-hours; the combined common ancestor size was 181 Mb. Median human coverage was 2.3 Gb from Euarchonta, 1.2 Gb from Laurasiatheria, and 1.0 Gb from Glires.
  • Ancestral reconstructions retained 86% of human coding bases in the placental ancestor and 95% of chicken coding bases in the avian ancestor. Best-hit filtering reduced human sequence mapping to two or more chimpanzee locations from 6.1% to 2.6% and reduced inferred paralogous alignments from 46% to 26%; Progressive Cactus covered 69.4% of chicken versus 64.9% for MULTIZ, and 79% of zebra finch versus 49.2% for MULTIZ.

Methods

  • Progressive Cactus uses an input guide tree to recursively split whole-genome alignment into subproblems, each comparing ingroup genomes plus outgroup genomes; subproblems use LASTZ local alignments, CAF and BAR algorithms, and ancestral assembly reconstruction, with results combined into HAL format.
  • Evaluations included Alignathon simulated primate and mammal datasets; twenty simulated 30-Mb catarrhine genomes under progressive versus star trees; 48 avian species reduced to chicken chromosome 1 under four guide trees; 11 boreoeutherian mammals with high- versus low-quality assemblies; and the 605-genome amniote alignment.
  • Main analyses compared runtime, precision/recall/F1 against truth sets, Jaccard similarity of aligned pairs, coverage statistics, micro-indel rates, RepeatMasker annotations, and transcript/gene mappings against BLAT, BLAST, LASTZ, and MULTIZ.

Limitations

  • Stated: ancestral reconstructions are hypothetical histories; ancestral base calls are generated during alignment and may differ from ideal post hoc calls, though `ancestorsML` can re-estimate them. Adding a genome to an existing alignment re-infers at most one ancestral sequence, so rare sequence in the new genome may not align properly to distant outgroups.
  • Stated: paralogy resolution forbids representing incomplete lineage sorting or horizontal transfer and cannot exactly order multiple duplication events along a single branch. Guide trees can affect alignments, though multiple outgroups reduce this effect, and poor assembly quality can still alter alignments.
  • Evident: the 600-way alignment is a composite of the Zoonomia and B10K alignments joined by a linker alignment using frog, coelacanth, and zebrafish outgroups, not a single monolithic run; it also required large computational resources (2.1 million core-hours).

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1038/s41586-020-2871-y

Cites

66 of 66 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Figures

Fig. 1 The alignment process within Progressive Cactus. a, A large alignment problem is split into many smaller subproblems using an input guide tree. Each subproblem compares a set of ingroup genomes (the children of the internal node to be reconstructed) against each other as well as a sample of outgroup genomes (non-descendants of the internal node in question). b, Flowchart represents the phases in which the overall alignment, as well as each subproblem alignment, proceeds through. The end result is a new genome assembly that represents the Progressive Cactus reconstruction of the ancestral genome, and an alignment between this ancestral genome and its children. After all subproblems have been completed, the parent–child alignments are combined to create the full reference-free alignment in the HAL27 format.
Fig. 1 The alignment process within Progressive Cactus. a, A large alignment problem is split into many smaller subproblems using an input guide tree. Each subproblem compares a set of ingroup genomes (the children of the internal node to be reconstructed) against each other as well as a sample of outgroup genomes (non-descendants of the internal node in question). b, Flowchart represents the phases in which the overall alignment, as well as each subproblem alignment, proceeds through. The end result is a new genome assembly that represents the Progressive Cactus reconstruction of the ancestral genome, and an alignment between this ancestral genome and its children. After all subproblems have been completed, the parent–child alignments are combined to create the full reference-free alignment in the HAL27 format.CC BY · PubMed Central
Fig. 2 Comparing alignments of varying numbers of simulated genomes using Progressive Cactus. a, The progressive mode of Progressive Cactus is shown, versus the mode without progressive decomposition that is similar to that previously described6 (‘star’). The average total runtime of the two alignment methods across three runs is shown. Data are mean and s.d. The runtime is identical when aligning two genomes as the alignment problem is not further decomposed, but the linear scaling of the progressive mode means it is much faster with large numbers of genomes than the quadratic scaling required without progressive alignment. b, The precision, recall and F1 score (harmonic mean of precision and recall) of aligned pairs for each alignment compared with pairs from the true alignment produced by the simulation. Source data
Fig. 2 Comparing alignments of varying numbers of simulated genomes using Progressive Cactus. a, The progressive mode of Progressive Cactus is shown, versus the mode without progressive decomposition that is similar to that previously described6 (‘star’). The average total runtime of the two alignment methods across three runs is shown. Data are mean and s.d. The runtime is identical when aligning two genomes as the alignment problem is not further decomposed, but the linear scaling of the progressive mode means it is much faster with large numbers of genomes than the quadratic scaling required without progressive alignment. b, The precision, recall and F1 score (harmonic mean of precision and recall) of aligned pairs for each alignment compared with pairs from the true alignment produced by the simulation. Source dataCC BY · PubMed Central
Fig. 3 Analysing the 600-way amniote alignment. a, The species tree relating the 600 genomes. Branches are coloured by clades as in b and c. b, Percentage coverage on human within the eutherian mammals, grouped by clade from highest to lowest coverage. c, As in b, but for coverage on chicken within the avian alignment. d, Percentage of various regions within the human genome mappable to each ancestral genome reconstructed along the path leading from human to the root. The positions of selected ancestors are labelled by dotted lines to indicate useful taxonomic reference points as context. UTR, untranslated region. e, As in d, but for the path of reconstructed ancestors between chicken and the root. Source data
Fig. 3 Analysing the 600-way amniote alignment. a, The species tree relating the 600 genomes. Branches are coloured by clades as in b and c. b, Percentage coverage on human within the eutherian mammals, grouped by clade from highest to lowest coverage. c, As in b, but for coverage on chicken within the avian alignment. d, Percentage of various regions within the human genome mappable to each ancestral genome reconstructed along the path leading from human to the root. The positions of selected ancestors are labelled by dotted lines to indicate useful taxonomic reference points as context. UTR, untranslated region. e, As in d, but for the path of reconstructed ancestors between chicken and the root. Source dataCC BY · PubMed Central
Fig. 4 Comparing Cactus and MULTIZ alignment coverage. A comparison of coverage in the Progressive Cactus avian alignment compared to a chicken-referenced MULTIZ22 alignment of the same genomes. Coverage of both alignments on chicken and zebra finch is shown to illustrate the effects of reference bias on the completeness of the MULTIZ alignment. The diagonal dotted line indicates a slope of 1 (that is, if the coverage of MULTIZ and Progressive Cactus were equal). Source data
Fig. 4 Comparing Cactus and MULTIZ alignment coverage. A comparison of coverage in the Progressive Cactus avian alignment compared to a chicken-referenced MULTIZ22 alignment of the same genomes. Coverage of both alignments on chicken and zebra finch is shown to illustrate the effects of reference bias on the completeness of the MULTIZ alignment. The diagonal dotted line indicates a slope of 1 (that is, if the coverage of MULTIZ and Progressive Cactus were equal). Source dataCC BY · PubMed Central
Extended Data Fig. 1 Results from improved paralogue filtering. a, b, A sample snake track64 within a recently duplicated region before (a) and after (b) the filtering change. Nucleotide substitutions are shown as red bars, and insertions are shown as thin orange bars. c, Coverage results from two alignments of identical assemblies using the outgroup and best-hit filtering methods. Multiple-mappings: sites that map to two or more sites on the target genome. d, Results from comparing phylogenetic trees implicit in the HAL alignment to ML re-estimated trees of the same regions. ‘Early’ coalescences indicate that too many duplication events have been created in the reconciled trees, and ‘late’ indicates that too many loss events have been created. e, Percentage of human genes that map more than once to the chimp/gorilla genomes in two CAT9 annotations using alignments created with the outgroup and best-hit filtering methods. KZNF, KRAB zinc-finger genes.
Extended Data Fig. 1 Results from improved paralogue filtering. a, b, A sample snake track64 within a recently duplicated region before (a) and after (b) the filtering change. Nucleotide substitutions are shown as red bars, and insertions are shown as thin orange bars. c, Coverage results from two alignments of identical assemblies using the outgroup and best-hit filtering methods. Multiple-mappings: sites that map to two or more sites on the target genome. d, Results from comparing phylogenetic trees implicit in the HAL alignment to ML re-estimated trees of the same regions. ‘Early’ coalescences indicate that too many duplication events have been created in the reconciled trees, and ‘late’ indicates that too many loss events have been created. e, Percentage of human genes that map more than once to the chimp/gorilla genomes in two CAT9 annotations using alignments created with the outgroup and best-hit filtering methods. KZNF, KRAB zinc-finger genes.CC BY · PubMed Central
Extended Data Fig. 2 Methods of adding a genome to a Progressive Cactus alignment. The top row shows the different ways of adding a new genome given its phylogenetic position, and the bottom row shows what subproblems would need to be computed for the new genome to be properly merged into the existing alignment. Green circles represent a new genome, and red circles represent newly reconstructed genomes.
Extended Data Fig. 2 Methods of adding a genome to a Progressive Cactus alignment. The top row shows the different ways of adding a new genome given its phylogenetic position, and the bottom row shows what subproblems would need to be computed for the new genome to be properly merged into the existing alignment. Green circles represent a new genome, and red circles represent newly reconstructed genomes.CC BY · PubMed Central
Extended Data Fig. 3 Analysing insertions, deletions and L1PA6 repeats in the 600-way alignment. a, Rates of micro-insertions and -deletions (micro-indels) along each branch within the 600-way alignment, compared to conventional substitutions/site branch length. The data from avian and eutherian branches are separated. Lines show a best-fit linear model for each category. b, Violin plot showing the increasing similarity to consensus of L1PA6 elements within reconstructed ancestral genomes along the path to the emergence of modern L1PA6 elements (in the human-rhesus ancestor). Horizontal lines indicate the median values.
Extended Data Fig. 3 Analysing insertions, deletions and L1PA6 repeats in the 600-way alignment. a, Rates of micro-insertions and -deletions (micro-indels) along each branch within the 600-way alignment, compared to conventional substitutions/site branch length. The data from avian and eutherian branches are separated. Lines show a best-fit linear model for each category. b, Violin plot showing the increasing similarity to consensus of L1PA6 elements within reconstructed ancestral genomes along the path to the emergence of modern L1PA6 elements (in the human-rhesus ancestor). Horizontal lines indicate the median values.CC BY · PubMed Central

Verification

Claims the paper makes

36 Own result · 33 No basis given · 26 Own interpretation · 12 Supported · 10 Partly supported · 6 Own method · 4 No full text of the sources · 2 Couldn’t confirm · 1 Not checked yet · accuracy not yet measured

  • Probably not a substantial claim. 27
  • It may state two separate claims as one. 38
58 of 58
  • The paper relies on this without support.

    The existing implementation of Cactus struggles in regions of highly duplicated sequences.

    “and struggles in regions of highly duplicated sequences.”
  • The paper relies on this without support.

    Genome alignment is a computationally intensive task.

    “Although genome alignment is a computationally intensive task”
  • The paper relies on this without support.

    Any region already containing an outgroup alignment benefits very little from aligning an additional outgroup.

    “we note that in general any region already containing an outgroup alignment benefits very little from aligning an additional outgroup.”
  • The paper relies on this without support.

    Unmasked repetitive sequence can negatively affect alignment runtimes and quality.

    “often repetitive sequence goes unmasked due to poor masking or incomplete repeat libraries for newly-sequenced species. This can negatively affect alignment runtimes (as alignments need to be enumerated to and from all copies of a repetitive sequence) and impact quality.”
  • The paper relies on this without support.

    The approximately maximum-likelihood trees independently re-estimated by FastTree from the same regions are accurate enough to serve as a reference against which errors in the HAL trees can be detected.

    “we compared phylogenetic trees implicit in the columns of HAL alignments to independently re-estimated approximately maximum likelihood (ML) trees produced by FastTree (http://www.microbesonline.org/fasttree/, version 2.1.11)57 for the same regions.”
5 of 5

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?

Self-check

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

Each contradiction between two passages listed here was confirmed by an independent check.

1 of 1

Citations

Cites

Show all 66 references

Cited by

Sorted by citations

  • Ensembl 2022

    Cunningham, F., Allen, J. E., Allen, J., Alvarez-Jarreta, J., Amode, M. R., Armean, I. M., Austine-Orimoloye, O., Azov, A. G., Barnes, I., Bennett, R., et al. (2022) · Nucleic Acids Research · doi:10.1093/nar/gkab1049 · Cited by 1,923

    “We have deployed the Cactus (9) multiple genome aligner software, which is able to compute high quality multiple genome alignments with thousands of genomes in linear time.”
  • GENCODE 2021

    Frankish, A., Diekhans, M., Jungreis, I., Lagarde, J., Loveland, J. E., Mudge, J. M., Sisu, C., Wright, J. C., Armstrong, J., Barnes, I., et al. (2021) · Nucleic Acids Research · doi:10.1093/nar/gkaa1087 · Cited by 1,334

    “For example, we have used Cactus to create a 600-way vertebrate whole genome alignment incorporating data from the 200 Mammals and Bird 10K projects as the basis of a single base-pair resolution map of evolutionary selection (20).”
    MethodSelf-citation
  • A draft human pangenome reference.

    Liao, W.-W., Asri, M., Ebler, J., Doerr, D., Haukness, M., Hickey, G., Lu, S., Lucas, J. K., Monlong, J., Abel, H. J., et al. (2023) · Nature · doi:10.1038/s41586-023-05896-x · Cited by 1,129

    “MC extends the Minigraph pangenome with a base-level alignment of the homology relationships between the assemblies using the Cactus genome aligner (Armstrong et al., 2020), while retaining the structure of the Minigraph pangenome.”
    MethodInfluentialSelf-citation
  • Ensembl 2023

    Martin, F. J., Amode, M. R., Aneja, A., Austine-Orimoloye, O., Azov, A. G., Barnes, I., Becker, A., Bennett, R., Berry, A. E., Bhai, J. N. N. T., et al. (2022) · Nucleic Acids Research · doi:10.1093/nar/gkac958 · Cited by 1,041

  • Comparative host-coronavirus protein interaction networks reveal pan-viral disease mechanisms

    Gordon, D. E., Hiatt, J. B., Bouhaddou, M., Rezelj, V. V., Ulferts, S., Braberg, H., Jureka, A. S., Obernier, K., Guo, J. Z., Batra, J., et al. (2020) · Science · doi:10.1126/science.abe9403 · Cited by 747

See all 611

Metadata

Authors
Armstrong, J., Hickey, G., Diekhans, M., Fiddes, I. T., Novak, A. M., Deran, A., Fang, Q., Xie, D., Feng, S., Stiller, J., Genereux, D., Johnson, J., Marinescu, V. D., Alföldi, J., Harris, R. S., Lindblad-Toh, K., Haussler, D., Karlsson, E., Jarvis, E. D., Zhang, G., & Paten, B.
Affiliations
  • University of California, Santa Cruz (US)
  • University of Copenhagen (DK)
  • University of Chinese Academy of Sciences (CN)
  • Kunming Institute of Zoology (CN)
  • Broad Institute (US)
  • Uppsala University (SE)
  • Pennsylvania State University (US)
  • Howard Hughes Medical Institute (US)
Corresponding author
  • Zhang, Guojie
  • Paten, Benedict
Venue
Nature
Published
2020-11-11
Volume
587
Issue
7833
Pages
246-251
ISSN
  • 0028-0836 (ISSN-L)
  • 1476-4687
OpenAlex
W3100651612
Cited by
586
References
66
Citations by year
2026: 96 · 2025: 132 · 2024: 128 · 2023: 100 · 2022: 85 · 2021: 27 · 2020: 17
FWCI
19.29
Type
journal article
Language
en
Open access
Locations
  • Nature (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • Research at the University of Copenhagen (University of Copenhagen) (publishedVersion, cc-by)
  • eScholarship@UMassChan (submittedVersion, cc-by)
  • KTH Publication Database DiVA (KTH Royal Institute of Technology) (submittedVersion, other-oa)
  • RePEc: Research Papers in Economics (submittedVersion)
  • eScholarship (California Digital Library) (submittedVersion)
  • eScholarship (California Digital Library) (submittedVersion, cc-by)
Funders
  • Villum Fonden (00025900)
  • National Institutes of Health
  • National Heart, Lung, and Blood Institute (U01HL137183)
  • National Human Genome Research Institute (R01HG009737, R01HG010485, R01HG008742, U01HG010971, T32HG008345, U41HG007234, U54HG007990, U01HG010961, U24HG007234, U41HG010972)
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 › Genetics › Chromosomal and Genetic Variations
Keywords
multiple genome alignment, structural variants, genome evolution
MeSH terms
Amnion, Animals, Computer Simulation, Haplotypes, Humans, Quality Control, Software, Vertebrates, Sequence Alignment, Genome, 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.

A language model drew the claims from the paper on 2026-11-02, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-11-02 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Cited sources are checked with a language model’s help (gpt-6-sol).

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