RATIONALE: Vaccine therapy may help the body build an effective immune response to kill tumor cells.

PURPOSE: This randomized clinical trial is studying how well vaccine therapy works in treating patients with advanced melanoma.

OBJECTIVES:

• To assess the circulating CD8 T-cell response to vaccination with a multipeptide vaccine in patients with advanced melanoma.
• To determine whether immunization with peptides and incomplete Freund's adjuvant induces lymph-node-like aggregates (LNLA) and tertiary lymphoid organs (TLOs) in the skin of these patients.
• To determine whether extended immunization (vaccinations 4-6) is associated with induction of negative immune-regulatory processes in the vaccination site microenvironment/TLO.
• To characterize peptide-reactive CD4 and CD8 T cells in loco at sites of immunization with a multipeptide vaccine.
• To characterize the expression of toll-like receptors 4, 7, 8, and 9, and MyD88 in dendritic cells infiltrating vaccination sites over the course of 6 vaccinations and after vaccination.

OUTLINE: Patients are randomized to 1 of 10 arms.

All patients receive primary vaccine comprising melanoma multipeptides and tetanus toxoid helper peptide emulsified in incomplete Freund's adjuvant, half of the volume subcutaneously (SC) and the other half intradermally (ID), 6 times over 7 weeks on days 1, 8, 15, 29, 36, and 43. Vaccines are administered in a single skin location on an extremity clinically uninvolved with melanoma. A replicate vaccine site is identified for each patient for skin biopsy with or with out replica vaccine administration.

• Arm 1A: Patients receive no replicate vaccine. Patients undergo surgical biopsy at replicate vaccine site on day 1.
• Arm 1B: Patients receive replicate vaccine comprising incomplete Freund's adjuvant only SC and ID on day 1 and undergo surgical biopsy at replicate vaccine site on day 8 (1 week after replicate vaccine 1).
• Arm 1C: Patients receive replicate vaccine comprising incomplete Freund's adjuvant only SC and ID on days 1, 8, and 15 and undergo surgical biopsy at replicate vaccine site on day 22 (1 week after replicate vaccine 3).
• Arm 1D: Patients receive replicate vaccine comprising incomplete Freund's adjuvant only SC and ID on days 1, 8, 15, 29, 36, and 43 and undergo surgical biopsy at replicate vaccine site on day 50 (1 week after replicate vaccine 6). Patients are evaluated 1-3 weeks after biopsy.
• Arm 1E: Patients receive replicate vaccine comprising incomplete Freund's adjuvant only SC and ID on days 1, 8, 15, 29, 36, and 43 and undergo surgical biopsy at replicate vaccine site on day 85 (6 week after replicate vaccine 6). Patients are evaluated 1-3 weeks after biopsy.
• Arm 2A: Patients receive no replicate vaccine. Patients undergo surgical biopsy at replicate vaccine site on day 1.
• Arm 2B: Patients receive replicate vaccine (the same as primary vaccine) SC and ID on day 1 and undergo surgical biopsy at replicate vaccine site on day 8 (1 week after replicate vaccine 1).
• Arm 2C: Patients receive replicate vaccine (the same as primary vaccine) SC and ID on days 1, 8, and 15 and undergo surgical biopsy at replicate vaccine site on day 22 (1 week after replicate vaccine 3).
• Arm 2D: Patients receive replicate vaccine (the same as primary vaccine) SC and ID on days 1, 8, 15, 29, 36, and 43 and undergo surgical biopsy at replicate vaccine site on day 50 (1 week after replicate vaccine 6). Patients are evaluated 1-3 weeks after biopsy.
• Arm 2E: Patients receive replicate vaccine (the same as primary vaccine) SC and ID on days 1, 8, 15, 29, 36, and 43 and undergo surgical biopsy at replicate vaccine site on day 85 (1 week after replicate vaccine 6). Patients are evaluated 1-3 weeks after biopsy.

Tissue biopsies are examined by reverse transcriptase-PCR, IHC, protein analysis, flow cytometry, and western blot. Blood samples are collected periodically and examined by ELIspot assay, tetramer staining, and proliferation assay.

After completion of study therapy, patients are followed annually.

DISEASE CHARACTERISTICS:

• Histologically or cytologically confirmed melanoma that meets one of the following criteria:

  • Stage IIB-IV melanoma rendered clinically free of disease by surgery, other therapy, or spontaneous remission within the past 6 months
  • Stage III or IV melanoma with disease

• Persistent or metastatic disease allowed if RECIST criteria for measurable disease is not met

• Multiple primary melanomas allowed

• Prior or concurrent metastasis from a cutaneous, mucosal, ocular, or unknown primary site allowed

• No clinically detectable melanoma deemed likely by the investigator to require intervention during the first 12 weeks of the study that would require premature discontinuation (e.g., untreated bone metastases at risk for fracture or rapidly progressive low-volume disease)

• Brain metastases allowed if all of the following criteria are met:

  • The total number of brain metastases ever is ≤ 3
  • The brain metastases have been completely removed by surgery or have been treated completely by stereotactic radiotherapy
  • There has been no evident growth of any brain metastasis since treatment
  • No treated brain metastasis > 2 cm in diameter

• At least two intact axillary and/or inguinal lymph node basins

• Prior lymph node biopsy allowed if lymphoscintigraphy demonstrates intact drainage to a node in that basin

  • If a sentinal lymph node is not located by lymphoscintigraphy, patient is not eligible for study

• HLA-A1, -A2, -A3, or -A11 positive

• Either eligible for, but refused interferon therapy OR not a candidate for interferon therapy for the following reasons:

  • Active ischemic heart disease or cerebrovascular disease
  • Anginal syndrome requiring ongoing medications or history of myocardial infarction or arrhythmia disorder
  • History of treatment for depression, active depression, or other psychiatric disorder
  • Autoimmune disorders
  • Hypersensitivity to interferon-alfa or any component associated with interferon therapy
  • Debilitating medical conditions such as severe pulmonary disease or severe diabetes mellitus
  • Thyroid abnormalities, where thyroid function cannot be maintained in the normal range without medication
  • Resected stage IV melanoma
  • Discontinued interferon therapy due to the occurrence of a major toxicity that has been documented by the treating physician
  • Experienced tumor progression while on interferon or after completing interferon therapy
  • Missed the standard-of-care enrollment window for interferon therapy initiation

PATIENT CHARACTERISTICS:

• ECOG performance status 0-1
• ANC > 1,000/mm^3
• Platelets > 100,000/mm^3
• Hemoglobin > 9 g/dL
• AST and ALT ≤ 2.5 times upper limit of normal (ULN)
• Bilirubin ≤ 2.5 times ULN
• Alkaline phosphatase ≤ 2.5 times ULN
• Creatinine ≤ 1.5 times ULN
• Hepatitis C and HIV negative (antibody screening)
• Hemoglobin_A1C level < 7%
• Body weight ≥ 110 pounds
• Not pregnant or nursing
• Negative pregnancy test
• Fertile patients must use effective contraception during study treatment
• No New York Heart Association class III-IV heart disease
• No known or suspected allergies to any component of the vaccine
• No medical contraindication or potential problem in complying with the requirements of the protocol

PRIOR CONCURRENT THERAPY:

• See Disease Characteristics

• Prior peptide vaccines (including MELITAC 12.1 and similar vaccines) or non-peptide vaccines allowed

• At least 1 week since prior stereotactic radiotherapy, such as gamma knife

• No influenza vaccine ≥ 2 weeks before, during, and ≥ 2 weeks after completion of study therapy

• More than 4 weeks since prior and no concurrent use of any of the following:

  • Systemic cytotoxic chemotherapy (6 weeks for nitrosoureas)

  • Radiotherapy

  • Other experimental therapy

  • 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., fluticasone propionate [Advair® or Flovent®] or triamcinolone acetonide [Azmacort®])

    • Topical corticosteroids and steroids with very low solubility administered nasally for local effects only allowed (e.g., mometasone furoate [Nasonex®])

  • Growth factors (e.g., sargramostim [GM-CSF], filgrastim [G-CSF], or epoetin alfa)

  • Interferon therapy

  • Aldesleukin or other interleukins

  • Street drugs

• At least 1 month since prior and no other concurrent investigational drugs or therapy

• At least 12 weeks since prior melanoma vaccine for patients who have recurred or progressed either after or during treatment with vaccine