A Bin-Based Indexing for Scalable Range Join on Genomic Data
- 27 January 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 20 (3) , 2210-2222
Abstract
Range-join is an operation for finding overlaps in interval-form genomic data. Range-join is widely used in various genome analysis processes such as annotation, filtering and comparison of variants in whole-genome and exome analysis pipelines. The quadratic complexity of current algorithms with sheer data volume has surged the design challenges. Existing tools have limitations on algorithm efficiency, parallelism, scalability and memory consumption. This paper proposes BIndex, a novel bin-based indexing algorithm and its distributed implementation to attain high throughput range-join processing. BIndex features near-constant search complexity while the inherently parallel data structure facilitates exploitation of parallel computing architectures. Balanced partitioning of dataset further enables scalability on distributed frameworks. The implementation on Message Passing Interface shows upto 933.5x speedup in comparison to state-of-the-art tools. Parallel nature of BIndex further enables GPU-based acceleration with 3.72x speedup than CPU implementations. The add-in modules for Apache Spark provides upto 4.65x speedup than the previously best available tool. BIndex supports wide variety of input and output formats prevalent in bioinformatics community and the algorithm is easily extendable to streaming data in recent Big Data solutions. Furthermore, the index data structure is memory-efficient and consumes upto two orders-of-magnitude lesser RAM, while having no adverse effect on speedup.Keywords
Funding Information
- Ministry of Science and Technology, Taiwan (MOST 111-2221-E-A49-092-MY3)
This publication has 25 references indexed in Scilit:
- The impact of genomics on health outcomes, quality, and safetyNursing Management, 2016
- GenAp: a distributed SQL interface for genomic dataBMC Bioinformatics, 2016
- Big Data: Astronomical or Genomical?PLOS Biology, 2015
- Rethinking Data-Intensive Science Using Scalable Analytics Systems2015
- An Efficient Search Algorithm for Finding Genomic-Range Overlaps Based on the Maximum Range LengthIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2014
- The UCSC Genome Browser database: 2014 updateNucleic Acids Research, 2013
- Software for Computing and Annotating Genomic RangesPLOS Computational Biology, 2013
- BEDOPS: high-performance genomic feature operationsBioinformatics, 2012
- Kaviar: an accessible system for testing SNV noveltyBioinformatics, 2011
- BEDTools: a flexible suite of utilities for comparing genomic featuresBioinformatics, 2010