Post-translational modification (PTM) of proteins by enzymes such as methyltransferases, kinases and deacetylases play a crucial role in the regulation of many metabolic pathways. Determining the substrate scope of these enzymes is essential when studying their biological role. However, the combinatorial nature of possible protein substrate sequences makes experimental screening assays intractable. To predict new substrates for proteins, various computational approaches have been developed. Our method relies on crystallographic data and a novel multistate computational protein design algorithm. We previously used our method to successfully predict four new substrates for SMYD2 (Lanouette S & Davey J.A., 2015), doubling the number of known targets for this PTM enzyme that has been difficult to characterize using other methods. This was possible by first extracting a specificity profile of Smyd2 using our algorithm and subsequently screening a peptide library for matching sequences. However, our method did not yield successful results when attempting to reproduce specificity profiles of other proteins (64% accuracy on average). Different protein environments have demonstrated limitations in the methodology and lead us to further develop the algorithm on a more thorough dataset. Using our new optimized method, specificity profile predictions increase by roughly 20% (84% accuracy on average), independent of the structural template used. The algorithm was then used to blindly predict a specificity profile for the methyltransferase Smyd3, an enzyme for which limited data is currently available. A library of 2550 peptides was screened with the predicted profile, yielding 123 matching sequences. We randomly chose 64 for experimental validation (SPOT peptide array) of methylation by Smyd3 and found 45 methylated and 19 non-methylated peptides (70% success rate). Finally, we released to the community a web version of the algorithm, which can be accessed as http://viper.science.uottawa.ca.