Cache Friendly Optimisation of de Bruijn Graph Based Local Re-Assembly in Variant Calling.
Autor: Gamaarachchi, Hasindu; Bayat, Arash; Gaeta, Bruno; Parameswaran, Sri
Publication year: 2020
IEEE/ACM transactions on computational biology and bioinformatics
issn:1557-9964 1545-5963
doi: 10.1109/TCBB.2018.2881975
Abstract:
A variant caller is used to identify variations in an individual genome (compared to the reference genome) in a genome processing pipeline. For the sake of accuracy, modern variant callers perform many local re-assemblies on small regions of the genome using a graph-based algorithm. However, such graph-based data structures are inefficiently stored in the linear memory of modern computers, which in turn reduces computing efficiency. Therefore, variant calling can take several CPU hours for a typical human genome. We have sped up the local re-assembly algorithm with no impact on its accuracy, by the effective use of the memory hierarchy. The proposed algorithm maximises data locality so that the fast internal processor memory (cache) is efficiently used. By the increased use of caches, accesses to main memory are minimised. The resulting algorithm is up to twice as fast as the original one when executed on a commodity computer and could gain even more speed up on computers with less complex memory subsystems.
Language: eng
Rights:
Pmid: 30452377
Tags: *Algorithms; Genetic Variation/*genetics; Genomics/*methods; High-Throughput Nucleotide Sequencing/*methods; Sequence Analysis, DNA/*methods
Link: https://pubmed.ncbi.nlm.nih.gov/30452377/
