University Professor Ming Li has received the 2020 Lifetime Achievement Award in Computer Science from CS-Can|Info-Can, the non-profit professional society dedicated to representing all aspects of computer science and the interests of the discipline across the nation. Conferred annually since 2014, the prestigious lifetime achievement award recognizes faculty members in departments, schools and faculties of computer science who have made outstanding and sustained achievement in research, teaching and service.
“On behalf of CS-Can|Info-Can, it is my great pleasure to inform you that you have been awarded a 2020 CS-Can|Info-Can Lifetime Achievement Award in Computer Science,” wrote Kelly Lyons, Chair of the 2020 CS-Can|Info-Can Awards Committee in her letter. “Congratulations on this tremendous recognition by your computer science peers in Canada.”
University Professor Ming Li, the Canada Research Chair in Bioinformatics, is known for his fundamental contributions to Kolmogorov complexity, bioinformatics, machine learning theory, and analysis of algorithms.
“Congratulations to Ming,” said Raouf Boutaba, Professor and Director of the David R. Cheriton School of Computer Science. “Ming is a pioneer in Kolmogorov complexity, which has laid the foundation for a modern information theory. He is also a pioneer in computational biology, having introduced both algorithmic ideas into the field as well as demonstrated how computer scientists can contribute to real-world problems from protein sequencing to develop novel treatments for cancer to analyzing DNA sequencing data for studies in evolutionary biology.”
University Professor Li is the eighth faculty member in the Cheriton School of Computer Science to receive a Lifetime Achievement Award from CS-Can|Info-Can. Previous recipients are University Professor M. Tamer Özsu (2018 recipient), Distinguished Professor Emeritus Don Cowan (2017 recipient), Professor Emeritus Ric Holt (2017 recipient), Distinguished Professor Emeritus Janusz Brzozowski (2016 recipient), University Professor J. Ian Munro (2016 recipient), Distinguished Professor Emeritus Alan George (2015 recipient), and Distinguished Professor Emeritus Frank Tompa (2015 recipient).
About University Professor Ming Li
University Professor Li completed his PhD at Cornell University in 1985, followed by a postdoctoral fellowship at Harvard. In 1988 he joined what was then the Department of Computer Science at the University of Waterloo.
University Professor Li received the prestigious E.W.R. Steacie Memorial Fellowship in 1996. He was named a University Professor by the University of Waterloo in 2009 and won the Killam Prize in 2010 for his contributions in computer science. He is the Canada Research Chair in Bioinformatics, and a Fellow of the Royal Society of Canada, Fellow of the Association for Computing Machinery, and Fellow of the Institute of Electrical and Electronics Engineers.
University Professor Li has contributed significantly to developing a modern information theory and in shaping the field of computational biology. We live in an information society, but what exactly is information? Does a theory govern information-carrying entities similar to what Newtonian mechanics governs in classical physics? The answer is yes, and it is called Kolmogorov complexity — a field that University Professor Li and his colleagues introduced to computer science and have extended to many other fields.
Kolmogorov complexity and its applications
Kolmogorov complexity provides a universal measure of information, information content, and randomness. University Professor Li and his colleagues have extended Kolmogorov complexity to two sequences that leads to a universal metric of information distance. They have also connected information to thermodynamics and computed the ultimate thermodynamics cost of creating or erasing a sequence. This has led to zero-shot learning — a problem widely studied in computer vision, natural language processing and machine perception in which, at test stage, a learner recognizes objects from classes not previously seen at a training stage.
In an ACM Special Interest Group on Knowledge Discovery in Data paper, Keogh, Lonardi and Ratanamahatana demonstrated that University Professor Li’s parameter-free information distance method was better than all 51 methods for time series clustering. Since then, more than 1,000 papers have applied his method to a huge and diverse range of problems — language classification, question and answer, cancer cell line identification, music classification, phylogeny, anomaly detection, software measurement and obfuscation, malware detection, nucleosome occupancy, protein sequencing and structure classification, fetal heart rate tracing, deep learning, and many more.
Expected-case analysis of algorithms is a major challenge in computer science, as it requires averaging over all inputs. A Kolmogorov random string holds the key to solving this problem. If an algorithm on one typical Kolmogorov random input is analyzed it automatically gives the average case over all inputs. University Professor Li and his colleagues used this method to solve many open questions in theoretical computer science. The complete history and theory of Kolmogorov complexity, together with many applications, are summarized and presented in Professors Li and Vitányi’s book An Introduction to Kolmogorov Complexity and its Applications, a widely read computer science classic that received a McGuffey Longevity Award in 2020.
Computational biology
University Professor Li has contributed to many other scientific fields, most notably to bioinformatics. DNA and RNA sequences can be amplified using polymerase chain reaction — or PCR — a laboratory technique used to make millions or even billions of copies of a specific DNA or RNA sample so it can be studied in detail, making molecular and genetic analyses possible. Protein sequences, however, are much harder to analyze as they cannot be similarly amplified for study.
In 2016, University Professor Li and his team published in Nature Scientific Report the first complete protocol to sequence a complete monoclonal antibody protein. They have since improved their computational techniques and published their results in a variety of prestigious journals, including in the Proceedings of the National Academy of Sciences in 2017, Nature Methods in 2019, and most recently in Nature Machine Intelligence in 2020.
University Professor Li co-founded and served as an editor-in-chief for Journal of Bioinformatics and Computational Biology. Through this journal and his innovations, he played a major role in reshaping the early heuristic bioinformatics into the current computer science–based computational biology. Furthermore, his elegant algorithms and ideas have led to commercially viable products that have made a tremendous impact on the proteomics healthcare industry.
