Scalable multiple whole-genome alignment and locally collinear block construction with SibeliaZ
Open Access
- 10 December 2020
- journal article
- research article
- Published by Springer Nature in Nature Communications
- Vol. 11 (1) , 1-11
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.Keywords
All Related Versions
Funding Information
- 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)
This publication has 51 references indexed in Scilit:
- Reference-assisted chromosome assemblyProceedings of the National Academy of Sciences, 2013
- i-ADHoRe 3.0—fast and sensitive detection of genomic homology in extremely large data setsNucleic Acids Research, 2011
- Cactus: Algorithms for genome multiple sequence alignmentGenome Research, 2011
- Mugsy: fast multiple alignment of closely related whole genomesBioinformatics, 2010
- progressiveMauve: Multiple Genome Alignment with Gene Gain, Loss and RearrangementPLOS ONE, 2010
- Multiple whole-genome alignments without a reference organismGenome Research, 2009
- Enredo and Pecan: Genome-wide mammalian consistency-based multiple alignment with paralogsGenome Research, 2008
- BLAT—The BLAST-Like Alignment ToolGenome Research, 2002
- Gapped BLAST and PSI-BLAST: a new generation of protein database search programsNucleic Acids Research, 1997
- Basic local alignment search toolJournal of Molecular Biology, 1990