From Theory to Assembled Genomes
Thomas Courtade, PhD
Abstract: Emerging long-read sequencing technologies promise to enable near-perfect reconstruction of whole genomes. Unfortunately, the genome assembly problem—a necessary step for all high-throughput sequencing technologies—is NP-hard under most formulations. As a result, available algorithmic approaches are generally heuristic in nature, leading to suspect correctness even on relatively simple problem instances.
Contrary to conventional wisdom, we find that by focusing only on "information-feasible" instances of the assembly problem, we can sidestep the apparent hardness issues and design efficient assembly algorithms with correctness guarantees. These insights form the theoretical foundation of our open-source, long-read assembly software HINGE. HINGE has been shown to outperform existing tools through extensive validation on long-read datasets and has been commercially adopted.
Note: This talk does not assume any prior knowledge about biology or DNA sequencing. This is joint work with Ilan Shomorony, Govinda Kamath, Fei Xia, Sam Kim and David Tse.
Bio: Thomas Courtade is an Assistant Professor in the Department of Electrical Engineering and Computer Sciences at UC Berkeley, and a core member of the Center for Computational Biology. He received a BS from Michigan Tech in 2007 and a PhD from UCLA in 2012, both degrees in Electrical Engineering. He spent a short time at Stanford afterward, where he was the inaugural postdoctoral fellow of the NSF Center for Science of Information. He does research on both fundamental and applied aspects of information theory, with work rang-ing from data compression and complexity to problems in genomics. Courtade is the recipient of several awards, including a UCLA Distinguished PhD Dissertation award, a best paper award at the International Symposium on Information Theory, a Hellman Fellowship and a NSF CAREER award.
Meet and Greet to follow, refreshments provided.
Thursday, February 28 at 2:00 pm to 3:00 pm
Electrical Energy Resources Center (EERC), 122
1400 Townsend Drive, Houghton, MI 49931