Fast variation-aware read alignment with deBGA-VARA
Authors:
- 1 December 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 227-233
Abstract
Many genetic variants have been reported from sequencing projects due to decreasing experimental costs. Compared to the current typical paradigm, read mapping incorporating existing variants can improve the performance of subsequent analysis. However, storing and indexing various types of variation require costly RAM space. Aligning reads to a graph model-based index including the whole set of variants is ultimately an NP-hard problem in theory. This method is supposed to map sequencing reads efficiently to a graphical index with a reference genome and known variation to increase alignment quality and variant calling accuracy. Herein, we propose a variation-aware read alignment algorithm (VARA), which generates the alignment between read and multiple genomic sequences simultaneously utilizing the schema of the Landau-Vishkin algorithm. VARA dynamically extracts regional variants to construct a pseudo tree-based structure on-the-fly for seed extension without loading the whole genome variation into memory space. We developed the novel high-throughput sequencing read aligner deBGA-VARA by integrating VARA into deBGA. The deBGA-VARA is benchmarked both on simulated reads and the NA12878 sequencing dataset. The experimental results demonstrate that read alignment incorporating genetic variation knowledge can achieve high sensitivity and accuracy. Moreover, due to its efficiency, VARA provides a promising solution for further improvement of variant calling while maintaining small memory footprints. The deBGA-VARA is available at: https://github.com/hitbc/deBGA-VARA.Keywords
This publication has 33 references indexed in Scilit:
- SSW Library: An SIMD Smith-Waterman C/C++ Library for Use in Genomic ApplicationsPLOS ONE, 2013
- Short read alignment with populations of genomesBioinformatics, 2013
- Haplotype phasing: existing methods and new developmentsNature Reviews Genetics, 2011
- The variant call format and VCFtoolsBioinformatics, 2011
- Genotype and SNP calling from next-generation sequencing dataNature Reviews Genetics, 2011
- CpG islands and the regulation of transcriptionGenes & Development, 2011
- A framework for variation discovery and genotyping using next-generation DNA sequencing dataNature Genetics, 2011
- A map of human genome variation from population-scale sequencingNature, 2010
- The Genome Analysis Toolkit: A MapReduce framework for analyzing next-generation DNA sequencing dataGenome Research, 2010
- The Sequence Alignment/Map format and SAMtoolsBioinformatics, 2009