Background: For genome sequencing projects to achieve their full impact on biology and medicine, each protein sequence must be identified with its three-dimensional structure. Fold assignment methods (also called profile and threading methods) attempt to assign sequences to known protein folds by computing the compatibility of sequence to fold.Results: We have extended profile methods for the detection of protein folds having structural similarity but low sequence similarity to sequence probes. Our extension combines sequence substitution tables with structural properties to form a combined profile. The structural properties used in this study include distances between residues, exposed areas, areas buried by polar atoms, and properties of the original three-dimensional profile method. We compared the performance of these combined profiles with different sequence matrices and with the original three-dimensional profile method. To determine the optimal gap penalties and weights used with these profiles, we employed a genetic algorithm. The performance of these combined profiles was tested by cross validation using independent test and training sets.Conclusions: These studies show that the combined profiles perform better than profiles based on either structural or sequence information alone.