Inclusion Criteria

DISEASE CHARACTERISTICS: Histologically or cytologically confirmed stage III or IV
melanoma gp100 positive tumor cells and/or tyrosinase positive tumor cells HLA type A1,
A2, or A3 Measurable disease May have up to 3 brain metastases if all are less than 2 cm
in diameter and are asymptomatic, and there is no mass effect or they have been treated
successfully by surgical excision or by gamma knife radiation therapy

PATIENT CHARACTERISTICS: Age: 18 to 79 Performance status: ECOG 0-1 Life expectancy: Not
specified Hematopoietic: Absolute neutrophil count greater than 1,000/mm3 Platelet count
greater than 100,000/mm3 Hemoglobin greater than 9 g/dL Hepatic: Bilirubin no greater than
2.5 times upper limit of normal (ULN) AST and ALT no greater than 2.5 times ULN Alkaline
phosphatase no greater than 2.5 times ULN Renal: Creatinine no greater than 1.5 times ULN
Cardiovascular: No New York Heart Association class II, III, or IV heart disease Other: No
known or suspected allergy to any component of the vaccine No medical condition that would
preclude study Not pregnant or nursing Negative pregnancy test Fertile patients must use
effective contraception

PRIOR CONCURRENT THERAPY: Biologic therapy: At least 3 months since prior growth factors
At least 3 months since prior agents with putative immunomodulating activity (except
nonsteroidal antiinflammatory agents) At least 1 year since other prior melanoma
vaccinations Chemotherapy: At least 3 months since prior chemotherapy No concurrent
chemotherapy Endocrine therapy: At least 3 months since prior corticosteroids No
concurrent corticosteroids Radiotherapy: At least 3 months since prior radiotherapy No
concurrent radiotherapy Surgery: See Disease Characteristics Other: At least 3 months
since other prior investigational drugs or therapy At least 3 months since prior allergy
desensitization injections At least 14 days since completion of acute treatment for a
serious infection No concurrent allergy desensitization injections