This study determined the effect of tyrosine (Tyr) and phenylalanine (Phe) deprivation on protein expression and phosphorylation of mitogen-activated protein kinase kinase 4 (MKK4)/stress-activated protein/Erk kinase (SEK1), a metastasis suppressor gene. Differential display and suppressive subtractive hybridization techniques identified genes modulated by Tyr and Phe deprivation. Expression of MKK4/SEK1 protein varied widely among human A375, A375SM and SB2 melanoma, PC-3 and DU145 prostate cancer, and MDA-MB-231 breast cancer cell lines and within the different lines. Phosphorylation of the MKK4/SEK1 protein similarly varied. No differences in MKK4/SEK1 gene expression or in the 41 other metastasis and tumor suppressor genes were found in A375 melanoma cells cultured in Tyr- and Phe-deprived media. A number of up-regulated and down-regulated genes in A375 melanoma cells were identified by differential display and suppressive subtractive hybridization that were pertinent to regulation of cytoskeletal organization, cell movement, gene transcription and metastasis. Two tumor marker genes, the gene for enolase and FUS/CHOP, were down-regulated by Tyr and Phe deprivation. This study shows that tumor cells display heterogeneity in their response to deprivation of Tyr and Phe and that these amino acids may be signaling molecules that regulate gene expression and function in tumor cells.