Limits...
An algorithm to enumerate all possible protein conformations verifying a set of distance constraints.

Cassioli A, Bardiaux B, Bouvier G, Mucherino A, Alves R, Liberti L, Nilges M, Lavor C, Malliavin TE - BMC Bioinformatics (2015)

Bottom Line: Whereas the most common method currently employed is simulated annealing, there have been other methods previously proposed in the literature.Most of them, however, are designed to find one solution only.The pruning devices used here are directly related to features of protein conformations.

View Article: PubMed Central - PubMed

Affiliation: LIX, Ecole Polytechnique, Palaiseau, 91128, France. cassioliandre@gmail.com.

ABSTRACT

Background: The determination of protein structures satisfying distance constraints is an important problem in structural biology. Whereas the most common method currently employed is simulated annealing, there have been other methods previously proposed in the literature. Most of them, however, are designed to find one solution only.

Results: In order to explore exhaustively the feasible conformational space, we propose here an interval Branch-and-Prune algorithm (iBP) to solve the Distance Geometry Problem (DGP) associated to protein structure determination. This algorithm is based on a discretization of the problem obtained by recursively constructing a search space having the structure of a tree, and by verifying whether the generated atomic positions are feasible or not by making use of pruning devices. The pruning devices used here are directly related to features of protein conformations.

Conclusions: We described the new algorithm iBP to generate protein conformations satisfying distance constraints, that would potentially allows a systematic exploration of the conformational space. The algorithm iBP has been applied on three α-helical peptides.

Show MeSH

Related in: MedlinePlus

Discretization of the distance constraints. An example of discretization of the distance di,i−3. The solid circle represents the result of the intersection of the spheres centered in i−1,i−2 with radii di,i−1,di,i−2, respectively. The distance di,i−3 is discretized accordingly to Equation 2 with b=5: dotted circles represent the intersections of spheres centered in i−3 with radii in  with the plane containing the i−3,i−2 and i−1. Thick gray arcs represent the feasible regions for the atom i.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4384350&req=5

Fig5: Discretization of the distance constraints. An example of discretization of the distance di,i−3. The solid circle represents the result of the intersection of the spheres centered in i−1,i−2 with radii di,i−1,di,i−2, respectively. The distance di,i−3 is discretized accordingly to Equation 2 with b=5: dotted circles represent the intersections of spheres centered in i−3 with radii in with the plane containing the i−3,i−2 and i−1. Thick gray arcs represent the feasible regions for the atom i.

Mentions: When a distance is not uniquely defined, but rather defined by lower and upper bounds, i.e. di,j∈[li,j,ui,j], this distance is uniformly discretized by sampling b≥1 values in [li,j,ui,j], as depicted in Figure 5.(2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \tilde d_{i}=\left\{ l_{i,i-3} + (t-1)\frac{(u_{i,i-3}-l_{i,i-3})}{b} : t=1,\ldots,b\right\}. $$\end{document}d~i=li,i−3+(t−1)(ui,i−3−li,i−3)b:t=1,…,b.Figure 5


An algorithm to enumerate all possible protein conformations verifying a set of distance constraints.

Cassioli A, Bardiaux B, Bouvier G, Mucherino A, Alves R, Liberti L, Nilges M, Lavor C, Malliavin TE - BMC Bioinformatics (2015)

Discretization of the distance constraints. An example of discretization of the distance di,i−3. The solid circle represents the result of the intersection of the spheres centered in i−1,i−2 with radii di,i−1,di,i−2, respectively. The distance di,i−3 is discretized accordingly to Equation 2 with b=5: dotted circles represent the intersections of spheres centered in i−3 with radii in  with the plane containing the i−3,i−2 and i−1. Thick gray arcs represent the feasible regions for the atom i.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4384350&req=5

Fig5: Discretization of the distance constraints. An example of discretization of the distance di,i−3. The solid circle represents the result of the intersection of the spheres centered in i−1,i−2 with radii di,i−1,di,i−2, respectively. The distance di,i−3 is discretized accordingly to Equation 2 with b=5: dotted circles represent the intersections of spheres centered in i−3 with radii in with the plane containing the i−3,i−2 and i−1. Thick gray arcs represent the feasible regions for the atom i.
Mentions: When a distance is not uniquely defined, but rather defined by lower and upper bounds, i.e. di,j∈[li,j,ui,j], this distance is uniformly discretized by sampling b≥1 values in [li,j,ui,j], as depicted in Figure 5.(2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \tilde d_{i}=\left\{ l_{i,i-3} + (t-1)\frac{(u_{i,i-3}-l_{i,i-3})}{b} : t=1,\ldots,b\right\}. $$\end{document}d~i=li,i−3+(t−1)(ui,i−3−li,i−3)b:t=1,…,b.Figure 5

Bottom Line: Whereas the most common method currently employed is simulated annealing, there have been other methods previously proposed in the literature.Most of them, however, are designed to find one solution only.The pruning devices used here are directly related to features of protein conformations.

View Article: PubMed Central - PubMed

Affiliation: LIX, Ecole Polytechnique, Palaiseau, 91128, France. cassioliandre@gmail.com.

ABSTRACT

Background: The determination of protein structures satisfying distance constraints is an important problem in structural biology. Whereas the most common method currently employed is simulated annealing, there have been other methods previously proposed in the literature. Most of them, however, are designed to find one solution only.

Results: In order to explore exhaustively the feasible conformational space, we propose here an interval Branch-and-Prune algorithm (iBP) to solve the Distance Geometry Problem (DGP) associated to protein structure determination. This algorithm is based on a discretization of the problem obtained by recursively constructing a search space having the structure of a tree, and by verifying whether the generated atomic positions are feasible or not by making use of pruning devices. The pruning devices used here are directly related to features of protein conformations.

Conclusions: We described the new algorithm iBP to generate protein conformations satisfying distance constraints, that would potentially allows a systematic exploration of the conformational space. The algorithm iBP has been applied on three α-helical peptides.

Show MeSH
Related in: MedlinePlus