The geometric build-up algorithm determines an atom, one at a time, by using a metric basis that can define the atom.

With qunfeng dong, Atilla Sit, Vlad Sukhoy, Zack voller, di wu, ...

Distance Based Protein Modeling

A distance based approach for protein modeling uses the inter-atomic or inter-residual distances to determine and analyze protein structures. In principle, the coordinates of the atoms and hence the protein structure can be determined if the distances for all pairs of atoms are given. The problem is polynomial-time solvable. However, in practice, only a subset of distances may be available, and the problem can be computationally intractable. The distances may only be estimated within certain ranges as well, which further complicates the problem: There can be an ensemble of structures, instead of an unique one, satisfying the constraints. In any case, the problem of determining the coordinates of the atoms in a molecule for a given set of distance constraints is called the molecular distance geometry problem. It is a central problem in distance based protein modeling.

 

We have developed a geometric build-up algorithm for solving the molecular distance geometry problem. The algorithm can solve the problem in linear time if the exact distances for all pairs of atoms are given, while a conventional SVD algorithm requires O(n²) time. 

 

The basic geometric build-up algorithm has been extended to handling sparse and inexact distances and to generating unique as well as multiple rigid protein structures. 

 

We are developing a geometric build-up algorithm for problems with distance ranges using optimization methods and interval methods. The algorithm will be able to generate ensembles of structures that are allowed by the given distance ranges.