A hybrid method for the exact planted (l, d) motif finding problem and its parallelization.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• The (l, d) motif problem seeks an l-length motif M in t DNA sequences, allowing up to d mismatches per sequence.
• Existing exact algorithms for motif finding are computationally intensive and limited to small motif lengths (l) and mismatch counts (d).

Purpose of the Study:

• To develop an efficient hybrid method that enhances the performance of exact algorithms for the motif finding problem.
• To enable the discovery of longer motifs and solve more challenging instances of the (l, d) motif problem.

Main Methods:

• A two-step hybrid approach: 1. Identify candidate motifs from a subset of sequences (q). 2. Search for these candidates in the remaining sequences.
• Integration of existing state-of-the-art algorithms to optimize runtime.
• Determination of the optimal subset size (q) for maximum efficiency.
• Development of a parallel version for shared memory architectures.

Main Results:

• Achieved approximately 24% speed-up compared to the best existing algorithm.
• Demonstrated linear scalability of the parallel version with the number of processors.
• Successfully solved a challenging (21, 8) motif instance in 20.42 hours using 8 processors, compared to 6.68 days for the serial version.

Conclusions:

• The proposed hybrid method significantly accelerates the exact motif problem solution.
• The method is generic and adaptable to new, faster algorithms.
• Expectation of facilitating the discovery of longer motifs.
• Developed software is freely available for academic research.