The purpose of this study is to learn what effects (good and bad) experimental phosphopeptide vaccines plus a tetanus peptide and other substances called polyICLC and Montanide ISA-51 have on people with melanoma. The investigators will also look at whether the experimental reagents cause any changes in the immune system.

Inclusion Criteria:

Histologically or cytologically proven high-risk or advanced solid malignancies including melanoma, colorectal cancer, ovarian cancer, breast cancer, or non small-cell lung cancer (NSCLC) that meets one of the following criteria:

Melanoma:

For Arms A and B: Stage IIIB-IV melanoma rendered clinically free of disease by surgery, other therapy, or spontaneous remission For Arm C: Stage IIA-IV melanoma rendered clinically free of disease by surgery, other therapy, or spontaneous remission For all Arms: Stage III or IV melanoma with disease, for patients who have failed other approved therapies, are not candidates for approved therapies, or refuse other approved therapies.

Staging will be based on the 7th edition AJCC staging system for melanoma and other cancers. Staging of mucosal melanomas will be based on the following system modified from the cutaneous melanoma staging system: IIA: 2.01- 4mm primary, or stage IIB: > 4mm primary, lymph node metastases = stage III, distant metastases = stage IV.

Breast cancer:

Metastatic stage IV or unresectable breast cancer on endocrine therapy or on no other systemic therapy who have had at least one prior therapy for their metastatic disease. Patients who are metastatic, but with no measurable disease are eligible. Participation in this study should not preclude the delivery of any approved and appropriate anti-cancer therapies, but they are not to be delivered concurrent with this trial, except that patients may participate while taking endocrine-only therapy (eg: aromatase inhibitors or tamoxifen or Lupron). Patients may also participate during pre-planned chemotherapy holidays.

Patients after resection for stage IIIA to IV breast cancer (any ER, PR, or Her2 status) after surgery, radiation therapy, adjuvant chemotherapy, or HER2 targeted therapy.

For Arm C only: Stage I-II, high risk patients with either triple negative breast cancer or HER2 positive disease are also eligible if the tumor is larger than 1 cm. Vaccine will be offered after surgery, radiation therapy or adjuvant chemotherapy (if indicated)

Colorectal cancer:

Metastatic (advanced) colorectal cancer that has failed at least 2 prior chemotherapy regimens, including 5-FU, ironotecan, and oxaliplatin.

High-risk resected metastatic colorectal cancer after resection of liver metastases and after approved agents are administered. For patients after surgical resection of liver metastases,

Eligibility to Arms A and B will be limited to those with at least 3 of the following risk factors: node-positive primary, disease-free interval less than 1 year, more than 1 liver metastasis, size of largest liver metastasis greater than 5 cm, and serum CEA greater than 200 ng/ml.

Eligibility to Arm C will be limited to those with at least 1 of the 5 risk factors listed above.

Ovarian cancer:

Ovarian or fallopian tube cancer that is recurrent or treatment refractory with no remaining alternative, approved therapy options with a reasonable possibility of clinical response.

Non small-cell lung cancer:

Patients with stage IIIB-IV non-small cell lung cancer who have stable disease or clinical response (CR/PR) after treatment with chemotherapy and concurrent radiation therapy.

Patients may have had prior therapy for this cancer in the adjuvant setting and may have had 1-4 prior systemic therapies for advanced cancer.

Patients may have had multiple primary melanomas.

Patients with less than or equal to 5 brain metastases may be eligible as long as the following 3 criteria are true:

1. 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.
2. There has been no evident growth of any brain metastasis since treatment.
3. No metastasis greater than 2 cm at the time of protocol entry

Patients with greater than 5 brain metastases may be eligible if the above 3 criteria are met and if at least one year has elapsed since the last treatment.

All participants must have:

ECOG performance status of 0 or 1 (Appendix 3) Ability and willingness to give informed consent

Patients must have at least one intact axillary and/or inguinal lymph node basin. A patient with a prior lymph node biopsy may be a candidate if lymphoscintigraphy demonstrates intact drainage to a node in that basin. A lymphoscintigram may be performed during screening to ensure that there is drainage to a regional node from a planned vaccine site. If the lymphoscintigram is performed and a sentinel lymph node is not located, the patient will be ineligible for this study if no other vaccine sites are available.

Laboratory parameters as follows: 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-A2+
• ANC > 1000/mm3
• Total lymphocyte count > 500/mm3. If this value is low on initial test after prior cytotoxic therapy, the test may be repeated as the patient recovers further from that therapy.
• 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 Creatinine ≤ 1.5 x ULN
• Serology (within 6 months of study entry) HIV negative Hepatitis C negative
• LDH up to 2 x ULN

Participants must be 18 years or older at study entry.

Patients who have recurred or progressed either after or during administration of a cancer vaccine may be eligible to enroll 12 weeks following their last vaccination.

Exclusion Criteria

Patients who have had brain metastases unless they meet the criteria outlined in the inclusion criteria section of the protocol.

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.

Patients will not be eligible if there is clinically detectable malignancy deemed likely by the investigator to require intervention during the first 12 weeks 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.

Patients with known or suspected allergies to any component of the vaccine.

Patients receiving the following medications at study entry or within the preceding 4 weeks are excluded:

1. Agents with putative immunomodulating activity (with the exception of non-steroidal anti-inflammatory agents and topical steroids (see section 4.2.5(3)).
2. Allergy desensitization injections.
3. 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®).
4. Any pharmacologic growth factors (e.g. GM-CSF, G-CSF, erythropoietin).
5. Interferon therapy
6. Interleukin-2 or other interleukins.
7. Toll-like receptor agonists, including imiquimod, resiquimod, or polyICLC.

Participants may not have been vaccinated previously with any of the synthetic phosphopeptides included in this protocol.

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. The methods are specified in the consent form and include the following: Norplant, IUD, Dep-Provera, Birth Control Pills, Birth Control Patch, and Sterilization. The following may be used if combined with other birth control methods: Condoms, Jellies or foam, Diaphragm, Rhythm, Withdrawal, Sponge, or Cervical cap.

Women must also not be breast feeding.

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.

Patients classified according to the New York Heart Association classification as having Class III or IV heart disease (Appendix 4).

Patients with a body weight < 110 lbs because of the amount and frequency with which blood will be drawn

Participants must not have known inflammatory conditions of the gastrointestinal tract (oropharynx, esophagus, stomach, small bowel, colon, rectum, or anus) or the respiratory tract (airway and lungs) of autoimmune, infectious, or other cause. Examples may include but are not limited to, gastritis, C. difficile colitis, radiation proctitis, bronchitis. Patients may have had such conditions in the past if they have recovered completely at least 3 months prior, and are not expected to have relapses of the condition.

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 associated symptoms Clinical evidence of vitiligo Other forms of depigmenting illness Mild arthritis requiring NSAID medications or no medical therapy Non small-cell lung cancers expressing EGFR or ALK mutations, or with neuroendocrine features.