CoChat
Sign Up
Cited by 2Protein Structure and DynamicsEnzyme Structure and FunctionMachine Learning in Bioinformatics

The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.

An interpretable alphabet for local protein structure search based on amino acid neighborhoods

Open access
Zerefa, Saba, Cool, Jesse, Singh, Pramesh, Petti, Samantha·2025·Bioinformatics
DOI 10.1093/bioinformatics/btaf458PMC PMC12516309

Published version of a preprint

Open this paper in CoChat — free account

Abstract

Motivation: Recent advancements in protein structure prediction methods have vastly increased the size of databases of protein structures, necessitating fast methods for protein structure comparison. Search methods that find structurally similar proteins can be applied to find remote homologs, study the functional relationships among proteins, and aid in protein engineering tasks. Results: We design a “3Dn” structural alphabet that encodes the local neighborhoods around each amino acid in an interpretable way. In a search benchmark task, a combination of our alphabet and Foldseek’s 3Di alphabet, outperforms each alphabet individually and ranks best among local search methods that do not require amino acid identity information. We provide software tools that enable the exploration of novel alphabets and combinations of alphabets for protein structure search. Availability and implementation: The code is freely available at https://github.com/spetti/structure_comparison and at Zenodo https://doi.org/10.5281/zenodo.15734371.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1093/bioinformatics/btaf458

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1. Overview of the process for encoding a 3Dn sequence and generating an alignment. (A) Encoding process for a single amino acid. We define a reference frame centered at the Cα atom and divide the surrounding 15Å sphere into bins. Then we compute an n-hot vector that tabulates the positions and secondary structures of neighboring amino acids in the sphere. The n-hot vector shown is a simplified 2D example. A transition matrix is applied to the n-hot vector, resulting in a blurry neighborhood. The blurry neighborhood is compared via weighted Jaccard similarity to twenty landmark blurry neighborhoods, each of which are affiliated with a 3Dn character. The amino acid is assigned to the 3Dn character with the largest weighted Jaccard similarity value. (B) Pipeline demonstrating how to obtain an alignment from two PDB files. Each amino acid is encoded into a 3Dn character according to the process outlined in A. For simplicity, we only show a short (three or four character) subsequence of the encoded sequence. A scoring matrix for the pair of encoded sequences is generated by looking up a substitution score for each pair. With this scoring matrix, the Smith-Waterman (S-W) algorithm is used to generate an alignment, the quality of which is computed using lDDT. Protein depictions are courtesy of SCOPe (Chandonia et al. 2019).
Figure 1. Overview of the process for encoding a 3Dn sequence and generating an alignment. (A) Encoding process for a single amino acid. We define a reference frame centered at the Cα atom and divide the surrounding 15Å sphere into bins. Then we compute an n-hot vector that tabulates the positions and secondary structures of neighboring amino acids in the sphere. The n-hot vector shown is a simplified 2D example. A transition matrix is applied to the n-hot vector, resulting in a blurry neighborhood. The blurry neighborhood is compared via weighted Jaccard similarity to twenty landmark blurry neighborhoods, each of which are affiliated with a 3Dn character. The amino acid is assigned to the 3Dn character with the largest weighted Jaccard similarity value. (B) Pipeline demonstrating how to obtain an alignment from two PDB files. Each amino acid is encoded into a 3Dn character according to the process outlined in A. For simplicity, we only show a short (three or four character) subsequence of the encoded sequence. A scoring matrix for the pair of encoded sequences is generated by looking up a substitution score for each pair. With this scoring matrix, the Smith-Waterman (S-W) algorithm is used to generate an alignment, the quality of which is computed using lDDT. Protein depictions are courtesy of SCOPe (Chandonia et al. 2019).CC BY · PubMed Central
Figure 2. Visualizing 3Dn characters. We discretize the 15Å sphere oriented with respect to the reference frame depicted in Fig. 1A into 250 bins by taking 10 intervals in ϕ, 5 intervals in θ and 5 intervals in r (hidden in the left image). To visualize the neighbor counts in each of these bins, we show two flattened images obtained by averaging over ϕ (upper row) and θ (lower row). In the upper row, the darkness of each cell represents the average number of neighbors across all bins with a particular interval for r and interval for θ. In the lower row, the darkness of each cell represents the average number of neighbors across all bins with a particular interval for r and interval for ϕ. The z-axis appears as a line in the upper plot and a point in the lower plot, as depicted in yellow. See Fig. 3 for examples. Note that these figures are not to scale; true r, θ, and ϕ values are chosen so that each bin has equal volume.
Figure 2. Visualizing 3Dn characters. We discretize the 15Å sphere oriented with respect to the reference frame depicted in Fig. 1A into 250 bins by taking 10 intervals in ϕ, 5 intervals in θ and 5 intervals in r (hidden in the left image). To visualize the neighbor counts in each of these bins, we show two flattened images obtained by averaging over ϕ (upper row) and θ (lower row). In the upper row, the darkness of each cell represents the average number of neighbors across all bins with a particular interval for r and interval for θ. In the lower row, the darkness of each cell represents the average number of neighbors across all bins with a particular interval for r and interval for ϕ. The z-axis appears as a line in the upper plot and a point in the lower plot, as depicted in yellow. See Fig. 3 for examples. Note that these figures are not to scale; true r, θ, and ϕ values are chosen so that each bin has equal volume.CC BY · PubMed Central
Figure 3. Visualization of 3Dn characters 14, 16, and 18. Figure 2 explains how to interpret the circle and semi-circle figures. The left figures illustrate the spatial distributions of neighbors in the landmark blurry neighborhood for the 3Dn character. The number of neighbors varies substantially across the different 3Dn states, as indicated by the given neighborhood populations. The vertical bar shows the distribution of the secondary structure of the neighbors. The top rightmost plots illustrate the distribution of the right helix neighbors, whereas the bottom rightmost plots illustrate the distribution of beta sheet neighbors. See Section 3.2.1 for a qualitative description of the three 3Dn states visualized here. The full alphabet, including left α-helix (yellow) and unclassified secondary structure (green) is depicted in Fig. 12, available as supplementary data at Bioinformatics online.
Figure 3. Visualization of 3Dn characters 14, 16, and 18. Figure 2 explains how to interpret the circle and semi-circle figures. The left figures illustrate the spatial distributions of neighbors in the landmark blurry neighborhood for the 3Dn character. The number of neighbors varies substantially across the different 3Dn states, as indicated by the given neighborhood populations. The vertical bar shows the distribution of the secondary structure of the neighbors. The top rightmost plots illustrate the distribution of the right helix neighbors, whereas the bottom rightmost plots illustrate the distribution of beta sheet neighbors. See Section 3.2.1 for a qualitative description of the three 3Dn states visualized here. The full alphabet, including left α-helix (yellow) and unclassified secondary structure (green) is depicted in Fig. 12, available as supplementary data at Bioinformatics online.CC BY · PubMed Central
Figure 4. Superfamily search benchmark results. (A) Sensitivity up to the first false positive for AA, Dihedral, 3Di, 3Dn, 3Di-3Dn, and BV alphabets at the superfamily level. The benefit of adding amino acid information is shown in gray, and the benefit of adding dihedral information is shown in brown. (B) The fraction of queries that receive a greater sensitivity up to the first false positive than indicated in the corresponding x-axis value, at the superfamily level. Each color and line type represent a different alphabet or combination of alphabets. (C) Precision and recall of each alphabet at the superfamily level. Each color and line type represent a different alphabet or combination of alphabets.
Figure 4. Superfamily search benchmark results. (A) Sensitivity up to the first false positive for AA, Dihedral, 3Di, 3Dn, 3Di-3Dn, and BV alphabets at the superfamily level. The benefit of adding amino acid information is shown in gray, and the benefit of adding dihedral information is shown in brown. (B) The fraction of queries that receive a greater sensitivity up to the first false positive than indicated in the corresponding x-axis value, at the superfamily level. Each color and line type represent a different alphabet or combination of alphabets. (C) Precision and recall of each alphabet at the superfamily level. Each color and line type represent a different alphabet or combination of alphabets.CC BY · PubMed Central
Figure 5. Co-occurance of 3Di, 3Dn, amino acid and dihedral characters. (A) A log odds matrix illustrating the co-occurance of 3Di and 3Dn characters; a positive log odds score (red) indicates the pair co-occur more than what would be expected by chance. (B) Probabilities of any given amino acid belonging to any 3Dn character or 3Di character. (C) Labels of regions corresponding to our learned dihedral characters on a Ramachandran plot. (D) Probabilities of any given dihedral character associating to any given 3Dn character or 3Di character.
Figure 5. Co-occurance of 3Di, 3Dn, amino acid and dihedral characters. (A) A log odds matrix illustrating the co-occurance of 3Di and 3Dn characters; a positive log odds score (red) indicates the pair co-occur more than what would be expected by chance. (B) Probabilities of any given amino acid belonging to any 3Dn character or 3Di character. (C) Labels of regions corresponding to our learned dihedral characters on a Ramachandran plot. (D) Probabilities of any given dihedral character associating to any given 3Dn character or 3Di character.CC BY · PubMed Central

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Research works printed but not linked: 28

  1. Altschul, 1990, Basic local alignment search tool, J Mol Biol, 215, 403, 10.1016/S0022-2836(05)80360-2 · DOI · Paper page
  2. Blondel, 2008, Fast unfolding of communities in large networks, J Stat Mech, 2008, P10008, 10.1088/1742-5468/2008/10/P10008 · DOI · Paper page
  3. Bystroff, 1998, Prediction of local structure in proteins using a library of sequence-structure motifs, J Mol Biol, 281, 565, 10.1006/jmbi.1998.1943 · DOI
  4. Camproux, 2004, A hidden Markov model derived structural alphabet for proteins, J Mol Biol, 339, 591, 10.1016/j.jmb.2004.04.005 · DOI
  5. Chandonia, 2019, SCOPe: classification of large macromolecular structures in the structural classification of proteins—extended database, Nucleic Acids Res, 47, D475, 10.1093/nar/gky1134 · DOI
  6. de Brevern, 2000, Bayesian probabilistic approach for predicting backbone structures in terms of protein blocks, Proteins, 41, 271, 10.1002/1097-0134(20001115)41:3<271::AID-PROT10>3.0.CO;2-Z · DOI
  7. Finn, 2011, HMMER web server: interactive sequence similarity searching, Nucleic Acids Res, 39, W29, 10.1093/nar/gkr367 · DOI · Paper page
  8. Hauser, 2016, MMseqs software suite for fast and deep clustering and searching of large protein sequence sets, Bioinformatics, 32, 1323, 10.1093/bioinformatics/btw006 · DOI
  9. Heinzinger, 2024, Bilingual language model for protein sequence and structure, NAR Genom Bioinform, 6, lqae150, 10.1093/nargab/lqae150 · DOI · Paper page
  10. Henikoff, 1992, Amino acid substitution matrices from protein blocks, Proc Natl Acad Sci USA, 89, 10915, 10.1073/pnas.89.22.10915 · DOI · Paper page
  11. Holm, 2020, DALI and the persistence of protein shape, Protein Sci, 29, 128, 10.1002/pro.3749 · DOI
  12. Hong, 2025, Fast, sensitive detection of protein homologs using deep dense retrieval, Nat Biotechnol, 43, 983, 10.1038/s41587-024-02353-6 · DOI
  13. Johnson, 2024, Sensitive remote homology search by local alignment of small positional embeddings from protein language models, Elife, 12, RP91415, 10.7554/eLife.91415 · DOI · Paper page
  14. Le, 2009, Structural alphabets for protein structure classification: a comparison study, J Mol Biol, 387, 431, 10.1016/j.jmb.2008.12.044 · DOI
  15. Liu, 2024, PLMSearch: protein language model powers accurate and fast sequence search for remote homology, Nat Commun, 15, 2775, 10.1038/s41467-024-46808-5 · DOI · Paper page
  16. Lu, 2025, Patterns, 6, 101286, 10.1016/j.patter.2025.101289 · DOI
  17. Ma, 2014, Algorithms, applications, and challenges of protein structure alignment, Adv Protein Chem Struct Biol, 94, 121, 10.1016/B978-0-12-800168-4.00005-6 · DOI
  18. Miao, 2008, Tali: local alignment of protein structures using backbone torsion angles, J Bioinform Comput Biol, 6, 163, 10.1142/S0219720008003370 · DOI
  19. Petti, 2023, End-to-end learning of multiple sequence alignments with differentiable Smith–Waterman, Bioinformatics, 39, btac724, 10.1093/bioinformatics/btac724 · DOI · Paper page
  20. Procházka, 2024, Nucleic Acids Res
  21. Reichardt, 2006, Statistical mechanics of community detection, Phys Rev E Stat Nonlin Soft Matter Phys, 74, 016110, 10.1103/PhysRevE.74.016110 · DOI · Paper page
  22. Rooman, 1990, Automatic definition of recurrent local structure motifs in proteins, J Mol Biol, 213, 327, 10.1016/S0022-2836(05)80194-9 · DOI
  23. Smith, 1981, Identification of common molecular subsequences, J Mol Biol, 147, 195, 10.1016/0022-2836(81)90087-5 · DOI
  24. Tung, 2007, Kappa-alpha plot derived structural alphabet and blosum-like substitution matrix for rapid search of protein structure database, Genome Biol, 8, R31, 10.1186/gb-2007-8-3-r31 · DOI
  25. UniProt Consortium, 2015, UniProt: a hub for protein information, Nucleic Acids Res, 43, D204, 10.1093/nar/gku989 · DOI · Paper page
  26. Van Kempen, 2024, Fast and accurate protein structure search with Foldseek, Nat Biotechnol, 42, 243, 10.1038/s41587-023-01773-0 · DOI · Paper page
  27. Zhang, 2004, Scoring function for automated assessment of protein structure template quality, Proteins Struct Funct Bioinf, 57, 702, 10.1002/prot.20264 · DOI · Paper page
  28. Zhang, 2005, TM-align: a protein structure alignment algorithm based on the TM-score, Nucleic Acids Res, 33, 2302, 10.1093/nar/gki524 · DOI · Paper page

Metadata

Authors
Zerefa, S., Cool, J., Singh, P., & Petti, S.
Affiliations
  • Harvard University (US)
  • Tufts University (US)
Corresponding author
Petti, Samantha
ORCID
Venue
Bioinformatics
Publisher
Oxford University Press (OUP)
Published
2025-08-23
Volume
41
Issue
10
ISSN
  • 1367-4803 (ISSN-L)
  • 1367-4811
DOI
10.1093/bioinformatics/btaf458
PMC
PMC12516309
OpenAlex
W4413491758
Cited by
2
References
3
Citations by year
2026: 2
FWCI
0.60
Type
journal article
Language
en
Open access
Licence
Locations
  • Bioinformatics (publishedVersion, cc-by)
  • bioRxiv (Cold Spring Harbor Laboratory) (acceptedVersion, cc-by-nc-nd)
  • Europe PMC (PubMed Central) (publishedVersion, cc-by)
  • PubMed (publishedVersion)
Funders
  • NSF-Simons Center for Mathematical and Statistical Analysis of Biology at Harvard (#1764269)
  • Burroughs-Wellcome Careers at the Scientific Interface
Topics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Protein Structure and Dynamics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Structural Biology › Enzyme Structure and Function
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Machine Learning in Bioinformatics
Keywords
protein structure search, structural alphabet, remote homology detection, interpretable representations, protein structure database
MeSH terms
Algorithms, Amino Acids, Protein Conformation, Proteins, Software, Computational Biology, Sequence Analysis, Protein, Databases, Protein

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review