Motif search in computational biology is a most challenging problem. This plays a crucial role ingene finding and understanding the gene regulation relationship. In this study, a new efficient algorithm isproposed for the (l, d) motif search problem to find all string of length l which present in each of the input stringwith d mismatches. The method is based on 2 key aspects. First, a group of 3 l-mers of close proximity isprocessed efficaciously to generate the common d-neighborhood and second the data structure bit vector isused which simplifies the process of making the union and intersection of the common d-neighborhood. Theproposed approach can be considered to be a hybrid one, as it integrates the existing algorithm with the novelideas of common d-neighborhood generation to achieve better running time. Moreover, a parallel version ofproposed method is also presented which runs on 4 SMP cluster systems with each of 2.4 GHz Intel Pentium-IVhaving 16 GB ram running under Red Hat Linux. The experimental result shows that the proposed algorithm islinearly scalable with the number of processors.
展开▼
机译：计算生物学中的主题搜索是一个最具挑战性的问题。这在寻找和理解基因调控关系中起着至关重要的作用。在这项研究中，针对（l，d）主题搜索问题提出了一种新的有效算法，以找到存在于每个输入字符串中d不匹配的长度为l的所有字符串。该方法基于两个关键方面。首先，有效地处理一组3个紧密相邻的l-mer，以生成公共d邻域，其次，使用数据结构位向量，从而简化了建立公共d邻域的并集和交集的过程。所提出的方法可以被认为是一种混合方法，因为它将现有算法与常见d邻域生成的新颖思想相集成，以实现更好的运行时间。此外，还提出了建议方法的并行版本，该方法在4个SMP群集系统上运行，每个2.4 GHz Intel Pentium-IV具有16 GB内存，在Red Hat Linux下运行。实验结果表明，该算法可随着处理器数量的增加而线性扩展。
展开▼
