Correlation-compressed direct-coupling analysis

Learning Ising or Potts models from data has become an important topic in statistical physics and computational biology, with applications to predictions of structural contacts in proteins and other areas of biological data analysis. The corresponding inference problems are challenging since the normalization constant (partition function) of the Ising or Potts distribution cannot be computed efficiently on large instances. Different ways to address this issue have resulted in a substantial amount of methodological literature. In this paper we investigate how these methods could be used on much larger data sets than studied previously. We focus on a central aspect, that in practice these inference problems are almost always severely undersampled, and the operational result is almost always a small set of leading predictions. We therefore explore an approach where the data are prefiltered based on empirical correlations, which can be computed directly even for very large problems. Inference is only used on the much smaller instance in a subsequent step of the analysis. We show that in several relevant model classes such a combined approach gives results of almost the same quality as inference on the whole data set. It can therefore provide a potentially very large computational speedup at the price of only marginal decrease in prediction quality. We also show that the results on whole-genome epistatic couplings that were obtained in a recent computation-intensive study can be retrieved by our approach. The method of this paper hence opens up the possibility to learn parameters describing pairwise dependences among whole genomes in a computationally feasible and expedient manner.

Figure 1

Illustration of CCDCA as applied to nucleotide sequence data. The input MSA data set is an $N\times L$ matrix $A$, with $N$ the total number of sample sequences (${\mathbf{\sigma }}^{\left(\alpha \right)}$, $\alpha =1,2,...,N$) and $L$ the length of each sequence. Each entry is a sequence letter (one of the four nucleotides A, G, C, and T). In the data analyzed in Sec. 6 one of the sequence letters can also be N (anything). The covariance matrix $C_{ij}$ between any two loci $i$ and $j$ is then computed by reading the $i\mathrm{th}$ and the $j\mathrm{th}$ column of matrix $A$, and the column pair $(i,j)$ is given a score. In Sec. 6 the score used is MI. The $m$ column pairs of largest scores are selected. After considering the $\ell \le 2m$ loci involved in these $m$ pairs, the original MSA matrix $A$ is reduced to another $N\times \ell$ MSA matrix $B$ for further analysis by some flavors of DCA.

Figure 2

Scatter diagrams of inferred couplings vs true couplings for ferromagnetic RPL data. The number of spins is $L=1024$ and the number of samples (obtained at $T=2500$) is (a)–(d) $N=0.5L$ and (e)–(h) $N=16L$. (a) and (e) Scatter diagrams of the covariance elements $C_{ij}$ as the inferred couplings. Also shown are scatter diagrams of the inferred couplings being the CCPLM results at different levels of compression: CCPLM on MSA from the subsystem of size (b) $\ell =16$ (with $m=8$), (c) $\ell =32$ (with $m=16$), (d) $\ell =64$ (with $m=32$), (f) $\ell =16$ (with $m=8$), (g) $\ell =31$ (with $m=16$), and (h) $\ell =61$ (with $m=32$).

Figure 3

Same as Fig. 2 but for a spin-glass RPL instance ($L=1024$ and temperature $T=300$). The number of samples is (a)–(d) $N=0.5L$ and (e)–(h) $N=16L$. The size of the subsystem is (b) $\ell =16$ (with $m=8$), (c) $\ell =29$ (with $m=16$), (d) $\ell =57$ (with $m=32$), (f) $\ell =16$ (with $m=8$), (g) $\ell =31$ (with $m=16$), and (h) $\ell =56$ (with $m=32$).

Figure 4

True positive rates [Eq. (7)] for the random power-law model, with couplings being [(a) and (b)] ferromagnetic (FM) and [(c) and (d)] spin-glass (SG). The data dimension $L=1024$ and the power-law exponent $\gamma =3$. Results are shown for sample numbers (a) and (c) $N=0.5L$ and (b) and (d) $N=16L$. Temperatures are $T=2500$ for the ferromagnetic case and $T=300$ for the spin-glass case, in both cases well above the estimated critical temperature. The elements of the coupling matrix $\mathit{J}$ are ranked according to the covariance matrix $C$ (circles), the PLM predictions on the whole system (squares), or the PLM predictions on the correlation-compressed subsystem constructed using $m=8$ (stars), $m=16$ (crosses), and $m=32$ (triangles) strongest covariance elements.

Figure 5

Comparison of PLM and CCPLM on the SK model. There are $L=1024$ spins and $p=L(L-1)/2$ coupling constants. A total number of $N=16L$ independent equilibrium configurations are sampled at temperature $T=2$. (a) Relation between the covariance element $C_{ij}$ and the true coupling constant $J_{ij}$. (b) Relation between the predicted coupling constant $J_{ij}^{\mathrm{PLM}}$ and the true value $J_{ij}$ for the whole system. (c)–(e) Relation between the predicted coupling constant and the true coupling constant for the subsystem of size (c) $\ell =16$ (obtained by considering the $m=8$ strongest covariance elements), (d) $\ell =31$ (for $m=16$), and (e) $\ell =62$ (for $m=32$).

Figure 6

The 6003 long-range couplings among the $1.2\times {10}^5$ strongest ones identified by CCPLM with $3\times {10}^4$ largest correlations. Numbers outside the rim indicates genomic positions in units of $1000\mathrm{bp}$. The darkness of the lines represents the strength of couplings. The number of loci involved is 9304. Short-range couplings, the distance of which is smaller than $10000\mathrm{bp}$, are not shown here. (See Fig. 11 in Appendix pp5 for the visualization of all $1.2\times {10}^5$ strongest couplings.) Positions 293, 332, and 1613 are the genes pbp2x, pbp1a, and pbp2b, respectively.

Figure 7

The 5199 long-range strong couplings identified in [14] depicted with the same visualization procedure as for Fig. 6. Besides the links among genes pbp2x, pbp1a, and pbp2b, one can also identify the link to dyr (position 1530) and the triad of interactions involving divIVA (position 1600), pspA (position 120), and a site upstream of gene ply (position 1890).

Figure 8

The $19224$ long-range correlations among the $1.2\times {10}^5$ strongest ones of the subsystem from which the results shown in Fig. 6 are obtained.

Figure 9

Phase diagrams of RPL instances used: (a) FM RPL and (b) SG RPL. Here $m\equiv \frac{1}{L}{\sum }_{i=1}^L{m}_i$ denotes the system's magnetization and $q\equiv \frac{1}{L}{\sum }_{i=1}^L\left|m_i\right|$ denotes the schematic order parameter for a spin-glass model, where $m_i=\frac{1}{N}{\sum }_{b=1}^N{\sigma }_i^b$.

Figure 10

The (a), (e), and (i) DCA and (b)–(d), (f)–(h), and (j)–(l) CCDCA on a chain SK model containing $L=1024$ spins and $p=L(L-1)/2$ couplings $J_{ij}$. A total number of $N=16L$ equilibrium spin configurations are sampled from this model at temperature $T=5$. (a)–(d) Relation between coupling $J_{ij}$ and covariance element $C_{ij}$. (e)–(h) and (i)–(l) Relation between the predicted coupling $J_{ij}^{\text{PLM}}$ and the true coupling $J_{ij}$; the results are obtained with regularization parameter (e)–(h) $\lambda ={10}^{-2}$ and (i)–(l) $\lambda ={10}^{-5}$. The analysis is of (a), (e), and (i) the whole system and the subsystems with (b), (f), and (j) $\ell =15$ (according to the $m=8$ strongest covariance elements); (c), (g), and (k) $\ell =19$ (for $m=16$); and (d), (h), and (l) $\ell =20$ (for $m=32$) spins.

Figure 11

The $1.2\times {10}^5$ strongest couplings identified by CCPLM with the $3\times {10}^4$ largest correlations. This figure supplements Fig. 6 by showing short-range couplings as well as long-range ones. Short-range couplings are depicted near the rim and long-range couplings are depicted inside; there is a visible margin between them.

Figure 12

The 2423 long-range correlations among the $1.2\times {10}^5$ strongest ones of the whole genome after filtering.

Figure 13

The $1.2\times {10}^5$ strongest couplings identified by CCPLM with the ${10}^4$ largest correlations.

Figure 14

The $52790$ long-range couplings among the $1.2\times {10}^5$ strongest ones identified by CCPLM with the ${10}^4$ largest correlations.