Machine Learning Research

Machine Learning Techniques to Warm Start Solutions to NP-Hard Problems

What’s Involved in this Research?

In mathematics, there is a certain category of problems designated as non-deterministic polynomial-time problems (NP problems) that grow increasingly hard and sometimes impossible to solve as the numbers of variables in the problems increase.

Some problems have so many potential solutions that it would take all the time left in the universe to analyze each solution to find the ‘best solution’, the ‘optimal solution’ or even to find one solution that works pretty good for us.

In fact, there is a one in ten to the fiftieth chance that a random protein structure will provide anything but mush or junk.

Using NP-hard problems in the quest to engineer DNA

If we found a way to create proteins and analyze their structure (folding/unfolding) very quickly using computer simulation, then we could back into creating proteins by engineering DNA that does specific things we need it to do. Even getting close can be helpful. If the DNA creates something like plastic instead of bone, then we might be able to use that. We want the computer to learn by itself to formulate solutions problems for these discontinuous problems.  A simple DNA sequence creates, say a protein. What is the relationship between sequences and proteins? This is discontinuous. However, we believe that there are relationships, tensors, derivatives and information that are in the problem that the computer can find that would otherwise take us thousands of years to find.

How Students Benefit

Students who like mathematics and computer programming work with professors to find algorithms that auto-create complex mathematical models for sequencing. This can be termed sorting-sequencing machine learning.

This is one of the foremost problems in mathematics today. Being able to say you worked on an algorithm to solve the most complex mathematical problem in the world is helpful.

Also, most systems problems are NP-hard problems. We can’t fathom nor can a computer fathom all the possible solutions for a system.

However, there are algorithms that solve these types of smaller problems quite quickly for ISE.

Impact on Society

This research goes to the heart of simulating folding/unfolding proteins which are the building blocks for all life.  If it is possible to reduce computational time, then much can be explored in terms of medicines, poisons, antidotes, etc.