Claude Shannon invented information theory in 1948 to study the fundamental limits of communication. The theory not only establishes the baseline to judge all communication schemes but inspires the design of ones that are simultaneously information optimal and computationally efficient. In this talk, we discuss how this point of view can be applied on the problems of de novo DNA and RNA assembly from high-throughput sequencing data. We establish information limits for these problems, and show how efficient assembly algorithms can be designed to perform close to these information limits, despite the fact that combinatorial optimization formulations of these problems are NP-hard. We discuss Shannon and HINGE, two de novo assembly software designed based on such principles, and compare their performance against state-of-the-art assemblers on several high-throughput sequencing datasets.
David Tse received the B.A.Sc. degree in systems design engineering from University of Waterloo in 1989, and the M.S. and Ph.D. degrees in electrical engineering from Massachusetts Institute of Technology in 1991 and 1994 respectively. From 1994 to 1995, he was a postdoctoral member of technical staff at A.T. & T. Bell Laboratories. From 1995 to 2014, he was on the faculty of the University of California at Berkeley. He is currently a professor at Stanford University.
David Tse is the recipient of the 2017 Claude E. Shannon Award, the top award from the Information Theory Society. Previously, he received a NSF CAREER award in 1998, the Erlang Prize from the INFORMS Applied Probability Society in 2000 and a Gilbreth Lectureship from the National Academy of Engineering in 2012. He received multiple best paper awards, including the Information Theory Society Paper Award in 2003, the IEEE Communications Society and Information Theory Society Joint Paper Awards in 2000, 2013 and 2015, the Signal Processing Society Best Paper Award in 2012 and the IEEE Communications Society Stephen O. Rice Prize in 2013. For his contributions to education, he received the Outstanding Teaching Award from the Department of Electrical Engineering and Computer Sciences at U.C. Berkeley in 2008 and the Frederick Emmons Terman Award from the American Society for Engineering Education in 2009. He is a coauthor, with Pramod Viswanath, of the text Fundamentals of Wireless Communication, which has been used in over 60 institutions around the world. He is the inventor of the proportional-fair scheduling algorithm used in all third and fourth-generation cellular systems.
His research interests are in information theory and its applications in various fields, including wireless communication, computational biology and machine learning.
Reception in the Bowen Hall Atrium to follow the presentation.
This seminar is supported by the Korhammer Lecture Series Fund.