THE TRAVELING SALESMAN PROBLEM - A NEW APPROACH FOR IDENTIFICATION OFDIFFERENCES AMONG POLLEN ALLERGENS

Background: It is not easy to identify the specific plant species that causes an allergic response in a certain patient at a certain time. T his is further complicated by the fact that closely related plant spec ies cause similar allergic responses. A novel mathematical technique i s used for analysis of skin responses of a large number of patients to several groups of allergens for improvement of the understanding of t heir similarity or dissimilarity and their status regarding cross-reac tivity. Methods: The responses of 153 atopic patients to 42 different pollen extracts were tested by skin prick tests. Among the responses o f patients to various extracts, a measure of dissimilarity was introdu ced and calculated for all pairs of allergens. A matrix-structuring te chnique, based on a solution of the 'Travelling Salesman Problem', was used for clustering of the investigated allergens into groups accordi ng to patients' responses. The discrimination among clusters was confi rmed by statistical analysis. Results: Sub groups can be discerned eve n among allergens of closely related plants, i.e. allergens that are u sually regarded as fully cross-reactive. A few such cases are demonstr ated for various cultivars of olives and pecans and for various source s of date palms, turf grasses, three wild chenopods and an amaranth. C onclusion: The usefulness of the proposed approach for the understandi ng of similarity and dissimilarity among various pollen allergens is d emonstrated.