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

The DOI matches its Crossref record.

A Probabilistic Model of Local Sequence Alignment That Simplifies Statistical Significance Estimation

Open access
Eddy, Sean R.·2008·PLoS Computational Biology
DOI 10.1371/journal.pcbi.1000069
Open this paper in CoChat — free account

Abstract

Sequence database searches require accurate estimation of the statistical significance of scores. Optimal local sequence alignment scores follow Gumbel distributions, but determining an important parameter of the distribution (lambda) requires time-consuming computational simulation. Moreover, optimal alignment scores are less powerful than probabilistic scores that integrate over alignment uncertainty ("Forward" scores), but the expected distribution of Forward scores remains unknown. Here, I conjecture that both expected score distributions have simple, predictable forms when full probabilistic modeling methods are used. For a probabilistic model of local sequence alignment, optimal alignment bit scores ("Viterbi" scores) are Gumbel-distributed with constant lambda = log 2, and the high scoring tail of Forward scores is exponential with the same constant lambda. Simulation studies support these conjectures over a wide range of profile/sequence comparisons, using 9,318 profile-hidden Markov models from the Pfam database. This enables efficient and accurate determination of expectation values (E-values) for both Viterbi and Forward scores for probabilistic local alignments.

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.1371/journal.pcbi.1000069

Cites

Statistics

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

No references could be resolved yet.

Research works printed but not linked: 48

  1. SF Altschul, 1997, Gapped BLAST and PSI-BLAST: a new generation of protein database search programs., Nucl Acids Res, 25, 3389, 10.1093/nar/25.17.3389 · DOI · Paper page
  2. A Krogh, 1994, Hidden Markov models in computational biology: applications to protein modeling., J Mol Biol, 235, 1501, 10.1006/jmbi.1994.1104 · DOI
  3. SF Altschul, 1994, Issues in searching molecular sequence databases., Nature Genetics, 6, 119, 10.1038/ng0294-119 · DOI · Paper page
  4. AY Mitrophanov, 2006, Statistical significance in biological sequence analysis., Brief Bioinform, 7, 2, 10.1093/bib/bbk001 · DOI
  5. SF Altschul, 1990, Basic local alignment search tool., J Mol Biol, 215, 403, 10.1016/S0022-2836(05)80360-2 · DOI · Paper page
  6. S Karlin, 1990, Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes., Proc Natl Acad Sci USA, 87, 2264, 10.1073/pnas.87.6.2264 · DOI · Paper page
  7. S Karlin, 1993, Applications and statistics for multiple high-scoring segments in molecular sequences., Proc Natl Acad Sci USA, 90, 5873, 10.1073/pnas.90.12.5873 · DOI · Paper page
  8. SF Altschul, 1996, Local alignment statistics., Meth Enzymol, 266, 460, 10.1016/S0076-6879(96)66029-7 · DOI · Paper page
  9. J Park, 1998, Sequence comparisons using multiple sequences detect three times as many remote homologues as pairwise methods., J Mol Biol, 284, 1201, 10.1006/jmbi.1998.2221 · DOI · Paper page
  10. RC Edgar, 2004, A comparison of scoring functions for protein sequence profile alignment., Bioinformatics, 20, 1301, 10.1093/bioinformatics/bth090 · DOI
  11. WR Pearson, 2005, The limits of protein sequence comparison?, Curr Opin Struct Biol, 15, 254, 10.1016/j.sbi.2005.05.005 · DOI
  12. SF Altschul, 1991, Amino acid substitution matrices from an information theoretic perspective., J Mol Biol, 219, 555, 10.1016/0022-2836(91)90193-A · DOI · Paper page
  13. R Mott, 1992, Maximum likelihood estimation of the statistical distribution of Smith–Waterman local sequence similarity scores., Bull Math Biol, 54, 59, 10.1007/BF02458620 · DOI
  14. D Drasdo, 1998, A statistical theory of sequence alignment with gaps., Proc Int Conf Intell Syst Mol Biol, 6, 52
  15. R Mott, 1999, Approximate statistics of gapped alignments., J Comput Biol, 6, 91, 10.1089/cmb.1999.6.91 · DOI
  16. R Olsen, 1999, Rapid assessment of extremal statistics for gapped local alignment., Proc Int Conf Intell Syst Mol Biol, 7, 211
  17. R Mott, 2000, Accurate formula for P-values of gapped local sequence and profile alignments., J Mol Biol, 300, 649, 10.1006/jmbi.2000.3875 · DOI
  18. D Siegmund, 2000, Approximate P-values for local sequence alignments., The Annals of Statistics, 28, 657, 10.1214/aos/1015951993 · DOI
  19. SF Altschul, 2001, The estimation of statistical parameters for local alignment score distributions., Nucl Acids Res, 29, 351, 10.1093/nar/29.2.351 · DOI
  20. JD Storey, 2001, Approximate P-values for local sequence alignments: Numerical studies., J Comput Biol, 8, 549, 10.1089/106652701753216530 · DOI
  21. R Bundschuh, 2002, Rapid significance estimation in local sequence alignment with gaps., J Comput Biol, 9, 243, 10.1089/10665270252935449 · DOI
  22. N Chia, 2006, A practical approach to significance assessment in alignment with gaps., J Comput Biol, 13, 429, 10.1089/cmb.2006.13.429 · DOI
  23. D Metzler, 2006, Robust E-values for gapped local alignments., J Comput Biol, 13, 882, 10.1089/cmb.2006.13.882 · DOI
  24. RD Finn, 2006, Pfam: clans, web tools and services., Nucl Acids Res, 34, D247, 10.1093/nar/gkj149 · DOI · Paper page
  25. I Letunic, 2006, SMART 5: domains in the context of genomes and networks., Nucl Acids Res, 34, D257, 10.1093/nar/gkj079 · DOI · Paper page
  26. Y-K Yu, 2001, Statistical significance of probabilistic sequence alignment and related local hidden Markov models., J Comput Biol, 8, 249, 10.1089/10665270152530845 · DOI
  27. K Karplus, 2005, Calibrating E-values for hidden Markov models using reverse-sequence null models., Bioinformatics, 21, 4107, 10.1093/bioinformatics/bti629 · DOI
  28. A Pertsemlidis, 2001, Having a BLAST with bioinformatics (and avoiding BLASTphemy)., Genome Biol, 2, reviews2002.1, 10.1186/gb-2001-2-10-reviews2002 · DOI
  29. SR Eddy, 2002, Computational genomics of noncoding RNA genes., Cell, 109, 137, 10.1016/S0092-8674(02)00727-4 · DOI
  30. S Miyazawa, 1995, A reliable sequence alignment method based on probabilities of residue correspondences., Protein Eng, 8, 999, 10.1093/protein/8.10.999 · DOI
  31. MQ Zhang, 1995, Alignment of molecular sequences seen as random path analysis., J Theor Biol, 174, 119, 10.1006/jtbi.1995.0085 · DOI
  32. P Bucher, 1996, A sequence similarity search algorithm based on a probabilistic interpretation of an alignment scoring system., Proc Int Conf Intell Syst Mol Biol, 4, 44
  33. BJ Webb, 2002, BALSA: Bayesian algorithm for local sequence alignment., Nucl Acids Res, 30, 1268, 10.1093/nar/30.5.1268 · DOI
  34. A Milosavljević, 1993, Discovering simple DNA sequences by the algorithmic significance method., Comput Applic Biosci, 9, 407
  35. C Barrett, 1997, Scoring hidden Markov models., Comput Applic Biosci, 13, 191
  36. K Karplus, 1998, Hidden Markov models for detecting remote protein homologies., Bioinformatics, 14, 846, 10.1093/bioinformatics/14.10.846 · DOI · Paper page
  37. TF Smith, 1981, Identification of common molecular subsequences., J Mol Biol, 147, 195, 10.1016/0022-2836(81)90087-5 · DOI · Paper page
  38. MG Kann, 2007, The identification of complete domains within protein sequences using accurate E-values for semi-global alignment., Nucl Acids Res, 35, 4678, 10.1093/nar/gkm414 · DOI
  39. K Sjölander, 1996, Dirichlet mixtures: a method for improving detection of weak but significant protein sequence homology., Comput Applic Biosci, 12, 327
  40. AA Schäffer, 2001, Improving the accuracy of PSI-BLAST protein database searches with composition-based statistics and other refinements., Nucl Acids Res, 29, 2994, 10.1093/nar/29.14.2994 · DOI · Paper page
  41. M Madera, 2002, A comparison of profile hidden Markov model procedures for remote homology detection., Nucl Acids Res, 30, 4321, 10.1093/nar/gkf544 · DOI
  42. EP Nawrocki, 2007, Query-dependent banding (QDB) for faster RNA similarity searches., PLoS Comput Biol, 3, e56, 10.1371/journal.pcbi.0030056 · DOI · Paper page
  43. C Webber, 2001, Estimation of P-values for global alignments of protein sequences., Bioinformatics, 17, 1158, 10.1093/bioinformatics/17.12.1158 · DOI
  44. MS Waterman, 1987, Phase transitions in sequence matches and nucleic acid structure., Proc Natl Acad Sci U S A, 84, 1239, 10.1073/pnas.84.5.1239 · DOI
  45. Y-K Yu, 2002, Hybrid alignment: high-performance with universal statistics., Bioinformatics, 18, 864, 10.1093/bioinformatics/18.6.864 · DOI
  46. A Marchler-Bauer, 2007, CDD: a conserved domain database for interactive domain family analysis., Nucl Acids Res, 35, D237, 10.1093/nar/gkl951 · DOI · Paper page
  47. Y-K Yu, 2003, The compositional adjustment of amino acid substitution matrices., Proc Natl Acad Sci U S A, 100, 15688, 10.1073/pnas.2533904100 · DOI
  48. JS Liu, 1999, Bayesian inference on biopolymer models., Bioinformatics, 15, 38, 10.1093/bioinformatics/15.1.38 · DOI

Cited by

See all 348

Metadata

Authors
Eddy, S. R.
Venue
PLoS Computational Biology
Publisher
Public Library of Science (PLoS)
Published
2008-05-30
Volume
4
Issue
5
Pages
e1000069
ISSN
  • 1553-734X (ISSN-L)
  • 1553-7358
DOI
10.1371/journal.pcbi.1000069
OpenAlex
W1996112765
Cited by
348
References
0
FWCI
9.06
Type
journal article
Language
en
Open access
gold
Licence
creativecommons.org/licenses/by/4.0/ (unspecified)

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: A Probabilistic Model of Local Sequence Alignment That Simplifies Statistical Significance Estimation. https://app.cochat.ai/papers/10.1371/journal.pcbi.1000069
The paper
Eddy, S. R. (2008). A Probabilistic Model of Local Sequence Alignment That Simplifies Statistical Significance Estimation. PLoS Computational Biology. https://doi.org/10.1371/journal.pcbi.1000069

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.