Distributed Compressive Genomics: Fundamental Pattern Matching Primitives via Spark

Abstract Background: Compressive genomics consists of a set of techniques that, for some important bioinformatics tasks such as sequence comparison and search, leverages on a compressed representation of the data in order to improve time performance. That is, its good compression is not the final goal, since the new and smaller representation of the data should support fast processing of it. Although Big Data technologies, such as distributed systems incarnated by Spark, have no apparent limit on the overall amount of memory available, making compression not so appealing, they may benefit of compressive genomics for a variety of reasons (e.g., the economic cost of adding more computational nodes may be significant). Unfortunately, there is no study that provides an evaluation of how convenient such an approach would be, to fix ideas, for Spark. Results: Although porting compressive genomics techniques to a distributed environment is not simple neither immediate, we present here the first study regarding the benefits of compressive genomics for Big Data technologies such as Spark. In particular, we provide the first Spark version of the FM-Index, a fundamental compressed pattern matching data structure with pervasive use in bioinformatics. For completeness, we also propose Spark versions of the Compressed Boyer-Moore Pattern Matching algorithm. A carefully designed experimental analysis indicates the clear advantages of using those two compressed genomics primitives within Spark. Moreover, we propose a general method, with associated software, that simplifies the development of compressive genomics techniques on Spark. Conclusions: We provide the first, and much needed study, regarding the potential advantages of using compressive genomics within Big data technologies: the proof of principle is via a fundamental compressed data structure for bioinformatics such as the FM-Index on a leading system such as Spark. The software platform associated to this research is perceived as a fundamental building block for further studies in this area. Availability: https://github.com/ldirocco/SparkGeco