Purpose of investigation: Primary hypotheses: Immunization of patients with 4 melanoma antigen peptides will induce augmented specific IFN-y-producing CD8+ T cells against all 4 antigens simultaneously. Immunization with 4 melanoma antigen peptides will increase the response rate from 10% to 30%. Administration of low-dose IL-2 following each vaccine will result in a greater than 3-fold increase in specific T cells compared to no IL-2.

Secondary hypotheses: Immunization will clear the blood of detectable circulating melanoma cells. Tumors that grow despite induction of melanoma antigen-specific T cells may lack expression of antigens, class I MHC, or the TAP peptide transporter, or may fail to show increased expression of mRNA for IFN-y or perforin. Tumors that resist vaccination may express a different array of genes than those that are susceptible to vaccination.

Based on the above preclinical and Phase I results, a logical strategy for a second generation melanoma vaccine has emerged. A randomized Phase II study in metastatic melanoma patients will be undertaken. Patients first will be HLA-typed; HLA-A2-positive patients will be eligible for screening. When feasible, each patient will undergo a tumor biopsy to screen for expression of MAGE-3, Melan-A, gplOO, and NAI 7 using RT-PCR and immunohistochemistry, to determine whether T cells are present in the lesion, to measure cytokine gene expression by RT-PCR, and to perform gene array analysis. In addition, blood cells will be analyzed for certain parameters of T cell function.

Patients will be randomized to cohorts A (no IL-2) or B (with low-dose IL-2). For treatment, peripheral blood will be collected and fractionated by density centrifugation to isolate PBMC as a source of APC. The PBMC will be divided into four pools, each of which will be incubated with one of the following peptides: MAGE-3, Melan-A, gp 100, or Ni 7A. The peptide-loaded cells will then be washed and recombined into a single suspension in PBS, and lethally irradiated. Approximately 120 x 106 pulsed cells will be injected subcutaneously at a site near a lymph node not thought to be involved with tumor. The subcutaneous route has been selected for the reasons of safety, efficacy in the preclinical model, and the goal of targeting the vaccine to a draining lymph node. rhIL-12 (4 .tg straight dose) will then be given subcutaneously adjacent to the vaccine site days 1,3, and 5 of each cycle. This dose and schedule was found to be effective in our phase I study. In one-half of the patients (cohort B), IL-2 (I MU straight dose) will be administered subcutaneously daily, days 7-18. Re-immunization along with rhIL-12 followed by IL-2 (if assigned) will be performed at 3 week intervals as in cycle I.

On day 1 of each cycle, peripheral blood will be collected to measure peptide-specific IFN-y production. Before treatment and after every 3 cycles, PBMC will be collected to quantify peptide specific CD8 T cells by flow cytometric analysis with peptide/HLA-A2 tetramers, and evidence for a molecular response will be assessed by performing RT-PCR. for melanoma antigens on peripheral blood samples. In addition, prior to treatment, after the first 3 cycles, and at the time of going off- study, a tumor biopsy will be performed to assess the immune response in the tumor microenvironment, including gene array analysis. It is hoped that these studies will uncover the reason for lack of clinical response in patients with residual tumors. Clinical response will be assessed as a secondary outcome.

Inclusion Criteria:

• Histologically-confirmed melanoma with evidence of metastatic disease, either by radiologic or physical examination. In transit metastases are allowed. Biopsy should be performed to reconfirm the diagnosis in cases of doubt.
• Life expectancy of at least 12 weeks.
• Karnofsky performance status index >/=70.
• Written informed consent
• Adequate hematopoietic, renal, and hepatic function
• LDH <1.25 x ULN
• HLA typing: patient must express HLA-A2.
• Tumor biopsy: patient must agree to undergo biopsy of accessible tumor before and after therapy, when feasible, to study tumor cell properties and characteristics of immune cells.

Exclusion Criteria:

• Significant cardiovascular disease, or cardiac arrhythmia requiring medical intervention.
• Pregnant or nursing women.
• Biological therapy in the 4 weeks prior to the start of dosing.
• Prior therapy with a melanoma vaccine containing MAGE-3, Melan-A, gplOO, NA17 peptides.
• Patients with intrinsic immunosuppression, including seropositivity for HIV antibody. Patient should be tested if risk factors are identified.
• Serious concurrent infection, including active tuberculosis, hepatitis B, or hepatitis C.
• Concurrent systemic corticosteroids (except physiologic replacement doses) or other immunosuppressive drugs (eg. cyclosporin A).
• Psychiatric illness that may make compliance to the clinical protocol unmanageable or may compromise the ability of the patient to give informed consent.
• Active or history of autoimmune disease including but not limited to: rheumatoid arthritis (RF-positive with current or recent flare), inflammatory bowel disease, systemic lupus erythematosis (clinical evidence with ANA 1:80 or greater), ankylosing spondylitis, scleroderma, multiple sclerosis, autoimmune hemolytic anemia, and immune thrombocytopenic purpura.
• Active gastrointestinal bleeding or uncontrolled peptic ulcer disease. Presence of untreated brain metastases. All patients must undergo brain imaging as part of the pre-study evaluation. Only patients with no brain metastases, or with brain lesions successfully treated by stereotactic radiation or surgical removal without recurrence at 28 day follow-up, will be eligible.