Design and development of efficient Bloom Filters to improve the efficiency of the preprocessing filtering of a DNA Assembly

Abstract

DNA assembly consists of many processes to combine the huge volume of Read fragments into a DNA sequence. The complexity of DNA assembly is due to the Read fragments, which are erroneous, repetitive, and massive in volume. This makes the processes data and resource-intensive. Furthermore, the DNA data is increasing exponentially, and thus, it increases the processing complexity. The pre-processing stage of DNA assembly deals with the DNA data. The processes of this stage require considerable time and space for computation. Therefore, there is a necessity for a fast and low-memory data structure to boost the performance of the pre-processing processes to enhance the overall performance of DNA assembly. Bloom Filter is such a data structure. Bloom Filter is a probabilistic data structure used for fast filtering and membership validation of data. It has low space and time complexity. Its main issue is false positives. Many variants are proposed to address this issue, but their performance is unsatisfactory. This dissertation proposed a two-dimensional Bloom Filter variant that uses bitwise operations to reduce false positives drastically. This Bloom Filter variant is further manipulated to utilise Bloom Filter for membership validation of paired data. This work also proposes a counting Bloom Filter variant with low false positives implemented for counting data. This counting Bloom Filter variant is implemented in K-mer counting and Read compression to enhance the performance of the pre-processing stage of DNA assembly. Our first work proposed a robust Bloom Filter called robustBF. This two-dimensional Bloom Filter can effectively filter large volumes of data with exceptional accuracy while maintaining high-performance levels. We enhance the Murmur hash function and rigorously test various modified versions to identify the best-performing variant through experimentation. Then, this optimised hash function is integrated into robustBF. Our experimental findings demonstrate that robustBF surpasses the state-of-the-art.