Informatics and Machine Learning. Stephen Winters-Hilt

      3.4.1 Markov Chains

      A Markov chain is a sequence of random variables S₁; S₂; S₃; … with the Markov property of limited memory, where a first‐order Markov assumption on the probability for observing a sequence “s₁ s₂ s₃ s₄…s_n” is:

      In the Markov chain model, the states are also the observables. For a HMM we generalize to where the states are no longer directly observable (but still first‐order Markov), and for each state, say S₁, we have a statistical linkage to a random variable, O₁, that has an observable base emission, with the standard (0th‐order) Markov assumption on prior emissions.

      The key “short‐term memory” property of a Markov chain is: P(x_i ∣ x_{i − 1}, …, x₁) = P(x_i ∣ x_{i − 1}) = a_{i − 1, i}, where a_{i − 1, i} are sometimes referred to as “transition probabilities”, and we have: P(x) = P(x_L, x_{L − 1}, …, x₁) = P(x₁)∏_{i = 2…L} a_{i − 1, i}. If we denote C_y for the count of events y, C_xy for the count of simultaneous events x and y, T_y for the count of strings of length one, and T_xy for the count of strings of length two: a_{i − 1, i} = P(x ∣ y) = P(x, y)/P(y) = [C_xy/T_xy]/[ C_y/T_y]. Note: since T_xy + 1 = T_y → T_xy ≅ T_y (sequential data sample property if one long training block), a_{i − 1, i} ≅ C_xy/C_y = C_xy/∑_x C_xy, so counts C_xy is complete information for determining transition probabilities.

      For prokaryotic gene prediction much of the problem with obtaining high‐confidence training data can be circumvented by using a bootstrap gene‐prediction approach. This is possible in prokaryotes because of their simpler and more compact genomic structure: simpler in that long ORFs are usually long genes, and compact in that motif searches upstream usually range over hundreds of bases rather than thousands (as in human).

Interpolated Markov Model (IMM): the order of the MM can be interpolated according to a globally imposed cutoff criterion (see Figure 3.5), such as a minimum sub‐sequence count: fourth‐order passes if Counts (x₀; x₋₁; x₋₂; x₋₃; x₋₄)>cutoff for all x₋₄…x₀ sub‐sequences (100, for example), the utility of this becomes apparent with the following reexpression:

      TotalCounts(length5)/TotalCounts(length4)

Figure 3.5 Hash interpolated Markov model (hIMM) and gap/hash interpolated Markov model (ghIMM): now no longer employ a global cutoff criterion – count cutoff criterion applied at the sub‐sequence level. Given the current state and the emitted sequence as x₁, …, x_L; compute: P(x_L ∣ x₁, …, x_{L − 1}) ≈ Count(x₁, …, x_L)/Count(x₁, …, x_{L − 1}). If Count(x₁, …, x_{L − 1}) ≥ 400 i.e. only if the parental sequence shows statistical significance (consider 400 = 4 × 100, or requiring >100 counts on observations assuming uniform distribution for count cutoff determination), store P(x_L ∣ x₁, …, x_{L − 1}) in the hash. (If gene finding, have at least five states, e.g. need to maintain a separate hash for each of the following states – Junk, Intron, and Exon0, 1, 2.)

Suppose Counts (x₀; x₋₁; x₋₂; x₋₃; x₋₄; x₋₅) <cutoff for some x₋₅…x₀ sub‐sequence, then the interpolation would halt (globally), and the order of MM used would be fourth‐order.

      Gap Interpolated Markov Model (gIMM): like IMM with its count cutoff, but when going to higher order in the interpolation there is no constraint to contiguous sequence elements – i.e. “gaps” are allowed. The resolution of what gap‐size to choose when going to the next higher order is resolved by evaluating the Mutual Information. i.e. when going to 3rd order in the Markov context, P(x₀ ∣ x₋₅; x₋₂; x₋₁) is chosen over P(x₀ ∣ x₋₃; x₋₂; x₋₁) if

Скачать книгу