Evaluating the Safety and the Biological Effects of Intratumoral Interferon Gamma and a Peptide-Based Vaccine in Patients With Melanoma

Inclusion Criteria: 1. Participants with stage IIIB, IIIC or IV melanoma. Staging must be confirmed by cytological or histological examination. Staging of cutaneous melanoma will be based on the revised AJCC staging system. 2. Patients must have adequate cutaneous or subcutaneous metastases of melanoma readily accessible for biopsy to provide a minimum of 0.3 cm3 of tissue per biopsy (approximately 0.85 cm by 0.85 cm x 0.85 cm or five 2mm core biopsies) at each time point. Additionally, at least one of the subcutaneous or cutaneous metastases must be accessible to intratumoral IFN-gamma administration. Several scenarios may fulfill the tumor burden requirement. For example, a patient may have one large lesion from which core biopsies can be taken for the first and second biopsy time points and then the entire lesion excised for the final tissue sample. Alternatively, a patient may have three lesions, each ≥0.3 cm3, and these lesions would be excised sequentially as biopsies 1, 2 and 3. Other combinations are acceptable. The intent is to limit this study to patients with cutaneous or subcutaneous melanoma metastasis rather than lymph node metastasis. There may be cases where a subcutaneous nodule cannot be definitively characterized as a non-nodal metastasis at the start of the trial - these patients may be included. 3. Participants with ocular, mucosal or unknown primaries and participants with multiple primaries will be eligible. 4. Participants who have had brain metastases may be eligible in selected circumstances: Patients with less than or equal to 3 metastases may eligible as long as the following 3 criteria are true: * The brain metastases have been completely removed by surgery or have been treated completely by stereotactic radiotherapy. Stereotactic radiotherapy, such as gamma knife, can be used up to 1 week prior to study entry. * There has been no evident growth of any brain metastasis since treatment. * No metastasis greater than 2 cm at the time of protocol entry Patients with greater than 3 metastases may be eligible if the above 3 criteria are met and if at least one year has elapsed since the last treatment. 5. All participants must have: * ECOG performance status of 0 or 1 * Ability and willingness to give informed consent 6. Laboratory parameters - The following laboratory parameters will be required for all participants. If a lab value appears to be an error or a result of a transient or treatable condition, the investigator will use his/her clinical judgment to decide if the test may be repeated. The requirements for inclusion are as follows: * HLA-A1, -A2, -A3, or -A11+ * ANC \> 1000/mm3 * Platelets \> 100,000/mm3 * Hgb \> 9 g/dL * HGBA1C \< 7% * Hepatic: * AST and ALT ≤ 2.5 x upper limits of normal (ULN) * Bilirubin ≤ 2.5 x ULN * Alkaline phosphatase ≤ 2.5 x ULN * Renal o Creatinine ≤ 1.5 x ULN * Serology (within 6 months of study entry) * HIV negative * Hepatitis C negative * LDH up to 2 x ULN 7. Age 18 years or older at the time of trial entry 8. Participants must have at least one intact (undissected) axillary and/or inguinal lymph node basin Exclusion Criteria: 1. Patients who have had brain metastases unless they meet the criteria outlined above in the inclusion criteria. 2. Patients who are currently receiving systemic cytotoxic chemotherapy, radiation, or other experimental therapy, or who have received this therapy within the preceding 4 weeks. Gamma knife or stereotactic radiosurgery may be administered within the prior 4 weeks, but must not be administered less than one week prior to study enrollment. Patients who are currently receiving nitrosoureas or who have received this therapy within the preceding 6 weeks. 3. Patients will not be eligible if there is clinically detectable melanoma deemed likely by the investigator to require intervention during the first 3 months of the study that would require premature discontinuation. Examples for such circumstances may include untreated bone metastases at risk for fracture, and rapidly progressive low volume disease. 4. Patients with known or suspected allergies to any component of the vaccine. 5. Patients receiving the following medications at study entry or within the preceding 4 weeks are excluded: * Agents with putative immunomodulating activity (with the exception of non-steroidal anti-inflammatory agents and topical steroids) * Allergy desensitization injections. * Systemic corticosteroids, administered parenterally or orally. Inhaled steroids (e.g. Advair®, Flovent®, Azmacort®) are not permitted. Topical corticosteroids are acceptable, including steroids with very low solubility administered nasally for local effects only (e.g. Nasonex®). * Any growth factors (e.g. GM-CSF, G-CSF, erythropoietin). * Interferon therapy * Interleukin-2 or other interleukins. 6. Prior melanoma vaccinations may be an exclusion criterion in some circumstances: * Patients who have recurred or progressed either after or during administration of a melanoma vaccine may be eligible to enroll 12 weeks following their last vaccination. * Patients may have been vaccinated previously with peptide vaccines (including MELITAC 12.1 and similar vaccines) or with non-peptide vaccines. 7. Other investigational drugs or investigational therapy if the patient is currently taking those drugs/therapy, or if they have received the drugs/therapy within 1 month. 8. Pregnancy or the possibility of becoming pregnant during vaccine administration. Female patients of child-bearing potential must have a negative pregnancy test (urinary or serum beta-HCG) prior to administration of the first vaccine dose. Males and females must agree, in the consent form, to use effective birth control methods during the course of vaccination. Women must also not be breast feeding. This is consistent with existing standards of practice for vaccine and chemotherapy protocols. 9. Patients in whom there is a medical contraindication or potential problem in complying with the requirements of the protocol, in the opinion of the investigator. 10. Patients classified according to the New York Heart Association classification as having Class III or IV heart disease. 11. Patients with a body weight \< 110 lbs because of the amount and frequency with which blood will be drawn 12. Participants must not have had prior autoimmune disorders requiring cytotoxic or immunosuppressive therapy, or autoimmune disorders with visceral involvement. Participants with an active autoimmune disorder requiring these therapies are also excluded. The following will not be exclusionary: * The presence of laboratory evidence of autoimmune disease (e.g. positive ANA titer) without symptoms * Clinical evidence of vitiligo * Other forms of depigmenting illness * Mild arthritis requiring NSAID medications