Exploring Scalable Parallelization for Edit Distance-Based Motif Search
Exploring Scalable Parallelization for Edit Distance-Based Motif Search
复制标题
DOI：
10.1109/tcbb.2022.3208867
复制
发表时间：
2023-03-01
影响因子：
4.5
通讯作者：
Ebnenasir，Ali
中科院分区：
文献类型：
--
作者：
Qiu，Junqiao;Ebnenasir，Ali
模体搜索是从生物数据中发现关键信息的一个重要问题。由于一般模体搜索是NP难的，近年来生物数据量呈指数级增长，迫切需要开发时间和空间有效的算法来找到模体。在本文中，我们探讨了可扩展的并行编辑距离为基础的基序搜索（EMS）。我们介绍了两个并行设计，recursEMS集成现有的EMS求解器到一个并行递归树运行在多个进程中，parEMS提出了一种新的基于线程的方法，避免了冗余的主题候选人的存储。为了使并行设计切实可行，我们实现了SPEMS，一个可扩展性敏感并行求解EMS。对于任何给定的生物数据集和搜索实例，SPEMS可以提供朝向最佳性能的EMS并行化，或者次优性能但空间效率更高。在两个实际的DNA序列TRANSFAC和ChIP-seq上的测试表明，SPEMS在48核机器上运行时，可以在不低于74.7%的内存开销下获得10倍的几何平均加速比，或者在可能消耗较少内存的情况下获得2.2倍的几何平均加速比.
Motif Searching is an important problem that can reveal crucial information from biological data. Since the general motif searching is NP-hard and the volume of biological data is growing exponentially in recent years, there is a pressing need for developing time and space-efficient algorithms to find motifs. In this paper, we explore scalable parallelization for Edit Distance-Based Motif Search (EMS). We introduce two parallel designs, recursEMS which integrates the existing EMS solver into a parallel recursion tree running in multiple processes, and parEMS that presents a novel thread-based method which avoids the storage of redundant motif candidates. To make the parallel designs practical, we implementSPEMS, aScalability-sensitiveParallel solver for EMS. For any given biological dataset and search instance, SPEMS can provide an EMS parallelization towards the optimal performance, or a sub-optimal performance but being more space efficient. Evaluations on two real-world DNA datasetTRANSFACandChIP-seqshow that SPEMS can obtain 10× geometric mean speedup over the state-of-the-art at the expense of no less than 74.7% memory overheads, or provide 2.2× geometric mean speedup with the possibility of consuming less memory, when running on a 48-core machine.