pmTM-align: scalable pairwise and multiple structure alignment with Apache Spark and OpenMP

Weiya Chen, Chun Yao, Yingzhong Guo, Yan Wang, Zhidong XueBMC Bioinformatics 2020 · DOI

TL;DR

This paper introduces pmTM-align, a novel approach that significantly accelerates protein structure alignment by leveraging Apache Spark for distributed pairwise alignments and OpenMP for efficient multi-core processing of multiple structure alignments. This hybrid architecture enables scalable and timely analysis of large protein structure datasets, overcoming the computational bottlenecks of existing methods.

What Problem Does This Paper Address?

Comparing protein structures is crucial for understanding their function and evolutionary relationships. However, the exponential growth of protein structure data in databases like the Protein Data Bank makes large-scale structure comparisons computationally prohibitive. Existing methods, while accurate, struggle with the sheer volume of data, leading to long processing times. This paper addresses the critical need for scalable and efficient tools that can handle massive datasets for both pairwise and multiple structure alignment tasks.

Methods

pmTM-align employs a two-stage hybrid architecture:

  • Stage 1: Spark-based Pairwise Structure Alignment (PSA): This stage leverages Apache Spark for distributed computation. Protein structures are loaded into Resilient Distributed Datasets (RDDs) and processed in parallel across a Spark cluster. The existing TM-align algorithm is integrated via a pipe-based approach, allowing it to run as an external C++ library within Spark. This stage is designed for data-level parallelism and scalability.
  • Stage 2: OpenMP-based Multiple Structure Alignment (MSTA): After generating pairwise alignments and a distance matrix, a phylogenetic tree is constructed. The subsequent incremental alignment of multiple structures, which is computationally intensive and involves interdependencies, is handled locally using OpenMP on multi-core CPUs. Key optimizations include:
  • Binary Tree Data Structure: Replacing the original array-based phylogenetic tree with a binary tree for more efficient traversal and node access.
  • OpenMP Tasks for Tree Traversal: Parallelizing the post-order traversal of the phylogenetic tree using OpenMP tasks.
  • OpenMP for pragmas for Loop Schedules: Accelerating the numerous loops involved in incremental alignment and metric computation using dynamic scheduling for load balancing.

Datasets

The primary dataset used for evaluation is the SABmark dataset (version 1.65). This dataset is a standard benchmark for MSTA algorithms and contains two subsets:

  • Superfamily: Structures with pairwise sequence identity < 50%.
  • Twilight Zone: Structures with pairwise sequence identity < 25%.

The authors also created custom subsets by merging groups from SABmark to test scalability with varying numbers of structures, ranging from 25 to 1600 for PSA tests, and finer subsets from 20 to 100 for the full MSTA process.

Key Insights and Ideas

  • Hybrid Architecture is Key: Combining distributed computing (Spark) for embarrassingly parallel tasks (PSA) with multi-core parallelism (OpenMP) for more complex, interdependent tasks (MSTA) is crucial for achieving significant speedups.
  • Spark's Scalability for PSA: For large datasets (e.g., 400+ structures), Spark-based PSA demonstrates near-ideal linear speedup, making it highly effective for the initial pairwise comparison phase.
  • OpenMP's Impact on MSTA: OpenMP provides substantial acceleration for the incremental alignment and metric computation stages, especially for larger datasets, even after other optimizations.
  • Data Structure Matters: Replacing the array-based phylogenetic tree with a binary tree significantly improves the efficiency of the MSTA stage.
  • Partitioning is Critical for Spark: The default Spark partitioning can lead to unbalanced workloads. Manually setting the number of partitions, especially for large datasets, is essential for optimal performance.
  • Overhead of Distribution: For very small datasets, the overhead of distributing tasks across a Spark cluster can outweigh the benefits, making local execution more efficient.

Key Results

  • Spark-based PSA: Achieved near-ideal speedup for all-to-all PSA tasks with datasets of 400 structures or more, scaling almost linearly with the number of executors. For 1600 structures, the speedup ratio was close to ideal.
  • OpenMP Acceleration:
    • Incremental alignment speedup of approximately 2x.
  • Metrics computation speedup of approximately 5.5x.
  • End-to-End MSTA Performance:
    • pmTM-align (Spark + OpenMP) showed a significant performance gain over the original mTM-align.
  • In the best case (subset 100), a 72-fold gain in performance was observed.
  • pmTM-align-single (Spark only, no OpenMP) also provided substantial speedups, demonstrating the impact of Spark. For example, for subset 100, it reduced execution time from over 300s to around 40s.
  • Partitioning Impact: Using user-specified partitions (e.g., 64) significantly outperformed the default (2) for PSA tasks, reducing execution time by up to half for larger subsets.
  • Task-based Parallel Tree Traversal: This specific parallelization strategy did not yield visible acceleration and was sometimes slower than the serial version, likely due to the nature of tree climbing and varying tree shapes.

Limitations and Future Work

  • Task-based Parallel Tree Traversal: The authors found that this approach did not provide significant speedups and recommend sticking with loop parallelism for MSTA.
  • Small Dataset Performance: For very small input data, deploying tasks on Spark can be less efficient than local execution due to overhead.
  • Future Work:
    • Investigate distributed methods for building phylogenetic trees and performing incremental alignment.
  • Explore combining Spark with GPU computing for further acceleration of PSA tasks.
  • Address the limitations of small dataset performance.

Summary updated

BibTeX
@article{chen2020pmtm,
  author = {Weiya Chen and Chun Yao and Yingzhong Guo and Yan Wang and Zhidong Xue},
  title = {{pmTM-align: scalable pairwise and multiple structure alignment with Apache Spark and OpenMP}},
  journal = {BMC Bioinformatics},
  year = {2020},
  doi = {10.1186/s12859-020-03757-2},
}
Figure