Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

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

Sensitive inference of alignment-safe intervals from biodiverse protein sequence clusters using EMERALD

Open access

Preprint — published as 10.1186/s13059-023-03008-6

Abstract

Sequence alignments are the foundation of life science research, but most innovation focused on optimal alignments, while ignoring information derived from suboptimal solutions. We argue that one optimal alignment per pairwise sequence comparison was a reasonable approximation when dealing with very similar sequences, but is insufficient when exploring the biodiversity of the protein universe at tree-of-life scale. To overcome this limitation, we introduce pairwise alignment-safety to uncover the amino acid positions robustly shared across all suboptimal solutions. We implemented this approach into EMERALD, a dedicated software solution for alignment-safety inference and apply it to 400k sequences from the SwissProt database.

Overview

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

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

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

Integrity signals

Registry

Crossref · 10.1101/2023.01.11.523286

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Figures

Fig. 1 Schematic representation of EMERALD’s safety window calculation of a DIAMOND DeepClust cluster containing 4 member sequences. EMERALD performs a pairwise global alignment between the cluster representative against each of the 4 cluster member sequences using affine gap costs and BLOSUM62 as substitution matrix. For the first sequence pair, the right-hand side illustrates the suboptimal alignment graph and their corresponding suboptimal alignment configurations between the two sequences listed as Δ-suboptimal alignments (an alignment is Δ-suboptimal if its score is not more than Δ smaller than the optimal score). The illustrated graph is one of minimum size to fulfill the property of including all Δ-suboptimal alignments (here, we choose Δ=8). Source-to-sink paths in the graph correspond to suboptimal alignments; nodes and edges on the unique optimal alignment path are shown in black, while those configurations on a Δ-suboptimal path are illustrated in gray. The optimal alignment path is color coded in black and the two top Δ-suboptimal alignment paths illustrated in orange and blue. For α=0.75 and Δ=8, we obtain three safety windows shown as green intervals. These three colored safety windows correspond to subpaths contained in at least α=0.75 (i.e., 75%) of all source-to-sink paths (i.e., of all Δ-suboptimal alignments). Note that the middle safety window is not captured (i.e., contained) by the (unique) optimal alignment, in black, and is only revealed by the subgraph of all Δ-suboptimal alignments. Finally, we project the safety windows onto the cluster member (and cluster representative sequence) as explained in (the “Methods" section). This procedure is repeated for all possible pairwise comparisons between the representative sequence and the 4 members, thereby obtaining (α,Δ)-safety windows for each cluster member (bottom left)
Fig. 1 Schematic representation of EMERALD’s safety window calculation of a DIAMOND DeepClust cluster containing 4 member sequences. EMERALD performs a pairwise global alignment between the cluster representative against each of the 4 cluster member sequences using affine gap costs and BLOSUM62 as substitution matrix. For the first sequence pair, the right-hand side illustrates the suboptimal alignment graph and their corresponding suboptimal alignment configurations between the two sequences listed as Δ-suboptimal alignments (an alignment is Δ-suboptimal if its score is not more than Δ smaller than the optimal score). The illustrated graph is one of minimum size to fulfill the property of including all Δ-suboptimal alignments (here, we choose Δ=8). Source-to-sink paths in the graph correspond to suboptimal alignments; nodes and edges on the unique optimal alignment path are shown in black, while those configurations on a Δ-suboptimal path are illustrated in gray. The optimal alignment path is color coded in black and the two top Δ-suboptimal alignment paths illustrated in orange and blue. For α=0.75 and Δ=8, we obtain three safety windows shown as green intervals. These three colored safety windows correspond to subpaths contained in at least α=0.75 (i.e., 75%) of all source-to-sink paths (i.e., of all Δ-suboptimal alignments). Note that the middle safety window is not captured (i.e., contained) by the (unique) optimal alignment, in black, and is only revealed by the subgraph of all Δ-suboptimal alignments. Finally, we project the safety windows onto the cluster member (and cluster representative sequence) as explained in (the “Methods" section). This procedure is repeated for all possible pairwise comparisons between the representative sequence and the 4 members, thereby obtaining (α,Δ)-safety windows for each cluster member (bottom left)CC BY · PubMed Central
Fig. 2 Comparing stable structure retention and safety coverage (y-axis) for several sequence identity ranges between cluster members against the cluster representative (x-axis) carried out with EMERALD parameters α=0.75 and Δ=8 on all obtained sequences, where N denotes the number of sequences in each identity range. The dashed lines indicate medians and the dotted lines the first and third quartiles. The safety coverage increases with higher identity ranges due to the smaller size of the suboptimal alignment space for high identity sequence pairs. Since the stable structure retention quantifies the proportion of stable amino acids that are alignment-safe, it increases alongside an increase in safety coverage. The high stable structure retention results indicate that EMERALD is indeed able to capture biologically relevant stable positions, as they make up a higher proportion when restricting the sequence to safety windows. a All sequences are included (i.e., with safety coverage of at most 100%). b Sequences restricted to those having safety coverage of maximum 80%
Fig. 2 Comparing stable structure retention and safety coverage (y-axis) for several sequence identity ranges between cluster members against the cluster representative (x-axis) carried out with EMERALD parameters α=0.75 and Δ=8 on all obtained sequences, where N denotes the number of sequences in each identity range. The dashed lines indicate medians and the dotted lines the first and third quartiles. The safety coverage increases with higher identity ranges due to the smaller size of the suboptimal alignment space for high identity sequence pairs. Since the stable structure retention quantifies the proportion of stable amino acids that are alignment-safe, it increases alongside an increase in safety coverage. The high stable structure retention results indicate that EMERALD is indeed able to capture biologically relevant stable positions, as they make up a higher proportion when restricting the sequence to safety windows. a All sequences are included (i.e., with safety coverage of at most 100%). b Sequences restricted to those having safety coverage of maximum 80%CC BY · PubMed Central
Fig. 3 For a given threshold x, safety coverage of the sequences whose stable structure retention is at least x (on the left), and the proportion of the sequences whose stable structure retention is at least x (on the right). The results are split into different identity ranges. a All 396k sequences are included. b Restricted to sequences whose safety coverage is at most 80%. The dark red curves, which cover sequences of all identities, show in a that around 20% of the sequences (right plot) have a stable structure retention of 100% and only 15% of safety coverage (left plot), while the purple curves, which cover sequences from the identity range 40–70%, show in b that 10% out of the sequences with at most 80% safety coverage inside this identity range (right plot) have a stable structure retention of 100% and only a safety coverage of around 5% (left plot)
Fig. 3 For a given threshold x, safety coverage of the sequences whose stable structure retention is at least x (on the left), and the proportion of the sequences whose stable structure retention is at least x (on the right). The results are split into different identity ranges. a All 396k sequences are included. b Restricted to sequences whose safety coverage is at most 80%. The dark red curves, which cover sequences of all identities, show in a that around 20% of the sequences (right plot) have a stable structure retention of 100% and only 15% of safety coverage (left plot), while the purple curves, which cover sequences from the identity range 40–70%, show in b that 10% out of the sequences with at most 80% safety coverage inside this identity range (right plot) have a stable structure retention of 100% and only a safety coverage of around 5% (left plot)CC BY · PubMed Central
Fig. 4 CPU runtime of EMERALD. a Computational run time for all DIAMOND DeepClust clusters generated from the filtered Swiss-Prot database using the threshold combination α=0.75 and Δ=8 and calculated on a single thread. Each dot corresponds to a protein sequence cluster and the color of each dot indicates its number of corresponding member sequences. b Maximum memory consumption of EMERALD runs. For all trialed α and Δ parameter settings, the average memory consumption for each cluster ranged between 205 and 207 Mb and the average run time between 11.4 and 11.5 s
Fig. 4 CPU runtime of EMERALD. a Computational run time for all DIAMOND DeepClust clusters generated from the filtered Swiss-Prot database using the threshold combination α=0.75 and Δ=8 and calculated on a single thread. Each dot corresponds to a protein sequence cluster and the color of each dot indicates its number of corresponding member sequences. b Maximum memory consumption of EMERALD runs. For all trialed α and Δ parameter settings, the average memory consumption for each cluster ranged between 205 and 207 Mb and the average run time between 11.4 and 11.5 sCC BY · PubMed Central
Fig. 5 Conceptual overview of EMERALD’s safety window calculation workflow. As input EMERALD receives a set of clusters in fasta format. For example, such protein sequence clusters can be generated using DIAMOND DeepClust or alternative clustering methods. Next, users can specify the scoring matrix (e.g., BLOSUM62) according to which optimal alignment configurations will be determined. Each cluster member sequence is then globally aligned against the cluster representative sequence (centroid) using the pairwise Needleman-Wunsch alignment algorithm. The resulting dynamic programming (DP) matrix of each pairwise comparison is then encoded as a graph data structure to search for optimal and suboptimal alignment paths according to the selected scoring matrix and the threshold configurations defining the suboptimal alignment space. Once all alignment-safe intervals are computed, EMERALD projects these safety intervals (safety windows) back to the representative sequence, thereby annotating the sequence intervals that are robust across all possible alignment configurations within the suboptimal alignment space
Fig. 5 Conceptual overview of EMERALD’s safety window calculation workflow. As input EMERALD receives a set of clusters in fasta format. For example, such protein sequence clusters can be generated using DIAMOND DeepClust or alternative clustering methods. Next, users can specify the scoring matrix (e.g., BLOSUM62) according to which optimal alignment configurations will be determined. Each cluster member sequence is then globally aligned against the cluster representative sequence (centroid) using the pairwise Needleman-Wunsch alignment algorithm. The resulting dynamic programming (DP) matrix of each pairwise comparison is then encoded as a graph data structure to search for optimal and suboptimal alignment paths according to the selected scoring matrix and the threshold configurations defining the suboptimal alignment space. Once all alignment-safe intervals are computed, EMERALD projects these safety intervals (safety windows) back to the representative sequence, thereby annotating the sequence intervals that are robust across all possible alignment configurations within the suboptimal alignment spaceCC BY · PubMed Central

Verification

Claims the paper makes

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

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

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

Show all 1 references

Research works printed but not linked: 37

  1. 10.1126/science.abj8754 · doi:10.1126/science.abj8754 · Paper page
  2. 10.1093/nar/25.1.31 · DOI · Paper page
  3. 2022, Highly significant improvement of protein sequence alignments with alphafold2, Bioinformatics, 38, 5007, 10.1093/bioinformatics/btac625 · doi:10.1093/bioinformatics/btac625
  4. 10.1016/j.jspi.2005.02.004 · DOI
  5. Sarah E Bondos , A Keith Dunker , and Vladimir N Uversky . On the roles of intrinsically disordered proteins and regions in cell communication and signaling, 2021. · DOI
  6. 2021, Sensitive protein alignments at tree-of-life scale using diamond, Nature methods, 18, 366, 10.1038/s41592-021-01101-x · DOI · Paper page
  7. 10.1093/bioinformatics/9.4.387 · DOI
  8. 10.1093/bib/bbv099 · DOI · Paper page
  9. 2008, Estimating quality of template-based protein models by alignment stability, Proteins: Structure, Function, and Bioinformatics, 71, 1255, 10.1002/prot.21819 · DOI
  10. 2011, Effect of using suboptimal alignments in template-based protein structure prediction, Proteins: Structure, Function, and Bioinformatics, 79, 315, 10.1002/prot.22885 · DOI
  11. 10.1093/bioinformatics/18.2.306 · DOI
  12. 10.1093/nar/gkaa1100 · DOI · Paper page
  13. 10.1093/nar/gkh340 · DOI · Paper page
  14. 1995, Knowledge-based protein secondary structure assignment, Proteins: Structure, Function, and Bioinformatics, 23, 566, 10.1002/prot.340230412 · DOI · Paper page
  15. Trevor Hastie , Robert Tibshirani , Jerome H Friedman , and Jerome H Friedman . The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009. · DOI · Paper page
  16. 10.1073/pnas.89.22.10915 · DOI · Paper page
  17. 10.1110/ps.4820102 · DOI
  18. 10.1089/cmb.2022.0261 · DOI
  19. 10.4230/LIPIcs.CPM.2019.8 · DOI
  20. Maik Kschischo and Michael Lässig . Finite-temperature sequence alignment. In Biocomputing 2000, pages 624–635. World Scientific, 1999. · DOI
  21. 10.1093/sysbio/syy059 · DOI
  22. Zeming Lin , Halil Akin , Roshan Rao , Brian Hie , Zhongkai Zhu , Wenting Lu , Nikita Smetanin , Robert Verkuil , Ori Kabeli , Yaniv Shmueli , et al. Evolutionary-scale prediction of atomic level protein structure with a language model. bioRxiv, 2022.
  23. Felix Mölder , Kim Philipp Jablonski , Brice Letcher , Michael B Hall , Christopher H Tomkins-Tinch , Vanessa Sochat , Jan Forster , Soohyun Lee , Sven O Twardziok , Alexander Kanitz , et al. Sustainable data analysis with snakemake. F1000Research, 10, 2021. · DOI · Paper page
  24. Eugene W. Myers and Webb Miller . Optimal alignments in linear space. Computer applications in the biosciences : CABIOS, 4 1, 1988. · DOI · Paper page
  25. 1994, On near-optimal alignments of biological sequences, Journal of Computational Biology, 1, 349, 10.1089/cmb.1994.1.349 · DOI
  26. 10.1016/0022-2836(70)90057-4 · DOI · Paper page
  27. 10.1006/jmbi.2000.4042 · DOI · Paper page
  28. 10.1093/molbev/msq066 · DOI · Paper page
  29. 10.1093/protein/12.2.85 · DOI · Paper page
  30. 10.1093/bioinformatics/18.6.847 · DOI
  31. 10.1186/1471-2105-11-1 · DOI · Paper page
  32. 10.1016/0022-2836(81)90087-5 · DOI · Paper page
  33. 1974, A note on finding the bridges of a graph, Inf. Process. Lett, 2, 160, 10.1016/0020-0190(74)90003-9 · DOI
  34. 10.1089/cmb.2016.0141 · DOI
  35. 10.1093/NAR/GKAB1061 · DOI · Paper page
  36. 10.1093/protein/3.7.565 · DOI
  37. 1995, Alignment of molecular sequences seen as random path analysis, Journal of theoretical Biology, 174, 119, 10.1006/jtbi.1995.0085 · DOI

Metadata

Authors
Grigorjew, A., Gynter, A., Dias, F. H. C., Buchfink, B., Drost, H.-G., & Tomescu, A. I.
Affiliations
  • University of Helsinki (FI)
  • Max Planck Institute for Biology (DE)
Corresponding author
  • Drost, Hajk-Georg
  • Tomescu, Alexandru I.
Venue
Genome biology
Publisher
openRxiv
Published
2023-01-15
Volume
24
Issue
1
Pages
168-168
ISSN
1465-6906 (ISSN-L)
OpenAlex
W4384558888
Cited by
4
References
1
Citations by year
2026: 3 · 2023: 1
FWCI
0.36
Type
journal article
Language
en
Open access
Licence
cc-by
Locations
  • Genome biology (publishedVersion, cc-by)
  • bioRxiv (Cold Spring Harbor Laboratory) (acceptedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • Discovery Research Portal (University of Dundee) (publishedVersion, cc-by)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • Työväentutkimus Vuosikirja (submittedVersion)
Funders
  • European Commission (HORIZON2020, 851093)
  • Academy of Finland (322595, 328877, grants No. 322595, 328877, 352821, grants No. 322595, 352821, 322595, 328877)
  • Bundesministerium für Bildung und Forschung (031A537C, 031A533A, 031A532B, 031A533A, 031A533B, 031A534A, 031A535A, 031A537A, 031A537B, 031A537C, 031A537D, 031A538A, 031A535A, 031A537A, 031A538A, 031A537D, 031A534A, 031A532B, 031A533B, 031A537B)
  • Max-Planck-Gesellschaft
  • German Network for Bioinformatics Infrastructure (031A533A, 031A534A, 031A538A, 031A537 A, 031A537D, 031 A535 A, 031 A537B, 031 A532B, 031 A533B, #031A537C, 031A532B,031A533A,031A533B,031A534A,031A535A,031A537A,031A537B,031A537C,031A537D,031A538A)
  • HORIZON EUROPE European Research Council (grant agreement No. 851093, SAFEBIO)
Topics
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
  • Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
Keywords
pairwise sequence alignment, emerald, tree of life, Swiss-Prot
MeSH terms
Algorithms, Amino Acid Sequence, Animals, Birds, Proteins, Software, Sequence Alignment

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

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Sensitive inference of alignment-safe intervals from biodiverse protein sequence clusters using EMERALD. https://app.cochat.ai/papers/10.1101/2023.01.11.523286
The paper
Grigorjew, A., Gynter, A., Dias, F. H. C., Buchfink, B., Drost, H.-G., & Tomescu, A. I. (2023). Sensitive inference of alignment-safe intervals from biodiverse protein sequence clusters using EMERALD. Genome biology. https://doi.org/10.1101/2023.01.11.523286

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.