Cactus Graphs for Genome Comparisons
Open accessAbstract
We introduce a data structure, analysis, and visualization scheme called a cactus graph for comparing sets of related genomes. In common with multi-break point graphs and A-Bruijn graphs, cactus graphs can represent duplications and general genomic rearrangements, but additionally, they naturally decompose the common substructures in a set of related genomes into a hierarchy of chains that can be visualized as two-dimensional multiple alignments and nets that can be visualized in circular genome plots. Supplementary Material is available at www.liebertonline.com/cmb .
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?
Progressive Cactus produces reference-free all-to-all genome alignments.
“One of the state-of-the-art tools [14–16] is Progressive Cactus [17,18] which produces reference-free all-to-all genome alignments.”
From halSynteny: a fast, easy-to-use conserved synteny block construction method for multiple whole-genome alignments (2020) · cites this paper as [18]
Section 2 (Overview; page unavailable) describes aligning homologous segments between and within multiple genomes, supporting the general genome-alignment aspect. But the paper describes cactus graphs, not a tool called Progressive Cactus, and the passages do not establish that it produces reference-free, all-to-all genome alignments. (LLM, conf=0.84)
Experimental — accuracy not yet measuredBy producing a single, reference-free multiple alignment, Cactus allows synteny block reconstruction between any 2 genomes without reference bias, directly from the HAL representation.
“By producing a single, reference-free multiple alignment, Cactus allows synteny block reconstruction between any 2 genomes without reference bias, directly from the HAL representation.”
From halSynteny: a fast, easy-to-use conserved synteny block construction method for multiple whole-genome alignments (2020) · cites this paper as [18]
The Overview and Abstract describe cactus graphs as representing comparisons of sets of genomes through homologous blocks and chains that can be visualized as multiple alignments. This supports the multiple-genome alignment aspect, but our copy does not describe synteny-block reconstruction between any two genomes, establish freedom from reference bias, or mention a HAL representation (searched: HAL, synteny, reference bias). (LLM, conf=0.88)
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
No references could be resolved yet.
Research works printed but not linked: 8
- Caprara, A. 1999. Formulations and hardness of multiple sorting by reversals. Proc. RECOMB 99 84-93.
- Durbin, R., Eddy, S., Krogh, A., et al. 1998. Biological Sequence Analysis. Cambridge University Press, New York.
- Hannenhalli, S., and Pevzner, P.A. 1995. Transforming men into mice (polynomial algorithm for genomic distance problem). Proc. 36th Annu. Symp. Found. Comput. Sci. 1, 581-592.
- Hannenhalli, S., and Pevzner, P.A. 1999. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM 46, 1-27.
- Harary, F., and Uhlenbeck, G. 1953. On the number of husimi trees, i. Proc. Nat. Acad. Sci. USA 39, 315-322.
- Kent, W.J., Baertsch, R., Hinrichs, A., et al. 2003. Evolution's cauldron: duplication, deletion, and rearrangement in the mouse and human genomes. Proc. Natl. Acad. Sci. USA 100, 11484-11489.
- Tetsuo, N. 1991. On the number of solutions of a class of nonlinear resistive circuit. Proc. IEEE Int. Symp. Circuits Syst. 766-769.
- Zamazek, B., and Zerovnik, J. 2005. Estimating the traffic on weighted cactus networks in linear time. Ninth Int. Conf. Inform. Visual . 536-541.
Cited by
Sorted by citations
Nanopore sequencing and assembly of a human genome with ultra-long reads
Jain, M., Koren, S., Miga, K. H., Quick, J., Rand, A. C., Sasani, T. A., Tyson, J. R., Beggs, A. D., Dilthey, A. T., Fiddes, I. T., et al. (2018) · Nature Biotechnology · doi:10.1038/nbt.4060 · Cited by 1,892 · see citing works
Self-citationProgressive Cactus is a multiple-genome aligner for the thousand-genome era
Armstrong, J., Hickey, G., Diekhans, M., Fiddes, I. T., Novak, A. M., Deran, A., Fang, Q., Xie, D., Feng, S., Stiller, J., et al. (2020) · Nature · doi:10.1038/s41586-020-2871-y · Cited by 586 · see citing works
Self-citationGenomic legacy of the African cheetah, Acinonyx jubatus
Dobrynin, P., Liu, S., Tamazian, G., Xiong, Z., Yurchenko, A. A., Krasheninnikova, K., Kliver, S., Schmidt-Küntzel, A., Koepfli, K.-P., Johnson, W., et al. (2015) · Genome Biology · doi:10.1186/s13059-015-0837-4 · Cited by 204 · see citing works
Self-citationPlant pan-genomics comes of age
Lei, L., Goltsman, E., Goodstein, D., Wu, G. A., Rokhsar, D. S., & Vogel, J. P. (2021) · Annual Review of Plant Biology · doi:10.1146/annurev-arplant-080720-105454 · Cited by 102 · see citing works
Krasheninnikova, K., Diekhans, M., Armstrong, J., Dievskii, A., Paten, B., & O'Brien, S. (2020) · GigaScience · doi:10.1093/gigascience/giaa047 · Cited by 30 · see citing works
Self-citationPangenome Graph Construction from Genome Alignment with Minigraph-Cactus
Hickey, G., Monlong, J., Ebler, J., Novak, A., Eizenga, J. M., Gao, Y., Human Pangenome Reference Consortium, Marschall, T., Li, H., & Paten, B. (2022) · doi:10.1101/2022.10.06.511217 · Cited by 345 · see citing works
Self-citation
- Authors
- Paten, B., Diekhans, M., Earl, D., John, J. S., Ma, J., Suh, B., & Haussler, D.
- Affiliations
- University of California, Santa Cruz (US)
- University of Illinois Urbana-Champaign (US)
- Corresponding author
- Paten, Benedict
- Venue
- Journal of Computational Biology
- Publisher
- SAGE Publications
- Published
- 2011-03-01
- Volume
- 18
- Issue
- 3
- Pages
- 469-481
- ISSN
- 1066-5277 (ISSN-L)
- 1557-8666
- PMC
- PMC8884192
- OpenAlex
- W2037219729
- Cited by
- 102
- References
- 0
- Citations by year
- 2026: 3 · 2025: 7 · 2024: 2 · 2023: 8 · 2022: 6 · 2021: 6 · 2020: 10 · 2019: 9 · 2018: 10 · 2017: 8 · 2016: 7 · 2015: 12 · 2014: 6 · 2013: 3 · 2012: 3
- FWCI
- 2.61
- Type
- journal article
- Language
- en
- Open access
- green
- www.ncbi.nlm.nih.gov
- Locations
- Journal of Computational Biology (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- Funders
- National Human Genome Research Institute (U41HG007234)
- 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 › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
- Keywords
- cactus graphs, comparative genomics, genome rearrangement, duplication, multiple sequence alignment, genome visualization
- MeSH terms
- Algorithms, Animals, Base Sequence, Computer Graphics, DNA, Humans, Molecular Sequence Data, Sequence Alignment, Genome, Evolution, Molecular, 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
