Enhancing Parallel Recursive Brute Force Algorithm for Motif Finding

search is a fundamental problem in bioinformatics. Its main application is locating transcription factor binding sites (TFBSs) in DNA sequences. Numerous algorithms have been proposed in the literature to solve this problem. The exact algorithms solve M(l,d) problem by reporting all l-length motifs M with at most d mutations. Recursive Brute Force (R- BF) algorithm is an exact algorithm that has solved M(l,d) problem in exponential time with d. Multicore implementations of R-BF have efficiently utilized computation resources of modern multicore architectures to achieve more advantageous operation than sequential one. In this paper, we explore an enhanced version of R-BF algorithm. The new algorithm is called R-BF2. R-BF2 enhances the running time of R-BF by memorizing more information about each node in search space. R-BF2 pays more than 40% memory space to achieve a speedup factor of 3. However, parallel implementations of R-BF2 keep the same scalability just like R-BF on multicore systems.