Biology:Direct coupling analysis

From HandWiki

Direct coupling analysis or DCA is an umbrella term comprising several methods for analyzing sequence data in computational biology.[1] The common idea of these methods is to use statistical modeling to quantify the strength of the direct relationship between two positions of a biological sequence, excluding effects from other positions. This contrasts usual measures of correlation, which can be large even if there is no direct relationship between the positions (hence the name direct coupling analysis). Such a direct relationship can for example be the evolutionary pressure for two positions to maintain mutual compatibility in the biomolecular structure of the sequence, leading to molecular coevolution between the two positions. DCA has been used in the inference of protein residue contacts,[1][2][3][4][5] RNA structure prediction,[6][7] the inference of protein-protein interaction networks,[8][9][10][11][12] the modeling of fitness landscapes,[13][14][15] the generation of novel function proteins,[16] and the modeling of protein evolution.[17][18]

Mathematical Model and Inference

Mathematical Model

The basis of DCA is a statistical model for the variability within a set of phylogenetically related biological sequences. When fitted to a multiple sequence alignment (MSA) of sequences of length [math]\displaystyle{ N }[/math], the model defines a probability for all possible sequences of the same length.[1] This probability can be interpreted as the probability that the sequence in question belongs to the same class of sequences as the ones in the MSA, for example the class of all protein sequences belonging to a specific protein family.

We denote a sequence by [math]\displaystyle{ a = (a_1,a_2..,a_N) }[/math], with the [math]\displaystyle{ a_i }[/math] being categorical variables representing the monomers of the sequence (if the sequences are for example aligned amino acid sequences of proteins of a protein family, the [math]\displaystyle{ a_i }[/math] take as values any of the 20 standard amino acids). The probability of a sequence within a model is then defined as

[math]\displaystyle{ \begin{align} P\left(a | J,h\right) = \frac{1}{Z} \exp{\left(\sum\limits_{i=1}^{N-1} \sum\limits_{j=i+1}^{N} J_{ij}(a_i,a_j) + \sum\limits_{i=1}^{N} h_i(a_i)\right)}, \end{align} }[/math]

where

  • [math]\displaystyle{ J,h }[/math] are sets of real numbers representing the parameters of the model (more below)
  • [math]\displaystyle{ Z }[/math] is a normalization constant (a real number) to ensure [math]\displaystyle{ \sum\limits_{a} P(a | J,h) = 1 }[/math]

The parameters [math]\displaystyle{ h_i(a_i) }[/math] depend on one position [math]\displaystyle{ i }[/math] and the symbol [math]\displaystyle{ a_i }[/math] at this position. They are usually called fields[1] and represent the propensity of symbol to be found at a certain position. The parameters [math]\displaystyle{ J_{ij}(a_i,a_j) }[/math] depend on pairs of positions [math]\displaystyle{ i,j }[/math] and the symbols [math]\displaystyle{ a_i,a_j, }[/math] at these positions. They are usually called couplings[1] and represent an interaction, i.e. a term quantifying how compatible the symbols at both positions are with each other. The model is fully connected, so there are interactions between all pairs of positions. The model can be seen as a generalization of the Ising model, with spins not only taking two values, but any value from a given finite alphabet. In fact, when the size of the alphabet is 2, the model reduces to the Ising model. Since it is also reminiscent of the model of the same name, it is often called Potts model.[19]

Even knowing the probabilities of all sequences does not determine the parameters [math]\displaystyle{ J,h }[/math] uniquely. For example, a simple transformation of the parameters

[math]\displaystyle{ J_{ij}(a,b) \rightarrow J_{ij}(a,b) + R_{ij} }[/math]

for any set of real numbers [math]\displaystyle{ R_{ij} }[/math] leaves the probabilities the same. The likelihood function is invariant under such transformations as well, so the data cannot be used to fix these degrees of freedom (although a prior on the parameters might do so[3]).

A convention often found in literature[3][20] is to fix these degrees of freedom such that the Frobenius norm of the coupling matrix

[math]\displaystyle{ F_{ij} = \sqrt{\sum\limits_{a,b} J_{ij}(a,b)^2}, }[/math]

is minimized (independently for every pair of positions [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math]).

Maximum Entropy Derivation

To justify the Potts model, it is often noted that it can be derived following a maximum entropy principle:[21] For a given set of sample covariances and frequencies, the Potts model represents the distribution with the maximal Shannon entropy of all distributions reproducing those covariances and frequencies. For a multiple sequence alignment, the sample covariances are defined as

[math]\displaystyle{ C_{ij}(a,b) = f_{ij}(a,b) - f_i(a)f_j(b) }[/math],

where [math]\displaystyle{ f_{ij}(a,b) }[/math] is the frequency of finding symbols [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] at positions [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] in the same sequence in the MSA, and [math]\displaystyle{ f_i(a) }[/math] the frequency of finding symbol [math]\displaystyle{ a }[/math] at position [math]\displaystyle{ i }[/math]. The Potts model is then the unique distribution [math]\displaystyle{ P }[/math] that maximizes the functional

[math]\displaystyle{ \begin{align} F[P] = &- \sum\limits_{a} P(a) \log P(a) \\ &+ \sum\limits_{i\lt j} \sum\limits_{x,y} \lambda_{ij}(x,y) \Big( P_{ij}(x,y) - f_{ij}(x,y) \Big) \\ &+ \sum\limits_{i}\sum\limits_{x} \lambda_{i}(x) \Big( P_i(x) - f_i(x) \Big) \\ &+ \Omega \left(1 - \sum\limits_{a} P(a)\right). \end{align} }[/math]

The first term in the functional is the Shannon entropy of the distribution. The [math]\displaystyle{ \lambda }[/math] are Lagrange multipliers to ensure [math]\displaystyle{ P_{ij}(x,y) = f_{ij}(x,y) }[/math], with [math]\displaystyle{ P_{ij}(x,y) }[/math] being the marginal probability to find symbols [math]\displaystyle{ x,y }[/math] at positions [math]\displaystyle{ i,j }[/math]. The Lagrange multiplier [math]\displaystyle{ \Omega }[/math] ensures normalization. Maximizing this functional and identifying

[math]\displaystyle{ \begin{align} &\lambda_{ij}(x,y) = J_{ij}(x,y) \\ &\lambda_{i}(x) = h_i(x) \\ &\Omega = Z \\ \end{align} }[/math]

leads to the Potts model above. This procedure only gives the functional form of the Potts model, while the numerical values of the Lagrange multipliers (identified with the parameters) still have to be determined by fitting the model to the data.

Direct Couplings and Indirect Correlation

The central point of DCA is to interpret the [math]\displaystyle{ J_{ij} }[/math] (which can be represented as a [math]\displaystyle{ q\times q }[/math] matrix if there are [math]\displaystyle{ q }[/math] possible symbols) as direct couplings. If two positions are under joint evolutionary pressure (for example to maintain a structural bond), one might expect these couplings to be large because only sequences with fitting pairs of symbols should have a significant probability. On the other hand, a large correlation between two positions does not necessarily mean that the couplings are large, since large couplings between e.g. positions [math]\displaystyle{ i,j }[/math] and [math]\displaystyle{ j,k }[/math] might lead to large correlations between positions [math]\displaystyle{ i }[/math] and [math]\displaystyle{ k }[/math], mediated by position [math]\displaystyle{ j }[/math].[1] In fact, such indirect correlations have been implicated in the high false positive rate when inferring protein residue contacts using correlation measures like mutual information.[22]

Inference

The inference of the Potts model on a multiple sequence alignment (MSA) using maximum likelihood estimation is usually computationally intractable, because one needs to calculate the normalization constant [math]\displaystyle{ Z }[/math], which is for sequence length [math]\displaystyle{ N }[/math] and [math]\displaystyle{ q }[/math] possible symbols a sum of [math]\displaystyle{ q^N }[/math] terms (which means for example for a small protein domain family with 30 positions [math]\displaystyle{ 20^{30} }[/math] terms). Therefore, numerous approximations and alternatives have been developed:

All of these methods lead to some form of estimate for the set of parameters [math]\displaystyle{ J,{h} }[/math] maximizing the likelihood of the MSA. Many of them include regularization or prior terms to ensure a well-posed problem or promote a sparse solution.

Applications

Protein Residue Contact Prediction

A possible interpretation of large values of couplings in a model fitted to a MSA of a protein family is the existence of conserved contacts between positions (residues) in the family. Such a contact can lead to molecular coevolution, since a mutation in one of the two residues, without a compensating mutation in the other residue, is likely to disrupt protein structure and negatively affect the fitness of the protein. Residue pairs for which there is a strong selective pressure to maintain mutual compatibility are therefore expected to mutate together or not at all. This idea (which was known in literature long before the conception of DCA[25]) has been used to predict protein contact maps, for example analyzing the mutual information between protein residues.

Within the framework of DCA, a score for the strength of the direct interaction between a pair of residues [math]\displaystyle{ i,j }[/math] is often defined[3][20] using the Frobenius norm [math]\displaystyle{ F_{ij} }[/math] of the corresponding coupling matrix [math]\displaystyle{ J_{ij} }[/math] and applying an average product correction (APC):

[math]\displaystyle{ F^{APC}_{ij} = F_{ij} - \frac{F_{i} F_{j}}{F}, }[/math]

where [math]\displaystyle{ F_{ij} }[/math] has been defined above and

[math]\displaystyle{ \begin{align} &F_{i} = \frac{1}{N}\sum\limits_{j \neq i}^{N} F_{ij} \\ &F = \frac{1}{N^2-N}\sum\limits_{i,j, i \neq j}^{N} F_{ij} \end{align} }[/math].

This correction term was first introduced for mutual information[26] and is used to remove biases of specific positions to produce large [math]\displaystyle{ F_{ij} }[/math]. Scores that are invariant under parameter transformations that do not affect the probabilities have also been used.[1] Sorting all residue pairs by this score results in a list in which the top of the list is strongly enriched in residue contacts when compared to the protein contact map of a homologous protein.[4] High-quality predictions of residue contacts are valuable as prior information in protein structure prediction.[4]

Inference of protein-protein interaction

DCA can be used for detecting conserved interaction between protein families and for predicting which residue pairs form contacts in a protein complex.[8][9] Such predictions can be used when generating structural models for these complexes,[27] or when inferring protein-protein interaction networks made from more than two proteins.[9][12]

Modeling of fitness landscapes

DCA can be used to model fitness landscapes and to predict the effect of a mutation in the amino acid sequence of a protein on its fitness.[13][14]

External links

Online services:

Source code:

Useful applications:

References

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Morcos, F.; Pagnani, A.; Lunt, B.; Bertolino, A.; Marks, D. S.; Sander, C.; Zecchina, R.; Onuchic, J. N. et al. (21 November 2011). "Direct-coupling analysis of residue coevolution captures native contacts across many protein families". Proceedings of the National Academy of Sciences 108 (49): E1293–E1301. doi:10.1073/pnas.1111471108. PMID 22106262. Bibcode: 2011PNAS..108E1293M. 
  2. ↑ Kamisetty, H.; Ovchinnikov, S.; Baker, D. (5 September 2013). "Assessing the utility of coevolution-based residue-residue contact predictions in a sequence- and structure-rich era". Proceedings of the National Academy of Sciences 110 (39): 15674–15679. doi:10.1073/pnas.1314045110. PMID 24009338. Bibcode: 2013PNAS..11015674K. 
  3. ↑ 3.0 3.1 3.2 3.3 3.4 Ekeberg, Magnus; Lövkvist, Cecilia; Lan, Yueheng; Weigt, Martin; Aurell, Erik (11 January 2013). "Improved contact prediction in proteins: Using pseudolikelihoods to infer Potts models". Physical Review E 87 (1): 012707. doi:10.1103/PhysRevE.87.012707. PMID 23410359. Bibcode: 2013PhRvE..87a2707E. 
  4. ↑ 4.0 4.1 4.2 Marks, Debora S.; Colwell, Lucy J.; Sheridan, Robert; Hopf, Thomas A.; Pagnani, Andrea; Zecchina, Riccardo; Sander, Chris; Sali, Andrej (7 December 2011). "Protein 3D Structure Computed from Evolutionary Sequence Variation". PLOS ONE 6 (12): e28766. doi:10.1371/journal.pone.0028766. PMID 22163331. Bibcode: 2011PLoSO...628766M. 
  5. ↑ Ekeberg, Magnus; Hartonen, Tuomo; Aurell, Erik (2014-11-01). "Fast pseudolikelihood maximization for direct-coupling analysis of protein structure from many homologous amino-acid sequences" (in en). Journal of Computational Physics 276: 341–356. doi:10.1016/j.jcp.2014.07.024. ISSN 0021-9991. Bibcode: 2014JCoPh.276..341E. https://www.sciencedirect.com/science/article/pii/S0021999114005178. 
  6. ↑ De Leonardis, Eleonora; Lutz, Benjamin; Ratz, Sebastian; Cocco, Simona; Monasson, Rémi; Schug, Alexander; Weigt, Martin (29 September 2015). "Direct-Coupling Analysis of nucleotide coevolution facilitates RNA secondary and tertiary structure prediction". Nucleic Acids Research 43 (21): 10444–55. doi:10.1093/nar/gkv932. PMID 26420827. 
  7. ↑ Weinreb, Caleb; Riesselman, Adam J.; Ingraham, John B.; Gross, Torsten; Sander, Chris; Marks, Debora S. (May 2016). "3D RNA and Functional Interactions from Evolutionary Couplings". Cell 165 (4): 963–975. doi:10.1016/j.cell.2016.03.030. PMID 27087444. 
  8. ↑ 8.0 8.1 Ovchinnikov, Sergey; Kamisetty, Hetunandan; Baker, David (1 May 2014). "Robust and accurate prediction of residue–residue interactions across protein interfaces using evolutionary information". eLife 3: e02030. doi:10.7554/eLife.02030. PMID 24842992. 
  9. ↑ 9.0 9.1 9.2 Feinauer, Christoph; Szurmant, Hendrik; Weigt, Martin; Pagnani, Andrea; Keskin, Ozlem (16 February 2016). "Inter-Protein Sequence Co-Evolution Predicts Known Physical Interactions in Bacterial Ribosomes and the Trp Operon". PLOS ONE 11 (2): e0149166. doi:10.1371/journal.pone.0149166. PMID 26882169. Bibcode: 2016PLoSO..1149166F. 
  10. ↑ dos Santos, R.N.; Morcos, F.; Jana, B.; Andricopulo, A.D.; Onuchic, J.N. (4 September 2015). "Dimeric interactions and complex formation using direct coevolutionary couplings.". Scientific Reports 5: 13652. doi:10.1038/srep13652. PMID 26338201. Bibcode: 2015NatSR...513652D. 
  11. ↑ Uguzzoni, Guido; John Lovis, Shalini; Oteri, Francesco; Schug, Alexander; Szurmant, Hendrik; Weigt, Martin (2017-03-28). "Large-scale identification of coevolution signals across homo-oligomeric protein interfaces by direct coupling analysis" (in en). Proceedings of the National Academy of Sciences 114 (13): E2662–E2671. doi:10.1073/pnas.1615068114. ISSN 0027-8424. PMID 28289198. Bibcode: 2017PNAS..114E2662U. 
  12. ↑ 12.0 12.1 Croce, Giancarlo; Gueudré, Thomas; Cuevas, Maria Virginia Ruiz; Keidel, Victoria; Figliuzzi, Matteo; Szurmant, Hendrik; Weigt, Martin (2019-10-21). "A multi-scale coevolutionary approach to predict interactions between protein domains" (in en). PLOS Computational Biology 15 (10): e1006891. doi:10.1371/journal.pcbi.1006891. ISSN 1553-7358. PMID 31634362. Bibcode: 2019PLSCB..15E6891C. 
  13. ↑ 13.0 13.1 Ferguson, Andrew L.; Mann, Jaclyn K.; Omarjee, Saleha; Ndung'u, Thumbi; Walker, Bruce D.; Chakraborty, Arup K. (March 2013). "Translating HIV Sequences into Quantitative Fitness Landscapes Predicts Viral Vulnerabilities for Rational Immunogen Design". Immunity 38 (3): 606–617. doi:10.1016/j.immuni.2012.11.022. PMID 23521886. 
  14. ↑ 14.0 14.1 Figliuzzi, Matteo; Jacquier, Hervé; Schug, Alexander; Tenaillon, Oliver; Weigt, Martin (January 2016). "Coevolutionary Landscape Inference and the Context-Dependence of Mutations in Beta-Lactamase TEM-1". Molecular Biology and Evolution 33 (1): 268–280. doi:10.1093/molbev/msv211. PMID 26446903. 
  15. ↑ Asti, Lorenzo; Uguzzoni, Guido; Marcatili, Paolo; Pagnani, Andrea; Ofran, Yanay (13 April 2016). "Maximum-Entropy Models of Sequenced Immune Repertoires Predict Antigen-Antibody Affinity". PLOS Computational Biology 12 (4): e1004870. doi:10.1371/journal.pcbi.1004870. PMID 27074145. Bibcode: 2016PLSCB..12E4870A. 
  16. ↑ Russ, William P.; Figliuzzi, Matteo; Stocker, Christian; Barrat-Charlaix, Pierre; Socolich, Michael; Kast, Peter; Hilvert, Donald; Monasson, Remi et al. (2020-07-24). "An evolution-based model for designing chorismate mutase enzymes" (in en). Science 369 (6502): 440–445. doi:10.1126/science.aba3304. ISSN 0036-8075. PMID 32703877. Bibcode: 2020Sci...369..440R. https://www.sciencemag.org/lookup/doi/10.1126/science.aba3304. 
  17. ↑ Rodriguez-Rivas, Juan; Croce, Giancarlo; Muscat, Maureen; Weigt, Martin (2022-01-25). "Epistatic models predict mutable sites in SARS-CoV-2 proteins and epitopes" (in en). Proceedings of the National Academy of Sciences 119 (4). doi:10.1073/pnas.2113118119. ISSN 0027-8424. PMID 35022216. Bibcode: 2022PNAS..11913118R. 
  18. ↑ Vigué, Lucile; Croce, Giancarlo; Petitjean, Marie; Ruppé, Etienne; Tenaillon, Olivier; Weigt, Martin (2022-07-12). "Deciphering polymorphism in 61,157 Escherichia coli genomes via epistatic sequence landscapes" (in en). Nature Communications 13 (1): 4030. doi:10.1038/s41467-022-31643-3. ISSN 2041-1723. PMID 35821377. Bibcode: 2022NatCo..13.4030V. 
  19. ↑ Feinauer, Christoph; Skwark, Marcin J.; Pagnani, Andrea; Aurell, Erik (9 October 2014). "Improving Contact Prediction along Three Dimensions". PLOS Computational Biology 10 (10): e1003847. doi:10.1371/journal.pcbi.1003847. PMID 25299132. Bibcode: 2014PLSCB..10E3847F. 
  20. ↑ 20.0 20.1 20.2 Baldassi, Carlo; Zamparo, Marco; Feinauer, Christoph; Procaccini, Andrea; Zecchina, Riccardo; Weigt, Martin; Pagnani, Andrea (24 March 2014). "Fast and Accurate Multivariate Gaussian Modeling of Protein Families: Predicting Residue Contacts and Protein-Interaction Partners". PLOS ONE 9 (3): e92721. doi:10.1371/journal.pone.0092721. PMID 24663061. Bibcode: 2014PLoSO...992721B. 
  21. ↑ Stein, Richard R.; Marks, Debora S.; Sander, Chris; Chen, Shi-Jie (30 July 2015). "Inferring Pairwise Interactions from Biological Data Using Maximum-Entropy Probability Models". PLOS Computational Biology 11 (7): e1004182. doi:10.1371/journal.pcbi.1004182. PMID 26225866. Bibcode: 2015PLSCB..11E4182S. 
  22. ↑ Burger, Lukas; van Nimwegen, Erik; Bourne, Philip E. (1 January 2010). "Disentangling Direct from Indirect Co-Evolution of Residues in Protein Alignments". PLOS Computational Biology 6 (1): e1000633. doi:10.1371/journal.pcbi.1000633. PMID 20052271. Bibcode: 2010PLSCB...6E0633B. 
  23. ↑ Weigt, M.; White, R. A.; Szurmant, H.; Hoch, J. A.; Hwa, T. (30 December 2008). "Identification of direct residue contacts in protein-protein interaction by message passing". Proceedings of the National Academy of Sciences 106 (1): 67–72. doi:10.1073/pnas.0805923106. PMID 19116270. Bibcode: 2009PNAS..106...67W. 
  24. ↑ Barton, J. P.; De Leonardis, E.; Coucke, A.; Cocco, S. (21 June 2016). "ACE: adaptive cluster expansion for maximum entropy graphical model inference". Bioinformatics 32 (20): 3089–3097. doi:10.1093/bioinformatics/btw328. PMID 27329863. 
  25. ↑ Göbel, Ulrike; Sander, Chris; Schneider, Reinhard; Valencia, Alfonso (April 1994). "Correlated mutations and residue contacts in proteins". Proteins: Structure, Function, and Genetics 18 (4): 309–317. doi:10.1002/prot.340180402. PMID 8208723. 
  26. ↑ Dunn, S.D.; Wahl, L.M.; Gloor, G.B. (5 December 2007). "Mutual information without the influence of phylogeny or entropy dramatically improves residue contact prediction". Bioinformatics 24 (3): 333–340. doi:10.1093/bioinformatics/btm604. PMID 18057019. 
  27. ↑ Schug, A.; Weigt, M.; Onuchic, J. N.; Hwa, T.; Szurmant, H. (17 December 2009). "High-resolution protein complexes from integrating genomic information with molecular simulation". Proceedings of the National Academy of Sciences 106 (52): 22124–22129. doi:10.1073/pnas.0912100106. PMID 20018738. Bibcode: 2009PNAS..10622124S. 
  28. ↑ Jarmolinska, Aleksandra I.; Zhou, Qin; Sulkowska, Joanna I.; Morcos, Faruck (11 January 2019). "DCA-MOL: A PyMOL Plugin To Analyze Direct Evolutionary Couplings". Journal of Chemical Information and Modeling 59 (2): 625–629. doi:10.1021/acs.jcim.8b00690. PMID 30632747. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Biology:Direct_coupling_analysis&oldid=3645970"