title: Analysis of pattern overlaps and exact computation of P-values of pattern occurrences numbers: case of Hidden Markov Models.
abstract: BACKGROUND
  Finding new functional fragments in biological sequences is a challenging problem. Methods addressing this problem commonly search for clusters of pattern occurrences that are statistically significant. A measure of statistical significance is the P-value of a number of pattern occurrences, i.e. the probability to find at least S occurrences of words from a pattern in a random text of length N generated according to a given probability model. All words of the pattern are supposed to be of same length.
  
  
  RESULTS
  We present a novel algorithm SufPref that computes an exact P-value for Hidden Markov models (HMM). The algorithm is based on recursive equations on text sets related to pattern occurrences; the equations can be used for any probability model. The algorithm inductively traverses a specific data structure, an overlap graph. The nodes of the graph are associated with the overlaps of words from . The edges are associated to the prefix and suffix relations between overlaps. An originality of our data structure is that pattern need not be explicitly represented in nodes or leaves. The algorithm relies on the Cartesian product of the overlap graph and the graph of HMM states; this approach is analogous to the automaton approach from JBCB 4: 553-569. The gain in size of SufPref data structure leads to significant improvements in space and time complexity compared to existent algorithms. The algorithm SufPref was implemented as a C++ program; the program can be used both as Web-server and a stand alone program for Linux and Windows. The program interface admits special formats to describe probability models of various types (HMM, Bernoulli, Markov); a pattern can be described with a list of words, a PSSM, a degenerate pattern or a word and a number of mismatches. It is available at http://server2.lpm.org.ru/bio/online/sf/. The program was applied to compare sensitivity and specificity of methods for TFBS prediction based on P-values computed for Bernoulli models, Markov models of orders one and two and HMMs. The experiments show that the methods have approximately the same qualities.
authors: INRIA, d'Estienne d'Orves 1, Palaiseau, 91120 France ; CNRS, d'Estienne d'Orves 1, Palaiseau, 91120 France ; LIX, Ecole Polytechnique, Batiment A. Turing, Palaiseau, 91128 France.
authors: Mireille
authors: M
authors: Régnier
authors: Institute of Mathematical Problems of Biology, 142290, Institutskaya, 4, Pushchino, Russia ; Pushchino State University, 142290, Prospect Nauki, 5, Pushchino, Russia.
authors: Evgenia
authors: E
authors: Furletova
authors: Institute of Mathematical Problems of Biology, 142290, Institutskaya, 4, Pushchino, Russia ; National Research University "Higher School of Economics", 101978, Myasnitskaya str., 20, Moscow, Russia.
authors: Victor
authors: V
authors: Yakovlev
authors: Institute of Mathematical Problems of Biology, 142290, Institutskaya, 4, Pushchino, Russia ; Laboratoire J.-V. Poncelet (UMI 2615), 119002, Bolshoy Vlasyevskiy Pereulok, 11, Moscow, Russia ; National Research University "Higher School of Economics", 101978, Myasnitskaya str., 20, Moscow, Russia ; Moscow Institute of Physics and Technology, 141700, Institutsky pereulok, 11, Moscow Region, Dolgoprudny, Russia.
authors: Mikhail
authors: M
authors: Roytberg
keywords: Hidden Markov model; P-value; PSSM (PWM); Pattern occurrences
references: Bioinformatics. 2000 Jan;16(1):16-23
references: 10812473
references: Bioinformatics. 2007 Mar 1;23(5):531-7
references: 17237046
references: J Comput Biol. 2005 Apr;12(3):314-30
references: 15857245
references: J Comput Biol. 1998 Summer;5(2):223-53
references: 9672830
references: Bioinformatics. 2008 Dec 15;24(24):2839-48
references: 18845582
references: Stat Appl Genet Mol Biol. 2006;5:Article26
references: 17049037
references: J Comput Biol. 2000 Feb-Apr;7(1-2):1-46
references: 10890386
references: Nucleic Acids Res. 1992 Mar 25;20(6):1363-70
references: 1313968
references: Nature. 2012 Sep 6;489(7414):57-74
references: 22955616
references: Nucleic Acids Res. 2000 Feb 15;28(4):1000-10
references: 10648794
references: Nucleic Acids Res. 2013 Jan;41(Database issue):D195-202
references: 23175603
references: Genome Biol. 2004;5(9):R61
references: 15345045
references: Algorithms Mol Biol. 2006 Apr 07;1(1):5
references: 16722531
references: IEEE/ACM Trans Comput Biol Bioinform. 2012 Nov-Dec;9(6):1737-50
references: 22868683
references: J Comput Biol. 2004;11(6):1023-33
references: 15662195
references: Biofizika. 2009 Sep-Oct;54(5):791-7
references: 19894615
references: J Bioinform Comput Biol. 2006 Apr;4(2):553-69
references: 16819802
references: Nucleic Acids Res. 2004 Feb 12;32(3):949-58
references: 14963262
references: Nat Biotechnol. 2005 Jan;23(1):137-44
references: 15637633
references: Adv Protein Chem Struct Biol. 2013;91:135-71
references: 23790213
references: J Bioinform Comput Biol. 2006 Apr;4(2):537-51
references: 16819801
references: J Math Biol. 2008 Jan;56(1-2):51-92
references: 17668213
references: Bioinformation. 2007 Dec 30;2(5):169-74
references: 18305824
references: Algorithms Mol Biol. 2007 Oct 10;2:13
references: 17927813
references: Bioinformatics. 2005 Jul 1;21(13):2933-42
references: 15860560