David Tse | EECS at UC Berkeley2018 Viterbi Lecture

Ming Hsieh Department of Electrical Engineering


“Maximum likelihood Genome Sequencing”


David Tse
Thomas Kailath and Guanghan Xu Professor in Engineering
Stanford University



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 1995 to 2014, he was on the faculty of the University of California at Berkeley. He received the Claude E. Shannon Award in 2017 and was elected member of the U.S. National Academy of Engineering in 2018. Previously, he received a NSF CAREER award in 1998, the Erlang Prize from the INFORMS Applied Probability Society in 2000 and the Frederick Emmons Terman Award from the American Society for Engineering Education in 2009. He received multiple best paper awards, and is the inventor of the proportional-fair scheduling algorithm used in all third and fourth-generation cellular systems.


Published on February 3rd, 2023

Last updated on August 2nd, 2023