Corner Image AISWeb
The Online Home of Artificial Immune Systems

Home
(Last Modified: 21st October 2013)

Basic Immune Inspired Algorithms


Here 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 Selection



The 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

  • Dipankar Dasupta has develped many deriviates of Negative Selection and his AIS website should be checked for those related publications.
  • Thomas Stibor has also worked a great deal on negative selection, and the more theoretical side.

Back to top


Clonal Selection

The Biology
According 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 

There are many different clonal selection algorithms around, a good paper to read to help you decide which one to use is :
V. Cutello, G. Narzisi, G. Nicosia, M. Pavone, " Clonal Selection Algorithms: A Comparative Case Study using Effective Mutation Potentials, optIA versus CLONALG, 4th Int. Conference on Artificial Immune Systems, ICARIS 2005, August 14-17, 2005, Banff, Canada. Springer, LNCS 3627:13-28, 2005.
Code

  • Leandro de Castro provides MATLAB code of CLONALG
  • WEKA version by Jason Brownlee. This implements the following algorithms:
    • Artificial Immune Recognition System (AIRS).
    • Clonal Selection Algorithm (CLONALG)
    • Immunos-81
  • Optimization Algorithm Toolkit supplied by Jason Brownlee. This is an open source Java project with the following Clonal Selection Algorithms implemented:

    • Adaptive Clonal Selection (ACS)
    • Optimization Immune Algorithm (opt-IMMALG)
    • Optimized Artificial Immune Network (opt-aiNET)
    • Optimization Immune Algorithm (opt-IA) (Papers on this can be found here)
    • Clonal Selection Algorithm (CLONALG, CLONALG1, CLONALG2)
    • B-Cell Algorithm (BCA)
    • Cloning, Information Gain, Aging (CLIGA)
    • Immunological Algorithm (IA)

* AIRS: An immune-inspired supervised learning system by Andrew Watkins (papers from Andrews website), C++ code is available, and a WEKA version of the code is available
* opt-IA : A clonal selection optimisation algorithm by Giuseppe Nicosia (all available from Giuseppe's website)
* Immune-PAES from the paper A Multi-Objective Evolutionary Approach to the Protein Structure Prediction Problem. Journal of the Royal Society Interface, Royal Society Publications London, 3(6):139-151, 2006.
* B-cell algorithm (BCA) zip file of C++ code : A clonal selection optimisation algorithm by Johnny Kelsey.
* Paper explaining the algorithm GECCO 2003. LNCS 2723.
* Paper showing proof of convergence of the BCA by Clark et al . LNCS 3627, pp. 318-330. 2005


Back to top


Immune Networks

The 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 Cell

The 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 
Create an initial population of dendritic cells (DCs), D Create a set to contain migrated DCs, M forall data items in S do Create a set of DCs randomly selected from D , P forall DCs in P do Add data item to DCs collected list Update danger, PAMP and safe signal concentrations Update concentrations of output cytokines Migrate the DC from D to M and create a new DC in D if concentration of co-stimulatory molecules is above a threshold end end forall DCs in M do Set DC to be semi-mature if output concentration of semi-mature cytokines is greater than mature cytokines, otherwise set as mature end forall data items in S do Calculate number of times data item is presented by a mature DC and a semi-mature DC Label data item a safe if presented by more than semi-mature DCs than mature DC's, otherwise label as dangerous Add data item to labelled set M end end


Code

Derivatives


Back to top

Divider Bar Go to page top