Title:
Distance Geometry Problem for Protein Modeling via Geometric Buildup
Abstract:
A well-known problem in protein modeling is the determination of
the structure of a protein with a given set of inter-atomic or
inter-residue distances obtained from either physical experiments or
theoretical estimates. A general form of the problem is known as the
distance geometry problem in mathematics, the graph embedding problem in
computer science, and the multidimensional scaling problem in statistics.
The problem has applications in many other scientific and engineering
fields as well such as sensor network localization, image recognition, and
protein classification. We describe the formulations and complexities of
the problem in its various forms, and introduce a so-called geometric
buildup approach to the problem. We present the general algorithm and
discuss related computational issues including control of numerical errors,
determination of rigid vs. unique structures, and tolerance of distance
errors. The theoretical basis of the approach is established based on the
theory of distance geometry. A group of necessary and sufficient conditions
for the determination of a structure with a given set of distances using a
geometric buildup algorithm are justified. The applications of the
algorithm to model protein problems are demonstrated.