A C++ library for protein sub-structure search

Jianfu Zhou, Gevorg GrigoryanBiorxiv 2020 · DOI

TL;DR

This paper introduces MASTER v.2, a C++ API library for efficiently searching large protein structure databases for specific sub-structural motifs. By enabling in-memory database storage and a novel proximity search algorithm, it significantly simplifies and accelerates automated structure-based data mining for researchers.

What Problem Does This Paper Address?

Proteins, the workhorses of biology, often exhibit recurring local structural patterns, or "motifs." Identifying these motifs within vast databases of known protein structures is crucial for understanding protein function, evolution, and for designing new proteins. The authors' previous work, MASTER, addressed this by finding protein fragments that match a query motif within a specified structural similarity (RMSD). However, the original MASTER relied on an on-disk database, making automated searches slow due to input/output (I/O) and inter-process communication bottlenecks. This paper tackles the challenge of making MASTER more accessible and efficient for programmatic use, allowing researchers to integrate its powerful search capabilities directly into their own computational pipelines.

Methods

The core innovation of MASTER v.2 lies in its new implementation as a C++ Application Program Interface (API) library. This allows researchers to call MASTER functions directly from their code, eliminating the need for external scripting and reducing overhead.

Key methodological improvements include:

  • In-Memory Database: Instead of storing the database on disk, MASTER v.2 loads it entirely into RAM. This drastically reduces I/O operations, a major bottleneck in the previous version.
  • Proximity Search Algorithm: To manage the memory footprint of an in-memory database, the authors developed a "room-saving" proximity search method. This approach embeds protein structures into a 3D grid. Instead of storing explicit inter-residue distances, proximity queries are performed by visiting grid boxes that are likely to contain nearby atoms. This reduces the memory cost from O(N²) to an estimated O(N) for typical globular proteins, where N is the number of residues.
  • API Design: The library provides a straightforward API with functions to set queries, add target databases, specify RMSD cutoffs, initiate searches, and retrieve results.

Datasets

The paper does not explicitly list specific datasets used for training or evaluation. However, it refers to "large structural databases" and mentions using "a nonredundant subset of the Protein Data Bank selected by using BLASTClust at 30% sequence identity" for Figure 1, which illustrates the correlation between protein radius of gyration and its length.

Key Insights and Ideas

  • The Power of In-Memory: Moving the database into RAM is a game-changer for performance in structure search applications, highlighting the importance of memory management in computational biology.
  • Grid-Based Proximity Search: The novel grid-based approach to proximity searching is an elegant solution to the memory demands of large databases, demonstrating that clever data structuring can overcome computational challenges without sacrificing asymptotic search speed.
  • API-Driven Research: Providing a programmatic interface (API) for powerful algorithms like MASTER democratizes their use, enabling more complex and automated research workflows in structural biology.
  • Protein Structure Modularity: The paper reinforces the idea that proteins are not monolithic but rather composed of recurring, modular sub-structures, making motif searching a fundamental tool for understanding their behavior.

Key Results

The paper emphasizes that the new implementation, MASTER v.2, significantly simplifies programmatic access to MASTER's search functionality. While the asymptotic running time of the proximity search itself remains comparable (O(d³), where d is the query distance), the removal of disk I/O overhead makes the overall search process much faster in practice. The memory footprint for storing databases is also substantially reduced, allowing for larger databases to be held in memory. The authors also note the availability of a Python interface for the library, further enhancing its accessibility.

Limitations and Future Work

The paper acknowledges that the worst-case memory usage for the grid structure can be cubic in protein length (O(N³)), although they argue this is uncommon in practice due to the typical globular nature of proteins and the focus on spatially localized motifs. They suggest that splitting very long, extended structures into smaller, overlapping portions can mitigate this. The authors do not explicitly discuss limitations of the search accuracy or potential biases introduced by the new methods, focusing primarily on the implementation and performance improvements. Future work is implied by the availability of the API, which is intended to facilitate a wide range of automated structure-based data mining applications.

Summary updated

Abstract

Abstract Summary MASTER is a previously published algorithm for protein sub-structure search. Given a database of protein structures and a query structural motif, composed of multiple disjoint segments, it finds all sub-structures from the database that align onto the query to within a pre-specified backbone root-mean-square deviation. Here, we present an improved version of the algorithm, MASTER v.2, in the form of an open-source C++ Application Program Interface library, thereby providing programmatic access to structure search functionality. An entirely reorganized approach to database representation now enables large structural databases to be stored in memory, further simplifying development of automated search-based methods. Given the increasingly important role of structure-based data mining, our improved implementation should find ample uses in structural biology applications. Availability MASTER is available at https://grigoryanlab.org/master/master-v2.php . Contact [email protected]
BibTeX
@misc{zhou2020c,
  author = {Jianfu Zhou and Gevorg Grigoryan},
  title = {{A C++ library for protein sub-structure search}},
  year = {2020},
  doi = {10.1101/2020.04.26.062612},
  howpublished = {Biorxiv},
}
Figure