Exploiting Anti-Monotonic Constraints in Mining Palindromic Motifs from Big Genomic Data
Oluwafemi Abimbola Sarumi, Carson Kai-Sang Leung · 2019
The advent of high-throughput technologies such as Illumina HiSeq X, mass spectrometry, and microarray heralds a new era of big biological datasets in computational biology. This digital revolution in bioinformatics has generated unprecedented volumes of omics data (e.g., transcriptomes, genomes, proteomes, metabolomes) with various degrees of veracities and values. These deluge of omics data are awash with a wealth of information in the form of frequently repeated contiguous patterns-namely, sequence motifs. Sequence motifs are short repeated contiguous subsequences located in the promoter region of a genome sequence. On some occasions, users are interested in mining only a particular type of sequence motifs (e.g., palindromic motifs). In genomics, palindromes are sequences from the nucleotide bases from deoxyribonucleic acid (DNA) or ribonucleic acid (RNA) strands that are symmetrical in the sense that they read exactly the same as their complementary sequences in the reverse direction. The use of classical constraints (e.g., anti-monotonic, succinct, and/or convertible constraints) allows users to specify their interest in the universal search space, and thus enhancing distinct and effective pruning of the search space- leading to a reduction in the computational time required for the mining process. Despite several attempts made by existing algorithms for mining palindromic motifs from DNA sequences, a major drawback stems from the high volumes of the DNA sequences leading to high complexities and turnaround time of the algorithms. To this end, we propose a parallel scalable sequential mining algorithm that exploits some features of anti-monotonic constraints-using the in-memory computing model of the Apache Spark framework deployed on a cluster of a homogeneous distributed-memory system-for mining palindromic motifs from high volumes of DNA sequences. To evaluate our algorithm, we obtained the human genome (Homo sapiens) assemblies GRCh37 patch 13 (hg19), which is of size 3.2 GB from the Ensembl data repository. It contains 104,763 protein-coding sequences and 24,513 non-coding sequences. Evaluation results show that our algorithm extracts accurate palindromic motifs using a short turnaround time.