TY  - JOUR
T1  - Improved Exact Parallel Algorithm for Planted (l, d) Motif Search
AU - Mohanty, Satarupa AU - Sahoo, Biswajit 
JO  - Asian Journal of Information Technology
VL  - 15
IS  - 23
SP  - 4835
EP  - 4843
PY  - 2016
DA  - 2001/08/19
SN  - 1682-3915
DO  - ajit.2016.4835.4843
UR  - https://makhillpublications.co/view-article.php?doi=ajit.2016.4835.4843
KW  - Planted motif search
KW  -Symmetric Multi Processor (SMP)
KW  -Message Passing Interface (MPI)
KW  -bit map vector
KW  -string algorithm
AB  - 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.
ER  -