The Viterbi Lecture is named for Andrew Viterbi, the legendary communications figure who helped open the doors to the digital age with the Viterbi Algorithm, an original mathematical formula for eliminating signal interference.
Today, his algorithm is used in all four international standards for digital cellular telephones, as well as in data terminals, digital satellite broadcast receivers and deep space telemetry.
Thursday, April 12th, 2018, 3 – 5PM, EEB 132
Title: Maximum Likelihood Genome Sequencing
Genome sequencing is one of the biggest breakthroughs in science in the past two decades. Modern sequencing methods use linking data at multiple scales to reconstruct pertinent information about the genome. Many such reconstruction problems can be formulated as maximum likelihood sequence decoding from noisy linking data. We discuss two in this talk: haplotype phasing, the problem of sequencing genomic variations on each of the maternal and paternal chromosomes, and genome scaffolding, the problem of finishing genome assembly using long-range 3D contact data. While maximum likelihood sequence decoding is NP-hard in both of these problems, spectral and linear programming relaxations yield efficient approximation algorithms that can provably achieve the information theoretic limits and perform well on real data. These results parallel the biggest success of information theory: efficiently achieving the fundamental limits of communication.
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 the Thomas Kailath and Guanghan Xu Professor at Stanford University.
David Tse was elected member of the U.S. National Academy of Engineering in 2018. He was the recipient of the Claude E. Shannon Award in 2017. 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.