Distance geometry and protein loop modeling Labiak, Rodrigo; Lavor, Carlile; Souza, Michael
Journal of computational chemistry,
February 15, 2022, Volume:
43, Issue:
5
Journal Article
Peer reviewed
Due to the role of loops in protein function, loop modeling is an important problem in computational biology. We present a new approach to loop modeling based on a combinatorial version of distance ...geometry, where the search space of the associated problem is represented by a binary tree and a branch‐and‐prune method is defined to explore it, following an atomic ordering previously given. This ordering is used to calculate the coordinates of atoms from the positions of its predecessors. In addition to the theoretical development, computational results are presented to illustrate the advantage of the proposed method, compared with another approach of the literature. Our algorithm is freely available at https://github.com/michaelsouza/bpl.
Minimum and maximum values for dN1Cα2.
The problem of 3D protein structure determination using distance information from nuclear magnetic resonance (NMR) experiments is a classical problem in distance geometry. NMR data and the chemistry ...of proteins provide a way to define a protein backbone order such that the distances related to the pairs of atoms
{
i
-
3
,
i
}
,
{
i
-
2
,
i
}
,
{
i
-
1
,
i
}
are available, implying a combinatorial method to solve the problem, called branch-and-prune (BP). There are two main steps in BP algorithm: the first one (the branching phase) is to intersect three spheres centered at the positions for atoms
i
-
3
,
i
-
2
,
i
, with radius given by the atomic distances
d
i
-
3
,
i
,
d
i
-
2
,
i
,
d
i
-
1
,
i
, respectively, to obtain two possible positions for atom
i
; and the second one (the pruning phase) is to check if additional spheres (related to distances
d
j
,
i
,
j
<
i
-
3
) can be used to select one of the two possibilities for atom
i
. Differently from distances
d
i
-
2
,
i
,
d
i
-
1
,
i
(associated to bond lenghts and bond angles), distances
d
j
,
i
,
j
≤
i
-
3
, may not be precise. BP algorithm has difficulties to deal with uncertainties, and this paper proposes the oriented conformal geometric algebra to take care of intersection of spheres when their centers and radius are not precise.
This is a partial account of the fascinating history of distance geometry. We make no claim to completeness, but we do promise a dazzling display of beautiful, elementary mathematics. We prove ...Heron's formula, Cauchy's theorem on the rigidity of polyhedra, Cayley's generalization of Heron's formula to higher dimensions, Menger's characterization of semimetric spaces, a result of Gödel on metric spaces on the sphere, and Schoenberg's equivalence of distance and positive semidefinite matrices, which is at the basis of multidimensional scaling.
3D protein structures and nanostructures can be obtained by exploiting distance information provided by experimental techniques, such as nuclear magnetic resonance and the pair distribution function ...method. These are examples of instances of the unassigned distance geometry problem (uDGP), where the aim is to calculate the position of some points using a list of associated distance values not previoulsy assigned to the pair of points. We propose new mathematical programming formulations and a new heuristic to solve the uDGP related to molecular structure calculations. In addition to theoretical results, computational experiments are also provided.
The discretizable molecular distance geometry problem (DMDGP) is related to the determination of 3D protein structure using distance information detected by nuclear magnetic resonance (NMR) ...experiments. The chemistry of proteins and the NMR distance information allow us to define an atomic order
v
1
,
…
,
v
n
such that the distances related to the pairs
{
v
i
-
3
,
v
i
}
,
{
v
i
-
2
,
v
i
}
,
{
v
i
-
1
,
v
i
}
, for
i
>
3
, are available, which implies that the search space can be represented by a tree. A DMDGP solution can be represented by a path from the root to a leaf node of this tree, found by an exact method, called branch-and-prune (BP). Because of uncertainty in NMR data, some of the distances related to the pairs
{
v
i
-
3
,
v
i
}
may not be precise values, being represented by intervals of real numbers
d
̲
i
-
3
,
i
,
d
¯
i
-
3
,
i
. In order to apply BP algorithm in this context, sample values from those intervals should be taken. The main problem of this approach is that if we sample many values, the search space increases drastically, and for small samples, no solution can be found. We explain how geometric algebra can be used to model uncertainties in the DMDGP, avoiding sample values from intervals
d
̲
i
-
3
,
i
,
d
¯
i
-
3
,
i
and eliminating the heuristic characteristics of BP when dealing with interval distances.
The fundamental inverse problem in distance geometry is the one of finding positions from inter-point distances. The Discretizable Molecular Distance Geometry Problem (DMDGP) is a subclass of the ...Distance Geometry Problem (DGP) whose search space can be discretized and represented by a binary tree, which can be explored by a Branch-and-Prune (BP) algorithm. It turns out that this combinatorial search space possesses many interesting symmetry properties that were studied in the last decade. In this paper, we present a new algorithm for this subclass of the DGP, which exploits DMDGP symmetries more effectively than its predecessors. Computational results show that the speedup, with respect to the classic BP algorithm, is considerable for sparse DMDGP instances related to protein conformation.
In the 2 years since our last 4OR review of distance geometry methods with applications to proteins and nanostructures, there has been rapid progress in treating uncertainties in the discretizable ...distance geometry problem; and a new class of geometry problems started to be explored, namely vector geometry problems. In this work we review this progress in the context of the earlier literature.
A Golomb Ruler (GR) is a set of integer marks along an imaginary ruler such that all the distances of the marks are different. Computing a GR of minimum length is associated to many applications ...(from astronomy to information theory). Although not yet demonstrated to be NP-hard, the problem is computationally very challenging. This brief note proposes a new continuous optimization model for the problem and, based on a given theoretical result and some computational experiments, we conjecture that an optimal solution of this model is also a solution to an associated GR of minimum length.