2021 · 13 citations · 11 references
Life SciencesBioinformaticsComputer EngineeringGenomicsHeterogeneous ComputingParallel ComputingComputational GenomicsData ParallelismDna SequencingGraphics Processing Unit ComputingHardware AccelerationSequence AlignmentComputational Alignment AlgorithmsComputational Efficiency In AlignmentGpu Parallel AlgorithmsGraph ProcessingMemory Access LocalityMemory LocalityMemory Locality OptimizationScientific Computing On Gpus
Sequence alignment is traditionally done between individual reads and a reference sequence. Recently, several sequence-to-graph aligners have been developed, because graph genomes provide more information than sequences. For example, variation graphs, which are created by augmenting linear genomes with known genetic variations, can significantly improve the quality of genotyping. However, existing sequence-to-graph aligners run on the CPU only, and the processing time is long. To speed up the processing, we propose a parallel sequence-to-graph alignment algorithm named HGA (Heterogeneous Graph Aligner) that runs on both the CPU and GPUs. Our algorithm achieves efficient CPU-GPU co-processing through dynamically distributing tasks to each processor. We design optimizations for frequent structures in genome graphs to reduce computational cost. Moreover, we propose the GCSR (Genome CSR) data structure for efficient genome graph processing on GPUs. We also apply architecture-aware optimizations to improve memory locality and increase throughput. Our experiments on a Xeon E5-2683 CPU and eight RTX 2080 Ti GPUs show that our algorithms outperform state-of-the-art aligners by up to 15.8 times and scale well on both the CPU and GPUs. The code of our HGA is available athttps://github.com/RapidsAtHKUST/hga.
11
Improved genome inference in the MHC using a population reference graph
Alexander Dilthey, Charles Cox, Zamin Iqbal et al. · Nature Genetics · 2015 · 224 citations · Full text