Protein Structure Similarity Search Explained

Structure search is a retrieval problem, not a prediction problem: you have coordinates and you want the entries in a database that look like them. The interesting part is that the fastest current answer works by refusing to do geometry at query time.

Why sequence search misses it

Protein structure is conserved far longer than protein sequence. Two enzymes catalysing the same reaction in organisms separated by a billion years can share almost no detectable sequence similarity while folding into superimposable backbones, because the constraint that survived was on the shape and not on the letters.

That is the entire motivation. Below roughly 25 to 30 percent sequence identity — the region usually called the twilight zone — an alignment score stops being distinguishable from noise, and the statistics described in how BLAST searches correctly report that the hit is not significant. The relationship is real; the sequence evidence for it is gone. Structure search recovers it, and the practical value is functional annotation: for a protein of unknown function whose structure you have, a structural neighbour with a known function is often the only usable lead.

The database side of this changed shape recently. Structure databases used to hold experimentally determined structures numbering in the hundreds of thousands. Large-scale predicted-structure databases moved that to hundreds of millions of entries, which broke every method whose cost per comparison involved a superposition search.

What structural similarity is measured with

Root-mean-square deviation of atomic positions after optimal superposition is the obvious measure and it behaves badly for this purpose. It is dominated by the worst-fitting residues, so a pair of structures with an identical core and one flexible loop in a different position scores poorly. It also has no length normalisation, so an RMSD of 3 ångström means something quite different across 50 residues and across 500.

TM-score was designed to fix both. It sums, over aligned residue pairs, a term that decays with the distance between them, scaled by a length-dependent normalisation, and lies between 0 and 1. Two properties make it the standard. It is dominated by the well-fitting core rather than by outliers, so a mobile loop cannot destroy the score. And the threshold is length-independent by construction: the statistical analysis behind it established that a TM-score above about 0.5 corresponds to two structures sharing the same fold, while scores below about 0.17 are what random unrelated pairs produce. Those two numbers are why TM-score is quoted rather than RMSD.

Computing it requires an alignment between the two structures and a superposition, and both are searched over. That is why the classical methods — matrices of intra-molecular distances compared between structures, or iterative superposition refinement — cost enough per pair that scanning hundreds of millions of entries is not on the table.

Turning structure back into letters

The manoeuvre that made large-scale structure search practical is to discretise local structure into an alphabet, and then run the mature, heavily optimised machinery of sequence search on the resulting strings.

Foldseek, published by Michel van Kempen and colleagues in Nature Biotechnology in 2024, uses a 20-state alphabet its authors call 3Di. The design choice worth understanding is what each letter describes. Earlier structural alphabets encoded backbone geometry — the local torsion angles of a short window of consecutive residues. 3Di instead encodes, for each residue i, the geometric conformation of its interaction with the residue j that is nearest to it in three-dimensional space, which is usually not a sequence neighbour at all.

Two consequences follow, and the paper is explicit about both. Because consecutive 3Di letters describe interactions with different, distant partners, they are much less correlated with each other than backbone-alphabet letters are, so a string of them carries more information per position and produces fewer chance high-scoring alignments. And the information is densest exactly where it should be: in the conserved hydrophobic core, where residues have well-defined tertiary contacts, rather than in surface loops, which is the opposite of how a backbone alphabet distributes its information.

Once a structure is a 20-letter string, everything downstream is sequence search: a substitution matrix over 3Di letters learned from aligned structure pairs, k-mer prefiltering, ungapped extension, then gapped Smith-Waterman — with the amino-acid sequence scored alongside the 3Di string so both signals contribute.

A query, worked through the stages

query: one 250-residue structure (PDB or predicted, with
       per-residue confidence scores)

1. encode      250 residues -> a 250-letter 3Di string
                              + the 250-letter AA string
2. prefilter   ungapped diagonal scoring on shared k-mers;
               the vast majority of database entries are
               eliminated here without alignment
3. align       gapped Smith-Waterman on the surviving
               candidates, scoring 3Di and AA together
4. report      E-value from the alignment score, plus
               optional TM-score computed on the final hits

The important structural feature of that pipeline is where the expensive geometry went: step 1, once per database entry, offline. At query time nothing is superposed. TM-score, if you want it, is computed only on the handful of hits that survive — a rescoring stage, not a search stage. This is the same two-stage shape as embedding retrieval followed by alignment, described in embedding biological sequences for search: a cheap approximate filter, then an exact method on what survives.

What a structural hit does and does not mean

• Predicted structures carry a confidence score, and it matters. Per-residue confidence estimates accompany predicted models, and low-confidence regions are frequently intrinsically disordered — meaning there is no single structure to encode. Their 3Di letters describe an arbitrary conformation the predictor emitted. Masking low-confidence residues before search is not optional hygiene; leaving them in generates hits driven by a shared prediction artefact rather than shared structure.
• Same fold is not same function. Some folds are enormously reused across unrelated functions — the TIM barrel is the standard example, hosting dozens of distinct enzymatic activities. A fold match narrows the hypothesis space; it does not name the function. Evidence that does is catalytic-residue geometry, ligand pockets and conserved motifs within the match.
• Domains, not chains. A multi-domain protein aligned as one chain scores poorly against a database of single domains even when one domain matches perfectly. Splitting the query into domains before searching changes the results substantially, and the split itself is an inference.
• Everything is a hypothesis for experiment. A structural neighbour with a known function suggests an assay to run. It is not evidence that the query protein performs that function, and the annotation transferred this way propagates through databases, which is how a single mis-transferred label ends up in ten thousand genome annotations.