Molecular distance geometry optimization using geometric build-up and evolutionary techniques on GPU

We present a combination of methods addressing the molecular distance problem, implemented on a graphic processing unit. First, we use geometric build-up and depth-first graph traversal. Next, we refine the solution by simulated annealing. For an exact but sparse distance matrix, the build-up method reconstructs the 3D structures with a root-mean-square error (RMSE) in the order of 0.1 Å. Small and medium structures (up to 10,000 atoms) are computed in less than 10 seconds. For the largest structures (up to 100,000 atoms), the build-up RMSE is 2.2 Å and execution time is about 540 seconds. The performance of our approach depends largely on the graph structure. The SA step improves accuracy of the solution to the expense of a computational overhead.