A Sudoku-Solving Algorithm Holds Promise for Protein Medicine

Sep 23, 2020
Jovana Drinjakovic
protein structure and sudoku puzzle

Computational biologists in the Donnelly Centre have developed an artificial intelligence algorithm that has the potential to create novel protein molecules as finely tuned therapeutics.

The team led by Philip M. Kim, a professor of molecular genetics and computer science at U of T’s Faculty of Medicine, have developed ProteinSolver, a graph neural network that can design a fully new protein to fit a given geometric shape. The researchers took inspiration from the Japanese number puzzle Sudoku, whose constraints are conceptually similar to those of a protein molecule.

Their findings are published in the journal Cell Systems.

"The parallel with Sudoku becomes apparent when you depict a protein molecule as a network,” says Kim, adding that the portrayal of proteins in graph form is standard practice in computational biology.

A newly synthesized protein is a string of amino-acids, stitched together according to the instructions in that protein’s gene code. The amino-acid polymer then folds in and around itself into a three-dimensional molecular machine that can be harnessed for medicine.

A protein converted into a graph looks like a network of nodes, representing amino-acids, connected by edges, which are the distances between them within the molecule. By applying principles from graph theory, it then becomes possible to model the molecule’s geometry for a specific purpose to, for example, neutralize an invading virus or shut down an overactive receptor in cancer.

Proteins make good drugs thanks to three-dimensional features on their surface with which they bind cellular targets with more precision than the synthetic small molecule drugs that tend to be broad spectrum and can lead to harmful off-target side effects.

Just over a third of all medications approved over the last couple of years were proteins, which also make up the vast majority of top ten drugs globally, Kim said. Insulin, antibodies and growth factors are only some examples of injectable cellular proteins, also known as biologics, already in use.

Designing proteins from scratch remains incredibly difficult however, owing to the vast number of possible structures to choose from.

“The main problem in protein design is that you have a very large search space,” says Kim, referring to the many ways in which the 20 naturally occurring amino-acids can be combined into protein structures.

“For a standard-length protein of 100 amino-acids, there are 20 to the power of 100 possible molecular structures, that’s more than the number of molecules in the universe,” he says.

Kim decided to turn the problem on its head, by starting with a three-dimensional structure and working out its amino-acid composition.

“It’s the protein design, or the inverse protein folding problem – you have a shape in mind and you want a sequence (of amino-acids) that will fold into that shape. Solving this is in some ways more useful than protein folding, as you can in theory generate new proteins for any purpose,” says Kim.

That’s when Alexey Strokach, a PhD student in Kim’s lab, turned to Sudoku, after learning in a class about its relatedness to molecular geometry.

In Sudoku, the goal is to find missing values in a sparsely filled grid by observing a set of rules and the existing number values.

Individual amino-acids in a protein molecule are similarly constrained by their neighbours. Local electrostatic forces ensure that amino-acids carrying opposite electric charge pack closely together while those with the same charge are pulled apart.

Strokach first built the constraints found in Sudoku into a neural network algorithm. He then trained the algorithms on a vast database of available protein structures and their amino-acid sequences from across the tree of life. The goal was to teach the algorithm, ProteinSolver, the rules, honed by evolution over millions of years, of packing amino-acids together into smaller folds. Applying these rules to the engineering process should increase the chances of having a functional protein at the end.

The researchers then tested ProteinSolver by giving it existing protein folds and asking it to generate amino-acid sequences that can build them. They then took the novel computed sequences, which do not exist in nature, and manufactured the corresponding protein variants in the lab. The variants folded into the expected structures, showing that the approach works.

In its current form, ProteinSolver is able to compute novel amino-acid sequences for any protein fold known to be geometrically stable. But the ultimate goal is to engineer novel protein structures with entirely new biological functions, as new therapeutics, for example.

“The ultimate goal is for someone to be able to draw a completely new protein by hand and compute sequences for that, and that’s what we are working on now,” says Strokach.

The researchers made ProteinSolver and the code behind it open source and available to the wider research community through a user-friendly website.

The Canadian Institutes of Health Research and the Natural Sciences and Engineering Research Council provided funding this work.


Temerty Medicine
RT : Have you listened to Ep 82 Making Strides: Amputation & Prosthetics yet? 🎧 Aristotle Domingo () shared his… https://t.co/HaGTiTk2u9
Temerty Medicine
RT : To avoid a 'twindemic' health officials are telling Canadians to following guidelines for the pandemic, and to get… https://t.co/mvEkEwlqrA
Temerty Medicine
“If we can't learn from it then it has little to no scientific value.” Scientists are challenging their colleagues… https://t.co/KcWqs2WNVe

Researchers are mobilizing against the novel SARS-CoV-2 coronavirus and COVID-19.

Make a gift and support their important work.
Sep 23 – Nov 11
Safer Opioid Prescribing
Course | 7:00am–9:00pm
Oct 5 – May 6
Academic Health Leadership Training – Now Accepting Applications 2020-2021 Cohort
Course | 8:00am–5:00pm
Oct 13 – Jun 8
Certificate Program in CPD Foundations
Course | 12:00pm–1:30pm
Oct 21 Creating AODA-Compliant Documents for the Web
Webinar | 10:30am–12:00pm
Oct 22 Medicine and the Machine: The Artificial Intelligence Health Revolution
Temerty Medicine Talk | 12:30pm–1:15pm
Oct 23 U of T Oncology Continuing Education Zoom Rounds - October 2020
Grand Rounds | 8:00am–9:00am
24 – 26
Organ Imaging Review
Symposium | 7:15am–5:15pm