The 'traveling salesman problem': a new approach for identification of differences among pollen allergens

It is not easy to identify the specific plant species that causes an allergic response in a certain patient at a certain time. This is further complicated by the fact that closely related plant species cause similar allergic responses. A novel mathematical technique is used for analysis of skin responses of a large number of patients to several groups of allergens for improvement of the understanding of their similarity or dissimilarity and their status regarding cross-reactivity.

The responses of 153 atopic patients to 42 different pollen extracts were tested by skin prick tests. Among the responses of patients to various extracts, a measure of dissimilarity was introduced and calculated for all pairs of allergens. A matrix-structuring technique, based on a solution of the 'Travelling Salesman Problem', was used for clustering of the investigated allergens into groups according to patients' responses. The discrimination among clusters was confirmed by statistical analysis.

Sub groups can be discerned even among allergens of closely related plants, i.e. allergens that are usually regarded as fully cross-reactive. A few such cases are demonstrated for various cultivars of olives and pecans and for various sources of date palms, turf grasses, three wild chenopods and an amaranth.

The usefulness of the proposed approach for the understanding of similarity and dissimilarity among various pollen allergens is demonstrated.