Asian Journal of Information Technology
ISSN: Online 1993-5994ISSN: Print 1682-3915
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. Improved Exact Parallel Algorithm for Planted (l, d) Motif Search.
DOI: https://doi.org/10.36478/ajit.2016.4835.4843
URL: https://www.makhillpublications.co/view-article/1682-3915/ajit.2016.4835.4843