A method is presented that uses beta-strand interactions at both the sequence and the atomic level, to predict the beta-structural motifs in protein sequences. A program called Wrap-and-Pack implements this method, and is shown to recognize beta-trefoils, an important class of globular beta-structures, in the Protein Data Bank with 92% specificity and 92.3% sensitivity in cross-validation. It is demonstrated that Wrap-and-Pack learns each of the ten known SCOP beta-trefoil families, when trained primarily on beta-structures that are not beta-trefoils, together with 3D structures of known beta-trefoils from outside the family. Wrap-and-Pack also predicts many proteins of unknown structure to be beta-trefoils. The computational method used here may generalize to other beta-structures for which strand topology and profiles of residue accessibility are well conserved.