Decoding Genetic Variations: Communications-Inspired Haplotype Assembly

Haris Vikalo

University of Texas at Austin

Abstract:

High-throughput DNA sequencing technologies allow fast and affordable sequencing of individual genomes and thus enable unprecedented studies of genetic variations. The complete information about variations in the genome of an individual is provided by haplotypes, ordered collections of single nucleotide polymorphisms.

Knowledge of haplotypes is instrumental in finding genes associated with diseases, drug development and evolutionary studies; however, their reconstruction is computationally challenging (NP-hard). Our key observation is that the minimum error-correction formulation of the haplotype assembly problem is identical to the task of deciphering a coded message received over a noisy channel – a classical problem in the mature field of communication theory. Exploiting this connection, we develop novel methods that explore the tradeoffs between performance and complexity of haplotype assembly. Motivated by sphere decoding ideas, we propose a novel branch-and-bound haplotyping algorithm and find its expected complexity, demonstrating that the optimal haplotype assembly, often considered impractical, is in fact practically feasible for haplotype blocks of moderate length. For long haplotype blocks, we reformulate the problem as a semi-definite program and exploit its structural features to derive a fast and accurate heuristic solution. Finally, an information-theoretic analysis of haplotype assembly allows us to establish its fundamental erformance limits.

Biography:

Haris Vikalo received the B.S. degree from the University of Zagreb, Croatia, in 1995, the M.S. degree from Lehigh University in 1997, and the Ph.D. degree from Stanford University in 2003, all in electrical engineering. He held a short-term appointment at Bell Laboratories, Murray Hill, NJ, in the summer of 1999. From January 2003 to July 2003 he was a Postdoctoral Researcher, and from July 2003 to August 2007 he was an Associate Scientist at the California Institute of Technology. Since September 2007, he has been with the Department of Electrical and Computer Engineering, the University of Texas at Austin, where he is currently an Associate Professor.

He is a recipient of the 2009 National Science Foundation Career Award. His research interests include signal processing, bioinformatics, and communications.