Analysis of pattern overlaps and exact computation of P-values of pattern occurrences numbers: case of Hidden Markov ModelsReport as inadecuate




Analysis of pattern overlaps and exact computation of P-values of pattern occurrences numbers: case of Hidden Markov Models - Download this document for free, or read online. Document in PDF available to download.

1 LIX - Laboratoire d-informatique de l-École polytechnique Palaiseau 2 Inria - Institut National de Recherche en Informatique et en Automatique 3 AMIB - Algorithms and Models for Integrative Biology LIX - Laboratoire d-informatique de l-École polytechnique Palaiseau, LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR8623 4 IMPB RAS - Institute of Mathematical Problems in Biology 5 Institute of Mathematical Problems of Biology 6 Puschino State University

Abstract : We present a novel algorithm, SufPref, computing an exact pvalue for Hidden Markov models HMM. The algorithm inductively traverses specific data structure, the overlap graph. Nodes of the graph are associated with the overlaps of words from a given set H. Edges are associated to the prefix and suffix relations between ovelaps. An originality of our data structure is that pattern H 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; the approach is analogous to a weighted automaton approach. The gain in size of SufPref data structure leads to significant space and time complexity improvements. We suppose that all words in the pattern H are of the same length m. The algorithm SufPref was implemented as a C++ program; it can be used both as Web-server and a stand alone program for Linux and Windows.

Résumé : Cet article présente un nouvel algorithme, SufPref, qui calcule la pvaleur pour un ensemble de mots qui prend en compte les modèles de Markov cachés HMM. Il est implémenté en C++ et peut être utilisé en ligne ou téléchargé.

Keywords : probability pvalue word combinatorics





Author: Mireille Régnier - Evgenia Furletova - Victor Yakovlev - Mikhail Roytberg -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents