Markov models take center stage in several applications such as telecommunication, biological sequence analysis, protein structure prediction, language modeling, automatic speech recognition, financial modeling, gesture recognition, and traffic analysis. For example, the Glycerol TraSH genome data pertaining to M. tuberculosis transposon mutants is typically modeled via a Hidden Markov Model (HMM). The data consists of multiple gene sites, each of which is in one of the four states, namely essential, growth-defect, non-essential, and growth-advantage. These states represent different categories of gene essentiality, as reflected in their read-counts (i.e. emissions). Being able to label the state of each gene from the read-counts is crucial for identifying the potential drug targets for antimicrobial treatment.
The classic approach for inferring the state labels is an optimal dynamic programming based method called the Viterbi algorithm. However, the Viterbi algorithm can suffer from a very high latency and memory footprint since it needs to process the entire sequence of observations before it can label any state. In particular, due to these limitations, Viterbi algorithm is not suitable for critical scenarios such as patient monitoring, intrusion detection, and credit card fraud monitoring where delay following the onset of a suspicious activity might prove detrimental. Indeed, low latency is also desirable for tasks such as drug discovery that rely on detecting interleaved coding regions in massive gene sequences. A lot of effort has thus rightly been invested into reducing the latency and memory requirements of the Viterbi algorithm.
We introduce the first provably near-optimal algorithms for decoding Markov models under hard constraints on latency (and storage). Our algorithms demonstrate excellent empirical performance, and can be applied even in the time-varying and adversarial settings. For example, on the Glycerol TraSH data, we perform almost as good as the Viterbi algorithm with a latency of only 20, which is more than 3500 times better than that of Viterbi (latency for Viterbi on this data is over 73000).