{"paper_id":"0119f928-e473-4b0d-bbed-d5e9e6b5fee9","body_text":"Ultra-fast and highly sensitive protein structure alignment with segment-level \nrepresentations and block-sparse optimization \nThomas Litfin1,a, Yaoqi Zhou1,2, Mark von Itzstein1 \n1Institute for Biomedicine and Glycomics, Griffith University, Gold Coast Campus, Southport, QLD 4222, Australia \n2Institute of Systems and Physical Biology, Shenzhen Bay Laboratory, Shenzhen, 518107, China \naFor correspondence, please email to Dr Thomas Litfin (t.litfin@griffith.edu.au) \nAbstract \nDeep learning models for protein structure prediction have given rise to extreme growth in 3D structure data. As a result, \ntraditional methods for geometric structure alignment are too slow to effectively search modern structure libraries. In \nthis study we introduce SPfast – a fully geometric method for structure-based alignment which accelerates search by \nmore than 2 orders of magnitude while increasing sensitivity by 21% and 5% compared with foldseek and TMalign \nrespectively. Using the significant speed of SPfast to conduct more than 100B pairwise comparisons between bona fide \nuncharacterized proteins and a large-scale, annotated structure library uncovers new biological insights relating to type \nIII secretion in pathogenic bacteria and identifies novel toxin-antitoxin systems. Putative SPfast-based functional \nassignments are supported by orthogonal evidence including shared genomic context and high-confidence AlphaFold3 \ncomplex modelling. \nIntroduction \nThe protein function annotation pipeline relies on propagating experimentally validated annotations across closely \nrelated proteins. Historically, sequence profile alignment  has been the gold -standard for identifying evolutionary \nrelationships which suggest a shared functional role1. Sequence-based alignment is well suited to high-throughput search \ndue to the extreme speed of the underlying algorithm – particularly when using heuristic approximations as implemented \nin methods such as BLAST2, HMMER33 and MMSeqs24. However, sequence similarity has limited sensitivity to detect \nfunctional relationships over great evolutionary distances leading to a large number of spurious ‘orphan’ genes without \nfunctional annotations5.  \nThe AlphaFold protein structure database (AFDB)6 provides high quality model structures for more than 200M reference \nproteins catalogued in the UniProt 7 database and the ESM metagenomic atlas 8 contains an additional 772M structures \npredicted from metagenome sequencing projects. These large-scale protein structure libraries represent an opportunity \nto enhance the sensitivity of homology -based annotation using structure-based search. Prior works in this space have \nused highly sensitive geometric search to identify functional clues from the relatively small, PDB database 9 or have \nsacrificed sensitivity by using tokenized structure alignments  to search large model libraries 10–12. Here we have \ndeveloped new heuristics to enable practical high-throughput search using highly sensitive geometric alignments to \nenhance the quality of structure-based annotations. \nTraditional approaches for geometric structure alignment utilize an iterative closest point  (ICP) heuristic to identify \npaired correspondences between matched amino acids 13–16. This heuristic involves an iterating process that alternates \nbetween superimposing structures, identifying an alignment and then updating the superposition to minimize root mean \nsquare deviation (RMSD) between aligned residues. However, alignments generated by the ICP algorithm are extremely \nsensitive to initial superpositions with early methods requiring manual assignment of matching residues to initialize a \nconvergent alignment13. Modern methods provide an automated solution but rely on brute force enumeration of potential \nseeds derived primarily from contiguous peptide fragments14–16. In the worst case, this strategy generates a candidate set \nof initial alignments that scales quadratically with protein length  (although many potential seeds are pruned based on \nfragment RMSD in practice). Similarly, the evaluation of each candidate alignment utilizes the intermolecular distance \nmatrix as input to  the Needleman-Wunch17 algorithm which also has nested quadratic complexity. While traditional \ntools such as TMalign14/USalign16 and SPalign15 have successfully leveraged this paradigm for pairwise alignment and \nPDB search, they cannot scale to handle the newfound abundance of predicted protein structure data. \nA recently developed method, foldseek18, has been designed to alleviate  the computational burden by representing \nproteins with a n SE3-invariant structure-state alphabet and utilizing sequence -based acceleration heuristics in a one -\npass alignment afforde d by the MMSeqs2 framework 4. Foldseek leverages a  structure-state substitution matrix to \ncharacterize structural similarity and a k-mer based alignment prefilter coupled with highly optimized single instruction, \nmultiple data (SIMD) intrinsics to accelerate database search. These heuristics facilitate lightning-fast execution times \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint \n\nwhich enable practical search of large model databases.  However, the acceleration is accompanied by a substantial \nreduction in  search sensitivity – particularly when invoking the database prefilter – which may be prohibitive for \napplications that rely on exhaustive search. \nIn this work, we introduce SPfast – a significantly accelerated, fully geometric method for protein structure alignment \nthat achieves state of the art search sensitivity with efficiency that can support high -throughput search. In SPfast we \nreplace the traditional, Cα-based structure representation with idealized key points extracted from secondary structure \nsegments. This coarse-grained, segment-level representation is used to generate a minimal set of alignment seeds  by \nsuperimposing compatible pairs of idealized fragments . Candidate seeds are  evaluated based on a segment-level \nalignment score which is used to screen potential structure matches.  The top-ranking seed is finally used to guide  a \nblock-sparse, all-atom refinement of the pairwise alignment objective  to produce a residue -level alignment . These \nheuristics are combined to increase the speed of geometric alignments by 2 orders of magnitude and up to 3 orders of \nmagnitude when combined with a foldseek-based prefilter.  \nResults \n \nFigure 1 (A) Mean sensitivity at the first false positive (F P) for SCOPe domains at the fold, superfamily and family level and \ncorresponding execution time for 11,211 x 11,211 all-by-all comparisons on an Intel Xeon E5-2670 @ 2.60GHz 16-core CPU. (B) \nProportion of multi-domain AFDB proteins for which another protein with a single domain overlap can be identified in the top -k \nranks. (C) Superfamily-level sensitivity at the first FP for synthetic SCOPe domains generated by RFdiffusion partial denoising (10 \nsteps) and searched against natural SCOPe domains. \nFold recognition of annotated SCOPe domains \nDomain-level search sensitivity was evaluated by conducting an all-against-all comparison of 11,211 domains from the \nSCOPe dataset 19 and ranking structures based on  pairwise alignment scores using each method  (Figure 1A). Of the \nexisting methods in the literature, ranking structures based on an exhaustive optimization of SPscore (SPalign) achieved \nthe highest mean sensitivity at first false positive across all 3 levels of the protein structure hierarchy (0.590 at the \nsuperfamily level). However, SPalign is impractical for use at scale – requiring 66.5 hours to complete  the SCOPe \nbenchmark. By comparison foldseek completed the benchmark in only 3.5 minutes on the same hardware – albeit at a \nconsiderable drop in search sensitivity (0.487). We found that the sensitivity of SPfast was equivalent to SPalign at the \nsuperfamily level (0.590) , and superior to all other methods (including TMalign with sensitivity of 0.562), while \ncompleting the benchmark in just 37.3 minutes. SPfast r e-ranking of structures identified by the foldseek prefilter  \n(foldseekSP) was found to recover most of the performance of SPfast alone ( 0.557) and completed the benchmark in \nonly 8.25 minutes (compared with just under 2 hours for foldseekTM to achieve sensitivity of 0.548). \nThe optimization of SPfast alignment heuristics  offered a continuous trade -off between search sensitivity and \nthroughput. To investigate this trade-off, we evaluated the performance of SPfast by optimizing an SPscore objective \nand varying individual heuristic parameters (Supplementary Figure S1). The secondary structure prefilter had the largest \nimpact on method performance. However, even the most stringent filtering criterion maintained superior sensitivity to \nfoldseek (0.524 superfamily -level sensitivity at first false positive) and reduced SPfast execution time to just 17.5 \nminutes. Relaxing the ICP convergence criterion to 9% had an extremely mild impact on search sensitivity (0.567 c.f. \n0.568 for the default 5%) and trimmed execution time to 35.8 minutes. Similarly, a segment-level alignment score cutoff \nof 5.5 reduced execution time to 29.4 minutes while maintaining sensitivity of 0.565. Default options maintain a balance \nbetween execution speed and search sensitivity but can be tuned for specific applications as required. \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint \n\nDomain recognition in multi-domain proteins \nTo investigate multi-domain search sensitivity, a benchmark dataset of AFDB6 multi-domain structures was assigned \nSCOPe fold classifications using SPfast. We evaluated the ability of each search method to identify multidomain partner \nproteins with a single overlapping domain (Figure 1B). The local alignment methods could retrieve partially overlapping \npairs with 71.9%, 77.0% and 69.6% recall at the top-1 rank for SPalign, SPfast and foldseek (-e inf --max-seqs 200) \nrespectively. Performance rose to 91.8%, 93.2% and 80.8% when considering matches within the top-25 structures. In \nthis setting, there was a small benefit to SPfast re -ranking of the top 200 foldseek hits (foldseekSP) leading to a top -1 \nrecall of 71.0% and top-25 recall of 81.7% respectively. The global alignment method, TMalign, was almost completely \nunable to recover partial structure matches, and identified only 42.9% of matched structures at the top-1 rank. \nSurprisingly, SPscore optimization with SPalign underperformed SPfast in this benchmark due to systematic differences \nbetween experimental structures and predicted models. AFDB models contain  isolated non-globular regions (often \nflexible, disordered loops predicted with low confidence) which can lead to disproportionately high scores between un-\nrelated structures when using a local alignment normalization strategy. Foldseek combats this problem by masking low \ncomplexity regions. Similarly, in SPfast,  isolated residues are trimmed to avoid low-complexity regions based on the \nnumber of non -local neighbour residues . While a few low -complexity matches pollute the top ranks  using SPalign, \nperformance parity with SPfast is mostly restored when considering recall of partner proteins in the top-25 structures. \nFold recognition of designed proteins \nCurrent methods for de novo protein design generate backbone coordinates before assigning compatible amino acid \nsequences in a two-stage design process20. Here we evaluated the sensitivity of various structure-search methods using \nsynthetic query structures designed by RFdiffusion to mimic SCOPe domain topologies without a corresponding amino \nacid sequence. The original foldseek (-s 9.5 --max-seqs 2000 -e 10 --comp-bias-corr 0 --mask 0 --alignment-type 0) \nscoring function was not optimized for backbone structure search and perform ed poorly in the absence of amino acid \nidentities (median sensitivity of 0.273) . In 2023, the foldseek scoring function was re -optimized for backbone -only \nstructures leading to a dramatic performance improvement. However, the median sensitivity of foldseek-2023 (0.500) \nstill falls far short of SPalign (0.643) and SPfast (0.667). Similarly, when we re-rank the top foldseek hits with SPfast \n(foldseekSP) the median sensitivity is significantly improved to 0.625. \nWe investigated the impact of increasing the degree of distortion introduced by the noising/denoising steps during the \ndesign process (Supplementary Figure S2).  Performance for all methods was degraded by increasing the number of \nnoise steps – likely reflecting the fact that the original SCOPe labels were not always appropriate for the sampled \nsynthetic structures in the high -noise regime. Surprisingly, foldseek performance slightly improved in the low -noise \nregime compared with natural structures and may benefit from idealised synthetic motifs which are more closely aligned \nwith the 3Di state alphabet. Threading  the parent sequence on to the designed structures also improved foldseek \nperformance at the family and superfamily level but was found to decrease sensitivity at the fold level. Similarly , \nsequence information appeared to buffer the degradation of performance with increasing noise which may be \nproblematic if designed proteins have adversarial inconsistency between sequence and structure representations. \nHOMSTRAD alignment accuracy \nWe also evaluated the ability of each method to re produce manually curated alignments from the HOMSTRAD 21 \ndatabase (Figure 2A). SPscore optimization was found to provide more accurate alignments than those pr oduced by \nfoldseek. However, TMalign was found to produce the most accurate alignments of all previously available methods. \nBy default, SPscore was designed to operate with no penalty for alignment gaps which le d to the inclusion of several \nisolated pairs which are unlikely to be representative of a true evolutionary relationship (Figure 2D). Introducing a gap \nopen penalty of up to 0.5 (consistent with TM align) dramatically improved alignment accuracy by eliminating  these \nisolated pairs. However, improved alignment accuracy was accompanied by a small drop in search sensitivity as high-\nquality local matches  (SCOPe false positives)  out-ranked lower fidelity, domain-level hits (SCOPe true positives) . \nSPscore-based methods relied on the extraneous matchings to dramatically increase the effective normalization length \nand partially suppress the score of high-fidelity alignments with low coverage. \nTo overcome the trade-off between alignment accuracy and search sensitivity, we re-optimized SPscore parameters (d0, \ngap_open penalty and α) to control the balance between alignment coverage and fidelity. We f ound that this score re-\nparameterization significantly improved performance of both alignment accuracy and search sensitivity such that SPfast \nwas equally sensitive  with the original SPalign  while also improving alignment accuracy and  maintaining a >100x \nincreased throughput. Combining the SPfast-optimized parameters with the original SPalign optimization algorithm also \nimproved the performance of SPalign to achieve a new state -of-the-art performance for both HOMSTRAD alignment \naccuracy and SCOPe search sensitivity (Figure 2A). \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint \n\n \nFigure 2 (A) Performance comparison of search sensitivity (SCOPe superfamily -level) and alignment accuracy  while varying \nSPscore gap open penalty. (B) Pairwise alignment compression of top-ranking hits from AFDB clusters averaged over 100 random \nqueries. The random baseline represents the average compression using an all -against-all comparison of the 100 queries. (C) \nProportion of AFDB hits (define d by an SPscore cutoff) identified in the top -ranking structures by foldseek ( --exhaustive-search). \nThe solid horizontal lines indicate the results when using the foldseek prefilter at the indicated number of maximum sequences (40-\n40,000). (D) SPfast alignment between d1a5ta2 (color) and d1vg5a_ (gray) as representatives of different SCOPe folds with spurious \naligned residues indicated. (E) Structure hits identified by SPfast but not found within the top 40,000 structures identified with the \nfoldseek prefilter (upper) A0A4 V0HUP4 – G8RV33 (rank: 203)  and (lower) A0A7C1N324 – A0A7C3KYU8 (rank: 5) . (F) \nStructure pairs identified by SPfast but not identified in the top 40,000 hits after exhaustive foldseek search. (upper) A0A832BBQ6 \n– A0A485P0T7 (rank: 102) and (lower) A0A3S3QK05 – A0A4P6JIK1 (rank: 507). Structures are trimmed to the aligned regions \nfor visual clarity. \nAFDB-clusters search sensitivity \nTo evaluate performance on a large predicted structure database we randomly  selected 100 model structures from the \nAFDB-clusters10 dataset. These structures were searched against the full set of 2.3M AFDB-cluster representatives. In \nthe absence of curated structural classifications, we used an objective, reference-free evaluation based on the degree of \ninformation compression afforded by pairwise structure alignments of top-ranked hits22. The very top-ranked foldseek \ncandidates were found to have comparable quality to the top-ranked candidates proposed by SPfast (consistent with the \nfamily-level evaluation in the SCOPe benchmark) . However,  SPfast showed a sustained advantage  in average \ncompression for each position across the first 1000 ranks. Running foldseek with a permissive prefilter (fast: --max-seqs \n40000 -e inf) was greatly improved by disabling the prefilter entirely (opt: --exhaustive-search) but was still unable to \nmatch the performance of SPfast (Figure 2B). SPfast search using the original SPscore parameters also provided a small \nimprovement over foldseek in exhaustive mode (Supplementary Figure S3). Notably, the quality of retrieved structures \nby all methods was significantly above random pairs, indicating the presence of shared structural motifs even beyond \nthe 1000th rank.  \nWe also investigated the potential to utilize foldseek to prefilter AFDB-clusters database prior to SPfast re-ranking. On \naverage, 80% of extreme high -quality SPfast hits (SPscore > 0.9) c ould be identified within the first 400 structures \nranked by foldseek bit score (Figure 2C). However, the remaining high-quality hits were not able to be identified even \nwithin the first 40,000 structures due to the nature of the k-mer based prefilter. We have highlighted several examples \nof top-ranking SPfast structure matches which were not identified by foldseek in the first 40,000 ranks (Figure 2E). For \nexample, A0A4V0HUP4 is characteristic of a β-propeller domain with clear visual similarity to G8RV33 (rank 203 by \nSPfast). However, when using A0A4VHUP4 as a query, G8RV33 does not pass the foldseek prefilter and is not \nidentified as a structural match. When disabling the prefilter with exhaustive search, similarity is identified and G8RV33 \nis recovered at rank 512. We have also highlighted a few examples of SPfast hits that were not identified by foldseek \neven in exhaustive mode (Figure 2F). These pairs display clear geometric similarity despite being poorly ranked by \nfoldseek. \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint \n\n \nFigure 3 Characteristic example (A0A6V8F1I9) demonstrating the benefit of global topology compared with local structure \nalphabet. (A) Pairwise alignment compression of top -ranking hits from AFDB -clusters for A0A6V8F1I9 query  (left) and \naccumulated compression advantage of SPfast -opt over foldseek -exhaustive (right) . (B) A0A6V8F1I9 structure and segment \ndiagram. (C) Structure and segment diagram of A0A3D1EE05 (D) Structure and segment diagram of A0A017TCA9. (E) foldseek \n3Di encoding and alignment of helical segments from A0A6V8F1I9 and A0A017TCA9. \nFinally, we highlight an example query (A0A6V8F1I9) to demonstrate the advantage of the global geometric approach \nemployed by SPfast compared with the local structure alphabet employed by foldseek (Figure 3). A0A6V8F1I9 contains \na repeated ββα structural motif where the helices rest on top of a  conserved β-sheet. Based on the local structural \nneighbourhood, A0A017TCA9 contains the same segment sequence as A0A6V8F1I9 but arranged with a distinct global \ntopology. Due to the compatible structural alphabet states (Figure 3E), foldseek ranks A0A017TCA9 highly (rank 386) \nat the expense of true geometric matches (eg A0A3D1EE05 – rank 2,232) which are correctly identified by SPfast (rank \n10). In this example, global geometric information is critical to discriminate true structure matches from structure-state \ndecoys. \nAFDB dark clusters annotation \nTo demonstrate the potential utility of SPfast for highly sensitive annotation of protein functions, we extracted 46,826 \nhigh-quality (pLDDT>90) ‘dark’ clusters from the AFDB-clusters database. We used SPfast to search these \nuncharacterized proteins against the set of 2.3M AFDB-clusters representatives (more than 100B pairwise comparisons). \nUsing SPfast, 21.6% of the dark clusters could be mapped to a high -complexity PFAM clan23. Using a foldseek cutoff \nof log 100.5, 35.1% of the annotated proteins shared at least 1 PFAM clan annotation in agreement with SPfast. An \nadditional 35.3% of the structures were uniquely annotated by SPfast while only 18.5% were uniquely annotated by \nfoldseek – highlighting the complementarity of the 2 methods. The remaining 11.1% of proteins were annotated by both \nmethods but with conflicting disjoint clan labels (Figure 4A).  In addition, for each annotated protein, SPfast can \nrecognize structural similarity to a larger number of PFAM clans. \nAs an example, the uncharacterized cluster, A0A0U5EPG3, is represented primarily by structures extracted from \ngenomes in the chlamydiota phylum. This cluster demonstrated structural similarity to members of several PFAM clans \n(FliG, YscK, OrgA_MxiK, T3SS_LEE_assoc)  which all have functions related to a type III secretion system (T3SS) \nadaptor protein responsible for connecting the sorting complex to the M ring 24. These families correspond to the SctK \ngene under the unified T3SS nomenclature25 (Figure 4B). However, the corresponding gene in chlamydiota has not been \npreviously reported despite several recent reviews 26,27. T3SS is prevalent in pathogenic gram -negative bacteria and \ncomponents are often found clustered in  conserved genomic islands. A0A0U5EPG3 in Candidatus Protochlamydia \nnaegleriophila is flanked by the SctJ and SctL genes which is consistent with the genomic context of the SctK gene in \nphyla where it has been annotated (Figure 4C). The combination of molecular and syntenic similarity provides \northogonal support for a shared functional role of the uncharacterized proteins in the A0A0U5EPG3 cluster with the \nwell-characterized T3SS SctK gene. Furthermore, AlphaFold3  (AF3) predicts a high -confidence ternary structure \nbetween A0A0U5EPG3, the second for khead association (FHA2) domain of the inner membrane ring protein (SctD) \nand the N-terminal domain of the cytosolic sorting platform (SctQ), consistent with the reported role of the SctK gene \nin other organisms28. Interestingly, in the AF3 model, the SctQ-A0A0U5EPG3 interface is mediated by the C-terminal \nlobe which is unique to the chlamydiota phylum. \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint \n\n \nFigure 4 (A) Number of uncharacterized proteins from AFDB -clusters (pLDDT>90) that could be mapped to proteins with PFAM \nannotations based on structural similarity and the number of corresponding PFAM clan annotations. (B) Structure of uncharacterized \nprotein A0A0U5EPG3 compared with A0A2Y0G0F7 which is annotated as a member of the Type III secretion system (SctK). (C) \nSctJKL genomic island in Candidatus Protochlamydia naegleriophila (CPN: GCF_001499655.1), Pseudomonas aeruginosa PA01 \n(PA: GCA_000006765.1) , Pseudomonas syringae  (PS: GCA_041154885.1) , Salmonella enterica  (SE: GCA_019026085.1) , \nShigella flexneri (SF: GCA_003719775.1), Yersinia pestis (YP: GCA_003798345.1) assemblies. (D) Structure of uncharacterized \nprotein A0A0F2PPL2 compared with A0A846TBU3 which is annotated as a Type II toxin. (E) Representative genomic context of \nstructures from the A0A0F2PPL2 cluster including those from  Gardnerella vaginalis (GV: GCA_001546485.1), Fusobacterium \nnecrophorum BFTR-2 (FN: GCA_000691725.1), Bacillus thuringiensis serovar mexicanensis  (BT: GCA_002146325.1), Bacillus \ncereus (BC: GCA_002560615.1), Peptococcaceae bacterium BRH_c4b (PB: GCA_000961595.1), Clostridiaceae bacterium (CB: \nGCA_003485415.1) assemblies. \nSimilarly, A0A0F2PPL2 from Peptococcaceae bacterium BRH_c4b  is representative of a cluster of uncharacterized \nproteins dominated by members from Bacillota genomes. SPfast identifies A0A846TBU3 as the top structural match \nwhich is annotated as a Type II toxin from the MqsR 29 family (Figure 4D). Inspecting the genomic context of the \nA0A0F2PPL2 cluster reveals that almost every member can be found immediately adjacent to a MqsA-Panacea30 \nantitoxin protein (Figure 4E). Based on the A F3 model complex, the Zn 2+-binding domain forms a high -confidence \ninterface with the putative toxin, providing additional support for a toxin-antitoxin functional assignment. Furthermore, \nA0A0F2PPL2 contains a conserved Tyrosine (Y109) in the putative RNA-binding groove which has been identified as \na critical catalytic residue in the B. fungorum MsqR endoribonuclease toxin30 adding further evidence to suggest a shared \nfunctional role. \nDiscussion \nSince the release of AlphaFold231, the number of protein structures available in public databases6,8 has been increased \nby three orders of magnitude compared with what was previously available in the PDB 32. Similarly, the emergence of \nnew predictive models for de novo design20, increased availability of dynamic trajectories33 and alternative models for \nstructure prediction34,35 will continue to drive a surge in protein structure data. This sustained data influx motivates the \ndevelopment of new bioinformatic tools that can scale to meet the rising demand.  In this work we have introduced a \nnew method for geometric structure comparison (SPfast) which achieves state of the art search sensitivity and improves \nalignment accuracy over a range of performance benchmarks. While we do not achieve the same speed as the tokenized \nalignment implemented in foldseek, we argue that the speed of SPfast is sufficient for practical use – particularly for \napplications that prioritize high sensitivity search such as supporting biological experiments which are conducted over \nlong timeframes. \nCompared with traditional methods, SPfast achieves remarkable acceleration by 1) superimposing only a minimal set \nof structure fragments  to define alignment seeds  2) filtering candidate structures with an efficient segment -level \nalignment and 3) using the segment -level alignment as a constraint to produce a block -sparse distance matrix. On \naverage, segment-guided superpositions are better quality than those produced by arbitrary contiguous fragments and \nbetter facilitate the discrimination of structural similarity at early stages of the alignment. Similarly, unlike tokenized \nsubstitution matrices, which create dense score matrices, geometric matches are necessarily unique since atomic \ncoordinates from the same protein cannot be overlapping. As a result , the segment-level constraints greatly reduce the \ntime required to compute all-residue distances matrices which are re-evaluated many times during ICP optimization.  \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint \n\nIn extremely rare cases, the minimal set of segment-guided seeds do not produce a high-quality superposition which \ndegrades the quality of the final alignment. As future work, we are exploring options to refine the set of seed comparisons \n(eg by utilizing a segment-level 3di state rather than simplistic secondary structures) which may further improve both \nsensitivity and computational efficiency. Similarly, we are investigating options to rescue poor initial superpositions by \nbetter sampling candidate alignments (eg by using pre-computed neighbour graphs to explore alternative matchings). \nFinally, t he current SPfast implementation does not take advantage of SIMD intrinsics to vectorize alignment and \nsuperposition (as implemented in foldseek). While SIMD operations can be of limited value for sparse data, the block-\nsparse nature of the SPfast algorithm would facilitate efficiency gains enabled by SIMD operations.  These proposed \nrefinements represent several viable strategies for further acceleration and improved sensitivity. \nAs a proof of principle, we have used SPfast to identify candidate annotations for a large database of ‘dark’ proteins \nwhich lack existing functional information. From this dataset, w e have highlighted two examples of SPfast-based \nannotations which are supported by independent in silico  evidence. The identification of a putative SctK gene in \nChlamydiota provides new insights into a major virulence factor responsible for modulating host cell biology in a highly \nrelevant human pathogen. Similarly, the annotation of new bacterial toxins sheds light on key cellular regulators. These \nputative annotations are strongly supported by synteny relationships and high confidence AlphaFold3 interactions. \nHowever, these examples are by no means comprehensive . For example, the dataset is also enriched with annotations \nof endonucleases with HTH domains and key conserved catalytic residues, and putative metalloproteases with HEXXH \nmotifs supporting the SPfast-based assignments. Finally, numerous structural relationships have also been identified by \nSPfast with no clear way to support the resulting functional assignments in silico. \nMethods \nSecondary structure assignment \nSecondary structure states are assigned based on the union of the permissive Cα-distance-based definition currently \nutilized by TMalign 14/SPalign15 as well as the DSSP definition based on electrostatic interactions 36. Protein structure \nmodels utilize the DSSP definition only (without Cα-based definition) to avoid an artifact which causes long disordered \nloops to be classified as strands. Segment breaks are introduced at residues classified as geometric turns by DSSP to \nmaintain equivalence between secondary structure segments of the same  type (ie long twisted beta strands are not \ngeometrically comparable to short straight strands). We enforce a minimum segment length of 6 for helices and 3 for \nstrands, as shorter segme nts appear to be less evolutionarily conserved and can obscure seed matches between \ncontiguous segments. \nSecondary structure prefilter \nTo reduce the total number of required comparisons during SCOPe database search, we prefilter the library to avoid \naligning proteins from clearly un-related protein classes. We utilize a sequential representation of secondary structure \nsegments by assigning helix and sheet labels to corresponding fragments. Structures are aligned based on the resulting \nsegment-state sequence and further processed if the alignment score reaches a critical score threshold. Structures that \ndo not pass the preliminary prefilter  are removed from the comparison set.  This prefilter was used for single domain \ndatasets (such as SCOPe) whereby the alignment score can be normalized by the total number of segments in the \nstructures. \nRepresentative key-point generation  \nWe reduce the all -residue representation of protein structure to a sequence of secondary structure segments. To \ncompensate for the varied segments lengths, we extract 3 representative key-points including the centroid and two \nterminal residues. Pseudo-atom coordinates are idealized by projecting true atomic coordinates on to the first principal \ncomponent of each segment to minimize the contribution of residue periodicity.  \nAlignment score \nIn this work, we use the SPscore alignment objective reported previously15. \n𝑆𝑃𝑠𝑐𝑜𝑟𝑒  =   1\n𝑆𝐹\n1\n𝐿𝑒𝑓𝑓\n1−𝛼\n[\n \n \n \n \n∑\n(\n \n 1\n1 + 𝑑𝑖𝑗\n2\n𝑑0\n2\n− 0.2\n)\n \n \n \n𝑑𝑖𝑗<2𝑑0\n]\n \n \n \n \n \nWhere dij is the distance between Cα atoms of aligned residues and d0 and α are free parameters optimized in prior work. \nSPscore is normalized by an effective length (Leff) which is dependent on the residue-level alignment. Core align ed \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint \n\nresidues are defined by correspondences with pairwise distances <2d 0. Leff is defined by the number of core residues \ncombined with the average number of neighbouring residues within a 3d0 window. SF is a purely cosmetic scaling factor \nwhich ensures that the typical fold discrimination cutoff falls approximately in a familiar range around 0.5. The coarse-\ngrained, segment-level alignment optimizes an objective with the same form as SPscore but averaged over the three \nrepresentative pseudo-atoms.  \nOptimization algorithm \nWe initially superimpose sets of 3 contiguous segments (3Segs) extracted from parent structures and prune seed \nsuperpositions with local fragment RMSD greater than a critical threshold. Successful seeds are extended to evaluate \ndomain-level similarity using a coarse-grained, segment-level alignment optimizing the SPscore objective (Figure 3B). \nSubsequently, the process is repeated with all possible combinations of 2Segs where the 2Seg definition is extended to \ninclude skip-pairs (ie pairs that are separated by an interloping segment). To minimize redundant evaluatio ns, 3Segs \nthat pass the initial quality filter are decomposed into the set of possible 2segs and excluded from re-analysis. Based on \nthe segment-level similarity score, the optimum seed is selected to generate residue-level correspondences. A block -\nsparse Smith-Waterman alignment is employed to identify a residue -level alignment constrained by initial segment \nmatchings (Figure 3C). A final iterative refinement stage is conducted which involves evaluating potential alignment \npairs in a 5-residue window around the preliminary alignment (Fig ure 3 D). Superpositions are updated based on \ncandidate alignments at each iteration.  After convergence, f inal alignments are conducted  with a default gap open \npenalty of 0.2. \n \nFigure 5 Pairwise alignment between d1w96a2 and d1a9xa3 SCOPe domains (A) d1a9xa3 domain with idealized segment -level \nkeypoints. (B) A  3seg seed pair is used to superimpose the structures and produce an SPscore pairwise distance matrix between \nrepresentative pseudo-atom coordinates. This score matrix is used to generate a segment -level sequence alignment . (C) A block-\nsparse all-atom distance matrix is constructed and constrained by  the initial segment -level alignment. ( D) A final all -residue \nrefinement is conducted by exploring a local window of size 5 around the preliminary alignment.  \nSCOPe benchmark \nWe evaluate SPfast in the SCOPe benchmark reported previously for the evaluation of foldseek18. Briefly, we generate \nall-against-all alignments between 11,211 non-redundant SCOPe domains with curated fold annotations. For each query, \nthe remaining structures are ranked, and methods are evaluated based on their ability to recover proteins with the same \nstructural classification at all 3 levels of the hierarchy (fold, superfamily, family).  Performance is evaluated based on \nthe sensitivity at the first-ranked false positive. \nMulti-domain benchmark \nWe collected representative structures from the AFDB-clusters dataset 10 and conducted structure search against the \nSCOPe domains to assign SCOPe fold classifications based on SPfast structural similarity (SP>0.55, Leff>100, Lafdb > \n1.2 x LSCOPe). We retained AFDB structures that could be assigned multiple structurally distinct SCOPe domains where \nstructural similarity between domain archetypes was determined by SPalign (SP<0.45 between each assigned domain). \nFinally, we randomly selected two multi-domain AFDB structures for each qualifying SCOPe domain. We searched \neach structure against the complete dataset and evaluated performance based on the rank of the assigned partner for each \ndomain. Structures that incidentally contained the same SCOPe classification (SP>0.45 to shared domain) but were not \nin the assigned pair were excluded during the evaluation. \nDesigned protein benchmark  \nTo generate diverse synthetic structures, we noised and de-noised SCOPe domains using the partial diffusion protocol \nfrom RFdiffusion20,37. We applied noise for 10 steps and then denoised the resulting distorted structure to produce a \ndistinct, backbone-only approximation for each of the representative SCOPe domains. It was assumed that synthetic \ndomains would have the same fold classification as the parent structure . Synthetic domains were used to search the \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint \n\nSCOPe database of natural proteins and performance was evaluated at the superfamily level based on the sensitivity at \nthe first false positive. \nHOMSTRAD alignment benchmark \nThe HOMSTRAD alignment benchmark21 includes manually curated alignments for 1032 protein families. We \nreproduced the alignment pairs used to evaluate foldseek by extracting the first and last family member from the \n2022_Aug_1 release. Note that there is a slight difference between structures used in this work and those reported \npreviously18 since the HOMSTRAD dataset is no longer publicly available and was reproduced from best efforts. \nAlignment performance was evaluated based on F1 score (harmonic mean of precision and recall) by comparing the set \nof alignment correspondences with the  correspondences from the gold-standard reference alignments  \n(https://wwwuser.gwdg.de/~compbiol/foldseek/). \nAFDB-clusters database \nTo evaluate search performance on a large model dataset, we collected ~2.3M representative structures from the AFDB-\nclusters10 database ( https://afdb-cluster.steineggerlab.workers.dev/). Structure coordinates were extracted from the \ncompressed foldcomp38 repository and then pre-processed to extract idealized secondary structure segments identified \nby DSSP. AFDB model structures contain regions of long extended loops predicted with low confidence which are \nlikely to be intrinsically disordered. To gracefully handle these cases, we trimmed the structures to remove non-compact \nregions based on the number of non -local (i -j>8) contacts (distance<12Å). This procedure  is similar to the low \ncomplexity masking employed by foldseek but has the added benefit of reducing the effective protein length to facilitate \nfurther accelerated search. \nAlignment compression \nWe used MMLigner22 to quantify the maximum degree of compression afforded by pairwise structural alignments as a \nreference-free evaluation of search sensitivity in the AFDB-clusters benchmark. Briefly, a Kent mixture model was used \nto encode internal pseudo-angles as a null model of independent protein structures. Theoretical compression was defined \nas the information saved by encoding structures jointly conditioned on the pairwise alignment  compared with the null \nmodel. Compression at each rank was smoothed by averaging in a window of 10 to aid visual clarity  in the figure  \n(window of 100 for A0A6V8F1I9 case study). \nFoldseek \nFor consistency, unless otherwise stated we use the foldseek commit (aeb5e) and commands as reported in the original \nmanuscript. Only time taken for the ‘prefilter’, ‘structurealign’ and ‘tmalign’  operations were considered when \nevaluating foldseek-based execution time. Commit ef4e9 was used to evaluate backbone only search (--comp-bias-corr \n0 --mask 0 --alignment-type 0). \nFoldseek prefilter \nFoldseekTM was developed to improve the sensitivity of foldseek  by re -ranking top scoring candidates with an \noptimized version of TMalign. In this work, we extend this idea to produce foldseekSP which pre-filters candidate pairs \nusing foldseek before re-ranking structures by SPfast alignment. \nTMalign \nTMalign was downloaded from https://zhanggroup.org/TM-align/TMalign.cpp using the version updated on \n2022/04/12. Consistent with prior work18, alignments were ranked by average TMscore using both the shorter and longer \nprotein lengths. We found that this strategy produced the best results in the SCOPe benchmark. \nAFDB dark clusters \nWe extracted high-quality (pLDDT>90) ‘dark’ clusters from the AFDB-clusters dataset which could not be mapped to \nPFAM domains. ‘Dark’ clusters were searched against the entire AFDB -clusters dataset with SPfast. Foldseek search \nresults were downloaded from https://afdb-cluster.steineggerlab.workers.dev/. PFAM annotations were assigned to dark \nclusters using high-scoring alignments with annotated cluster representatives. Structure matches were filtered based on \nsecondary structure complexity such that alignments between α -domains contained at least 6 aligned segments and \nalignments with β/mixed -domains contained at least 5 aligned segments. Annotations were transferred to the query \nstructure if aligned residues covered at least 70% of the PFAM domain from the reference structure.  \nGenomic context \nGenomic context was extracted using a modified version of GCsnap39. Briefly, UniProt IDs were mapped to GenkBank \nCDS ID using the UniProt id-mapping api. The GenBank ID was mapped to a GenBank assembly and the target protein \ngenomic context was extracted using the NCBI Entrez api. \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint \n\nAlphaFold3 structure prediction \nComplex structures were predicted using the AlphaFold3 web server ( https://alphafoldserver.com/). Full length \nsequences were trimmed to the expected interacting domains for visual clarity and to isolate direct interactions in the \npredicted aligned error (PAE) plot. \nData availability \nPre-computed benchmark data is made available at https://github.com/tlitfin/SPfast. The SPfast source code (including \na PyMOL plugin and demonstrative colab notebook) is available from https://github.com/tlitfin/SPfast. \nAcknowledgement \nWe gratefully acknowledge the support of the Griffith University eResearch Service & Specialised Platforms Team and \nthe use of the High-Performance Computing Cluster \"Gowonda\" to complete this research. TL is supported by a Griffith \nUniversity Postgraduate Fellowship. MvI is supported by the National Health and Medical Research Council, Australia \n(NHRMC, ID 2009677 & GNT1196520). YZ is supported by Natural Science Foundation of China (Grant #:92370202) \nand the computing facility at Shenzhen Bay Laboratory.  In addition, TL acknowledges Lenovo who provided a \nThinkstation workstation to support this research. We also thank Professor Yuedong Yang for making the SPalign source \ncode freely available. \nReferences \n1. Seemann, T. Prokka: rapid prokaryotic genome annotation. Bioinformatics 30, 2068–2069 (2014). \n2. Altschul, S. F., Gish, W., Miller, W., Myers, E. W. & Lipman, D. J. Basic local alignment search tool. J. Mol. \nBiol. 215, 403–410 (1990). \n3. Eddy, S. R. Accelerated Profile HMM Searches. PLOS Comput. Biol. 7, e1002195 (2011). \n4. Steinegger, M. & Söding, J. MMseqs2 enables sensitive protein sequence searching for the analysis of massive \ndata sets. Nat. Biotechnol. 35, 1026–1028 (2017). \n5. Weisman, C. M., Murray, A. W. & Eddy, S. R. Many, but not all, lineage-specific genes can be explained by \nhomology detection failure. PLOS Biol. 18, e3000862 (2020). \n6. Varadi, M. et al. AlphaFold Protein Structure Database: massively expanding the structural coverage of \nprotein-sequence space with high-accuracy models. Nucleic Acids Res. 50, D439–D444 (2022). \n7. Consortium, U. UniProt: the universal protein knowledgebase in 2023. Nucleic Acids Res. 51, D523–D531 \n(2023). \n8. Lin, Z. et al. Evolutionary-scale prediction of atomic-level protein structure with a language model. Science \n(80-. ). 379, 1123–1130 (2023). \n9. Pavlopoulos, G. A. et al. Unraveling the functional dark matter through global metagenomics. Nature 622, \n594–602 (2023). \n10. Barrio-Hernandez, I. et al. Clustering predicted structures at the scale of the known protein universe. Nature \n622, 637–645 (2023). \n11. Borujeni, P. M. & Salavati, R. Functional domain annotation by structural similarity. NAR Genomics \nBioinforma. 6, lqae005 (2024). \n12. Rodríguez del Río, Á. et al. Functional and evolutionary significance of unknown genes from uncultivated \ntaxa. Nature 626, 377–384 (2024). \n13. Cohen, G. E. ALIGN: a program to superimpose protein coordinates, accounting for insertions and deletions. J. \nAppl. Crystallogr. 30, 1160–1161 (1997). \n14. Zhang, Y. & Skolnick, J. TM-align: a protein structure alignment algorithm based on the TM-score. Nucleic \nAcids Res. 33, 2302–2309 (2005). \n15. Yang, Y., Zhan, J., Zhao, H. & Zhou, Y. A new size-independent score for pairwise protein structure alignment \nand its application to structure classification and nucleic-acid binding prediction. Proteins Struct. Funct. \nBioinforma. 80, 2080–2088 (2012). \n16. Zhang, C., Shine, M., Pyle, A. M. & Zhang, Y. US-align: universal structure alignments of proteins, nucleic \nacids, and macromolecular complexes. Nat. Methods 19, 1109–1115 (2022). \n17. Needleman, S. B. & Wunsch, C. D. A general method applicable to the search for similarities in the amino acid \nsequence of two proteins. J. Mol. Biol. 48, 443–453 (1970). \n18. van Kempen, M. et al. Fast and accurate protein structure search with Foldseek. Nat. Biotechnol. 42, 243–246 \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint \n\n(2024). \n19. Chandonia, J.-M., Fox, N. K. & Brenner, S. E. SCOPe: classification of large macromolecular structures in the \nstructural  classification of proteins-extended database. Nucleic Acids Res. 47, D475–D481 (2019). \n20. Watson, J. L. et al. De novo design of protein structure and function with RFdiffusion. Nature 620, 1089–1100 \n(2023). \n21. Mizuguchi, K., Deane, C. M., Blundell, T. L. & Overington, J. P. HOMSTRAD: a database of protein structure \nalignments for homologous families. Protein Sci. 7, 2469–2471 (1998). \n22. Collier, J. H. et al. Statistical inference of protein structural alignments using information and compression. \nBioinformatics 33, 1005–1013 (2017). \n23. Mistry, J. et al. Pfam: The protein families database in 2021. Nucleic Acids Res. 49, D412–D419 (2021). \n24. Soto, J. E., Galán, J. E. & Lara-Tejero, M. Assembly and architecture of the type III secretion sorting platform. \nProc. Natl. Acad. Sci. 119, e2218010119 (2022). \n25. Wagner, S. & Diepold, A. A Unified Nomenclature for Injectisome-Type Type III Secretion Systems BT  - \nBacterial Type III Protein Secretion Systems. in (eds. Wagner, S. & Galan, J. E.) 1–10 (Springer International \nPublishing, 2020). doi:10.1007/82_2020_210 \n26. Deng, W. et al. Assembly, structure, function and regulation of type III secretion systems. Nat. Rev. Microbiol. \n15, 323–337 (2017). \n27. Rucks, E. A. Type III Secretion in Chlamydia. Microbiol. Mol. Biol. Rev. 87, e0003423 (2023). \n28. Muthuramalingam, M. et al. The Structures of SctK and SctD from Pseudomonas aeruginosa Reveal the \nInterface of the Type III Secretion System Basal Body and Sorting Platform. J. Mol. Biol. 432, 166693 (2020). \n29. Sanchez-Torres, V., Kirigo, J. & Wood, T. K. Diverse physiological roles of the MqsR/MqsA toxin/antitoxin \nsystem. Sustain. Microbiol. 1, qvae006 (2024). \n30. Ernits, K. et al. The structural basis of hyperpromiscuity in a core combinatorial network of type II toxin–\nantitoxin and related phage defense systems. Proc. Natl. Acad. Sci. 120, e2305393120 (2023). \n31. Jumper, J. et al. Highly accurate protein structure prediction with AlphaFold. Nature 596, 583–589 (2021). \n32. Berman, H. M. et al. The Protein Data Bank. Nucleic Acids Res. 28, 235–242 (2000). \n33. Tiemann, J. K. S. et al. MDverse: Shedding Light on the Dark Matter of Molecular Dynamics Simulations. \nElife 2023.05.02.538537 (2023). doi:10.7554/elife.90061.1 \n34. Stahl, K., Graziadei, A., Dau, T., Brock, O. & Rappsilber, J. Protein structure prediction with in-cell photo-\ncrosslinking mass spectrometry and deep learning. Nat. Biotechnol. 41, 1810–1819 (2023). \n35. Abramson, J. et al. Accurate structure prediction of biomolecular interactions with AlphaFold 3. Nature 630, \n493–500 (2024). \n36. Kabsch, W. & Sander, C. Dictionary of protein secondary structure: Pattern recognition of hydrogen-bonded \nand geometrical features. Biopolymers 22, 2577–2637 (1983). \n37. Vázquez Torres, S. et al. De novo design of high-affinity binders of bioactive helical peptides. Nature 626, \n435–442 (2024). \n38. Kim, H., Mirdita, M. & Steinegger, M. Foldcomp: a library and format for compressing and indexing large \nprotein structure sets. Bioinformatics 39, btad153 (2023). \n39. Pereira, J. GCsnap: Interactive Snapshots for the Comparison of Protein-Coding Genomic Contexts. J. Mol. \nBiol. 433, 166943 (2021). \n \n.CC-BY 4.0 International licensemade available under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is \nThe copyright holder for this preprintthis version posted March 16, 2025. ; https://doi.org/10.1101/2025.03.14.643159doi: bioRxiv preprint","source_license":"CC-BY-4.0","license_restricted":false}