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.