Probablistic Error Correction Using Markov Inference in Errored Reads

• Activity Number: 289
• Type: Contributed
• Date/Time: Tuesday, August 5, 2014 : 8:30 AM to 10:20 AM
• Sponsor: ENAR
• Author(s): Karin Dorman*+ and Xin Yin and Vahid Noroozi and Aditya Ramamoorthy
• Companies: Iowa State University and Iowa State University and Iowa State University and Iowa State University
• Keywords: Next Generation Sequencing ; Error correction ; Hidden Markov Model ; Genomics ; Assembly ; Penalized Likelihood

Abstract

Recent developments in sequencing technology have catalyzed biological research with a broad range of applications. Unfortunately, the high error rate interferes with many downstream uses of sequence data. We present a probabilistic error correction algorithm that corrects sequence data with or without insertions and deletions (indels). Sequences and quality scores are modeled as independent emissions of a Hidden Markov Model (HMM), where transition probabilities account for local dependence in the genome and indels, and the emission distribution allows flexible position- and context-dependent substitution errors adjusted for the quality scores. Estimation of parameters is regularized using a l0-like penalty to enforce our belief that most kmers, for sufficiently large k, originate from unique locations in the genome. A version of this penalty improves performance by using DNA complementarity without requiring knowledge of read strandedness. Error correction is performed by identifying the maximum likelihood paths through the HMM. An exhaustive evaluation on several datasets shows the proposed method consistently outperforms other state of the art error correction software.