International Conference on Computer and Knowledge Engineering

Home / 14th International Conference on Computer and Knowledge Engineering

Fast and Accurate Motif Discovery in Protein Sequences Using Parallel Processing with OpenMP

Authors :

Rahele Mohammadi¹ Mahmoud Naghibzadeh² Abdorreza Savadi³

1- Computer Engineering Dept. Ferdowsi University of Mashhad Mashhad, Iran 2- Full Professor, Computer Engineering Dept. Ferdowsi University of Mashhad Mashhad, Iran 3- Assistant Professor, Computer Engineering Dept. Ferdowsi University of Mashhad Mashhad, Iran

Keywords :

Cell،Genome،Protein architecture،Amino acid sequence،Motif،Parallel multi-threading،Execution time reduction،Performance improvement

Abstract :

In today's rapidly advancing field of biomedical research, the demand for swift and accurate identification of mutations within biological sequences, including proteins and genomes, is essential for effective disease diagnosis and treatment. Within the realm of protein sequence analysis, recurring patterns known as motifs play a crucial role. These motifs, whether of fixed or variable lengths, often signify essential structural or functional features such as transcription factor binding sites or protein-protein interaction interfaces. Over time, several methods have emerged for detecting motifs within protein datasets. Among these, our previous work introduced the Tree-based Fast Exact Motif (TFEM) algorithm. Unlike some contemporary techniques like Sensitive Thorough Rapid Enriched Motif Elicitation (STREME), Multiple EM for Motif Elicitation (MEME), and Discriminative Regular Expression Motif Elicitation (DREME), TFEM demonstrated superior efficiency in accurately identifying motifs. However, the computational complexity of TFEM presents challenges. With a time complexity of O (n20k), where 'n' denotes the number of sequences in the input set and 'k' signifies the length of the motif under investigation, the algorithm's performance is heavily influenced by the size of the input set. To address this challenge, we propose leveraging CPU parallelization techniques, specifically Open-MP programming, to optimize the execution time of the TFEM algorithm. The evaluation results showed that parallelization in large datasets can reduce execution time up to approximately half compared to the serial algorithm.