CoChat
Sign Up
Cited by 47Genomics and Phylogenetic StudiesGenome Rearrangement AlgorithmsFractal and DNA sequence analysis

Multiple genome alignment in the telomere-to-telomere assembly era

Open access
Kille, Bryce, Balaji, Advait, Sedlazeck, Fritz J., Nute, Michael, Treangen, Todd J.·2022·Genome Biology
DOI 10.1186/s13059-022-02735-6PMC PMC9421119
Open this paper in CoChat — free accountOpen PDF

Abstract

With the arrival of telomere-to-telomere (T2T) assemblies of the human genome comes the computational challenge of efficiently and accurately constructing multiple genome alignments at an unprecedented scale. By identifying nucleotides across genomes which share a common ancestor, multiple genome alignments commonly serve as the bedrock for comparative genomics studies. In this review, we provide an overview of the algorithmic template that most multiple genome alignment methods follow. We also discuss prospective areas of improvement of multiple genome alignment for keeping up with continuously arriving high-quality T2T assembled genomes and for unlocking clinically-relevant insights.

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.1186/s13059-022-02735-6

Cites

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

  • Tools like Cloud Aligner (alpha version) and ParaGraph have leveraged cloud computing and parallel processing to perform alignments on a massive scale, handling large volumes of data and multiple genomes simultaneously.

    “Tools like Cloud Aligner (alpha version) and ParaGraph have leveraged these technologies to perform alignments on a massive scale, handling large volumes of data and multiple genomes simultaneously [70,71].”

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

    The Future perspectives section (Area 2: Reducing computational requirements; page unavailable) discusses GPU and cluster speedups and an alignment of more than 600 genomes. The paper does not identify Cloud Aligner or ParaGraph or establish that either tool uses cloud computing and parallel processing as claimed. (LLM, conf=0.76)

    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

Flagged first, then by citations

Research works printed but not linked: 141

  1. [1]Jarvis ED Perspectives from the avian phylogenomics project: questions that can be answered with sequencing all genomes of a vertebrate class Ann Rev Anim Biosci 2016 4 45 59 10.1146/annurev-animal-021815-111216 26884102 · DOI
  2. [2]Nurk S Koren S Rhie A Rautiainen M Bzikadze AV Mikheenko A Vollger MR Altemose N Uralsky L Gershman A The complete sequence of a human genome Science 2022 376 6588 44 53 10.1126/science.abj6987 35357919 PMC9186530 · DOI · Paper page
  3. [3]Hodgkinson A Eyre-Walker A Variation in the mutation rate across mammalian genomes Nat Rev Genet 2011 12 11 756 66 10.1038/nrg3098 21969038 · DOI · Paper page
  4. [4]Hannenhalli S Pevzner PA Transforming men into mice (polynomial algorithm for genomic distance problem) Proceedings of IEEE 36th Annual Foundations of Computer Science 1995 New York IEEE
  5. [5]Bejerano G Pheasant M Makunin I Stephen S Kent WJ Mattick JS Haussler D Ultraconserved elements in the human genome Science 2004 304 5675 1321 5 10.1126/science.1098119 15131266 · DOI · Paper page
  6. [6]Wenink PW Baker AJ Tilanus M Hypervariable-control-region sequences reveal global population structuring in a long-distance migrant shorebird, the dunlin (calidris alpina) Proc Natl Acad Sci 1993 90 1 94 8 10.1073/pnas.90.1.94 8419948 PMC45606 · DOI
  7. [8]Wang L Jiang T On the complexity of multiple sequence alignment J Comput Biol 1994 1 4 337 48 10.1089/cmb.1994.1.337 8790475 · DOI
  8. [9]Elias I. Settling the Intractability of Multiple Alignment. J Comput Biol. 2016;13(7). 10.1089/cmb.2006.13.1323. 17037961 · DOI
  9. [10]Kececioglu J The maximum weight trace problem in multiple sequence alignment Annual Symposium on Combinatorial Pattern Matching 1993 Berlin, Heidelberg Springer
  10. [11]Stankiewicz P Lupski JR Structural variation in the human genome and its role in disease Annu Rev Med 2010 61 437 55 10.1146/annurev-med-100708-204735 20059347 · DOI · Paper page
  11. [12]Höhl M Ragan MA Is multiple-sequence alignment required for accurate inference of phylogeny? Syst Biol 2007 56 2 206 21 10.1080/10635150701294741 17454975 PMC7107264 · DOI
  12. [13]Van Noorden R Maher B Nuzzo R The top 100 papers Nat News 2014 514 7524 550 10.1038/514550a 25355343 · DOI
  13. [14]Fleischmann RD Adams MD White O Clayton RA Kirkness EF Kerlavage AR Bult CJ Tomb J-F Dougherty BA Merrick JM Whole-genome random sequencing and assembly of haemophilus influenzae rd Science 1995 269 5223 496 512 10.1126/science.7542800 7542800 · DOI
  14. [15]Venter JC Adams MD Myers EW Li PW Mural RJ Sutton GG Smith HO Yandell M Evans CA Holt RA The sequence of the human genome science 2001 291 5507 1304 51 10.1126/science.1058040 11181995 · DOI · Paper page
  15. [16]Pevzner P, Tesler G. Genome Rearrangements in Mammalian Evolution: Lessons From Human and Mouse Genomes. Genome Res. 2003;13(1). 10.1101/gr.757503. PMC430962 12529304 · DOI · Paper page
  16. [17]Zhao S Shetty J Hou L Delcher A Zhu B Osoegawa K de Jong P Nierman WC Strausberg RL Fraser CM Human, mouse, and rat genome large-scale rearrangements: stability versus speciation Genome Res 2004 14 10a 1851 60 10.1101/gr.2663304 15364903 PMC524408 · DOI
  17. [18]Bourque G Pevzner PA Tesler G Reconstructing the genomic architecture of ancestral mammals: lessons from human, mouse, and rat genomes Genome Res 2004 14 4 507 16 10.1101/gr.1975204 15059991 PMC383294 · DOI
  18. [19]Zody MC Garber M Adams DJ Sharpe T Harrow J Lupski JR Nicholson C Searle SM Wilming L Young SK Dna sequence of human chromosome 17 and analysis of rearrangement in the human lineage Nature 2006 440 7087 1045 9 10.1038/nature04689 16625196 PMC2610434 · DOI
  19. [20]Sharp AJ Cheng Z Eichler EE Structural variation of the human genome Annu Rev Genomics Hum Genet 2006 7 407 42 10.1146/annurev.genom.7.080505.115618 16780417 · DOI
  20. [21]Treangen TJ Salzberg SL Repetitive dna and next-generation sequencing: computational challenges and solutions Nat Rev Genet 2012 13 1 36 46 10.1038/nrg3117 PMC3324860 22124482 · DOI
  21. [22]Sotero-Caio CG Platt RN Suh A Ray DA Evolution and diversity of transposable elements in vertebrate genomes Genome Biol Evol 2017 9 1 161 77 10.1093/gbe/evw264 28158585 PMC5381603 · DOI · Paper page
  22. [23]Frith MC Khan S A survey of localized sequence rearrangements in human dna Nucleic Acids Res 2018 46 4 1661 73 10.1093/nar/gkx1266 29272440 PMC5829575 · DOI
  23. [24]Dewey CN. Whole-Genome Alignment In: Anisimova M, editor. New York: Springer. p. 121–147.
  24. [25]Armstrong J Fiddes IT Diekhans M Paten B Whole-genome alignment and comparative annotation Ann Rev Anim Biosci 2019 7 41 64 10.1146/annurev-animal-020518-115005 30379572 PMC6450745 · DOI
  25. [26]Coghlan A Eichler EE Oliver SG Paterson AH Stein L Chromosome evolution in eukaryotes: a multi-kingdom perspective TRENDS Genet 2005 21 12 673 82 10.1016/j.tig.2005.09.009 16242204 · DOI
  26. [27]Kumar S Filipski A Multiple sequence alignment: in pursuit of homologous dna positions Genome Res 2007 17 2 127 35 10.1101/gr.5232407 17272647 · DOI
  27. [28]Boussau B Daubin V Genomes as documents of evolutionary history Trends Ecol Evol 2010 25 4 224 32 10.1016/j.tree.2009.09.007 19880211 · DOI
  28. [29]Fitch WM Homology: a personal view on some of the problems Trends Genet 2000 16 5 227 31 10.1016/S0168-9525(00)02005-9 10782117 · DOI
  29. [30]Koonin EV Orthologs, paralogs, and evolutionary genomics Annu Rev Genet 2005 39 309 38 10.1146/annurev.genet.39.073003.114725 16285863 · DOI · Paper page
  30. [31]Altenhoff AM Studer RA Robinson-Rechavi M Dessimoz C Resolving the ortholog conjecture: orthologs tend to be weakly, but significantly, more similar in function than paralogs PLoS Comput Biol 2012 8 5 1002514 10.1371/journal.pcbi.1002514 PMC3355068 22615551 · DOI · Paper page
  31. [32]Ohno S Evolution by gene duplication 2013 Berlin, Heidelberg Springer
  32. [33]Dewey CN Positional orthology: putting genomic evolutionary relationships into context Brief Bioinforma 2011 12 5 401 12 10.1093/bib/bbr040 PMC3178058 21705766 · DOI
  33. [34]Lapierre P Gogarten JP Estimating the size of the bacterial pan-genome Trends Genet 2009 25 3 107 10 10.1016/j.tig.2008.12.004 19168257 · DOI
  34. [35]Segerman B The genetic integrity of bacterial species: the core genome and the accessory genome, two different stories Front Cell Infect Microbiol 2012 2 116 10.3389/fcimb.2012.00116 22973561 PMC3434323 · DOI
  35. [36]Darling ACE Mau B Blattner FR Perna NT Mauve: Multiple Alignment of Conserved Genomic Sequence With Rearrangements Genome Res 2004 14 7 1394 403 10.1101/gr.2289704 15231754 PMC442156 · DOI · Paper page
  36. [37]Treangen TJ Ondov BD Koren S Phillippy AM The Harvest suite for rapid core-genome alignment and visualization of thousands of intraspecific microbial genomes Genome Biol 2014 15 11 524 10.1186/s13059-014-0524-x 25410596 PMC4262987 · DOI
  37. [38]Touchon M Hoede C Tenaillon O Barbe V Baeriswyl S Bidet P Bingen E Bonacorsi S Bouchier C Bouvet O Organised genome dynamics in the escherichia coli species results in highly diverse adaptive paths PLoS Genet 2009 5 1 1000344 10.1371/journal.pgen.1000344 PMC2617782 19165319 · DOI
  38. [39]Altenhoff AM Glover NM Dessimoz C Anisimova M Inferring orthology and paralogy Evolutionary Genomics: Statistical and Computational Methods 2019 New York Springer
  39. [40]Paten B Earl D Nguyen N Diekhans M Zerbino D Haussler D Cactus: Algorithms for genome multiple sequence alignment Genome Res 2011 21 9 1512 28 10.1101/gr.123356.111 21665927 PMC3166836 · DOI · Paper page
  40. [41]Blanchette M Kent WJ Riemer C Elnitski L Smit AF Roskin KM Baertsch R Rosenbloom K Clawson H Green ED Aligning multiple genomic sequences with the threaded blockset aligner Genome Res 2004 14 4 708 15 10.1101/gr.1933104 15060014 PMC383317 · DOI · Paper page
  41. [42]National Research Council and others Frontiers in massive data analysis 2013 Washington National Academies Press
  42. [43]Mirarab S Nguyen N Guo S Wang L-S Kim J Warnow T Pasta: ultra-large multiple sequence alignment for nucleotide and amino-acid sequences J Comput Biol 2015 22 5 377 86 10.1089/cmb.2014.0156 25549288 PMC4424971 · DOI
  43. [44]Edgar RC Muscle: multiple sequence alignment with high accuracy and high throughput Nucleic Acids Res 2004 32 5 1792 7 10.1093/nar/gkh340 15034147 PMC390337 · DOI · Paper page
  44. [45]Katoh K Asimenos G Toh H Multiple alignment of dna sequences with mafft Bioinformatics for DNA Sequence Analysis 2009 Totowa Humana Press 19378139
  45. [46]Brudno M Malde S Poliakov A Do CB Couronne O Dubchak I Batzoglou S Glocal alignment: finding rearrangements during alignment Bioinformatics 2003 19 suppl_1 54 62 10.1093/bioinformatics/btg1005 12855437 · DOI
  46. [48]Kececioglu J Starrett D Aligning alignments exactly Proceedings of the Eighth Annual International Conference on Research in Computational Molecular Biology. RECOMB ’04 2004 New York Association for Computing Machinery
  47. [49]Darling AC Mau B Blattner FR Perna NT Mauve: multiple alignment of conserved genomic sequence with rearrangements Genome Res 2004 14 7 1394 403 10.1101/gr.2289704 15231754 PMC442156 · DOI · Paper page
  48. [50]Treangen TJ Ondov BD Koren S Phillippy AM The harvest suite for rapid core-genome alignment and visualization of thousands of intraspecific microbial genomes Genome Biol 2014 15 11 524 10.1186/s13059-014-0524-x 25410596 PMC4262987 · DOI
  49. [51]Blackwell GA Hunt M Malone KM Lima L Horesh G Alako BT Thomson NR Iqbal Z Exploring bacterial diversity via a curated and searchable snapshot of archived dna sequences PLoS Biol 2021 19 11 e3001421 10.1371/journal.pbio.3001421 34752446 PMC8577725 · DOI · Paper page
  50. [52]Shu Y McCauley J Gisaid: Global initiative on sharing all influenza data–from vision to reality Eurosurveillance 2017 22 13 30494 10.2807/1560-7917.ES.2017.22.13.30494 28382917 PMC5388101 · DOI · Paper page
  51. [53]of Scientists GKC Genome 10k: a proposal to obtain whole-genome sequence for 10 000 vertebrate species J Hered 2009 100 6 659 74 10.1093/jhered/esp086 19892720 PMC2877544 · DOI
  52. [54]Koepfli K-P Paten B Genome 10K Community of Scientists O’Brien SJ The genome 10k project: a way forward Annu Rev Anim Biosci 2015 3 1 57 111 10.1146/annurev-animal-090414-014900 25689317 PMC5837290 · DOI · Paper page
  53. [55]Rhie A McCarthy SA Fedrigo O Damas J Formenti G Koren S Uliano-Silva M Chow W Fungtammasan A Kim J Towards complete and error-free genome assemblies of all vertebrate species Nature 2021 592 7856 737 46 10.1038/s41586-021-03451-0 33911273 PMC8081667 · DOI · Paper page
  54. [56]Zhang G Bird sequencing project takes off Nature 2015 522 7554 34 10.1038/522034d 26040883 · DOI
  55. [58]Cheng S Melkonian M Smith SA Brockington S Archibald JM Delaux P-M Li F-W Melkonian B Mavrodiev EV Sun W 10kp: A phylodiverse genome sequencing plan Gigascience 2018 7 3 013 10.1093/gigascience/giy013 PMC5869286 29618049 · DOI · Paper page
  56. [60]i5K Consortium The i5k initiative: advancing arthropod genomics for knowledge, human health, agriculture, and the environment J Hered 2013 104 5 595 600 10.1093/jhered/est050 23940263 PMC4046820 · DOI
  57. [61]Lewin HA Robinson GE Kress WJ Baker WJ Coddington J Crandall KA Durbin R Edwards SV Forest F Gilbert MTP Earth biogenome project: Sequencing life for the future of life Proc Natl Acad Sci 2018 115 17 4325 33 10.1073/pnas.1720115115 29686065 PMC5924910 · DOI · Paper page
  58. [62]Wheway G Mitchison HM Ambrose J Baple E Bleda M Boardman-Pretty F Boissiere J Boustred C Caulfield M Chan G Opportunities and challenges for molecular understanding of ciliopathies–the 100,000 genomes project Front Genet 2019 10 127 10.3389/fgene.2019.00127 30915099 PMC6421331 · DOI · Paper page
  59. [63]Turnbaugh PJ Ley RE Hamady M Fraser-Liggett CM Knight R Gordon JI The human microbiome project Nature 2007 449 7164 804 10 10.1038/nature06244 17943116 PMC3709439 · DOI · Paper page
  60. [64]Almeida A Nayfach S Boland M Strozzi F Beracochea M Shi ZJ Pollard KS Sakharova E Parks DH Hugenholtz P A unified catalog of 204,938 reference genomes from the human gut microbiome Nat Biotechnol 2021 39 1 105 14 10.1038/s41587-020-0603-3 32690973 PMC7801254 · DOI · Paper page
  61. [65]Nayfach S Roux S Seshadri R Udwary D Varghese N Schulz F Wu D Paez-Espino D Chen I-M Huntemann M A genomic catalog of earth’s microbiomes Nat Biotechnol 2021 39 4 499 509 10.1038/s41587-020-0718-6 33169036 PMC8041624 · DOI
  62. [66]Grigoriev IV Nikitin R Haridas S Kuo A Ohm R Otillar R Riley R Salamov A Zhao X Korzeniewski F Mycocosm portal: gearing up for 1000 fungal genomes Nucleic Acids Res 2014 42 D1 699 704 10.1093/nar/gkt1183 PMC3965089 24297253 · DOI · Paper page
  63. [68]Blackburne BP Whelan S Measuring the distance between multiple sequence alignments Bioinformatics 2012 28 4 495 502 10.1093/bioinformatics/btr701 22199391 · DOI
  64. [69]Wong KM Suchard MA Huelsenbeck JP Alignment uncertainty and genomic analysis Science 2008 319 5862 473 6 10.1126/science.1151532 18218900 · DOI · Paper page
  65. [70]Holmes I Durbin R Dynamic programming alignment accuracy J Comput Biol 1998 5 3 493 504 10.1089/cmb.1998.5.493 9773345 · DOI
  66. [71]Feng S Stiller J Deng Y Armstrong J Fang Q Reeve AH Xie D Chen G Guo C Faircloth BC Dense sampling of bird diversity increases power of comparative genomics Nature 2020 587 7833 252 7 10.1038/s41586-020-2873-9 33177665 PMC7759463 · DOI · Paper page
  67. [73]Darling AE Treangen TJ Zhang L Kuiken C Messeguer X Perna NT Procrastination leads to efficient filtration for local multiple alignment International Workshop on Algorithms in Bioinformatics 2006 Berlin, Heidelberg Springer
  68. [74]Feng D-F Doolittle RF Progressive sequence alignment as a prerequisitet to correct phylogenetic trees J Mol Evol 1987 25 4 351 60 10.1007/BF02603120 3118049 · DOI · Paper page
  69. [75]Hickey G Paten B Earl D Zerbino D Haussler D Hal: a hierarchical format for storing and analyzing multiple genome alignments Bioinformatics 2013 29 10 1341 2 10.1093/bioinformatics/btt128 23505295 PMC3654707 · DOI · Paper page
  70. [76]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 11 2336 46 10.1101/gr.2657504 15520295 PMC525693 · DOI
  71. [77]Schwartz S Kent WJ Smit A Zhang Z Baertsch R Hardison RC Haussler D Miller W Human–Mouse Alignments with BLASTZ Genome Res 2003 13 1 103 7 10.1101/gr.809403 12529312 PMC430961 · DOI
  72. [78]Pevzner PA Tang H Tesler G De novo repeat classification and fragment assembly Genome Res 2004 14 9 1786 96 10.1101/gr.2395204 15342561 PMC515325 · DOI
  73. [79]Paten B Earl D Nguyen N Diekhans M Zerbino D Haussler D Cactus: Algorithms for genome multiple sequence alignment Genome Res 2011 21 9 1512 28 10.1101/gr.123356.111 21665927 PMC3166836 · DOI · Paper page
  74. [80]Harris R. Improved pairwise alignment of genomic dna. PhD thesis, Pennsylvania State University. 2007.
  75. [81]Paten B Herrero J Beal K Birney E Sequence progressive alignment, a framework for practical large-scale probabilistic consistency alignment Bioinformatics 2009 25 3 295 301 10.1093/bioinformatics/btn630 19056777 · DOI
  76. [82]Treangen TJ Messeguer X M-GCAT: interactively and efficiently constructing large-scale multiple genome comparison frameworks in closely related species BMC Bioinformatics 2006 7 1 433 10.1186/1471-2105-7-433 17022809 PMC1629028 · DOI
  77. [83]Darling AE Mau B Blattner FR Perna NT Gril: genome rearrangement and inversion locator Bioinformatics 2004 20 1 122 4 10.1093/bioinformatics/btg378 14693819 · DOI
  78. [84]Thompson JD Higgins DG Gibson TJ Clustal w: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice Nucleic Acids Res 1994 22 22 4673 80 10.1093/nar/22.22.4673 7984417 PMC308517 · DOI · Paper page
  79. [85]Bray N Dubchak I Pachter L AVID: A Global Alignment Program Genome Res 2003 13 1 97 102 10.1101/gr.789803 12529311 PMC430967 · DOI
  80. [86]Bray N Pachter L MAVID: Constrained Ancestral Alignment of Multiple Sequences Genome Res 2004 14 4 693 9 10.1101/gr.1960404 15060012 PMC383315 · DOI
  81. [87]Kent WJ BLAT—The BLAST-Like Alignment Tool Genome Res 2002 12 4 656 64 11932250 PMC187518
  82. [88]Burge C Karlin S Prediction of complete gene structures in human genomic dna J Mol Biol 1997 268 1 78 94 10.1006/jmbi.1997.0951 9149143 · DOI
  83. [89]Smith TF Waterman MS Identification of common molecular subsequences J Mol Biol 1981 147 1 195 7 10.1016/0022-2836(81)90087-5 7265238 · DOI
  84. [90]Needleman SB Wunsch CD A general method applicable to the search for similarities in the amino acid sequence of two proteins J Mol Biol 1970 48 3 443 53 10.1016/0022-2836(70)90057-4 5420325 · DOI · Paper page
  85. [91]Angiuoli SV Salzberg SL Mugsy: fast multiple alignment of closely related whole genomes Bioinformatics 2011 27 3 334 42 10.1093/bioinformatics/btq665 21148543 PMC3031037 · DOI · Paper page
  86. [92]Kurtz S Phillippy A Delcher AL Smoot M Shumway M Antonescu C Salzberg SL Versatile and open software for comparing large genomes Genome Biol 2004 5 2 1 9 10.1186/gb-2004-5-2-r12 PMC395750 14759262 · DOI · Paper page
  87. [93]Rausch T Emde A-K Weese D Döring A Notredame C Reinert K Segment-based multiple sequence alignment Bioinformatics 2008 24 16 187 92 10.1093/bioinformatics/btn281 18689823 · DOI
  88. [94]Brudno M Do CB Cooper GM Kim MF Davydov E Program NCS Green ED Sidow A Batzoglou S LAGAN and Multi-LAGAN: Efficient Tools for Large-Scale Multiple Alignment of Genomic DNA Genome Res 2003 13 4 721 31 10.1101/gr.926603 12654723 PMC430158 · DOI · Paper page
  89. [95]Brudno M Chapman M Göttgens B Batzoglou S Morgenstern B Fast and sensitive multiple alignment of large genomic sequences BMC Bioinformatics 2003 4 1 1 11 10.1186/1471-2105-4-66 14693042 PMC521198 · DOI
  90. [96]Höhl M Kurtz S Ohlebusch E Efficient multiple genome alignment Bioinformatics 2002 18 suppl_1 312 20 10.1093/bioinformatics/18.suppl_1.S312 12169561 · DOI
  91. [98]Darling AE Mau B Perna NT progressiveMauve: Multiple Genome Alignment with Gene Gain, Loss and Rearrangement PLoS ONE 2010 5 6 11147 10.1371/journal.pone.0011147 PMC2892488 20593022 · DOI · Paper page
  92. [99]Minkin I Medvedev P Scalable pairwise whole-genome homology mapping of long genomes with bubbz IScience 2020 23 6 101224 10.1016/j.isci.2020.101224 32563153 PMC7303978 · DOI · Paper page
  93. [100]Minkin I Pham S Medvedev P Twopaco: An efficient algorithm to build the compacted de bruijn graph from many complete genomes Bioinformatics 2017 33 24 4024 32 27659452
  94. [101]Vaser R Sović I Nagarajan N Šikić M Fast and accurate de novo genome assembly from long uncorrected reads Genome Res 2017 27 5 737 46 10.1101/gr.214270.116 28100585 PMC5411768 · DOI
  95. [102]Dubchak I Poliakov A Kislyuk A Brudno M Multiple whole-genome alignments without a reference organism Genome Res 2009 19 4 682 9 10.1101/gr.081778.108 19176791 PMC2665786 · DOI
  96. [103]Liu K Warnow TJ Holder MT Nelesen SM Yu J Stamatakis AP Linder CR Sate-ii: very fast and accurate simultaneous estimation of multiple sequence alignments and phylogenetic trees Syst Biol 2012 61 1 90 10.1093/sysbio/syr095 22139466 · DOI
  97. [104]Leimeister C-A Sohrabi-Jahromi S Morgenstern B Fast and accurate phylogeny reconstruction using filtered spaced-word matches Bioinformatics 2017 33 7 971 9 28073754 PMC5409309
  98. [105]Leimeister C-A Dencker T Morgenstern B Accurate multiple alignment of distantly related genome sequences using filtered spaced word matches as anchor points Bioinformatics 2019 35 2 211 8 10.1093/bioinformatics/bty592 29992260 PMC6330006 · DOI
  99. [106]Delcher AL Kasif S Fleischmann RD Peterson J White O Salzberg SL Alignment of whole genomes Nucleic Acids Res 1999 27 11 2369 76 10.1093/nar/27.11.2369 10325427 PMC148804 · DOI · Paper page
  100. [107]Delcher AL Phillippy A Carlton J Salzberg SL Fast algorithms for large-scale genome alignment and comparison Nucleic Acids Res 2002 30 11 2478 83 10.1093/nar/30.11.2478 12034836 PMC117189 · DOI · Paper page
  101. [108]Marçais G Delcher AL Phillippy AM Coston R Salzberg SL Zimin A Mummer4: A fast and versatile genome alignment system PLoS Comput Biol 2018 14 1 1005944 10.1371/journal.pcbi.1005944 PMC5802927 29373581 · DOI · Paper page
  102. [109]Vyverman M De Baets B Fack V Dawyndt P essamem: finding maximal exact matches using enhanced sparse suffix arrays Bioinformatics 2013 29 6 802 4 10.1093/bioinformatics/btt042 23349213 · DOI
  103. [110]Schwartz S Zhang Z Frazer KA Smit A Riemer C Bouck J Gibbs R Hardison R Miller W Pipmaker—a web server for aligning two genomic dna sequences Genome Res 2000 10 4 577 86 10.1101/gr.10.4.577 10779500 PMC310868 · DOI
  104. [111]Altschul SF Madden TL Schäffer AA Zhang J Zhang Z Miller W Lipman DJ Gapped blast and psi-blast: a new generation of protein database search programs Nucleic Acids Res 1997 25 17 3389 402 10.1093/nar/25.17.3389 9254694 PMC146917 · DOI · Paper page
  105. [112]Zhang Z Schwartz S Wagner L Miller W A greedy algorithm for aligning dna sequences J Comput Biol 2000 7 1-2 203 14 10.1089/10665270050081478 10890397 · DOI
  106. [113]Ma B Tromp J Li M Patternhunter: faster and more sensitive homology search Bioinformatics 2002 18 3 440 5 10.1093/bioinformatics/18.3.440 11934743 · DOI
  107. [114]Kehr B, Trappe K, Holtgrewe M, Reinert K. Genome alignment with graph data structures: a comparison. BMC Bioinformatics. 2014;15(1). 10.1186/1471-2105-15-99. PMC4020321 24712884 · DOI
  108. [115]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 11 1814 28 10.1101/gr.076554.108 18849524 PMC2577869 · DOI
  109. [116]Harary F, Uhlenbeck GE. Proc Natl Acad Sci USA. 1953; 39(4):315. PMC1063779 16589268
  110. [117]Paten B Diekhans M Earl D John JS Ma J Suh B Haussler D Cactus graphs for genome comparisons J Comput Biol 2011 18 3 469 81 10.1089/cmb.2010.0252 21385048 PMC8884192 · DOI · Paper page
  111. [119]Ford LR Fulkerson DR Maximal flow through a network Canadian journal of Mathematics 1956 8 399 404 10.4153/CJM-1956-045-5 · DOI
  112. [120]Durbin R Eddy SR Krogh A Mitchison G Biological sequence analysis: probabilistic models of proteins and nucleic acids 1998 Cambridge Cambridge university press
  113. [121]Minkin I, Patel A, Kolmogorov M, Vyahhi N, Pham S. Sibelia: A scalable and comprehensive synteny block generation tool for closely related microbial genomes. arXiv:1307.7941 [q-bio]. 2013. http://arxiv.org/abs/1307.7941. Accessed 25 May 2021. · arXiv
  114. [123]Earl D Nguyen N Hickey G Harris RS Fitzgerald S Beal K Seledtsov I Molodtsov V Raney BJ Clawson H Kim J Kemena C Chang J-M Erb I Poliakov A Hou M Herrero J Kent WJ Solovyev V Darling AE Ma J Notredame C Brudno M Dubchak I Haussler D Paten B Alignathon: a competitive assessment of whole-genome alignment methods Genome Res 2014 24 12 2077 89 10.1101/gr.174920.114 25273068 PMC4248324 · DOI · Paper page
  115. [125]Miga KH Koren S Rhie A Vollger MR Gershman A Bzikadze A Brooks S Howe E Porubsky D Logsdon GA Telomere-to-telomere assembly of a complete human x chromosome Nature 2020 585 7823 79 84 10.1038/s41586-020-2547-7 32663838 PMC7484160 · DOI · Paper page
  116. [126]Dalquen DA Anisimova M Gonnet GH Dessimoz C Alf—a simulation framework for genome evolution Mol Biol Evol 2012 29 4 1115 23 10.1093/molbev/msr268 22160766 PMC3341827 · DOI
  117. [127]Lilue J Doran AG Fiddes IT Abrudan M Armstrong J Bennett R Chow W Collins J Collins S Czechanski A Sixteen diverse laboratory mouse reference genomes define strain-specific haplotypes and novel functional loci Nat Genet 2018 50 11 1574 83 10.1038/s41588-018-0223-8 30275530 PMC6205630 · DOI · Paper page
  118. [128]Liu W Schmidt B Voss G Müller-Wittig W Robert Y Parashar M Badrinath R Prasanna VK Gpu-clustalw: Using graphics hardware to accelerate multiple sequence alignment High Performance Computing - HiPC 2006 2006 Berlin, Heidelberg Springer
  119. [129]Manavski SA Valle G Cuda compatible gpu cards as efficient hardware accelerators for smith-waterman sequence alignment BMC Bioinformatics 2008 9 2 1 9 18387198 PMC2323659
  120. [130]Vouzis PD Sahinidis NV Gpu-blast: using graphics processors to accelerate protein sequence alignment Bioinformatics 2011 27 2 182 8 10.1093/bioinformatics/btq644 21088027 PMC3018811 · DOI
  121. [131]Schatz MC Trapnell C Delcher AL Varshney A High-throughput sequence alignment using graphics processing units BMC Bioinformatics 2007 8 1 1 10 10.1186/1471-2105-8-474 18070356 PMC2222658 · DOI
  122. [132]Goenka SD Turakhia Y Paten B Horowitz M Segalign: a scalable gpu-based whole genome aligner SC20: International Conference for High Performance Computing, Networking, Storage and Analysis 2020 New York IEEE
  123. [133]Vivian J Rao AA Nothaft FA Ketchum C Armstrong J Novak A Pfeil J Narkizian J Deran AD Musselman-Brown A Toil enables reproducible, open source, big biomedical data analyses Nat Biotechnol 2017 35 4 314 6 10.1038/nbt.3772 28398314 PMC5546205 · DOI · Paper page
  124. [134]Di Tommaso P Chatzou M Floden EW Barja PP Palumbo E Notredame C Nextflow enables reproducible computational workflows Nat Biotechnol 2017 35 4 316 9 10.1038/nbt.3820 28398311 · DOI · Paper page
  125. [135]Kiełbasa SM Wan R Sato K Horton P Frith MC Adaptive seeds tame genomic sequence comparison Genome Res 2011 21 3 487 93 10.1101/gr.113985.110 21209072 PMC3044862 · DOI
  126. [136]Jain C Dilthey A Koren S Aluru S Phillippy AM A fast approximate algorithm for mapping long reads to large reference databases International Conference on Research in Computational Molecular Biology 2017 Cham Springer PMC6067103 29708767
  127. [137]Jain C Koren S Dilthey A Phillippy AM Aluru S A fast adaptive algorithm for computing whole-genome homology maps Bioinformatics 2018 34 17 748 56 10.1093/bioinformatics/bty597 30423094 PMC6129286 · DOI
  128. [138]Li H Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences Bioinformatics 2016 32 14 2103 10 10.1093/bioinformatics/btw152 27153593 PMC4937194 · DOI
  129. [139]Li H Minimap2: pairwise alignment for nucleotide sequences Bioinformatics 2018 34 18 3094 100 10.1093/bioinformatics/bty191 29750242 PMC6137996 · DOI · Paper page
  130. [141]Sahlin K Effective sequence similarity detection with strobemers Genome Res 2021 31 11 2080 2094 10.1101/gr.275648.121 34667119 PMC8559714 · DOI
  131. [142]Edgar R Syncmers are more sensitive than minimizers for selecting conserved k-mers in biological sequences PeerJ 2021 9 10805 10.7717/peerj.10805 PMC7869670 33604186 · DOI
  132. [143]Xin H Nahar S Zhu R Emmons J Pekhimenko G Kingsford C Alkan C Mutlu O Optimal seed solver: optimizing seed selection in read mapping Bioinformatics 2016 32 11 1632 42 10.1093/bioinformatics/btv670 26568624 PMC6363230 · DOI
  133. [144]Frith MC Noé L Kucherov G Minimally overlapping words for sequence similarity search Bioinformatics 2020 36 22-23 5344 50 10.1093/bioinformatics/btaa1054 PMC8016470 33346833 · DOI
  134. [146]Gondro C Kinghorn BP A simple genetic algorithm for multiple sequence alignment Genet Mol Res 2007 6 4 964 82 18058716
  135. [147]Boyce K Sievers F Higgins DG Instability in progressive multiple sequence alignment algorithms Algorithm Mol Biol 2015 10 1 1 10 10.1186/s13015-015-0057-1 PMC4599319 26457114 · DOI
  136. [148]Nosil P Speciation with gene flow could be common Mol Ecol 2008 17 9 2103 2106 10.1111/j.1365-294X.2008.03715.x 18410295 · DOI
  137. [150]Nakhleh L, Warnow T, Linder CR. Reconstructing reticulate evolution in species: theory and practice. In: Proceedings of the eighth annual international conference on Resaerch in computational molecular biology. Chicago: 2004. p. 337–346. 16108717
  138. [151]Vialle RA Tamuri AU Goldman N Alignment modulates ancestral sequence reconstruction accuracy Mol Biol Evol 2018 35 7 1783 97 10.1093/molbev/msy055 29618097 PMC5995191 · DOI
  139. [152]Hogeweg P Hesper B The alignment of sets of sequences and the construction of phyletic trees: an integrated method J Mol Evol 1984 20 2 175 86 10.1007/BF02257378 6433036 · DOI
  140. [153]Jandrasits C Dabrowski PW Fuchs S Renard BY seq-seq-pan: Building a computational pan-genome data structure on whole genome alignment BMC Genomics 2018 19 1 1 12 10.1186/s12864-017-4401-3 29334898 PMC5769345 · DOI
  141. [154]Hennig A Nieselt K Efficient merging of genome profile alignments Bioinformatics 2019 35 14 71 80 10.1093/bioinformatics/btz377 PMC6612806 31510683 · DOI

Cited by

Sorted by citations

Authors
Kille, B., Balaji, A., Sedlazeck, F. J., Nute, M., & Treangen, T. J.
Affiliations
  • Rice University (US)
  • Baylor College of Medicine (US)
Corresponding author
Treangen, Todd J.
ORCID
Venue
Genome Biology
Publisher
Springer Science and Business Media LLC
Published
2022-08-29
Volume
23
Issue
1
Pages
182-182
ISSN
  • 1465-6906 (ISSN-L)
  • 1474-760X
DOI
10.1186/s13059-022-02735-6
PMC
PMC9421119
OpenAlex
W4293680421
Cited by
47
References
9
Citations by year
2026: 6 · 2025: 16 · 2024: 11 · 2023: 11 · 2022: 3
FWCI
1.07
Type
journal article
Language
en
Open access
Licence
Locations
  • Genome biology (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • Rice Research Repository (Rice University) (submittedVersion, cc-by)
Funders
  • National Institute of Allergy and Infectious Diseases (P01AI152999-01)
  • U.S. National Library of Medicine (T15LM007093)
  • Aligning Science Across Parkinson (ASAP-000430)
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 › Molecular Biology › Fractal and DNA sequence analysis
Keywords
multiple genome alignment, telomere-to-telomere genome assembly, human genome assembly, comparative genomics, alignment algorithms, clinical genomics
MeSH terms
Humans, Nucleotides, Genome, Human, Telomere, 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