University of Waterloo

Professor Ming Li has made major contributions to the creation of a modern information theory (Kolmogorov complexity) and in shaping the field of Computational Biology. Li completed his PhD at Cornell University in 1985, followed by a postdoctoral fellowship at Harvard. A University Professor at the University of Waterloo, he won Killam Prize in 2010 for his contributions in Computer Science.

We live in an information society. What is information? Is there a theory that governs information carrying entities similar to that of Newtonian mechanics to the classical world? The answer is Kolmogorov complexity. Kolmogorov complexity provides a universal measure of information, information content, and randomness. Li and his colleagues have extended Kolmogorov complexity to two sequences that lead 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 actually led to zero-shot learning. In a SIGKDD04 paper (pp. 206-215), Keogh, Lonardi and Ratanamahatana demonstrated that Li’s parameter-free information distance method was better than all 51 methods for time series clustering found in the seven top data mining conferences. Over 1,000 papers have applied Li’s method to language classification, question and answer, cancer cell line identification, music classification, phylogeny, anomaly detection, software measurement and obfuscation, malware detection, nucleosome occupancy, protein sequence/structure classification, fetal heart rate tracing, COVID-19 analysis, deep learning, and many more.

Expected-case analysis of algorithms is a major challenge in Computer Science, as one has to average over all possible inputs. A Kolmogorov random string holds the key to this problem. It turns out that if one analyzes an algorithm on one typical Kolmogorov random input, then that automatically gives the average case over all inputs. 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 these works and many applications were digested in Li and Vitányi’s book “An Introduction to Kolmogorov Complexity and its Applications”. The book is considered a classic text in Computer Science and widely read. It won the McGuffey Longevity Award in 2020.

Li has worked in many other scientific areas, including his pioneering contributions to the field of Computational Biology. In particular, he has made substantial contributions to the area of Bioinformatics. Currently very relevant, some of his recent work is related to COVID-19 neutralizing antibody sequencing. DNA sequences have pairing mechanisms; hence, one can use PCR to sequence them, as in COVID-19 RNA tests. Protein sequences, on the other hand, cannot use PCR. In 2016, Li and his team published first complete protocol to sequence a complete monoclonal antibody in Nature Scientific Report. They then improved the process in PNAS’2017, Nature Methods’2019, then in Nature Machine Intelligence 2021 (accepted). These intensive research studies have created an industry of antibody sequencing. During the COVID-19 pandemic, Li’s team has helped to process and analyze many antibody sequences.

Li has been awarded the prestigious NSERC E.W.R. Steacie Memorial Fellowship and the Killam Research Fellowship. He is a Tier I Canada Research Chair in Bioinformatics and is a Fellow of the Royal Society of Canada, ACM, and IEEE.  He has also won the Ontario Premier’s Discovery Award for Innovation Leadership.

View all winners