CoChat
Sign Up
Cited by 77Genomics and Phylogenetic StudiesGenome Rearrangement AlgorithmsAlgorithms and Data Compression

Scalable multiple whole-genome alignment and locally collinear block construction with SibeliaZ

Open access
Minkin, Ilia, Medvedev, Paul·2020·Nature Communications
DOI 10.1038/s41467-020-19777-8PMC PMC7728760

Published version of a preprint

Open this paper in CoChat — free accountOpen PDF

Abstract

Multiple whole-genome alignment is a challenging problem in bioinformatics. Despite many successes, current methods are not able to keep up with the growing number, length, and complexity of assembled genomes, especially when computational resources are limited. Approaches based on compacted de Bruijn graphs to identify and extend anchors into locally collinear blocks have potential for scalability, but current methods do not scale to mammalian genomes. We present an algorithm, SibeliaZ-LCB, for identifying collinear blocks in closely related genomes based on analysis of the de Bruijn graph. We further incorporate this into a multiple whole-genome alignment pipeline called SibeliaZ. SibeliaZ shows run-time improvements over other methods while maintaining accuracy. On sixteen recently-assembled strains of mice, SibeliaZ runs in under 16 hours on a single machine, while other tools did not run to completion for eight mice within a week. SibeliaZ makes a significant step towards improving scalability of multiple whole-genome alignment and collinear block reconstruction algorithms on a single machine.

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.1038/s41467-020-19777-8

Cites

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

  • SibeliaZ provided better performance in terms of time of execution compared with the Mercator tool.

    “It also provided be tt er performance in terms of time of execution compared with the Mercator tool.”

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

    The Results section (‘Datasets, tools, and evaluation metrics’; page not provided) explicitly says the authors did not run Mercator because it requires gene-exon input and solves a different problem. The reported execution-time comparisons are with Cactus, not Mercator, so the paper does not report the attributed performance comparison. (LLM, conf=0.87)

    Checked by a reasoning model — may be wrong.

    Experimental — accuracy not yet measured

  • SibeliaZ-LCB constructs locally collinear blocks (LCBs) by grouping aligned regions that exhibit consistent gene order and orientation across genomes.

    “based on the alignment, it constructs locally collinear blocks (LCBs) by grouping aligned regions that exhibit consistent gene order and orientation across the genomes.”

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

    The Results (Algorithm overview; page not provided) confirm that SibeliaZ-LCB identifies blocks of homologous genomic subsequences. But it takes a de Bruijn graph as input, not an existing alignment, and the Introduction says the blocks are found before sequence alignment. The paper describes collinearity in terms of genomic walks, not grouping regions by consistent gene order and orientation. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • SibeliaZ-LCB performs pairwise sequence alignments between input genomes to identify regions of similarity and homology.

    “Thus, SibeliaZ-LCB performs pairwise sequence alignments between the input genomes to identify regions of similarity and homology.”

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

    The Results (Algorithm overview; page unavailable) say SibeliaZ-LCB identifies blocks of homologous subsequences, supporting the homology-identification part. But it takes a de Bruijn graph as input and identifies blocks from that graph; the Introduction says a separate aligner runs afterward. The paper does not describe SibeliaZ-LCB as performing pairwise sequence alignments between input genomes. (LLM, conf=0.90)

    Experimental — accuracy not yet measured

  • On sixteen recently assembled mice genomes, SibeliaZ ran in less than 16 h on a single machine, while other tools did not run to completion for eight mice within a week.

    “On sixteen recently assembled mice genomes, SibeliaZ ran in less than 16 h on a single machine, while other tools did not run to completion for eight mice within a week.”

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

  • SibeliaZ-LCB is suitable for detecting homologous sequences that have an evolutionary distance to the most recent common ancestor (MRCA) of at most 0.09 substitutions per site.

    “SibeliaZ-LCB is suitable for detecting homologous sequences that have an evolutionary distance to the most recent common ancestor (MRCA) of at most 0.09 substitutions per site [39].”

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

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

  1. [1]Earl D Alignathon: a competitive assessment of whole-genome alignment methods Genome Res. 2014 24 2077 2089 10.1101/gr.174920.114 25273068 PMC4248324 · DOI · Paper page
  2. [2]Dewey CN Pachter L Evolution at the nucleotide level: the problem of multiple whole-genome alignment Hum. Mol. Genet. 2006 15 R51 R56 10.1093/hmg/ddl056 16651369 · DOI
  3. [3]Altschul SF Gish W Miller W Myers EW Lipman DJ Basic local alignment search tool J. Mol. Biol. 1990 215 403 410 10.1016/S0022-2836(05)80360-2 2231712 · DOI · Paper page
  4. [4]Altschul SF Gapped blast and psi-blast: a new generation of protein database search programs Nucleic Acids Res. 1997 25 3389 3402 10.1093/nar/25.17.3389 9254694 PMC146917 · DOI · Paper page
  5. [5]Schwartz S Human–mouse alignments with blastz Genome Res. 2003 13 103 107 10.1101/gr.809403 12529312 PMC430961 · DOI
  6. [7]Kent WJ Blat—the blast-like alignment tool Genome Res. 2002 12 656 664 10.1101/gr.229202 11932250 PMC187518 · DOI · Paper page
  7. [8]Blanchette M Aligning multiple genomic sequences with the threaded blockset aligner Genome Res. 2004 14 708 715 10.1101/gr.1933104 15060014 PMC383317 · DOI · Paper page
  8. [9]Dubchak I Poliakov A Kislyuk A Brudno M Multiple whole-genome alignments without a reference organism Genome Res. 2009 19 682 689 10.1101/gr.081778.108 19176791 PMC2665786 · DOI
  9. [10]Angiuoli SV Salzberg SL Mugsy: fast multiple alignment of closely related whole genomes Bioinformatics 2011 27 334 342 10.1093/bioinformatics/btq665 21148543 PMC3031037 · DOI · Paper page
  10. [11]Paten B Cactus: algorithms for genome multiple sequence alignment Genome Res. 2011 21 1512 1528 10.1101/gr.123356.111 21665927 PMC3166836 · DOI · Paper page
  11. [12]Lilue J Sixteen diverse laboratory mouse reference genomes define strain-specific haplotypes and novel functional loci Nat. Genet. 2018 50 1574 10.1038/s41588-018-0223-8 30275530 PMC6205630 · DOI · Paper page
  12. [13]Darling AC Mau B Blattner FR Perna NT Mauve: multiple alignment of conserved genomic sequence with rearrangements Genome Res. 2004 14 1394 1403 10.1101/gr.2289704 15231754 PMC442156 · DOI · Paper page
  13. [14]Dewey, C. N. Aligning Multiple Whole Genomes with Mercator and MAVID. 221–235 (Humana Press, Totowa, NJ, 2008). 17993677
  14. [15]Paten B Herrero J Beal K Fitzgerald S Birney E Enredo and pecan: genome-wide mammalian consistency-based multiple alignment with paralogs Genome Res. 2008 18 1814 1828 10.1101/gr.076554.108 18849524 PMC2577869 · DOI
  15. [16]Darling AE Mau B Perna NT Progressivemauve: multiple genome alignment with gene gain, loss and rearrangement PloS ONE 2010 5 e11147 10.1371/journal.pone.0011147 20593022 PMC2892488 · DOI · Paper page
  16. [17]Minkin, I., Pham, H., Starostina, E., Vyahhi, N. & Pham, S. C-sibelia: an easy-to-use and highly accurate tool for bacterial genome comparison. F1000Research https://f1000research.com/articles/2-258 (2013). PMC4111117 25110578
  17. [18]Myers, G. & Miller, W. Chaining multiple-alignment fragments in sub-quadratic time. in Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’95, 38–47 (Society for Industrial and Applied Mathematics, USA, 1995).
  18. [19]Abouelhoda MI Ohlebusch E Chaining algorithms for multiple genome comparison J. Discret. Algorithms 2005 3 321 341 10.1016/j.jda.2004.08.011 · DOI
  19. [21]Raphael B Zhi D Tang H Pevzner P A novel method for multiple alignment of sequences with repeated and shuffled elements Genome Res. 2004 14 2336 2346 10.1101/gr.2657504 15520295 PMC525693 · DOI
  20. [22]Pham S Pevzner P Drimm-synteny: decomposing genomes into evolutionary conserved segments Bioinformatics 2010 26 2509 2516 10.1093/bioinformatics/btq465 20736338 · DOI
  21. [23]Minkin, I., Patel, A., Kolmogorov, M., Vyahhi, N. & Pham, S. Sibelia: A scalable and comprehensive synteny block generation tool for closely related microbial genomes. in (eds Darling, A. & Stoye, J.) Algorithms in Bioinformatics. 215–229 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2013).
  22. [24]Marcus S Lee H Schatz MC Splitmem: a graphical algorithm for pan-genome analysis with suffix skips Bioinformatics 2014 30 3476 3483 10.1093/bioinformatics/btu756 25398610 PMC4253837 · DOI
  23. [25]Chikhi R Limasset A Medvedev P Compacting de bruijn graphs from sequencing data quickly and in low memory Bioinformatics 2016 32 i201 i208 10.1093/bioinformatics/btw279 27307618 PMC4908363 · DOI
  24. [26]Baier U Beller T Ohlebusch E Graphical pan-genome analysis with compressed suffix trees and the burrows-wheeler transform Bioinformatics 2016 32 497 504 10.1093/bioinformatics/btv603 26504144 · DOI
  25. [27]Minkin I Pham S Medvedev P Twopaco: an efficient algorithm to build the compacted de bruijn graph from many complete genomes Bioinformatics 2017 33 4024 4032 27659452
  26. [28]Cleary, A., Kahanda, I., Mumey, B., Mudge, J. & Ramaraj, T. Exploring frequented regions in pan-genomic graphs. in Proceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics, 89–97 (Association for Computing Machinery, New York, NY, USA, 2017).
  27. [29]Vaser R Sović I Nagarajan N Šikić M Fast and accurate de novo genome assembly from long uncorrected reads Genome Res. 2017 27 737 746 10.1101/gr.214270.116 28100585 PMC5411768 · DOI
  28. [30]Sayers EW GenBank Nucleic Acids Res. 2019 48 D84 D86 PMC7145611 31665464
  29. [31]Brudno M Lagan and multi-lagan: efficient tools for large-scale multiple alignment of genomic dna Genome Res. 2003 13 721 731 10.1101/gr.926603 12654723 PMC430158 · DOI · Paper page
  30. [33]Tajima F Statistical method for testing the neutral mutation hypothesis by dna polymorphism Genetics 1989 123 585 595 2513255 PMC1203831
  31. [35]Paten B Cactus graphs for genome comparisons J. Comput. Biol. 2011 18 469 481 10.1089/cmb.2010.0252 21385048 PMC8884192 · DOI · Paper page
  32. [36]Fiddes IT Comparative annotation toolkit (cat)-simultaneous clade and personal genome annotation Genome Res. 2018 28 1029 1038 10.1101/gr.233460.117 29884752 PMC6028123 · DOI · Paper page
  33. [37]Schwartz AS Pachter L Multiple alignment by sequence annealing Bioinformatics 2007 23 e24 e29 10.1093/bioinformatics/btl311 17237099 · DOI
  34. [38]Sakharkar MK Perumal BS Sakharkar KR Kangueane P An analysis on gene architecture in human and mouse genomes Silico Biol. 2005 5 347 365 16268780
  35. [39]Pevzner P Tesler G Human and mouse genomic sequences reveal extensive breakpoint reuse in mammalian evolution Proc. Natl Acad. Sci. USA 2003 100 7672 7677 10.1073/pnas.1330369100 12810957 PMC164646 · DOI
  36. [40]Kim J Reconstruction and evolutionary history of eutherian chromosomes Proc. Natl Acad. Sci. USA 2017 114 E5379 E5388 10.1073/pnas.1702012114 28630326 PMC5502614 · DOI
  37. [41]Luo H Phylogenetic analysis of genome rearrangements among five mammalian orders Mol. Phylogenet. Evolut. 2012 65 871 882 10.1016/j.ympev.2012.08.008 PMC4425404 22929217 · DOI
  38. [42]Kolmogorov M Chromosome assembly of large and complex genomes using multiple references Genome Res. 2018 28 1720 1732 10.1101/gr.236273.118 30341161 PMC6211643 · DOI
  39. [44]Kolmogorov M Raney B Paten B Pham S Ragout—a reference-assisted assembly tool for bacterial genomes Bioinformatics 2014 30 i302 i309 10.1093/bioinformatics/btu280 24931998 PMC4058940 · DOI
  40. [45]Chen K-T Multi-car: a tool of contig scaffolding using multiple references BMC Bioinform. 2016 17 469 10.1186/s12859-016-1328-7 PMC5260120 28155633 · DOI
  41. [46]Aganezov, S. & Alekseyev, M. A. Multi-genome scaffold co-assembly based on the analysis of gene orders and genomic repeats. in (eds Bourgeois, A., Skums, P., Wan, X. & Zelikovsky, A.) Bioinformatics Research and Applications. 237–249 (Springer International Publishing, Cham, 2016).
  42. [47]Proost S i-adhore 3.0—fast and sensitive detection of genomic homology in extremely large data sets Nucleic Acids Res. 2011 40 e11 e11 10.1093/nar/gkr955 22102584 PMC3258164 · DOI
  43. [48]Portwood JL Maizegdb 2018: the maize multi-genome genetics and genomics database Nucleic Acids Res. 2018 47 D1146 D1154 10.1093/nar/gky1046 PMC6323944 30407532 · DOI
  44. [49]Onodera, T., Sadakane, K. & Shibuya, T. Detecting superbubbles in assembly graphs. in (eds Darling, A. & Stoye, J.) Algorithms in Bioinformatics. 338–348 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2013).
  45. [50]Sung W Sadakane K Shibuya T Belorkar A Pyrogova I An O(mlogm)-time algorithm for detecting superbubbles IEEE/ACM Trans. Comput. Biol. Bioinform. 2015 12 770 777 10.1109/TCBB.2014.2385696 26357315 · DOI
  46. [51]Iliopoulos, C. S., Kundu, R., Mohamed, M. & Vayani, F. Popping superbubbles and discovering clumps: Recent developments in biological sequence analysis. in (eds Kaykobad, M. & Petreschi, R.) WALCOM: Algorithms and Computation. 3–14 (Springer International Publishing, Cham, 2016).
  47. [52]Brankovic L Linear-time superbubble identification algorithm for genome assembly Theor. Comput. Sci. 2016 609 374 383 10.1016/j.tcs.2015.10.021 · DOI
  48. [53]Paten, B., Novak, A. M., Garrison, E. & Hickey, G. Superbubbles, ultrabubbles and cacti. in (ed Sahinalp, S. C.) Research in Computational Molecular Biology. 173–189 (Springer International Publishing, Cham, 2017). PMC6067107 29461862

Cited by

Sorted by citations

Authors
Minkin, I., & Medvedev, P.
Affiliations
Pennsylvania State University (US)
Corresponding author
Minkin, Ilia
ORCID
Venue
Nature Communications
Publisher
Springer Science and Business Media LLC
Published
2020-12-10
Volume
11
Issue
1
Pages
6327-6327
ISSN
2041-1723 (ISSN-L)
DOI
10.1038/s41467-020-19777-8
PMC
PMC7728760
OpenAlex
W3111607156
Cited by
77
References
2
Citations by year
2026: 8 · 2025: 15 · 2024: 12 · 2023: 8 · 2022: 20 · 2021: 6 · 2020: 5 · 2019: 3
FWCI
3.12
Type
journal article
Language
en
Open access
Licence
Locations
  • Nature Communications (publishedVersion, cc-by)
  • bioRxiv (Cold Spring Harbor Laboratory) (acceptedVersion, cc-by-nd)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • RePEc: Research Papers in Economics (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
Funders
  • National Science Foundation (CCF-1439057, IIS-1453527, DBI-1356529, IIS-1421908)
  • U.S. Department of Health & Human Services | NIH | National Institute of General Medical Sciences (R01GM130691)
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
de Bruijn graph, genome assembly comparison, mouse genome, scalability, closely related genomes
MeSH terms
Algorithms, Animals, Base Sequence, Computer Simulation, Nucleotides, Time Factors, Genetic Variation, Genome, Databases, Genetic, Mice

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