New Protein Structure Alignment Tool Finds Distant Relatives Faster Than Ever

Protein structures have become one of biology’s most abundant resources. Thanks to deep-learning systems such as AlphaFold and ESMFold, public databases now hold hundreds of millions of predicted structures, many of them with near-experimental accuracy. That abundance is quietly reshaping how researchers study proteins: instead of comparing amino acid sequences alone, scientists can increasingly compare the three-dimensional shapes that proteins adopt. But shape comparison at scale demands software that is simultaneously fast, sensitive and able to cope with the messy realities of multidomain proteins and flexible conformations. A new tool called LoL-align, described in a Brief Communication in Nature Methods by Lasse Reifenrath, Johannes Söding and colleagues at the Max Planck Institute for Multidisciplinary Sciences and Seoul National University, promises to deliver exactly that combination.

At the heart of LoL-align lies a deceptively simple idea: two residues in different proteins are likely to be homologous if their spatial neighborhoods look alike. The algorithm scores each candidate residue pair by examining the distances between that pair and an established set of aligned anchor pairs. For a candidate pair (j, l), the method compares the intramolecular Cα–Cα distances in the query protein with the corresponding distances in the target protein, within a 20-angstrom neighborhood of the anchor set. Each such comparison yields a log-odds value — the logarithm of the probability that the pair stems from a homologous alignment divided by the probability that it does not — and these values are summed to produce what the authors call the LoL-score. A small neural network with a single hidden layer, trained on positive pairs drawn from the same SCOPe superfamily and negative pairs from different folds, converts raw distance geometry into these probabilities.

The algorithm then works in an iterative loop that gradually grows the alignment from a few trustworthy seeds. It begins with a vectorized forward–backward computation of posterior alignment probabilities based on Foldseek’s 3Di structural alphabet and amino acid substitution scores. From the resulting matrix, the ten aligned seven-mers with the highest summed posterior probabilities are extended along the diagonal, and the three best candidates serve as seed anchors. For each seed, three steps repeat until convergence: the LoL-score matrix is computed from the current anchors, the forward–backward algorithm yields fresh posterior probabilities, and all residue pairs whose probabilities approach the maximum within a small offset are added to the anchor set. The alignment thus expands locally in three-dimensional space, anchoring itself ever more firmly in geometrically consistent residue correspondences.

Two operational modes make LoL-align versatile. In single-domain mode, final scores are normalized by (LQ × LT)^0.25 to improve ranking of compact proteins. In the default multidomain mode, if the anchor expansion stalls, the algorithm folds the 3Di and amino acid score matrices into the LoL-score matrix and reruns the forward–backward computation. This allows the alignment to leap across structural domains that lie far apart in space — outside the 20-angstrom neighborhood of any anchor — and stitch together full-length, multidomain proteins that rigid superposition methods struggle to align. Because many real-world queries are full-length proteins with multiple independently moving domains, this flexibility is arguably the tool’s most consequential design choice.

Speed presented the central engineering challenge, and the team solved it by rewriting the forward–backward algorithm itself. Earlier probabilistic alignment implementations ran unvectorized and in logarithmic space, where costly log and exp operations guard against numerical over- and underflow. LoL-align’s authors reformulated the update equations so the dynamic programming matrices can be processed with SIMD instructions on modern CPUs, computing several values per instruction. They divided the target protein into fixed-length blocks, rescaled each row by its block maximum — with scaling factors stored in log space — and thereby performed all other computations in linear space without numerical instability. An algebraic reformulation of the gap-recurrence, using precomputed constant vectors and a cumulative sum, made the gap-dependent term vectorizable despite its dependence on the immediate left neighbor. A fast C++ implementation reuses a single buffer across forward, backward and posterior passes, and employs branch-free SIMD approximations of logarithm and exponential functions to squeeze out further throughput.

The benchmarking results are striking. On the SCOPe40 single-domain database — 11,211 proteins clustered at 40 percent sequence identity, with 3,566 queries — LoL-align achieved average sensitivity up to the first false positive that was 7.3 percent higher than Dali and 9.9 percent higher than TM-align at the superfamily level. In precision–recall analysis it attained an area under the curve 14.5 percent above Dali and 2.3 percent above TM-align. These gains matter because superfamily-level detection represents remote homology: proteins whose shapes reveal shared ancestry invisible to sequence comparison. In an era when automated annotations must maintain low false discovery rates, ranking more true relatives before the first spurious hit translates directly into more functional insight per search.

Full-length searches against the AlphaFold Database present an even tougher test, and here the team constructed a reference-free benchmark: 2,000 query proteins sampled from the 2.3 million cluster representatives in the clustered AFDB were searched with Foldseek, and the top hits were re-aligned and ranked by each tool. Alignment quality was assessed with an LDDT-based G-score, the geometric mean of residue-wise precision and sensitivity, with alignments scoring below 0.5 classified as false positives. LoL-align proved considerably more sensitive than both Dali and TM-align, and when all alignments were re-ranked by G-score to isolate quality from ranking, LoL-align’s alignments achieved the highest scores. In runtime, it was roughly five times faster than TM-align and twenty times faster than Dali — meaning the sensitivity of the field’s gold standard now comes at a fraction of the cost.

Recognizing that a global similarity score alone cannot always judge whether a local alignment reflects true homology, the team trained a small neural network classifier to predict the probability of a homologous match from local alignment features. The 40-dimensional feature vector draws on alignment scalars such as the LoL-score and LDDT, an aligned-neighbor fraction summarized in histograms over a Cα contact graph, and sequence-separation topology descriptors. Trained with fivefold cross-validation on SCOPe, with folds kept disjoint between training and validation partitions, the classifier achieves calibrated precision levels: on the single-domain benchmark, a LoL-score threshold of 0.65 corresponds to 99 percent precision, 0.60 to 95 percent, and 0.50 to 75 percent. Calibrated probabilities let researchers set error budgets explicitly, a quality rarely offered by traditional alignment scores.

Perhaps the most practical aspect of the release is its integration into Foldseek, the widely used structure search engine that compresses proteins into a 20-state 3Di alphabet for blazingly fast prefiltering. In the combined workflow, Foldseek’s prefilter rapidly narrows hundreds of millions of structures to candidate hits, and LoL-align then refines and re-ranks the top hits with its more accurate probabilistic alignment. The SIMD forward–backward algorithm has also been released separately in MMseqs2 under an MIT license, potentially benefiting probabilistic sequence alignment applications well beyond structure comparison. LoL-align is freely available through the Foldseek web server and the open-source repository, and replacing TM-align with LoL-align inside the multiple-structure alignment tool Foldmason yielded slight improvements as well.

The broader significance extends beyond one software release. The comparison of predicted structures at planetary scale is becoming the successor to BLAST-style sequence searching, enabling evolutionary analyses and functional annotations across protein universes that sequence methods could never reach. LoL-align demonstrates that the classical trade-off between sensitivity and speed is not immutable: by combining a principled probabilistic model of structural homology with clever numerical engineering and hardware-level parallelism, the tool matches or exceeds the sensitivity of the slowest, most careful methods while running at near-prefilter speed. For biologists mining the AlphaFold Database for remote relatives, novel folds and evolutionary signatures, the era of choosing between accuracy and scale may finally be drawing to a close.

Subject of Research: Development and benchmarking of LoL-align, a probabilistic protein structure alignment algorithm

Article Title: LoL-align: sensitive and fast probabilistic protein structure alignment

Article References: LoL-align: sensitive and fast probabilistic protein structure alignment. (n.d.). https://doi.org/10.1038/s41592-026-03249-w

Image Credits: AI Generated

DOI: 10.1038/s41592-026-03249-w

Keywords: protein structure alignment, LoL-align, remote homology detection, AlphaFold Database, Foldseek, forward–backward algorithm, SIMD vectorization, SCOPe benchmark, log-odds score, LDDT G-score, computational biology, Nature Methods