Project Proposal:
Optimal from an electron's reference frame: energy minimizing binding configurations
Jocelyn Sunseri
Main Project Page
Summary
I want to write a (mostly) GPU program that returns a minimum energy configuration of two molecules. This involves estimating the energy of the current configuration as well as the forces atoms in the system would experience based on those positions, doing a line search for the next move toward a minimum, and then updating the atom coordinate positions based on the net force they would experience.
Motivation

Physical systems are often found in a configuration that is located at a minimum of energy. For this reason, predicting such configurations is of great practical interest - if you want to predict how a system might behave on average, you should try to identify what its minimum energy states look like. Unfortunately, for systems with many degrees of freedom, it rapidly becomes intractable to derive a closed-form solution for what these states look like. Instead it is common to use optimization strategies to find a local minimum from a given starting configuration, or to generate an ensemble of such local minima.

In particular, starting configurations may be generated using a particular algorithm - for example, a similarity search based on the known configuration of another system, or a Monte Carlo method. To generate states we are more likely to observe from these configurations, we should slightly perturb them until they reach a local minimum, which is more likely to be an observable state of the system than a randomly generated starting configuration.

The algorithm that is practical for performing this procedure depends on the system of interest. In my case, the system of interest is two molecules that may bind to one another, and the goal is to identify a putative binding pose and rank it energetically compared with other such potentially binding pairs. This type of method is used in developing pharmaceuticals, where a "virtual screen" can inexpensively replace a conventional "high-throughput screen." At its heart, it is a type of constrained n-body problem.

Background

The procedure for doing the energy minimization part of this project is: evaluate the scoring function (typically a simpler formula meant to approximate the energy) for the current configuration, use the forces on the atoms in the current configuration to do a search for where to move next, generate the atom positions in terms of internal coordinates, determine the net motion of each atom using a torsion tree representation of the molecule, perform a coordinate update, and then repeat the whole procedure until convergence.

It is desirable to accelerate this process because in practice it is often being performed for millions of molecules that each may consist of thousands of atoms. In our case, we maintain a webserver that allows anyone to perform virtual screening in their browser, including energy minimization of the poses returned by a similarity search through the database based on a starting query typically generated by the structure of a compound known to bind to the compound of interest. We run the backend on our servers and at high-traffic times, the energy minimization step in particular can be very computationally intensive.

Challenge

It isn't straightforward to parallelize our existing algorithms. I parallelized the scoring function evaluation last month, and to make it performant I used a reduction algorithm that utilized SHUFL intrinsics. The other steps, including the line search, conversion to internal coordinates, torsion tree, and coordinate updates, may require significant modifications in order to be made parallelizable.

Resources

We have an existing CPU implementation. Over the last month I have moved the scoring function evaluation to the GPU and have already observed a small speedup from doing this. I pretty much just need a decent NVIDIA graphics card for the purposes of this project, and I have a 780 and a TitanX in my workstation, as well as access to plenty of other graphics cards of similar capabilities (both the lower end and the higher end).

I don't know of anyone else who has implemented a GPU docking/minimization program.

Goals/Deliverables

The goal is to get the whole energy minimization component of our software to run on the GPU. In the process, I will initially implement a multithreaded CPU version (which will likely parallelize over separate small molecules, and which will trivially allow the GPU version to be parallelized over these as well). If there is time, I will start working on parallelizing the docking algorithm, too. There is also the potential for doing scoring function development, in particular with convolutional neural nets, since our group is currently working on that too and is developing the same software to do it.

Platform

Any NVIDIA GPU of compute capability 3.0 or greater.

Proposed Schedule

Week What We Plan To Do
Apr 1-7 Multithreaded CPU version to trivially parallelize over multiple ligands. Address minor issues with current GPU implementation of scoring function evaluation.  
Apr 8-14 Move line search onto GPU.  
Apr 15-21 Same as last week.  
Apr 22-28 Move coordinate update onto the GPU. This includes conversion to internal coordinates, torsion tree, etc.  
Apr 29-May 5 Same as last week. Time to finish everything I didn't finish already.