  One of the most challenging and long-standing problems in computational
biology is the prediction of three-dimensional protein structure from amino
acid sequence. A promising approach to infer spatial proximity between residues
is the study of evolutionary covariance from multiple sequence alignments,
especially in light of recent algorithmic improvements and the fast growing
size of sequence databases. In this paper, we present a simple, fast and
accurate algorithm for the prediction of residue-residue contacts based on
regularized least squares. The basic assumption is that spatially proximal
residues in a protein coevolve to maintain the physicochemical complementarity
of the amino acids involved in the contact. Our regularized inversion of the
sample covariance matrix allows the computation of partial correlations between
pairs of residues, thereby removing the effect of spurious transitive
correlations. The method also accounts for low number of observations by means
of a regularization parameter that depends on the effective number of sequences
in the alignment. When tested on a set of protein families from Pfam, we found
the RLS algorithm to have performance comparable to state-of-the-art methods
for contact prediction, while at the same time being faster and conceptually
simpler.
