Pattern occurrences Pvalues, Hidden Markov Models and Overlap Graphs

2013.

Régnier M., Eugenia F., Mikhail Roytberg, Victor Yakovlev

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.

Ключевые слова: probability, pvalue, word combinatorics