Modeling sequencing errors by combining Hidden Markov models.

Among the largest resources for biological sequence data is the large amount of expressed sequence tags (ESTs) available in public and proprietary databases. ESTs provide information on transcripts but for technical reasons they often contain sequencing errors. Therefore, when analyzing EST sequences computationally, such errors must be taken into account. Earlier attempts to model error prone coding regions have shown good performance in detecting and predicting these while correcting sequencing errors using codon usage frequencies. In the research presented here, we improve the detection of translation start and stop sites by integrating a more complex mRNA model with codon usage bias based error correction into one hidden Markov model (HMM), thus generalizing this error correction approach to more complex HMMs. We show that our method maintains the performance in detecting coding sequences.

MAMOT: hidden Markov modeling tool.

Hidden Markov models (HMMs) are probabilistic models that are well adapted to many tasks in bioinformatics, for example, for predicting the occurrence of specific motifs in biological sequences. MAMOT is a command-line program for Unix-like operating systems, including MacOS X, that we developed to allow scientists to apply HMMs more easily in their research. One can define the architecture and initial parameters of the model in a text file and then use MAMOT for parameter optimization on example data, decoding (like predicting motif occurrence in sequences) and the production of stochastic sequences generated according to the probabilistic model. Two examples for which models are provided are coiled-coil domains in protein sequences and protein binding sites in DNA. A wealth of useful features include the use of pseudocounts, state tying and fixing of selected parameters in learning, and the inclusion of prior probabilities in decoding. AVAILABILITY: MAMOT is implemented in C++, and is distributed under the GNU General Public Licence (GPL). The software, documentation, and example model files can be found at http://bcf.isb-sib.ch/mamot

Time Reversibility of Stationary Regular Finite State Markov Chains

We propose an alternate parameterization of stationary regular finite-state Markov chains, and a decomposition of the parameter into time reversible and time irreversible parts. We demonstrate some useful properties of the decomposition, and propose an index for a certain type of time irreversibility. Two empirical examples illustrate the use of the proposed parameter, decomposition and index. One involves observed states; the other, latent states.

Bayesian online algorithms for learning in discrete Hidden Markov Models

We propose and analyze two different Bayesian online algorithms for learning in discrete Hidden Markov Models and compare their performance with the already known Baldi-Chauvin Algorithm. Using the Kullback-Leibler divergence as a measure of generalization we draw learning curves in simplified situations for these algorithms and compare their performances.

A numerical study of large sparse matrix exponentials arising in Markov chains

Krylov subspace techniques have been shown to yield robust methods for the numerical computation of large sparse matrix exponentials and especially the transient solutions of Markov Chains. The attractiveness of these methods results from the fact that they allow us to compute the action of a matrix exponential operator on an operand vector without having to compute, explicitly, the matrix exponential in isolation. In this paper we compare a Krylov-based method with some of the current approaches used for computing transient solutions of Markov chains. After a brief synthesis of the features of the methods used, wide-ranging numerical comparisons are performed on a power challenge array supercomputer on three different models. (C) 1999 Elsevier Science B.V. All rights reserved.AMS Classification: 65F99; 65L05; 65U05.

Quasistationarity of continuous-time Markov chains with positive drift

We shall study continuous-time Markov chains on the nonnegative integers which are both irreducible and transient, and which exhibit discernible stationarity before drift to infinity sets in. We will show how this 'quasi' stationary behaviour can be modelled using a limiting conditional distribution: specifically, the limiting state probabilities conditional on not having left 0 for the last time. By way of a dual chain, obtained by killing the original process on last exit from 0, we invoke the theory of quasistationarity for absorbing Markov chains. We prove that the conditioned state probabilities of the original chain are equal to the state probabilities of its dual conditioned on non-absorption, thus allowing us to establish the simultaneous existence and then equivalence, of their limiting conditional distributions. Although a limiting conditional distribution for the dual chain is always a quasistationary distribution in the usual sense, a similar statement is not possible for the original chain.

Further results on the relationship between mu-invariant measures and quasi-stationary distributions for absorbing continuous-time Markov chains

This note considers continuous-time Markov chains whose state space consists of an irreducible class, C, and an absorbing state which is accessible from C. The purpose is to provide results on mu-invariant and mu-subinvariant measures where absorption occurs with probability less than one. In particular, the well-known premise that the mu-invariant measure, m, for the transition rates be finite is replaced by the more natural premise that m be finite with respect to the absorption probabilities. The relationship between mu-invariant measures and quasi-stationary distributions is discussed. (C) 2000 Elsevier Science Ltd. All rights reserved.

New methods for determining quasi-stationary distributions for Markov chains

We shall be concerned with the problem of determining quasi-stationary distributions for Markovian models directly from their transition rates Q. We shall present simple conditions for a mu-invariant measure m for Q to be mu-invariant for the transition function, so that if m is finite, it can be normalized to produce a quasi-stationary distribution. (C) 2000 Elsevier Science Ltd. All rights reserved.

Characterization of the rat exploratory behavior in the elevated plus-maze with Markov chains

The elevated plus-maze is an animal model of anxiety used to study the effect of different drugs on the behavior of the animal It consists of a plus-shaped maze with two open and two closed arms elevated 50 cm from the floor The standard measures used to characterize exploratory behavior in the elevated plus-maze are the time spent and the number of entries in the open arms In this work we use Markov chains to characterize the exploratory behavior of the rat in the elevated plus-maze under three different conditions normal and under the effects of anxiogenic and anxiolytic drugs The spatial structure of the elevated plus-maze is divided into squares which are associated with states of a Markov chain By counting the frequencies of transitions between states during 5-min sessions in the elevated plus-maze we constructed stochastic matrices for the three conditions studied The stochastic matrices show specific patterns which correspond to the observed behaviors of the rat under the three different conditions For the control group the stochastic matrix shows a clear preference for places in the closed arms This preference is enhanced for the anxiogenic group For the anxiolytic group the stochastic matrix shows a pattern similar to a random walk Our results suggest that Markov chains can be used together with the standard measures to characterize the rat behavior in the elevated plus-maze (C) 2010 Elsevier B V All rights reserved

Similar Markov chains

enin et al. (2000) recently introduced the idea of similarity in the context of birth-death processes. This paper examines the extent to which their results can be extended to arbitrary Markov chains. It is proved that, under a variety of conditions, similar chains are strongly similar in a sense which is described, and it is shown that minimal chains are strongly similar if and only if the corresponding transition-rate matrices are strongly similar. A general framework is given for constructing families of strongly similar chains; it permits the construction of all such chains in the irreducible case.

Path integrals for continuous-time Markov chains

This note presents a method of evaluating the distribution of a path integral for Markov chains on a countable state space.

Set-valued Markov chains and negative semitrajectories of discretized dynamical systems

Computer simulation of dynamical systems involves a phase space which is the finite set of machine arithmetic. Rounding state values of the continuous system to this grid yields a spatially discrete dynamical system, often with different dynamical behaviour. Discretization of an invertible smooth system gives a system with set-valued negative semitrajectories. As the grid is refined, asymptotic behaviour of the semitrajectories follows probabilistic laws which correspond to a set-valued Markov chain, whose transition probabilities can be explicitly calculated. The results are illustrated for two-dimensional dynamical systems obtained by discretization of fractional linear transformations of the unit disc in the complex plane.

Integrals for continuous-time Markov chains

This paper presents a method of evaluating the expected value of a path integral for a general Markov chain on a countable state space. We illustrate the method with reference to several models, including birth-death processes and the birth, death and catastrophe process. (C) 2002 Elsevier Science Inc. All rights reserved.

Predicting market direction with hidden Markov models

This paper develops the model of Bicego, Grosso, and Otranto (2008) and applies Hidden Markov Models to predict market direction. The paper draws an analogy between financial markets and speech recognition, seeking inspiration from the latter to solve common issues in quantitative investing. Whereas previous works focus mostly on very complex modifications of the original hidden markov model algorithm, the current paper provides an innovative methodology by drawing inspiration from thoroughly tested, yet simple, speech recognition methodologies. By grouping returns into sequences, Hidden Markov Models can then predict market direction the same way they are used to identify phonemes in speech recognition. The model proves highly successful in identifying market direction but fails to consistently identify whether a trend is in place. All in all, the current paper seeks to bridge the gap between speech recognition and quantitative finance and, even though the model is not fully successful, several refinements are suggested and the room for improvement is significant.

An integrated system for human action recognition from video using hidden Markov model

In this paper, we present an integrated system for real-time automatic detection of human actions from video. The proposed approach uses the boundary of humans as the main feature for recognizing actions. Background subtraction is performed using Gaussian mixture model. Then, features are extracted from silhouettes and Vector Quantization is used to map features into symbols (bag of words approach). Finally, actions are detected using the Hidden Markov Model. The proposed system was validated using a newly collected real- world dataset. The obtained results show that the system is capable of achieving robust human detection, in both indoor and outdoor environments. Moreover, promising classification results were achieved when detecting two basic human actions: walking and sitting.