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

By Sean R. Eddy. PLoS Comput. Biol., 2008

358 citations recorded by the source corpus.

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 (λ) 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 λ = log 2, and the high scoring tail of Forward scores is exponential with the same constant λ. 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.

Subfields: Artificial Intelligence, Molecular Biology, Signal Processing

View Paper: https://www.semanticscholar.org/paper/0b66a33b74518b0f0e46d5157a3b571035aab40e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Signal Processing

Citations in the corpus

DALI shines a light on remote homologs: One hundred discoveries (2022, background): “Pfam domain boundaries are based on conserved sequence blocks (Eddy, 2008).”
Exploring nucleo-cytoplasmic large DNA viruses in Tara Oceans microbial metagenomes (2013, methodology): “Profile-hidden Markov models (Eddy, 2008) derived from the sequence alignments of these marker genes were used to identify their homologs (E-valuep10 3) in the translated amino-acid sequence sets derived from metagenomic data.”
Learning the language of viral evolution and escape (2020, positive): “…fitness model, we use the EVcouplings framework (Hopf et al., 2017, 2019) (https://github.com/debbiemarkslab/EVcouplings), which leverages HMMER software for sequence alignment (Eddy, 2008) (http://hmmer.org/), to estimate the predicted fitness using both the independent and epistatic models.”
tRNAscan-SE 2.0: improved detection and functional classification of transfer RNA genes (2019, methodology): “The incorporation of the accelerated profile hidden Markov model (HMM) methods used in HMMER3 (23,24) and the constrained CM alignment algorithms (19,25) in Infernal provide multiple levels of filtering as part of sequence homology searches.”
Skylign: a tool for creating informative, interactive logos representing sequence alignments and profile hidden Markov models (2014, background): “Profile HMMs provide a formal probabilistic framework for sequence comparison [1-3], leveraging the information contained in a sequence alignment to improve detection of distantly related sequences [4,5].”
PhyLAT: a phylogenetic local alignment tool (2012, background): “However, many kinds of alignments involving gaps were empirically demonstrated to follow EVD (Altschul et al., 1997; Eddy, 2008; Sadreyev and Grishin, 2003; Schaffer et al., 1999).”
nhmmer: DNA homology search with profile HMMs (2013, positive): “…the past, this improved sensitivity came at a significant computational cost, but recent advances in HMMER3 have increased speed for protein search by 100-fold, reaching blastp-like speed through a combination of filtering heuristics (Eddy, 2008) and computer engineering (Eddy, 2011; Farrar, 2007).”
KofamKOALA: KEGG Ortholog assignment based on profile HMM and adaptive score threshold (2019, methodology): “Next, MAFFT (7) and HMMER/hmmbuild (8) are used to align sequences and to generate a profile HMM.”
Infernal 1.1: 100-fold faster RNA homology searches (2013, methodology): “We also tested two sequence-only methods: profile HMMs implemented in HMMER3 (Eddy, 2008, 2011) and family-pairwise (Grundy, 1998) single-sequence BLASTN queries (Altschul et al. , 1997), which were faster (0.02 and 0.01h, respectively), but significantly less sensitive than CMs, indicating the…”
Protein sequence comparison and fold recognition: progress and good-practice benchmarking. (2011, methodology): “Sensitivity was improved further by using the Forward instead of the Viterbi algorithm for scoring matches and replacing the timeconsuming sampling-based E-value calculation by a heuristic approximation [47].”
Accelerated Profile HMM Searches (2011, methodology): “HMMER3 ameliorates edge effect by calculating an ad hoc corrected ^ ll ~ log 2 z 1 : 44 MH , where M is the length of the profile in match states and H is the relative entropy per match emission state in bits [31].”
A new generation of homology search tools based on probabilistic inference. (2009, background): “These conjectures were shown by numerical simulation (though not by formal proof) to hold for a wide range of different query models and target sequences [7].”