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