  Protein contacts contain important information for protein structure and
functional study, but contact prediction from sequence information remains very
challenging. Recently evolutionary coupling (EC) analysis, which predicts
contacts by detecting co-evolved residues (or columns) in a multiple sequence
alignment (MSA), has made good progress due to better statistical assessment
techniques and high-throughput sequencing. Existing EC analysis methods predict
only a single contact map for a given protein, which may have low accuracy
especially when the protein under prediction does not have a large number of
sequence homologs. Analogous to ab initio folding that usually predicts a few
possible 3D models for a given protein sequence, this paper presents a novel
structure learning method that can predict a set of diverse contact maps for a
given protein sequence, in which the best solution usually has much better
accuracy than the first one. Our experimental tests show that for many test
proteins, the best out of 5 solutions generated by our method has accuracy at
least 0.1 better than the first one when the top L/5 or L/10 (L is the sequence
length) predicted long-range contacts are evaluated, especially for protein
families with a small number of sequence homologs. Our best solutions also have
better quality than those generated by the two popular EC methods Evfold and
PSICOV.
