Asian Journal of Information Technology

Year: 2016
Volume: 15
Issue: 23
Page No. 4835 - 4843

Improved Exact Parallel Algorithm for Planted (l, d) Motif Search

Authors : Satarupa Mohanty and Biswajit Sahoo

Abstract: Motif search in computational biology is a most challenging problem. This plays a crucial role in gene finding and understanding the gene regulation relationship. In this study, a new efficient algorithm is proposed for the (l, d) motif search problem to find all string of length l which present in each of the input string with d mismatches. The method is based on 2 key aspects. First, a group of 3 l-mers of close proximity is processed efficaciously to generate the common d-neighborhood and second the data structure bit vector is used which simplifies the process of making the union and intersection of the common d-neighborhood. The proposed approach can be considered to be a hybrid one, as it integrates the existing algorithm with the novel ideas of common d-neighborhood generation to achieve better running time. Moreover, a parallel version of proposed method is also presented which runs on 4 SMP cluster systems with each of 2.4 GHz Intel Pentium-IV having 16 GB ram running under Red Hat Linux. The experimental result shows that the proposed algorithm is linearly scalable with the number of processors.

How to cite this article:

Satarupa Mohanty and Biswajit Sahoo, 2016. Improved Exact Parallel Algorithm for Planted (l, d) Motif Search. Asian Journal of Information Technology, 15: 4835-4843.

Design and power by Medwell Web Development Team. © Medwell Publishing 2022 All Rights Reserved