Discretization orders for distance geometry problems

Given a weighted, undirected simple graph G = (V, E, d) (where \({d:E\to\mathbb{R}_+}\)), the distance geometry problem (DGP) is to determine an embedding \({x:V\to\mathbb{R}^K}\) such that \({\forall \{i,j\} \in E\;\|x_i-x_j\|=d_{ij}}\) . Although, in general, the DGP is solved using continuous methods, under certain conditions the search is reduced to a discrete set of points. We give one such condition as a particular order on V. We formalize the decision problem of determining whether such an order exists for a given graph and show that this problem is NP-complete in general and polynomial for fixed dimension K. We present results of computational experiments on a set of protein backbones whose natural atomic order does not satisfy the order requirements and compare our approach with some available continuous space searches.     

The discretizable molecular distance geometry problem

Given a simple weighted undirected graph G=(V,E,d) with d:E???₊, the Molecular Distance Geometry Problem (MDGP) consists in finding an embedding x:V???³ such that ??x _u ?x _v ??=d _uv for each {u,v}??E. We show that under a few assumptions usually satisfied in proteins, the MDGP can be formulated as a search in a discrete space. We call this MDGP subclass the Discretizable MDGP (DMDGP). We show that the DMDGP is NP-hard and we propose a solution algorithm called Branch-and-Prune (BP). The BP algorithm performs remarkably well in practice in terms of speed and solution accuracy, and can be easily modified to find all incongruent solutions to a given DMDGP instance. We show computational results on several artificial and real-life instances.     

The t-Cost-m-neighbour distance in digital geometry

A generalized distance measure called t-Cost-m-Neighbour (tCmN) distance in n-D grid point space is presented. Its properties as a metric are examined. It is shown that m-neighbour [2] and t-cost [3] distances evolve as subclasses of tCmN. An efficient method for computing the tCmN distance value between a pair of points is discussed.     

Good distance graphs and the geometry of matrices

Denote by G=(V,∼) a graph which V is the vertex set and ∼ is an adjacency relation on a subset of V×V. In this paper, the good distance graph is defined. Let (V,∼) and (V^′,∼^′) be two good distance graphs, and φ:V→V^′ be a map. The following theorem is proved: φ is a graph isomorphism ⇔φ is a bounded distance preserving surjective map in both directions ⇔φ is a distance k preserving surjective map in both directions (where k<diam(G)/2 is a positive integer), etc. Let D be a division ring with an involution such that both |F∩Z_D|?3 and D is not a field of characteristic 2 with D=F, where and Z_D is the center of D. Let H_n(n?2) be the set of n×n Hermitian matrices over D. It is proved that (H_n,∼) is a good distance graph, where A∼B⇔rank(A-B)=1 for all A,B∈H_n.     

Recent advances on the interval distance geometry problem

We discuss a discretization-based solution approach for a classic problem in global optimization, namely the distance geometry problem (DGP). We focus our attention on a particular class of the DGP which is concerned with the identification of the conformation of biological molecules. Among the many relevant ideas for the discretization of the DGP in the literature, we identify the most promising ones and address their inherent limitations to application to this class of problems. The result is an improved method for estimating 3D structures of small proteins based only on the knowledge of some distance restraints between pairs of atoms. We present computational results showcasing the usefulness of the new proposed approach. Proteins act on living cells according to their geometric and chemical properties: finding protein conformations can be very useful within the pharmaceutical industry in order to synthesize new drugs.     

An application-based characterization of dynamical distance geometry problems

The dynamical distance geometry problem (dynDGP) is the problem of finding a realization in a Euclidean space of a weighted undirected graph G representing an animation by relative distances, so that the distances between realized vertices are as close as possible to the edge weights. In the dynDGP, the vertex set of the graph G is the set product of V, representing certain objects, and T, representing time as a sequence of discrete steps. We suppose moreover that distance information is given together with the priority of every distance value. The dynDGP is a special class of the DGP where the dynamics of the problem comes to play an important role. In this work, we propose an application-based characterization of dynDGP instances, where the main criteria are the presence or absence of a skeletal structure, and the rigidity of such a skeletal structure. Examples of considered applications include: multi-robot coordination, crowd simulations, and human motion retargeting.     

Problems of distance geometry and convex properties of quadratic maps

A weighted graph is calledd-realizable if its vertices can be chosen ind-dimensional Euclidean space so that the Euclidean distance between every pair of adjacent vertices is equal to the prescribed weight. We prove that if a weighted graph withk edges isd-realizable for somed, then it isd-realizable for (this bound is sharp in the worst case). We prove that for a graphG withn vertices andk edges and for a dimensiond the image of the so-called rigidity map ℝ ^dn →ℝ ^k is a convex set in ℝ ^k provided . These results are obtained as corollaries of a general convexity theorem for quadratic maps which also extends the Toeplitz-Hausdorff theorem. The main ingredients of the proof are the duality for linear programming in the space of quadratic forms and the “corank formula” for the strata of singular quadratic forms. This research was supported by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C0027.     

-analogue triangular numbers and distance geometry

The so-called ``-identities' play a major role in classical combinatorics. Most of them can be viewed as arising somehow in the context of hypergeometric series. Here we present a ``sum of squares' identity involving -analogues of the triangular numbers that, by contrast, arises in the context of distance geometry.

     

Extensions of distance preserving mappings in euclidean and hyperbolic geometry

Suppose that X is a real inner product space of (finite or infinite) dimension at least 2. A distance preserving mapping , where is a (finite or infinite) subset of a finite-dimensional subspace of X, can be extended to an isometry of X. This holds true for euclidean as well as for hyperbolic geometry. To both geometries there exist examples of non-extentable distance preserving , where S is not contained in a finite-dimensional subspace of X.     

Applications of a distance formula in hyperbolic plane geometry

This note may be used in model-based courses on the classical geometries. Given two points P₁(x₁, y₁) and P₂(x₂, y₂) in the Poincaré upper half-plane model of hyperbolic plane geometry with x₁≠x₂, a Cartesian equation of thebowed geodesic passing through P₁ and P₂ and an integral expression for the hyperbolic distance between P₁ and P₂ are developed. These formulas depend only on the coordinates of P₁ and P₂, and it is easy to implement them with the numerical integrators of modern technology. The distance formula is used to find the coordinates of points of division along a bowed geodesic and, thus, leads to activities discovering that results such as Ceva's Theorem are valid in hyperbolic geometry. The distance formula is also used in verifying that the model satisfies the axioms of absolute geometry.     

Solving molecular distance geometry problems by global optimization algorithms

In this paper we consider global optimization algorithms based on multiple local searches for the Molecular Distance Geometry Problem (MDGP). Three distinct approaches (Multistart, Monotonic Basin Hopping, Population Basin Hopping) are presented and for each of them a computational analysis is performed. The results are also compared with those of two other approaches in the literature, the DGSOL approach (Moré, Wu in J. Glob. Optim. 15:219–234, 1999) and a SDP based approach (Biswas et al. in An SDP based approach for anchor-free 3D graph realization, Technical Report, Operations Research, Stanford University, 2005).     

Discretization orders and efficient computation of cartesian coordinates for distance geometry

Distance geometry is a class of problems where the position of points in space is to be identified by using information about some relative distances between these points. Although continuous approaches are usually employed, problems belonging to this class can be discretized when some particular assumptions are satisfied. These assumptions strongly depend on the order in which the points to be positioned are considered. We discuss new discretization assumptions that are weaker than previously proposed ones, and present a greedy algorithm for an automatic identification of discretization orders. The use of these weaker assumptions motivates the development of a new method for computing point coordinates. Computational experiments show the effectiveness and efficiency of the proposed approaches when applied to protein instances.     

Assigned and unassigned distance geometry: applications to biological molecules and nanostructures

Considering geometry based on the concept of distance, the results found by Menger and Blumenthal originated a body of knowledge called distance geometry. This survey covers some recent developments for assigned and unassigned distance geometry and focuses on two main applications: determination of three-dimensional conformations of biological molecules and nanostructures.     

Big Heegaard distance implies finite mapping class group

We show that if M is a closed three manifold with a Heegaard splitting with sufficiently big Heegaard distance then the subgroup of the mapping class group of the Heegaard surface, whose elements extend to both handlebodies is finite. As a corollary, this implies that under the same hypothesis, the mapping class group of M is finite.     

On the Alexandrov problem of distance preserving mapping

In this paper the author has studied the Alexandrov problem of area preserving mappings in linear 2-normed spaces and has provided some remarks for the generalization of earlier results of H.Y. Chu, C.G. Park and W.G. Park.In addition the author has introduced the concept of linear (2,p)-normed spaces and for such spaces he has solved the Alexandrov problem.     

On the existence of certain measures appearing in distance geometry

Abstract. We prove the following result: Let X be a compact connected Hausdorff space and f be a continuous function on X x X. There exists some regular Borel probability measure m\mu on X such that the value of¶¶ ò\limit _X f(x,y)dm(y)\int\limit _X f(x,y)d\mu (y) is independent of the choice of x in X if and only if the following assertion holds: For each positive integer n and for all (not necessarily distinct) x₁,x₂,...,x_n,y₁,y₂,...,y_n in X, there exists an x in X such that¶¶ ?_i=1ⁿ f(x_i,x)=?_i=1ⁿ f(y_i,x).\sum\limits _{i=1}^n f(x_i,x)=\sum\limits _{i=1}^n f(y_i,x).