Exploring Scalable Parallelization for Edit Distance-Based Motif Search

Area of Science:

• Bioinformatics
• Computational Biology
• Algorithm Design

Background:

• Motif searching is vital for extracting biological insights from rapidly growing datasets.
• The NP-hard nature of general motif searching necessitates efficient algorithms.
• Existing methods struggle with the scale and speed demands of modern biological data analysis.

Purpose of the Study:

• To develop scalable and efficient parallel algorithms for Edit Distance-Based Motif Search (EMS).
• To introduce practical parallelization strategies that optimize for speed and/or memory usage.
• To evaluate the performance of the proposed methods on real-world biological data.

Main Methods:

• Implementation of two parallel designs: recursEMS (parallel recursion tree) and parEMS (thread-based).
• Development of SPEMS (Scalability-sensitive Parallel solver for EMS) to provide adaptive parallelization.
• Evaluation using two real-world DNA datasets: TRANSFAC and ChIP-seq on a 48-core machine.

Main Results:

• SPEMS achieves up to 10x geometric mean speedup over state-of-the-art methods, with memory overheads.
• Alternatively, SPEMS provides 2.2x geometric mean speedup with potential memory savings.
• The solver offers flexible parallelization, balancing performance and space efficiency.

Conclusions:

• SPEMS presents a practical and scalable solution for Edit Distance-Based Motif Search.
• The algorithm effectively addresses the computational challenges posed by large biological datasets.
• SPEMS demonstrates significant performance improvements in motif discovery, adaptable to different resource constraints.