PaperlayerView exact revision on arXiv

Source-linked AI summary

Predicting protein contact map using evolutionary and physical constraints by integer programming (extended version)

Zhiyong Wang, Jinbo Xu

arXiv:1308.1975v2q-bio.QMcs.CEcs.LGmath.OCq-bio.BMstat.ML

TL;DR

Existing contact predictors can ignore whole-map contact relationships and physical feasibility, while co-evolution methods require many sequence homologs. PhyCMAP combines evolutionary information with physical constraints, and the authors report that it outperforms popular methods across homolog availability.

  • Problem

    Many predictors score contact-map elements independently, while co-evolution methods require at least several hundred homologs and enforce only sparsity.

    Source: §1 · p. 1

  • Method

    PhyCMAP uses machine learning to combine evolutionary and non-evolutionary information for contact probabilities, then uses integer linear programming to select contacts under physical constraints.

    Source: §1 · pp. 1–2

  • Results

    PhyCMAP outperforms currently popular methods regardless of how many sequence homologs are available for the protein under prediction.

    Source: §1 · p. 2, §4 · p. 12

  • Takeaways & Limitations

    The study indicates that physical constraints are helpful for contact prediction, especially when few sequence homologs are available.

    Source: §4 · p. 12

    The physical constraints used do not cover all contact-map properties; the authors identify global distance-matrix properties as a future direction for improving medium- and long-range prediction.

    Source: §4 · p. 12

Abstract

from arXiv · show

Motivation. Protein contact map describes the pairwise spatial and functional relationship of residues in a protein and contains key information for protein 3D structure prediction. Although studied extensively, it remains very challenging to predict contact map using only sequence information. Most existing methods predict the contact map matrix element-by-element, ignoring correlation among contacts and physical feasibility of the whole contact map. A couple of recent methods predict contact map based upon residue co-evolution, taking into consideration contact correlation and enforcing a sparsity restraint, but these methods require a very large number of sequence homologs for the protein under consideration and the resultant contact map may be still physically unfavorable. Results. This paper presents a novel method PhyCMAP for contact map prediction, integrating both evolutionary and physical restraints by machine learning and integer linear programming (ILP). The evolutionary restraints include sequence profile, residue co-evolution and context-specific statistical potential. The physical restraints specify more concrete relationship among contacts than the sparsity restraint. As such, our method greatly reduces the solution space of the contact map matrix and thus, significantly improves prediction accuracy. Experimental results confirm that PhyCMAP outperforms currently popular methods no matter how many sequence homologs are available for the protein under consideration. PhyCMAP can predict contacts within minutes after PSIBLAST search for sequence homologs is done, much faster than the two recent methods PSICOV and EvFold. See http://raptorx.uchicago.edu for the web server.

1 INTRODUCTION

Protein contact maps capture residue relationships relevant to structure prediction, but predicting them from sequence remains challenging. PhyCMAP combines evolutionary information with physical constraints to account for contact relationships and improve prediction accuracy.

1 INTRODUCTION

  • Contact maps encode pairwise spatial and functional relationships among residues and can support protein structure prediction, model assessment, alignment, and classification.A contact is defined by a residue-pair Euclidean distance below 8Å, and the map is a binary L×L matrix.Source: §1 · p. 1
  • Many machine-learning predictors score map elements independently, overlooking correlations among contacts and the physical feasibility of the whole map.A basic physical constraint is sparsity: the number of contacts grows linearly with protein length.Source: §1 · p. 1
  • PSICOV and Evfold use co-evolution and sparsity but require at least several hundred homologs, while sparsity alone misses more concrete contact constraints.The authors note that proteins with few homologs may lack close PDB templates, and give residue contact counts and beta-strand contacts as examples of additional constraints.Source: §1 · p. 1
  • Astro-Fold uses physical constraints that imply sparsity, but some are described as overly restrictive and it does not use evolutionary information.One example restricts a residue in one beta strand to contact only one residue in another beta strand.Source: §1 · p. 1
  • PhyCMAP combines evolutionary and physical constraints, reporting better prediction accuracy than popular methods across proteins with different numbers of sequence homologs.Its physical constraints specify relationships among contacts beyond sparsity and reduce the contact-map solution space.Source: §1 · pp. 1–2

2 METHODS

PhyCMAP predicts residue-pair contact probabilities with Random Forests, then uses integer linear programming to select high-probability contacts subject to physical constraints.

2 METHODS

  • Random Forests estimate residue-pair contact probabilities, and integer linear programming selects top contacts under physical constraints to form a physically favorable contact map.The ILP maximizes the selected contacts’ accumulated probabilities subject to linear constraints.Source: §2 · p. 2, §2.2 · p. 3

2.1 Predicting contact probability by Random Forests

  • The Random Forest model uses evolutionary, structural, mixed-source, and amino-acid property features, with about 300 features per residue pair.Parameters are selected by 5-fold cross-validation.Source: §2.1 · p. 2
  • Contrastive mutual information compares a residue pair’s mutual information with that of neighboring pairs, reducing local background bias.When few homologs are available or either position has entropy below 0.3, CMI is set to zero to avoid artificially high values.Source: §2.1 · p. 2
  • Powers of the mutual-information matrix from 2 to 11 capture chaining among residue couplings and improve medium- and long-range prediction when many homologs make MI accurate.Source: §2.1 · p. 2

2.2 The integer linear programming (ILP) method

  • The ILP maximizes selected contact probabilities while penalizing violations of soft physical constraints with relaxation variables.The desired number of selected contacts is k.Source: §2.2 · pp. 3, 5
  • Beta-strand constraints bound contact counts, while neighboring contacts are constrained according to whether strands form anti-parallel or parallel sheets.The figure depicts lower and upper bounds on contacts between two beta strands.Source: §2.2 · p. 4, Figure 3 · p. 4
  • Other constraints limit a strand to sheets with up to two other strands, discourage loop-end contacts, and prohibit one residue contacting both i and i+2 in the same alpha helix.The loop-end constraint is relaxed because 3.4% of training-set loop segments had such a contact.Source: §2.2 · p. 5
  • Evaluation compares PhyCMAP with four methods on 123 CASP10 targets and 601 Set600 proteins, scoring top 5, L/10, and L/5 predicted contacts.The RF training set contains 900 nonredundant structures; all contacts and a random 20% of noncontacts are used.Source: §2.2 · p. 5

3 RESULTS

On CASP10 and Set600, PhyCMAP generally outperformed competing methods, including on targets with few homologs. The results also indicate contributions from co-evolution features and physical constraints, with specific examples illustrating predictions across different homolog counts.

3 RESULTS

  • 0.373, 0.313, and 0.315 were the average accuracies of PhyCMAP, CMAPpro, and PSICOV on top L/5 long-range Cβ contacts.Across 123 CASP10 targets, PhyCMAP significantly exceeded CMAPpro on top 5, L/10, and L/5 contacts, and significantly outperformed NNcon, PSICOV, and Evfold under all evaluations.Source: Figure 4 · p. 6, Table 3 · p. 6, §3 · p. 6
  • 0.363, 0.308, and 0.180 were the average accuracies of PhyCMAP, CMAPpro, and PSICOV on top L/5 medium- and long-range contacts for 36 hard CASP10 targets.PhyCMAP exceeded CMAPpro by 5–7% on top 5, L/10, and L/5 predictions; PSICOV and Evfold almost failed on these targets.Source: Table 4 · p. 6, §3 · p. 6, Figure 5 · p. 7
  • Across CASP10 homolog-count groups, PhyCMAP outperformed Evfold, CMAPpro, and NNCON; its comparison with PSICOV varied by contact type and Meff.PhyCMAP greatly outperformed PSICOV for Cα contacts at all Meff levels and for Cβ contacts when logMeff ≤ 6; it was comparable for Cβ when logMeff > 6.Source: §3 · p. 7, Figure 6 · p. 7
  • On Set600, PhyCMAP outperformed PSICOV and Evfold with Meff > 100, and significantly outperformed PSICOV and slightly exceeded CMAPpro and NNcon with Meff ≤ 100.On a reduced Set600 excluding 226 proteins with >90% identity to CMAPpro’s training set, it outperformed CMAPpro and Evfold but was slightly worse than PSICOV for long-range Cβ contacts.Source: §3 · pp. 7–9, Table 7 · p. 9

3.1 Contribution of contrastive mutual information and pairwise contact scores

  • Contrastive mutual information and homologous pairwise contact scores improve the Random Forest model’s performance.Table 8 reports their contribution to Cβ prediction, with similar results for Cα prediction.Source: §3.1 · p. 9, Table 8 · p. 9

3.2 Contribution of the powers of the MI matrix

  • Powers of the mutual-information matrix greatly improve long-range prediction when many homologs are available.The authors associate these powers with the chaining effect of residue couplings and report they can be calculated faster than the matrix inverse used by PSICOV.Source: §3.2 · pp. 9–10, Table 9 · p. 10, Figure 9 · p. 10

3.3 Contribution of physical constraints

  • ILP physical constraints improve medium- and long-range prediction when Meff > 100, but not short-range prediction.Their improvement is larger at Meff ≤ 100, including substantial short-range gains; the authors interpret the constraints as complementary to evolutionary information when homologous information is insufficient.Source: §3.3 · p. 10, Table 10 · p. 10

3.4 Specific Examples

  • For four CASP10 targets, PhyCMAP’s top L/5 accuracy exceeded Evfold’s in each reported comparison.The targets span Meff from 31.53 to 3300.02; for T0677D2, PhyCMAP scored 0.357 while Evfold predicted no correct contacts.Source: §3.4 · p. 10, Figure 10 · p. 11, Figure 11 · p. 11

4 CONCLUSION AND DISCUSSIONS

PhyCMAP combines evolutionary information with physical constraints and outperforms popular contact-prediction methods regardless of homolog availability. Its current physical constraints remain incomplete, while its ILP approach differs from model-based filtering in speed and search strategy.

4 CONCLUSION AND DISCUSSIONS

  • PhyCMAP outperforms popular machine-learning and co-evolution methods regardless of how many sequence homologs are available.The compared methods include CMAPpro, NNCON, PSICOV, and Evfold.Source: §4 · p. 12
  • Current physical constraints do not cover all contact-map properties; future work could add global distance and beta-sheet constraints.The paper specifically proposes triangle inequalities and correlated pairwise distances for improving medium- and long-range prediction.Source: §4 · p. 12
  • Unlike model-based filtering, PhyCMAP predicts contacts within minutes after PSI-BLAST and avoids dependence on 3D-model energy optimization.The authors also say ILP can search the whole conformation space rather than being biased toward local minima.Source: §4 · p. 12
Loading 1308.1975v2…