The ability to predict structure from sequence is particularly important for toxins, virulence factors, allergens, cytokines, and other proteins of public health importance. Many such functions are represented in the parallel β-helix and β-trefoil families. A method using pairwise β-strand interaction probabilities coupled with evolutionary information represented by sequence profiles is developed to tackle these problems for the β-helix and β-trefoil folds. The algorithm BetaWrapPro employs a "wrapping" component which may capture folding processes with an initiation stage followed by progressive interaction of the sequence with the already-formed motifs. BetaWrapPro outperforms all previous motif recognition programs for these folds, recognizing the β-helix with 100% sensitivity and 99.7% specificity and the β-trefoil with 100% sensitivity and 92.5% specificity, in cross-validation on a database of all non-redundant known positive and negative examples of these fold classes in the PDB. It additionally aligns 88% of residues for the β-helices and 86% for the β-trefoils correctly to the structural template, which is then used with the side-chain packing program SCWRL to produce 3D structure predictions. One striking result has been the prediction of an unexpected parallel β-helix structure for a pollen allergen, and its recent confirmation through solution of its structure. A web server running BetaWrapPro is available and outputs putative PDB-style coordinates for sequences predicted to form the target folds.