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.