Graphical models for protein structure: Difference between revisions

Revision as of 14:11, 1 June 2010

Latest revision as of 11:34, 21 November 2022

(34 intermediate revisions by 23 users not shown)

Line 1:

{{nofootnotesNo footnotes|date=June 2010}}

[[Graphical Modelsmodel]]s have become powerful frameworks for [[Proteinprotein structure prediction]], [[Protein-proteinprotein–protein interaction]], and [[FreeThermodynamic free energy|free energy]] calculations for Proteinprotein Structuresstructures. Using a graphical model to represent the protein structure allows usthe tosolution solveof many problems including secondary structure prediction, protein -protein interactions, protein-drug interaction, and free energy calculations.

{{orphan|date=June 2010}}

[[Graphical Models]] have become powerful frameworks for [[Protein structure prediction]], [[Protein-protein interaction]] and [[Free energy]] calculations for Protein Structures. Using a graphical model to represent the protein structure allows us to solve many problems including secondary structure prediction, protein protein interactions, protein-drug interaction, and free energy calculations.

There are two main approaches to useusing Graphicalgraphical Modelsmodels in Proteinprotein Structurestructure Modelingmodeling. FirstThe first approach uses [[Discrete mathematics|discrete]] variables for representing the coordinates or the [[Dihedraldihedral angle]]s of the protein structure. The variables are originally all continuous values and, to transform them into discrete values, a discretization process is typically applied. SecondThe second approach uses [[Continuous]]continuous variables for the coordinates or [[Dihedraldihedral angle]]sangles.

==Discrete Graphicalgraphical Modelsmodels for Proteinprotein Structurestructure==

[[Markov random field]]s, also known as undirected graphical modelmodels is aare common representationrepresentations for this problem. Given an [[undirected graph]] ''G'' = (''V'', ''E''), a set of [[random variable]]s ''X'' = (''X''_''v'')_{''v'' ∈ ''V''} indexed by ''V'', form a Markov random field with respect to ''G'' if they satisfy the Pairwisepairwise Markov property:

Any*any two non-adjacent variables are [[conditional independence|conditionally independent]] given all other variables:

[[Markov random field]], also known as undirected graphical model is a common representation for this problem. Given an [[undirected graph]] ''G'' = (''V'', ''E''), a set of [[random variable]]s ''X'' = (''X''_''v'')_{''v'' ∈ ''V''} indexed by ''V'' form a Markov random field with respect to ''G'' if they satisfy the Pairwise Markov property:

::<math>X_u \perp\!\!\!\perp X_v | X_{V \setminus \{u,v\}} \quad \text{if } \{u,v\} \notin E.</math>

Any two non-adjacent variables are [[conditional independence|conditionally independent]] given all other variables:

In the Discretediscrete model, the continuous variables are discretized into a set of favorable discrete values. If the variables of choice are [[dihedral angle]]s, the discretization is typically done by mapping each value to the corresponding [[Rotamerrotamer]] conformation.

::<math>X_u \perp\!\!\!\perp X_v | X_{V \setminus \{u,v\}} \quad \text{if } \{u,v\} \notin E</math>

In the Discrete model, the continuous variables are discretized into a set of favorable discrete values. If the variables of choice are [[dihedral angle]]s, the discretization is typically done by mapping each value to the corresponding [[Rotamer]] conformation.

===Model===

Let ''X'' = {''X''_''b'', ''X''_''s''} be the random variables representing the entire protein structure. ''X''_''b'' can be represented by a set of 3-d coordinates of the [[Backbone chain|backbone]] atoms, or equivalently, by a sequence of [[bond length]]s and [[dihedral angle]]s. The probability of a particular [[Protein structure|conformation]] ''x'' can then be written as:

::<math>p(X = x|\Theta) = p(X_b = x_b)p(X_s = x_s|X_b,\Theta)</math>.

::<math>p(X = x|\Theta) = p(X_b = x_b)p(X_s = x_s|X_b,\Theta), \,</math>.

where <math>\Theta</math> represents any parameters used to describe this model, including sequence information, temperature etc. Frequently the backbone is assumed to be rigid with a known conformation, and the problem is then transformed to a side-chain placement problem. The structure of the graph is also encoded in <math>\Theta</math>. This structure shows which two variables are conditionally independent. As an example, side chain angles of two residues far apart can be independent given all other angles in the protein. To extract this structure, researchers use a distance [[threshold]], and only pair of residues which are within that threshold are considered connected (i.e. have an edge between them).

where <math>\Theta</math> represents any parameters used to describe this model, including sequence information, temperature etc. Frequently the backbone is assumed to be rigid with a known conformation, and the problem is then transformed to a side-chain placement problem. The structure of the graph is also encoded in <math>\Theta</math>. This structure shows which two variables are conditionally independent. As an example, side chain angles of two residues far apart can be independent given all other angles in the protein. To extract this structure, researchers use a distance [[threshold]], and only a pair of residues which are within that threshold are considered connected (i.e. have an edge between them).

Given this representation, the probability of a particular side chain conformation x_s given the backbone conformation x_b can be expressed as

Given this representation, the probability of a particular side chain conformation ''x''_''s'' given the backbone conformation ''x''_''b'' can be expressed as

<math>p(X_s = x_s|X_b = x_b) = \frac{1}{Z} \prod_{c\in C(G)}\Phi_c (x_s^c,x_b^c)</math>

:<math>p(X_s = x_s|X_b = x_b) = \frac{1}{Z} \prod_{c\in C(G)}\Phi_c (x_s^c,x_b^c)</math>

where C(G) is the set of all cliques in G, <math>\Phi</math> is a [[potential function]] defined over the variables, and Z is the so called [[partition function]].

where ''C''(''G'') is the set of all cliques in ''G'', <math>\Phi</math> is a [[function (mathematics)|potential function]] defined over the variables, and ''Z'' is the so called [[partition function (mathematics)|partition function]].

To completely characterize the MRF, it is necessary to define the potential function <math>\Phi</math>. To simplify, the cliques of a graph are usually restricted to only the cliques of size 2, which means the potential function is only defined over pairs of variables. In [[Goblin System]], this pairwise functions are defined as

To completely characterize the MRF, it is necessary to define the potential function <math>\Phi</math>. To simplify, the cliques of a graph are usually restricted to only the cliques of size 2, which means the potential function is only defined over pairs of variables. In [[Goblin System]], thisthese pairwise functions are defined as

<math>\Phi(x_s^{i_p},x_b^{j_q}) = exp ( -E(x_s^{i_p},x_b^{j_q})/K_BT)</math>

:<math>\Phi(x_s^{i_p},x_b^{j_q}) = \exp ( -E(x_s^{i_p},x_b^{j_q})/K_BT)</math>

where <math>E(x_s^{i_p},x_b^{j_q})</math> is the energy of interaction between rotamer state p of residue <math>X_i^s</math> and rotamer state q of residue <math>X_j^s</math> and <math>k_B</math> is the [[Boltzmann constant]].

Using a PDB file, this model can be built over the protein structure. From this model, free energy can be calculated.

===Free Energyenergy Calculationcalculation: Beliefbelief Propagationpropagation===

It has been shown that the free energy of a system is calculated as

:<math>G=E-TS</math>

It has been shown that the free energy of a system is calculated as

where E is the enthalpy of the system, T the temperature and S, the entropy. Now if we associate a probability with each state of the system, (p(x) for each conformation value, x), G can be rewritten as

<math>G=E-TS</math>

:<math>G=\sum_{x}p(x)E(x)-T\sum_xp(x)\ln(p(x)) \,</math>

where E is the enthalpy of the system, T the temperature and S, the entropy. Now if we associate a probability with each state of the system, (p(x) for each conformation value, x), G can be rewritten as

Calculating p(x) on discrete graphs is done by the [[Generalizedgeneralized belief propagation]] algorithm. This algorithm calculates an [[approximation]] to the probabilities, and it is not guaranteed to converge to a final value set. However, in practice, it has been shown to converge successfully in many cases.

<math>G=\sum_{x}p(x)E(x)-T\sum_xp(x)ln(p(x))</math>

==Continuous Graphicalgraphical Modelsmodels for Proteinprotein Structuresstructures==

Calculating p(x) on discrete graphs is done by the [[Generalized belief propagation]] algorithm. This algorithm calculates an [[approximation]] to the probabilities, and it is not guaranteed to converge to a final value set. However, in practice, it has been shown to converge successfully in many cases.

Graphical Modelsmodels can still be used when the variables of choice are continuous. In these cases, the probability distribution is represented as a [[multivariate probability distribution]] over continuous variables. Each family of distribution will then impose certain properties on the graphical model. [[Multivariate Gaussian distribution]] is one of the most convenient distributions in this problem. The simple form of the probability, and the direct relation with the corresponding graphical model makes it a popular choice among researchers.

===Gaussian graphical models of protein structures===

==Continuous Graphical Models for Protein Structures==

Gaussian Graphicalgraphical Modelsmodels are multivariate probability distributions encoding a network of dependencies among variables. Let <math>\Theta=[\theta_1, \theta_2, ..\dots, \theta_n]</math> be a set of <math>n</math> variables, such as <math>n</math> [[dihedral angles]], and let <math>f(\Theta=D)</math> be the value of the [[probability density function]] at a particular value ''D''. A multivariate Gaussian Graphicalgraphical Modelmodel defines this probability as follows:

:<math>f(\Theta=D) = \frac{1}{Z} \exp\left\{-\frac{1}{2}(D-\mu)^T\Sigma^{-1}(D-\mu)\right\}</math>

Graphical Models can still be used when the variables of choice are continuous. In these cases, the probability distribution is represented as a [[multivariate probability distribution]] over continuous variables. Each family of distribution will then impose certain properties on the graphical model. [[Multivariate Gaussian distribution]] is one of the most convenient distributions in this problem. The simple form of the probability, and the direct relation with the corresponding graphical model makes it a popular choice among researchers.

Where <math>Z = \frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}</math> is the closed form for the [[Partition function (mathematics)|partition function]]. The parameters of this distribution are <math>\mu</math> and <math>\Sigma</math>. <math>\mu</math> is the vector of [[mean values]] of each variable, and <math>\Sigma^{-1}</math>, the inverse of the [[covariance matrix]], also known as the [[precision matrix]]. Precision matrix contains the pairwise dependencies between the variables. A zero value in <math>\Sigma^{-1}</math> means that conditioned on the values of the other variables, the two corresponding variable are independent of each other.

===Guassian Graphical Models of Protein Structures===

Gaussian Graphical Models are multivariate probability distributions encoding a network of dependencies among variables. Let <math>\Theta=[\theta_1, \theta_2, .., \theta_n]</math> be a set of <math>n</math> variables, such as <math>n</math> [[dihedral angles]], and let <math>f(\Theta=D)</math> be the value of the [[probability density function]] at a particular value ''D''. A multivariate Gaussian Graphical Model defines this probability as follows:

To learn the graph structure as a multivariate Gaussian graphical model, we can use either [[L-1 regularization]], or [[neghborhoodneighborhood selection]] algorithms. These algorithms simultaneously learn a graph structure and the edge strength of the connected nodes. An edge strength corresponds to the potential function defined on the corresponding two-node [[Clique (graph theory)|clique]]. We use a training set of a number of PDB structures to learn the <math>\mu</math> and <math>\Sigma^{-1}</math>.

<math>f(\Theta=D) = \frac{1}{Z} \exp\{-\frac{1}{2}(D-\mu)^T\Sigma^{-1}(D-\mu)\}</math>

Once the model is learned, we can repeat the same step as in the discrete case, to get the density functions at each node, and use analytical form to calculate the Freefree energy. Here, the [[Partition function (mathematics)|partition function]] already has a [[Closed-form expression|closed form]], so the [[inference]], at least for the Gaussian Graphicalgraphical Modelsmodels is trivial. If the analytical form of the partition function wasis not available, we can use [[particle filtering]] or [[expectation propagation]] can be used to approximate the ''Z'', and then perform the inference and calculate free energy.

Where <math>Z = \frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}</math> is the closed form for the [[partition function]]. The parameters of this distribution are <math>\mu</math> and <math>\Sigma</math>. <math>\mu</math> is the vector of [[mean values]] of each variable, and <math>\Sigma^{-1}</math>, the inverse of the [[covariance matrix]], also known as the [[precision matrix]]. Precision matrix contains the pairwise dependencies between the variables. A zero value in <math>\Sigma^{-1}</math> means that conditioned on the values of the other variables, the two corresponding variable are independent of each other.

{{orphanNo footnotes|date=JuneAugust 2010}}

To learn the graph structure as a multivariate Gaussian graphical model, we can use either [[L-1 regularization]], or [[neghborhood selection]] algorithms. These algorithms simultaneously learn a graph structure and the edge strength of the connected nodes. An edge strength corresponds to the potential function defined on the corresponding two-node [[clique]]. We use a training set of a number of PDB structures to learn the <math>\mu</math> and <math>\Sigma^{-1}</math>.

== References ==

Once the model is learned, we can repeat the same step as in the discrete case, to get the density functions at each node, and use analytical form to calculate the Free energy. Here, the [[partition function]] already has a [[closed form]], so the [[inference]], at least for the Gaussian Graphical Models is trivial. If analytical form of the partition function was not available, we can use [[particle filtering]] or [[expectation propagation]] to approximate the Z, and then perform the inference and calculate free energy.

== References ==

<!--- See http://en.wikipedia.org/wiki/Wikipedia:Footnotes on how to create references using <ref></ref> tags which will then appear here automatically -->

Line 68 ⟶ 67:

* Free Energy Estimates of All-atom Protein Structures Using Generalized Belief Propagation, Hetunandan Kamisetty Eric P. Xing Christopher J. Langmead, RECOMB 2008

== External links ==

* http://www.liebertonline.com/doi/pdf/10.1089/cmb.2007.0131

* https://web.archive.org/web/20110724225908/http://www.learningtheory.org/colt2008/81-Zhou.pdf

* {{cite journal|author1= Liu Y |author2= Carbonell J |author3= Gopalakrishnan V |year=2009|title= Conditional graphical models for protein structural motif recognition

|journal= J. Comput. Biol. | volume=16|pages= 639–57 |doi=10.1089/cmb.2008.0176 |pmid=19432536 |issue=5|hdl= 1721.1/62177 |s2cid= 7035106 |hdl-access=free }}

<!--- Categories --->

* [https://www.cs.cmu.edu/~jgc/publication/Predicting_Protein_Folds_ICML_2005.pdf Predicting Protein Folds with Structural Repeats Using a Chain Graph Model]

[[Category:Articles created via the Article Wizard]]

===Guassian {{DEFAULTSORT:Graphical Models ofFor Protein Structures===Structure}}

{{uncategorized|date=June 2010}}

[[Category:Graphical models]]

[[Category:Protein methods]]

[[Category:Computational chemistry]]