|
||||
|
Contact Us About the Immune System Home ICARIS Immune-Inspired Algorithms Jobs and studentships Links to Researchers Modelling the Immune System New to AIS? Publications Teaching Resources |
Basic Immune Inspired AlgorithmsHere we outline a few of the basic immune algorithms. We provide psudocode and an outline description, and where we have it, code. If you want to add to this page, or suggest ammendments, then simply let us know. There are many derivatives of all of these algorithms around, and where possible we provide links to either the authors website or papers. Quick links to: negative selection, clonal selection, immune networks, dendritic cell Negative SelectionThe Biology The process of deleting self-reactive lymphocytes is termed clonal deletion and is carried out via a mechanism called negative selection that operates on lymphocytes during their maturation. For T-cells this mainly occurs in the thymus, which provides an environment rich in antigen presenting cells that present self-antigens. Immature T-cells that strongly bind these self-antigens undergo a controlled death (apoptosis). Thus, the T-cells that survive this process should be unreactive to self-antigens. The property of lymphocytes not to react to the self is called immunological tolerance The Algorithm Negative selection algorithms are inspired by the main mechanism in the thymus that produces a set of mature T-cells capable of binding only non-self antigens. The first negative selection algorithm was proposed by Forrest et al (1994) to detect data manipulation caused by a virus in a computer system. The starting point of this algorithm is to produce a set of self strings, S , that define the normal state of the system. The task then is to generate a set of detectors, D , that only bind/recognise the complement of S . These detectors can then be applied to new data in order to classify them as being self or non-self, thus in the case of the original work by Forrest et al , highlighting the fact that data has been manipulated. The algorithm of Forrest et al produces the set of detectors via the process outlined in below. input : Sseen = set of seen known self elements output : D = set of generated detectors begin repeat Randomly generate potential detectors and place them in a set P Determine the affinity of each member of P with each member of the self set Sseen If at least one element in S recognises a detector in P according to a recognition threshold, then the detector is rejected, otherwise it is added to the set of avaliable detectors D until Stopping criteria has been met end Code Derivatives
Back to top Clonal SelectionThe BiologyAccording to Burnet's 1959 clonal selection theory, the immune system repertoire undergoes a selection mechanism during the lifetime of the individual. The theory states that on binding with a suitable antigen, activation of lymphocytes occurs. Once activated, clones of the lymphocyte are produced expressing identical receptors to the original lymphocyte that encountered the antigen. Thus a clonal expansion of the original lymphocyte occurs. This ensures that only lymphocytes specific to an activating antigen are produced in large numbers. The clonal selection theory also stated that any lymphocyte that have antigen receptors specific to molecules of the organism's own body must be deleted during the development of the lymphocyte. This ensures that only antigen from a pathogen might cause a lymphocyte to clonally expand and thus elicit a destructive adaptive immune response. In this sense, the immune system can be viewed as a classifier of antigens into either self antigen or non-self antigen, with non-self antigen assumed to be from a pathogen and thus needs to be removed from the body. During the clonal expansion of B-cells (but not T-cells), the average antibody affinity increases for the antigen that triggered the clonal expansion. This phenomenon is calledaffinity maturation, and is responsible for the fact that upon a subsequent exposure to the antigen, the immune response is more effective due to the antibodies having a higher affinity for the antigen. Affinity maturation is caused by a somatic hypermutation and selection mechanism that occurs during the clonal expansion of B-cells. Somatic hypermutation alters the specificity of antibodies by introducing random changes to the genes that encode for them. The Algorithm The clonal selection theory has been used as inspiration for the development of AIS that perform computational optimisation and pattern recognition tasks. In particular, inspiration has been taken from the antigen driven affinity maturation process of B-cells, with its associated hypermutation mechanism. These AIS also often utilise the idea of memory cells to retain good solutions to the problem being solved. In de Castro and Timmis' book, they highlight two important features of affinity maturation in B-cells that can be exploited from the computational viewpoint. The first of these is that the proliferation of B-cells is proportional to the affinity of the antigen that binds it, thus the higher the affinity, the more clones are produced. Secondly, the mutations suffered by the antibody of a B-cell are inversely proportional to the affinity of the antigen it binds. Utilising these two features, de Castro and Von Zuben developed one of the most popular and widely used clonal selection inspired AIS called CLONALG, which has been used to performed the tasks of pattern matching and multi-modal function optimisation. When applied to pattern matching, a set of patterns, S , to be matched are considered to be antigens. The task of CLONALG is to then produce a set of memory antibodies, M , that match the members in S . This is achieved via the algorithm outlined below.
input : S = set of patterns to be recognised, n the number of worst elements to select for removal
output : M = set of memory detectors capable of classifying unseen patterns
begin
Create an initial random set of antibodies, A
forall patterns in S do
Determine the affinity with each antibody in A
Generate clones of a subset of the antibodies in A with the highest affinity.
The number of clones for an antibody is proportional to its affinity
Mutate attributes of these clones to the set A , and place a copy of the highest
affinity antibodies in A into the memory set, M
Replace the n lowest affinity antibodies in A with new randomly generated antibodies
end
end
Code
Back to top Immune NetworksThe Biology In 1974, Jerne proposed an immune network theory to help explain some of the observed emergent properties of the immune system, such as learning and memory. The premise of immune network theory is that any lymphocyte receptor within an organism can be recognised by a subset of the total receptor repertoire. The receptors of this recognising set have their own recognising set and so on, thus an immune network of interactions is formed. immune networks are often referred to as idiotypic networks. In the absence of foreign antigen, Jerne concluded that the immune system must display a behaviour or activity resulting from interactions with itself, and from these interactions immunological behaviour such as tolerance and memory emerge.The Algorithm
input : S = set of patterns to be recognised, nt network affinity threshold,
ct clonal pool threshold, h number of highest affinity clones, a number of
new antibodies to introduce
output : N = set of memory detectors capable of classifying unseen patterns
begin
Create an initial random set of network antibodies, N
repeat
forall patterns in S do
Determine the affinity with each antibody in N
Generate clones of a subset of the antibodies in N with the highest affinity. The number of clones for
an antibody is proportional to its affinity
Mutate attributes of these clones to the set A , a and place h number of
the highest affinity clones into a clonal memory set, C
Eliminate all elements of C whose affinity with the antigen is less than a predefined threshold ct
Determine the affinity amongst all the antibodies in C and eliminate those antibodies whose affinity with each
other is less than the threshold ct
Incorporate the remaining clones of C into N
end
Determine the affinity between each pair of antibodies in N and eliminate all antibodies whose affinity
is less than the threshold nt
Introduce a random number of randomly generated antibodies and place into N
end until a stopping criteria has been met
end
Code Java version of opt-aiNet A Java 1.5 version of de Castro's aiNet algorithm for function optimisation is available for download: OptAinet.jar: an executable jar file including source code OptAinet_config.txt: a sample configuration file OptAinet_info.txt: a brief outline of how to run the algorithm opt-aiNET was vontributed by: Paul Andrews, University of York, UK MATLAB version of aiNET Download code by Leandro de Castro Derivatives
Back to top Dendritic CellThe Biology Polly Matzinger explains how the clonal selection theory placed the antigen-specific cells of adaptive immunity (most notably the T helper cell) at the centre of the decision of whether or not to initiate an immune response. This decision was achieved through the deletion of the self-reacting lymphocytes, so that responses will only be initiated against non-self. It was discovered, however, that T helper cells themselves require a co-stimulatory signal from non-antigen-specific APCs in order to initiate an effective adaptive immune response. As a consequence, it could not be assured that immunity only be directed against non-self, as APCs express on their surfaces both self and non-self antigens.Matzinger proposed the danger theory in 1994, which has gained much popularity amongst immunologists in recent years as an explanation for the development of peripheral tolerance (tolerance to agents outside of the host). The danger theory states that APCs are themselves activated via an alarm: danger signals. These activated APCs will then be able to provide the necessary co-stimulatory signal to the T helper cells that subsequently control the adaptive immune response. The danger signals are emitted by ordinary cells of the body that have been injured due to attack by pathogen. For example, the intra-cellular contents released due to uncontrolled (necrotic) cell death could provide such signals. These signals are detected by specialised innate immune cells called dendritic cells that seem to have three modes of operation: immature, semi-mature and mature. In the dendritic cell's immature state it collects antigen along with safe and danger signals from its local environment such as: (PAMPS) and inflammatory cytokines. The dendritic cell is able to integrate these signals to decide whether the environment is safe or dangerous. If safe the dendritic cell becomes semi-mature and upon presenting antigen to T-cells the dendritic cell will cause T-cell tolerance. If dangerous the dendritic cell becomes mature and causes the T-cell to become reactive on antigen-presentation. The Algorithm Danger theory is a relatively new addition to the field of immunology, and thus danger theory inspired algorithms are still in their infancy. Greensmith et al with the dentritic cell algorithm (DCA), which introduced the notion of danger signals, safe signals and pathogen associated molecular patterns signals which all contribute to the context of a data signal at any given time. This context is integrated via a process inspired by the role of dendritic cells (a specialised APC of theinnate immune system). This removes the need to define what self is, but adds the necessity to define the danger, safe and PAMP signals. input : S = set of data items to be labelled safe or dangerous output : D = set of data items labelled safe or dangerous begin Code Derivatives Back to top
|
|||
