Informatics and Machine Learning

7Generalized HMMs (GHMMs): Major Viterbi Variants

Numerous prior book, journal, and patent publications by the author are drawn upon extensively throughout the text [1–68]. Almost all of the journal publications are open access. These publications can typically be found online at either the author’s personal website (www.meta‐logos.com) or with one of the following online publishers: www.m‐hikari.com or bmcbioinformatics.biomedcentral.com.

For an overview of Hidden Markov Models (HMMs) and their (minor) Viterbi generalizations, see Chapter 6.

7.1 GHMMs: Maximal Clique for Viterbi and Baum–Welch

The generalized clique HMM begins by enlarging the primitive hidden states associated with individual base labeling (as exon, intron, or junk) to substrings of primitive hidden states or footprint states (details on the definitions of the base‐label states and footprint states are in what follows). In what follows, the transitions between primitive hidden states for coding {e} and noncoding {i,j}, {ei,ie,je,ej}, are referred to as “eij‐transitions”, and the self‐transitions, {ee,ii,jj}, are referred to as “xx‐transitions”. The emissions are likewise expanded to higher order in the fundamental joint probability that is the basis of the generalized‐clique, or “meta‐state,” HMM. In [33] we consider application to eukaryotic gene finding and show how a meta‐state HMM improves the strength of eij‐transition contributions to gene‐structure identification. It is found that the meta‐state ...