This talk will overview our recent algorithmic work related to designing a messenger RNA (mRNA) vaccine for COVID-19. Designing an mRNA sequence to achieve high stability and protein yield is a challenging problem due to the exponentially large search space (e.g., there are 10^632 possible mRNA sequence candidates). We describe two on-going efforts at solving this problem, both using our new linear-time algorithms for intelligently processing sequence data. In the first effort, the Das Lab at Stanford Medical School uses a crowd-sourcing approach to let game players design stable sequences. To evaluate sequence stability (free energy), they use our LinearFold algorithm due to its computational efficiency compared to prior methods. In the second approach, we directly search for the optimal sequence in this exponentially large space via dynamic programming. We develop an approach that can design the optimal mRNA vaccine candidates in ~1.5 hours with exact search, or just 16 minutes using an approximate search with minimal loss in energy.
Liang Huang is currently an Assistant Professor of EECS at Oregon State University and Distinguished Scientist (part-time) at Baidu Research USA. Before that he was Assistant Professor for three years at the City University of New York (CUNY) and a part-time Research Scientist with IBM's Watson Group. He graduated in 2008 from Penn and has worked as a Research Scientist at Google and a Research Assistant Professor at USC/ISI. Most of his work develops fast algorithms and provable theory to speedup large-scale natural language processing, structured machine learning, and computational structural biology.