Inclusion Criteria

DISEASE CHARACTERISTICS:

- Histologically confirmed melanoma meeting the following criteria:

- Unresectable recurrent disease

- Stage III or IV disease

- Cutaneous, ocular, or mucosal melanoma

- Measurable disease as defined by the RECIST criteria

- HLA-A2 positive

- Prior brain metastases allowed provided adequate surgical or radiologic treatment for
brain disease

PATIENT CHARACTERISTICS:

- ECOG performance status 0 or 1

- WBC ≥ 3,000/mm³

- Lymphocytes ≥ 1,000/mm³

- Platelet count ≥ 100,000/mm³

- Creatinine ≤ 1.5 times upper limit of normal (ULN)

- Bilirubin ≤ 1.5 times ULN

- AST and ALT ≤ 2.5 times ULN

- Lactic dehydrogenase ≤ 2.0 times ULN

- aPTT < 40 seconds

- Not pregnant or nursing

- Negative pregnancy test

- Fertile patients must use effective contraception for ≥ 1 week before, during, and
for ≥ 2 weeks after completion of study therapy

- No conditions of immunosuppression

- Negative titers for antinuclear antibody (≤ 1/80) and antidouble stranded DNA (≤
1/10)

- No serious illnesses including, but not limited to, any of the following:

- Bleeding disorders

- Autoimmune diseases

- Severe obstructive or restrictive pulmonary diseases

- Active systemic infections

- Inflammatory bowel disorders

- No serious cardiovascular disease including, but not limited to, any of the
following:

- Uncontrolled congestive heart failure

- Hypertension

- Cardiac ischemia

- Myocardial infarction,

- Severe cardiac arrhythmia

- HIV1 and 2 negative

- HTLV-1 negative

- Hepatitis B and C negative

- No significant psychiatric disease, medical intervention, or other condition that, in
the opinion of the principal investigator, would limit study compliance

- No active infection within the past week, including unexplained fever (temperature >
38.1°C)

PRIOR CONCURRENT THERAPY:

- Fully recovered from prior major surgery

- More than 4 weeks since prior chemotherapy (6 weeks for mitomycin C or nitrosoureas),
hormonal therapy, radiotherapy, or biological therapy

- More than 1 week since prior antibiotics

- More than 28 days since prior investigational agent

- No prior vaccination with MART-1 (26-35, 27L), gp100 (209-217, 210M), and tyrosinase
(368-376, 370D) peptides alone or in combination

- Patients with history of vaccination with peptides other than MART-1 (26-35,
27L), gp100 (209-217, 210M), and tyrosinase (368-376, 370D) peptides allowed

- More than 4 weeks since prior and no concurrent systemic immunosuppressive therapy,
including steroids

- Patients on maintenance steroids given at physiologic doses because of adrenal
insufficiency are eligible

- More than 2 weeks since prior and no concurrent treatment with systemic steroids,
including oral steroids, continuous use of topical steroid creams or ointments, or
any inhaled steroids

- No concurrent anticoagulants, except to keep an indwelling line patent

- No other concurrent anticancer therapy, including chemotherapy, immunotherapy,
radiotherapy, experimental programs, and/or surgery