Constrained global optimization for estimating molecular structure from atomic distances

Finding optimal three-dimensional molecular configurations based on a limit ed amount of experimental and/or theoretical data requires efficient nonlin ear optimization algorithms. Optimization methods must be able to find atom ic configurations that are close to the absolute, or global, minimum error and also satisfy known physical constraints such as minimum separation dist ances between atoms (based on van der Waals interactions). The most difficu lt obstacles in these types of problems are that 1) using a limited amount of input data leads to many possible local optima and 2) introducing physic al constraints, such as minimum separation distances, helps to limit the se arch space but often makes convergence to a global minimum more difficult. We introduce a constrained global optimization algorithm that is robust and efficient in yielding near-optimal three-dimensional configurations that a re guaranteed to satisfy known separation constraints. The algorithm uses a n atom-based approach that reduces the dimensionality and allows for tracta ble enforcement of constraints while maintaining good global convergence pr operties. We evaluate the new optimization algorithm using synthetic data f rom the yeast phenylalanine tRNA and several proteins, all with known cryst al structure taken from the Protein Data Bank. We compare the results to co mmonly applied optimization methods, such as distance geometry, simulated a nnealing, continuation, and smoothing. We show that compared to other optim ization approaches, our algorithm is able combine sparse input data with ph ysical constraints in an efficient manner to yield structures with lower ro ot mean squared deviation.