On-line Viterbi Algorithm and Its Relationship to Random Walks

Details On-line Viterbi Algorithm and Its Relationship to Random Walks On-line Viterbi Algorithm and Its Relationship to Random Walks

2007-03-31

arxiv.org/abs/0704.0062v1

Algorithms in Bioinformatics: 7th International Workshop (WABI), 4645 volume of Lecture Notes in Computer Science, pp. 240-251

Computer Science

Data Structures and Algorithms

Scientific paper

10.1007/978-3-540-74126-8_23

In this paper, we introduce the on-line Viterbi algorithm for decoding hidden Markov models (HMMs) in much smaller than linear space. Our analysis on two-state HMMs suggests that the expected maximum memory used to decode sequence of length $n$ with $m$-state HMM can be as low as $\Theta(m\log n)$, without a significant slow-down compared to the classical Viterbi algorithm. Classical Viterbi algorithm requires $O(mn)$ space, which is impractical for analysis of long DNA sequences (such as complete human genome chromosomes) and for continuous data streams. We also experimentally demonstrate the performance of the on-line Viterbi algorithm on a simple HMM for gene finding on both simulated and real DNA sequences.

Affiliated with

Also associated with

No associations

Rating

On-line Viterbi Algorithm and Its Relationship to Random Walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On-line Viterbi Algorithm and Its Relationship to Random Walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-line Viterbi Algorithm and Its Relationship to Random Walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-460124