Rapid and sensitive protein complex alignment with Foldseek-Multimer

Abstract

Advances in computational structure prediction will vastly augment the hundreds of thousands of currently available protein complex structures. Translating these into discoveries requires aligning them, which is computationally prohibitive. Foldseek-Multimer computes complex alignments from compatible chain-to-chain alignments, identified by efficiently clustering their superposition vectors. Foldseek-Multimer is 3-4 orders of magnitudes faster than the gold standard, while producing comparable alignments; this allows it to compare billions of complex pairs in 11 h. Foldseek-Multimer is open-source software available at GitHub via https://github.com/steineggerlab/foldseek/ , https://search.foldseek.com/search/ and the BFMD database.

Fig. 1. Foldseek-Multimer schematic.

a, Foldseek-Multimer allows fast querying of input complex(es) against a large database, potentially containing millions of targets. b, All chains from the query (gray) are compared to those of each target (red). A prefilter allows to quickly reject non-matching chain pairs so the full alignment is only applied to promising complex pairs. c, Foldseek-Multimer represents each chain-to-chain alignment as a superposition, described by rotations and translations, required for superposing the target chain onto the query. In this simplified example, two chain-to-chain alignments (top, bottom) are a rotation along one axis (yellow and green highlights), while one (middle) is a rotation along a different axis. d, The complex-to-complex alignment is inferred from chain-to-chain alignments as the superpositions of chain pairs in the complex alignment are similar (‘Algorithm: overview’). Foldseek-Multimer uses the DBSCAN algorithm iteratively, with increasing radii, to identify superposition clusters and the best-scoring valid cluster for computing the complex alignment (Supplementary Fig. 1). e, Based on the best-scoring cluster, the complex TM score is computed across all chain alignments between query and target.

Fig. 2. Performance of Foldseek-Multimer.

a, Query-length normalized TM scores (target-normalized: Supplementary Fig. 2) computed for 931 pairs of structurally similar complexes by US-align or Foldseek-Multimer. Both measures correlated highly (Pearson’s r). b, Execution time based on the dataset used for a. Complexes were binned by their number of chains; selected bins are shown (for all bins, see Supplementary Fig. 3). Box plots depict quartiles, each point is a complex pair (top) or complex (bottom), sample sizes are indicated as N, and whiskers are drawn to the maximum (minimum) point within 1.5 times the interquartile range over (under) the 75th (25th) percentile. Pairwise mode (top): Foldseek-Multimer is 10–100 times faster than US-align due to efficient chain-to-chain alignment and superposition clustering. Database search (bottom): complexes were queried against 3DComplexV7. Foldseek-Multimer is further accelerated by its prefilter, making it 10³–10⁴ times faster. c, An AlphaFold-Multimer prediction of a part of a CRISPR–Cas ribonucleoprotein from an environmental sample (top left) was queried by Foldseek-Multimer and US-align against PDB100. Foldseek-MM-TM identified the same hits as US-align, while being >3,000 times faster. These hits were the top ranks by Foldseek-MM (red) with TM score > 0.5. Non-aligned components of 7xg4 (top right) are set as transparent. d, Foldseek-Multimer was run on 57 billion pairs of complexes from 3DComplexV7. It discovered nearly all homomeric pairs previously identified as similar by QSalign, and found an additional 1.7 million homomeric pairs (Supplementary Fig. 5).