Immunic.dvi

Classifying the unknown: The T-cell Recruitment Mechanism of the Immune System as a Paradigm for Pattern Recognition M. Koppen, M. Stellmacher, L. Lohmann and B. Nickolay Email: mario.koeppen stellmacher lohmann nickolay @ipk.fhg.de task of this system is to distinguish microorganisms into two classes: self and non-self.
The immune system of animals is considered an Due to several reasons, the immune system has adaptive system, capable of solving a classi cation found particular interest in medical research in the task: to distinguish microorganisms, which take part last decade. The rapid spread of the Acquired im- in the body metabolism, into self and non-self ones.
munode ciency syndrome (AIDS), the progress in Recent research results of immunobiologists, esp.
organic transplantation techniques and the increas- the discovery of the Major histocompatibility com- ing amount of allergical symptoms among the popu- plex (MHC), are discussed from an information the- lation of industrial countries are problems related oretic point of view. One of the most interesting to the understanding of the immune system. A aspects is the training of a two-class problem by the lot of fundamental research results have sharpened only provision of examples of one class. By adopting the picture of the processes involved in the immune the basic processes, which maintain the organisation system's actions and reactions, and most of them of the immune system, new algorithm esp. for pat- tern recognition can be designed. As an example, The most intriguing point is that the immune sys- a framework is proposed for character separation of tem is a learning system, capable of adaptation on melted char images, what is an important problem varying environmental conditions. But, in contrast to the higher nervous system, it is not capable of cog- Keywords: Immune Algorithms, T cell Recruit- nition. Its only task is to eliminate foreign microor- ment, T Cell Recognition, Optical Character Recog- ganisms, which entered the body and may threat the As for neural networks in the 60s, the immune sys- tem was studied as a model for adaptive procedures since the beginning of the 90s. Three purposes of The study of natural systems, which maintain the ability to classify, has been mostly occupied by the gain a better understanding of the immune sys- study of the nervous system of higher animals, es- pecially the human brain. However, there are other classi cation systems in nature, as well. As an exam- ple, the carnivorous plant Dionaea muscipula (venus apply the paradigms of the immune system in y trap) has to distinguish, whether an crawling in- sect has triggered its three capillary hairs or a drop of rain. The system here is quite simple: when two The rst item is quite important for medical re- hairs are triggered simultaneously or the same hair search. By using the information theoretic descrip- is triggered twice within a short time intervall, the tion of processes, which are involved in the im- venus y trap will close its leave. A more compli- munoresponse, the justi cation of the relative im- cated example is the immune system of animals (not portance of all processes can be obtained. Espe- only higher ones). The fundamental classi cation cially genetic algorithms have been considered a valuable model for the important processes FJSP93] presence of toxics or viruses would cause a danger for the living system, adaption has to be performed The second item follows the line of the devel- by the presence of self representing examples alone.
opment of soft computing algorithms in general: as evolutionary computation was derived from the study of the natural evolution, and neural networks from the nervous system, algorithms can be derived from the study of the immune system processes as well. So far, the most inspiring sources have been the T-cell recruitment mechanism BV91] and the cooperative behaviour of antibodies SKS99]. These studies and their relation to the theoretical under- standing of soft computing algorithms (as e.g. the schema theorem for genetic algorithms) will give a contribution for a better understanding of the im- The third item mentioned above was considered recently. So, in SHF97] and FHS97], there the au- thors start to consider the immune system a model for the design of a computer security system. By monitoring processes, a system becomes able to de- Figure 1: A virally infected cell is recognized by a T tect computer viruses. This fundamental idea opens a gate for a completely new research direction in sys- tem design. The results could be applied to other A similar problem can be stated for pattern recog- complex security systems (as in biometrics or digital nition: how is it possible to learn to distinguish ob- jects of class from objects of class with just a Up to now, the study of algorithms and systems stock of examples for class ? How is it possible to inspired by the immune system network are just at learn to classify or to become prepared for classifying the beginning of the development of a prospective fruitful new research direction. Further results in The problem, formulated this way, is mathemati- the medical research will enhance that development.
cally ill-posed. There is always a chance for decep- From the pattern recognition point of view, the tion, as stated by the fundamental \No Free Lunch" immune system is able to distinguish two classes theorem WM95] and the \Ugly Duckling" theorem of microorganisms: self and non-self ones. The de- Wat85]. Also, the immune system fails in some tection of foreign microorganisms is of vital impor- cases, as can be quickly exempli ed by the rapid tance. Since a living system is an open system ac- spread of viral diseases or allergies as immunic reac- cording to its metabolism, there is a continuous ex- tions on harmless substances (which can be consid- change of substances with its environment. Among ered pathogenic self-immune responses).
the substances entering the living system, there may However, non-optimalityof a system does not pre- be threatening ones like toxic substances or viruses.
vent the system to be able to cover a reasonable set The immune system acts on di erent levels to pre- of threatening situations, and this is, what the im- vent from such situations. On its top, there are the mune system actually does. It is related to the opti- skin and several mucous membranes, doing a very mal employment of a priori knowledge without any rough prevention. Other basic mechanisms are blood AI concepts, since there is no \intelligence" in the clotting, attack of foreign bacterias by B lympho- cytes and, what is in the scope of this paper, the In this paper, a framework is presented, which T cell reception of virally infected cells (see g. 1).
takes the so-called immune recruitment mechanism Nearly each of those subsystems performs its clas- BV91] as a paradigm for the classi cation of pat- si cation task in its own manner. Especially the terns. The purpose of the framework, which is exem- lymphocytic systems are adaptive systems, with the pli ed for the case of optical character recognition, ability to become trained. The problem of the under- is to solve the task of distinguishing known charac- lying information processing is: the immune system ter images from character-like patterns, as ligatures has to be trained on a two-class problem, without (i.e. meltings of two or more character images into any examples for one of the two classes! Since the one image). By a one-to-one correspondance of the framework with the processes that establish the T cell recruitment, an immune inspired procedure is given. This procedure is important for the under- standing of biological T cell recruitment as well.
The T cell recruitment has been considered in BV91], too. However, there are two important is- sues considered di erent in the following discussion.
The rst issue is the di erence of the goal of the framework, which was presented in BV91] and the one, which is proposed here. While in BV91] the task of T cell recruitment was formulated as the pro- vision of a su cient amount of di erent T cells for keeping up the lymphocytic system in an active level, the task here is considered as the provision of enough variablity among the T cell to become prepared for the recognition of possible antigens, which enter the living system. However, for both frameworks, the thymic selection procedure is considered as the ba- The second issue is related to the progress in medi- cal knowledge. In 1991, the MHC-antigen complexes and the dual selection processes in the thymus were not known. However, for a proper understanding of the T cell response this should be considered es- sential. The framework, which is presented here, Figure 2: Basic triggering of T cell reception by acknowledges these new research results.
Section 2 will recall the T cell recruitment and T cell response system from an information theoretic point of view. Since a complete description of the the cytoplasma of a cell are presented on the surface whole system would go far beyond the scope of this of cells by means of the major histocompatibility paper, the focus is done on the points, which are complex (MHC) molecules (there are MHC I and essential for the framework description. A lack in MHC II molecules, but the di erence is not consid- medical correctness might be the inescapable conse- ered here). For doing so, the antigen is broken up quence of that shortening. Among many, consider into antigenpeptids, i.e. shorter peptide fragments.
Dav97] a comprehensive textbook on animal im- Each MHC, located within the endoplasmotic retic- ulum, is roughly able to recognize a group of such Then, section 3 will describe the proposed frame- antigenpeptids. Roughly here means that a MHC in- work and study an example of its application to char- cludes a molecular pocket for embedding one peptid acter recognition. Section 4 will conclude this paper When a MHC carries an antigenpeptid, it moves to the outer surface of the cell. By doing so for sev- 2 The T cell recruitment and eral MHC-antigenpeptid complexes, a cell presents something like a \table of contents" of its internal T cells, which are passing by a cell, can try to dock T cells are vitally responsible for the detection of on the MHC complexes on the surface of the cell.
virally infected cells. Essentially, three components This will happen, when several conditions are ful- take part in the T cell response (see g. 2).
lled (see g. 3). The most signi cant one is the t- Antigens are substances, which are processed by tening of the molecular pocket of the and chain, the T cell reception system. There are antigens caus- a unique structural property of each T cell, with the ing immune response (immunogens), antigens caus- antigen presented by a MHC. Also, the T cell must ing no response (since not strongly related to threat- be able to dock on the MHC by means of the so- ening situations) and the so-called selfantigens, i.e.
called co-receptors DC8 (for MHC I molecules) or harmless substances of the body itself. Antigens in DC4 (for MHC II molecules). There are some other costimulatory signals necessary in order to put a T phocytic system, are able to pass the thymus and cell into action, which will not be considered here.
There are two selections going on in the thymus, The positive selection will only keep lymphocytes, which are able to dock on a body MHC by its co- stimulatory receptors (CD4 or CD8). So, this will select only those T cells, which are able to under- stand the \language" spoken by the cells to present Then, a negative selection takes place, which elim- inates all T cells, which are docking on the complex of a MHC and a selfantigen. This prevents the im- Only T cells passing both selections are able to take part in the immune response system. But it has to be mentioned that the lymphocytes, which leave the thymus, has still to become activated later on. This is due to the later presentation of self- antigens, which are not available within the thymus.
Also, some undisclosured process of T cell elimina- This is the manner, by which a living system solves the problem to classify the unknown. It uses the advantage of a common language of normal behav- Figure 3: Docking of a T cell to a MHC molecule ing cells and viruses as well (the processing of pep- by matching of antigenpeptid and co-stimulatory re- tid chains) it maintains a set of schemes (by about a dozen di erent MHC molecules) of this language and it generates a vast amount of di erent \language After successfull docking on a cell, a class switch speaking" T cells, each of which is quite sensitive to occurrs and the T cell is proliferated and initiates a exactly one antigenpeptid, which is not found within complex chain of reactions, which nally lead to the One important point is that the MHC molecules are speci c for each living being, but sensitive for a group of antigenpeptids, while the T cells are sen- sitive for only one antigenpeptid. Hence, the body must provide a large number of di erent T cells in order to be receptive for a large number of possible In the following, a framework is presented, which is The design of a T cell is the most interesting point.
based on the same paradigms as the T cell recruit- The genetic coding of T cell generation is di erent from the general protein production system of the DNA, since it includes ambiguity in the chromosome transcription process. The protein sequences of the and chain are generated in a more random fash- In character recognition applications a correct and ion by mixing of several chromosome parts. Hence, robust character separation process is very impor- the diversity of T cells is genetically coded.
tant. Most of the Optical Character Recognition T cells are generated in the marrow mark and then (OCR) procedures are only able to recognize well- transferred to the thymus (as so-called thymocytes), separated character images. Two or more fused where they will stay for a while. The task of the characters (e.g. as a result of noise on the carrier thymus can be compared to the recruitment of sol- medium) can not be classi ed as a proper element of diers for a war. Only T cells (i.e. thymocytes), which one character class. Especially in the outdoor area, prove to be able to perform a useful task in the lym- relevant characters are fused together quite often.
This problems are usually treated by measuring a small number of character stroke pixels or by distur- bance of the character objects. For instance, rusty screws between the characters fuse numbers and let- In approaches to the OCR-processing of recogni- tion systems, separation tasks are running in par- allel. Actually, dissectional, recognition based, hy- brid and holistic methods are used CL96] SP96] PSH 93]. Very important for the success of the sep- aration task is to decide correctly whether the char- acters are properly separated or not. Together with the development of a robust licence plate recogni- tion system, a merge decider network was proposed This neural network structure is able to decide between individual and fused characters in the in- elimination of the bestmatching templates put image. The disadvantage of the merge decider method is the requirement of a representative train- ing set of individual and fused characters (ligatures).
The proposed immune based framework is expected to simplifythis approach. Following the traces of the T cell recruitment mechanism, only representative training images of single character images should be Character and character-like images (antigens) The schema of the immune based framework is given in gure 4. Recruitment and reaction stage are sep- The mask character images combine coarse charac- ter features with re ned character features. A cross mask was used in the proposed framework.
The purpose of the recruitment stage is the selection of the randomly initialized templates. This means that the recruitment of the correct templates takes place in order to discriminate coarse versions of the The reaction stage includes a classi cation process correct individual characters. In its biological mean- of individual or merged character images. In the bi- ing the lymphozytes, which are able to respond to ological sense this is the detection of immunogens.
self MHCs, are selected from thymozytes. In agree- Based on positive and negative selection, the gener- ment with the immune system recruitment processes ated templates detect ligatures and other character- the recruitment stage is separated in the positive and The positive selection task detects the templates (thymozytes) which positively react on \coarse" fea- tures of the correct individual character images. The used matching procedure is based on binary Ham- The presented framework is di erent from other ming distance method. As inputs, sample images of character separation approaches in the sense that it learns to react on patterns which are di erent from The result of the negative selection task are the the patterns from which it was trained. The recently templates (lymphozytes), which are able to detect presented merge decider network is trained from a ligatures (body outside cells). In the matching pro- set of single character images for one class, and with cess, the best matching templates are eliminated.
a set of merged character images for the second class.
The problem is the large variability of merged char- acter images, which are necessary for training the network. The immune based approach will help to reduce the number of necessary examples and gen- HFP95] Ron R. Hightower, Stephanie Forrest, erate the templates, which can be either used for template matching, or for initialising the merge de- An important issue is the relation of the proposed framework to an evolutionary approach. The proce- dure could simply be made re-entrant, hence chang- Francisco, CA, 1995. Morgen Kaufmann.
ing to a population based approach. However, from rst experiments there seems to be no need for this Loh99] Lutz Lohmann. Bildanalysesystem zur procedure, especially for the chosen application ex- Fahrzeugen. PhD thesis, TU Berlin, 1999.
Another issue is related to the high number of tem- plates, which are needed in the online phase of the PSH 93] B. Plessis, A. Sicsu, L. Heutte, E. Menu, framework. A large number of di erent T cells, each of which being sensitive to a di erent virus, has to be handled by the animal immune system as well.
Of course, this is strongly related to the dynamics, the triggering and the spatio-temporal organization of the distribution of the T cells within the body.
The proposed framework has to be extended in or- der to provide T cells where and whenever they are SHF97] Anil Somayaji, Steven Hofmeyr, and BV91] Hugues Bersini and Francisco J. Varela.
SKS99] Toshiyuki Shimooka, Yasufumi Kikuchi, editors, Proc. of the Fourth Int. Conf. on feature extraction of patterns. In Proc.
CL96] G.R. Casey and E. Lecolinet. A survey of H. Shi and T. Pavlidis. A system for text Dav97] Huw Davies. Introductory Immunobiol- Philadelphia, PA, pages 415{427, 1996.
Wat85] Satosi Watanabe. Pattern Recognition: FHS97] Stephanie Forrest, Steven A. Hofmeyr, WM95] David H. Wolpert and William G.
FJSP93] Stephanie Forrest, Brenda Javornik, Robert E. Smith, and Alan S. Perelson.
010, Santa Fe Institute, 6. Februar 1995.
tern recognition in the immune system.

Source: http://science.mkoeppen.com/science/uploads/Publications/nc00.pdf