Abstract

Next generation DNA sequencing is a technology that is revolutionizing research in biology and medicine. The sequencers operate by randomly fragmenting a genome into reads (contiguous genome fragments) that are a few hundred of base pairs long. Reads are produced at a much higher throughput compared to classical techniques. However, they are often corrupted by errors which pose a serious problem for downstream processes such as genome assembly. Correcting errors in reads is thus an important problem. The problem differs significantly from classical error correction since there is a lack of alignment information between the different reads. We present a fully flexible, probabilistic and reference-free method of error correction for high throughput DNA sequencing data. The outputs of a sequencer are modeled as independent emissions of a Hidden Markov Model (HMM), where transition probabilities account for local dependence in the genome and the emission distribution models the error properties of the sequencer. We pose the problem of error correction of reads as one of maximum likelihood sequence detection over this HMM . Exhaustive results on publicly available datasets show that our algorithm consistently outperforms existing methods in terms of error correction performance.

BIO: Aditya Ramamoorthy is an Associate Professor of Electrical and Computer Engineering at Iowa State University. He received his B. Tech. degree in Electrical Engineering from the Indian Institute of Technology, Delhi in 1999 and the M.S. and Ph.D. degrees from the University of California, Los Angeles (UCLA) in 2002 and 2005 respectively. From 2005 to 2006 he was with the data storage signal processing group at Marvell Semiconductor Inc. His research interests are in the areas of network information theory, channel coding and signal processing for nanotechnology and bioinformatics. Dr. Ramamoorthy has been serving as an associate editor for the IEEE Transactions on Communications since 2011. He is the recipient of the 2012 Iowa State University’s Early Career Engineering Faculty Research Award, the 2012 NSF CAREER award, and the Harpole-Pentair professorship in 2009 and 2010.