Source-linked AI summary
Fast pseudolikelihood maximization for direct-coupling analysis of protein structure from many homologous amino-acid sequences
Magnus Ekeberg, Tuomo Hartonen, Erik Aurell
TL;DR
DCA must learn protein-family models approximately because exact likelihood inference is computationally difficult, while existing plmDCA is accurate but slow. The paper introduces an asymmetric, parallelizable pseudolikelihood implementation and reports practically identical accuracy with substantially lower running time, enabling broader application across protein families.
Problem
Exact likelihood inference is infeasible for realistic protein systems, while accurate plmDCA depends on a high-dimensional optimization that is relatively slow.
Method
The paper modifies l2-regularized plmDCA into an asymmetric implementation whose node-wise optimizations are inherently parallelizable.
Results
The asymmetric implementation works equally well as the symmetric variant while drastically decreasing running time.
Takeaways & Limitations
The speed-up allows plmDCA to be applied to more diverse protein sets and to compete with mean-field methods in execution speed.
Takeaways & Limitations
Regularization values used in the study were based on proteins with N in the range 50-100, so optimal values may differ for more diverse datasets with N spanning several hundred.
Abstract
from arXiv · showhide
Direct-Coupling Analysis is a group of methods to harvest information about coevolving residues in a protein family by learning a generative model in an exponential family from data. In protein families of realistic size, this learning can only be done approximately, and there is a trade-off between inference precision and computational speed. We here show that an earlier introduced $l_2$-regularized pseudolikelihood maximization method called plmDCA can be modified as to be easily parallelizable, as well as inherently faster on a single processor, at negligible difference in accuracy. We test the new incarnation of the method on 148 protein families from the Protein Families database (PFAM), one of the largest tests of this class of algorithms to date.
1. Introduction
DCA uses families of homologous protein sequences to infer spatial amino-acid contacts, addressing the growing gap between available sequences and structures. The paper introduces a faster plmDCA variant designed to preserve prediction precision while reducing computation.
- Contribution: The new plmDCA version is reported to retain practically identical precision while providing a large computational speed-up.It modifies an existing pseudolikelihood maximization approach rather than introducing a different prediction target.
- Motivation: DCA predicts protein contacts from sets of homologous amino-acid sequences rather than single sequences.The approach exploits evolutionary information shared across a protein family.
- Motivation: Known amino-acid sequences outnumber known protein structures by about 300:1, motivating sequence-family methods for structure prediction.The paper argues that this imbalance may persist or increase.
- Motivation: The method targets correlations between amino acids at different sequence positions that retain information about protein structure.These correlations reflect evolutionary constraints within homologous families.
2. A primer on Direct-Coupling Analysis
DCA models aligned homologous sequences with a Potts distribution and uses inferred interactions to predict spatial proximity. Exact likelihood learning is difficult because normalization scales exponentially, motivating approximate methods including pseudolikelihood maximization.
- Model: DCA treats aligned homologous protein sequences as independent samples from a Potts-model probability distribution.Each alignment row represents a protein, while columns represent aligned sequence positions.
- Model: The interaction parameters J_ij are used as predictions of spatial proximity between amino-acid positions.The paper connects such couplings to compensatory mutations and structural contacts.
- Model: The model uses 20 amino acids plus one alignment-gap state, giving q = 21.Position indices span sequence length N, and pairwise couplings are defined for distinct positions.
- Inference challenge: Exact inference is impractical for large proteins because the normalization constant Z has exponentially many terms in protein length.This prevents efficient exact computation of the full likelihood.
- Methods: plmDCA uses l2-regularized pseudolikelihood maximization to infer interaction parameters and the SCFN score to rank pairwise couplings.Other approaches approximate Z through mean-field, message-passing, or related procedures.
- Methods: The paper presents a faster plmDCA version because existing implementations are integrated into multiple computational frameworks and remain costly to run.The broader DCA field includes several alternative methods and extensions.
3. Symmetric and asymmetric pseudolikelihood maximization
Pseudolikelihood maximization estimates conditional probabilities for amino-acid positions, but symmetric optimization is slow and produces duplicate interaction estimates that must be reconciled. The asymmetric variant separates the problem into independent, lower-dimensional optimizations, enabling parallel execution while retaining regularization and scoring procedures.
- Pseudolikelihood criterion: Pseudolikelihood maximization estimates each amino-acid variable conditionally on all others without the costly approximations required by full-likelihood learning.With abundant data it can be consistent with full likelihood, although finite samples can produce different estimates from different conditional models.
- Symmetric formulation: Finite-data conditional fits produce two generally different estimates of each interaction Jij, although the model requires them to be equal.Symmetric plmDCA resolves this by jointly minimizing the conditional objectives under shared-interaction constraints.
- Symmetric formulation: Symmetric plmDCA is accurate but slow because it relies on a high-dimensional optimization.Its single optimization includes substantially more jointly coupled parameters than the asymmetric formulation.
- Asymmetric formulation: Asymmetric pseudolikelihood maximization minimizes N independent node-specific objectives, each lower-dimensional than the single symmetric problem.The independent multiclass logistic-regression problems can run in parallel across many cores and require fewer descent steps in practice.
- Supporting procedures: The asymmetric procedure retains sequence reweighting, l2 regularization, gauge handling, and interaction scoring as application-specific components of plmDCA.Sequence weights reduce bias from closely similar database sequences, while regularization addresses overfitting and fixes the parameter representation.
4. Data
The study uses aligned homologous sequences from PFAM and experimentally determined structures from PDB to evaluate predicted contacts. PFAM alignments are linked to PDB structures through UNIPROT and SIFTS, with contacts defined using spatial and sequence-separation criteria.
- Sequence data: plmDCA takes a multiple sequence alignment containing aligned evolutionary-related amino-acid sequences as its input.Each alignment row represents one amino-acid chain, and PFAM provides alignments for thousands of evolutionary domain families.
- Sequence data: PFAM alignments use gaps for non-alignable positions and lowercase letters for insertions that do not affect the rest of the alignment.An insertion in one sequence therefore introduces gaps in the corresponding positions of other sequences.
- Structural references: PDB supplies experimentally determined three-dimensional protein structures used as references for contact evaluation.The study primarily uses X-ray crystallography structures, with NMR also represented in the database.
- Structural references: PFAM alignment positions are matched to PDB residue positions through UNIPROT and SIFTS before comparing predicted and structural contacts.Backmapper software is used to relate the indexing of PFAM alignments and PDB structures.
- Contact definition: Contacts are defined as residue pairs closer than 8.5 Å in space and separated by more than four positions along the protein backbone.The distance is measured between amino-acid α-carbons in the X-ray structures.
5. Results
The asymmetric plmDCA implementation retained essentially the same contact-prediction accuracy as the symmetric version while substantially reducing runtime. Evaluation across 148 family–structure pairs showed generally persistent contacts but notable variation across families and structures.
- Accuracy and runtime: The difference in contact-prediction accuracy between symmetric and asymmetric plmDCA was negligible.TPR measures the fraction of predicted contacts also identified in the crystal structure.
- Accuracy and runtime: Some families requiring several hours with symmetric plmDCA terminated within minutes using asymmetric plmDCA, even with six CPUs.On one CPU, the asymmetric variant also converged several times faster, although runtime reduction was not linear with core count.
- Dataset scale and variability: The 148-family evaluation was more representative than the earlier 27-family comparison because it included larger and more varied family sizes.The authors report a slight average accuracy drop when both alignment length and sample size varied more widely.
- Limitations: The fixed regularization strengths λh = λJ = 0.01 were based on experiments with N around 50–100, limiting confidence for more diverse chain lengths.The authors suggest that new optimal values may be needed when N spans several hundred.
- Within-family variation: Prediction accuracy varied markedly among structures from the same family, including TPR values near 0.8 versus 0.2 for PF00051.PF00045 and PF00089 also contained families with substantial within-family variability.
- Dataset scale and variability: Alignment sample size B correlated positively with TPR, whereas chain length N showed no obvious dependency.This relationship was assessed for the 100 top-scoring position pairs across all family–structure pairs.
6. Discussion
The asymmetric plmDCA variant separates the optimization into position-specific problems, making it inherently parallel and faster than the symmetric formulation. The resulting precision change was insignificant, while tested scoring alternatives did not improve on SCFN.
- Algorithmic design: Asymmetric plmDCA separately predicts interaction matrices from positions i and j before combining them, unlike the symmetric joint optimization.The two formulations also differ in how regularization fixes their parameter gauges.
- Algorithmic design: The symmetric method solves one high-dimensional optimization, whereas the asymmetric method solves N independent lower-dimensional problems.The asymmetric formulation uses q (1 + (N − 1)q) parameters per subproblem instead of one problem with Nq (1 + (N − 1)q/2) parameters.
- Parallelization and speed: Asymmetric plmDCA is inherently parallel and can use up to N CPUs with virtually no overhead.For most protein families, N ranges from 50 to 500, while the observed precision change was insignificant.
- Optimization experiments: Alternative starting guesses and gauge constraints did not provide substantial additional speed-up over cold-starting at the origin.Mean-field starting estimates were too far from the pseudolikelihood maxima, while restricting the minimization to a gauge subspace increased the computational burden.
- Scoring experiments: None of the tested score replacements achieved accuracy as high as SCFN on the dataset.The alternatives included modified score combinations, omission of gap-state contributions, and replacing APC with average-sum correction.
- Conclusion: The authors conclude that plmDCA combines high accuracy with short running times, supporting its use for broader protein-structure prediction analyses.They also identify the method as a basis for further extensions of DCA theory and practice.