  In this work we present a flexible, probabilistic and reference-free method
of error correction for high throughput DNA sequencing data. The key is to
exploit the high coverage of sequencing data and model short sequence outputs
as independent realizations of a Hidden Markov Model (HMM). We pose the problem
of error correction of reads as one of maximum likelihood sequence detection
over this HMM. While time and memory considerations rule out an implementation
of the optimal Baum-Welch algorithm (for parameter estimation) and the optimal
Viterbi algorithm (for error correction), we propose low-complexity approximate
versions of both. Specifically, we propose an approximate Viterbi and a
sequential decoding based algorithm for the error correction. Our results show
that when compared with Reptile, a state-of-the-art error correction method,
our methods consistently achieve superior performances on both simulated and
real data sets.
