Statistical significance of probabilistic sequence alignment and related local hidden Markov models
- PMID: 11535176
- DOI: 10.1089/10665270152530845
Statistical significance of probabilistic sequence alignment and related local hidden Markov models
Abstract
The score statistics of probabilistic gapped local alignment of random sequences is investigated both analytically and numerically. The full probabilistic algorithm (e.g., the "local" version of maximum-likelihood or hidden Markov model method) is found to have anomalous statistics. A modified "semi-probabilistic" alignment consisting of a hybrid of Smith-Waterman and probabilistic alignment is then proposed and studied in detail. It is predicted that the score statistics of the hybrid algorithm is of the Gumbel universal form, with the key Gumbel parameter lambda taking on a fixed asymptotic value for a wide variety of scoring systems and parameters. A simple recipe for the computation of the "relative entropy," and from it the finite size correction to lambda, is also given. These predictions compare well with direct numerical simulations for sequences of lengths between 100 and 1,000 examined using various PAM substitution scores and affine gap functions. The sensitivity of the hybrid method in the detection of sequence homology is also studied using correlated sequences generated from toy mutation models. It is found to be comparable to that of the Smith-Waterman alignment and significantly better than the Viterbi version of the probabilistic alignment.
Similar articles
-
Toward an accurate statistics of gapped alignments.Bull Math Biol. 2005 Jan;67(1):169-91. doi: 10.1016/j.bulm.2004.07.001. Bull Math Biol. 2005. PMID: 15691544
-
A probabilistic model of local sequence alignment that simplifies statistical significance estimation.PLoS Comput Biol. 2008 May 30;4(5):e1000069. doi: 10.1371/journal.pcbi.1000069. PLoS Comput Biol. 2008. PMID: 18516236 Free PMC article.
-
A "Long Indel" model for evolutionary sequence alignment.Mol Biol Evol. 2004 Mar;21(3):529-40. doi: 10.1093/molbev/msh043. Epub 2003 Dec 23. Mol Biol Evol. 2004. PMID: 14694074
-
A sequence similarity search algorithm based on a probabilistic interpretation of an alignment scoring system.Proc Int Conf Intell Syst Mol Biol. 1996;4:44-51. Proc Int Conf Intell Syst Mol Biol. 1996. PMID: 8877503 Review.
-
Effects of long-range correlations in DNA on sequence alignment score statistics.J Comput Biol. 2007 Jun;14(5):655-68. doi: 10.1089/cmb.2007.R008. J Comput Biol. 2007. PMID: 17683266 Review.
Cited by
-
Estimating statistical significance of local protein profile-profile alignments.BMC Bioinformatics. 2019 Aug 13;20(1):419. doi: 10.1186/s12859-019-2913-3. BMC Bioinformatics. 2019. PMID: 31409275 Free PMC article.
-
How sequence alignment scores correspond to probability models.Bioinformatics. 2020 Jan 15;36(2):408-415. doi: 10.1093/bioinformatics/btz576. Bioinformatics. 2020. PMID: 31329241 Free PMC article.
-
Confidence assignment for mass spectrometry based peptide identifications via the extreme value distribution.Bioinformatics. 2016 Sep 1;32(17):2642-9. doi: 10.1093/bioinformatics/btw225. Epub 2016 Apr 29. Bioinformatics. 2016. PMID: 27153659 Free PMC article.
-
MSARC: Multiple sequence alignment by residue clustering.Algorithms Mol Biol. 2014 Apr 16;9:12. doi: 10.1186/1748-7188-9-12. eCollection 2014. Algorithms Mol Biol. 2014. PMID: 24735785 Free PMC article.
-
GraphAlignment: Bayesian pairwise alignment of biological networks.BMC Syst Biol. 2012 Nov 21;6:144. doi: 10.1186/1752-0509-6-144. BMC Syst Biol. 2012. PMID: 23171476 Free PMC article.
Publication types
MeSH terms
LinkOut - more resources
Full Text Sources
Other Literature Sources
Miscellaneous
