• PSA doubling-time response [ Time Frame: 18 months ] [ Designated as safety issue: Yes ]
  

• Serum PSA levels and immune response [ Time Frame: 18 months ] [ Designated as safety issue: Yes ]
  

Subjects will be randomized to Arm A (vaccine only) or Arm B (androgen deprivation therapy plus vaccine). On Arm A, subjects can begin the three vaccinations immediately. On Arm B, subjects will be started on androgen deprivation therapy (ADT) 14 days prior to beginning the vaccinations.

Subjects will be vaccinated three times, each injection administered at 30-day intervals. Based upon our earlier clinical trial, the vaccine is considered safe and should not induce any major side effects. We hope that vaccination with this PSA virus will cause the body to produce immunity to the PSA and that immunity will destroy any cell that produces PSA. Since the only cells left in the body that produce PSA will be the cancer cells, we propose that the vaccination and ensuing anti-PSA immunity will kill the prostate cancer cells. Importantly, this treatment should not cause any major side effects as would treatment with anti-cancer drugs.

Inclusion Criteria:

• Men with prostate cancer who have received prior local therapy (radical prostatectomy or definitive radiation therapy) and have biochemical (PSA) relapse without evidence of radiographic or clinical metastatic disease.
• For men who had prior prostatectomy, the surgery must have occurred at least 6 months prior to study enrollment.
• For men who had prior definitive radiation therapy, radiation must have occurred at least 1 year prior to study enrollment.
• Exhibit at least four separate rises in serum PSA, at least one month apart with differences >0.03 ng/ml and a total PSA of >0.2 ng/ml.
• Have a PSA doubling time of >6 months.
• Not at high risk as defined as those with a serum PSA of >20 ng/ml and a Gleason score of >7 before prostatectomy or radiation.
• Negative bone scans.
• Negative CT scans of chest abdomen and pelvis (no soft tissue metastases present).
• Scans must be obtained within 6 weeks of entry into the trial.
• Written informed consent.
• Age > 18 years.
• Required laboratory values (obtained within 2 weeks of study entry)
• Serum creatinine < 2.0 mg/dL
• Adequate hematologic function: granulocytes > 1800 per mm3, platelets > 100,000 per mm3, WBC >3700, and lymphocytes >590.
• Adequate hepatocellular function: AST <3x normal and bilirubin <1.5 mg/dl.

Exclusion Criteria:

• Candidates for salvage radiation therapy unless the patient refuses.
• Had a serum PSA of >20 ng/ml prior to surgery or radiation.
• Gleason score of >7.
• Seminal vesicle involvement or positive lymph nodes.
• Active or unresolved infection.
• Parenteral antibiotics <7 days prior to study entry.
• Evidence of prior or current CNS metastases. Specific imaging is not necessary in the absence of signs or symptoms.
• Co-morbid medical conditions which would result in a life expectancy (participation) of less than 1 year.
• Patients with compromised immune systems; congenital, acquired, or druginduced immunosuppressive agents) will be excluded from the study. Use of prednisone at doses higher than 10 mg daily (or equipotent steroid doses) for more than 7 days within the last 3 months is not allowed.
• No-pre-existing malignancies that required treatment within the past 5 years except for basal or squamous cell cancers of the skin.
• Prior systemic therapies for prostate cancer not allowed (hormonal therapy, including but not limited to LHRH agonists, antiandrogens, ketoconazole or chemotherapy - mitoxantrone/taxanes/estramustine, etc.); only patients in Arm B, undergoing androgen depletion therapy during the vaccination will be eligible.
• Prior participation in any vaccine studies for any disease.
• The inability to understand the language and the clinical protocol.
• Allergy or religious objection to pork products; Gelfoam is produced from pork.