T Cell–Inspired Algorithms - Immunological Computation: Theory and Applications - page 69

It is important to note that this a lgorithm requires storing an array C that represents
all the possible ways two strings can match over rcb . h ereby, the algorithm runs in
linear time in the sizes of the self-set and a detector set for specifi c values of param-
eters l and r . However, this algorithm requires exponential time and space in r , the
matching threshold. Clearly, this is a problem while dealing with long strings, and
thereby, higher values of the threshold value r .

4.3.3

A Greedy Algorithm for Detector Generation

A greedy method for generating negative detectors was suggested by D'haeseleer
et al. (1996), which can provide a better detector coverage of the complement
space with varying degrees of computational complexities. h is algorithm tries to
locate detectors (instead of selecting them at random as in the second phase of
the previous approach) as far apart as possible to avoid possible overlapping. At
each step, the algorithm picks a detector that matches as many unmatched nonself
strings as possible.
h e same array structure is used as in the previous algorithm, but to construct the
array C in phase I, the strings are examined from right to left, that is, from C l − r + 1 [] to
C 1 []. A second array C

′

is then constructed by scanning the strings from left to right,
and computing the subsequent levels using a similar recurrence relation for C . Let
D i [ s ]

i [ s ] be the number of unmatched fully specifi ed bits corresponding
to “template” t i,s , where C

= ×

C i [ s ] C

I is the number of nonmatching left completions.
If a specifi c template has a zero entry in D , then all strings containing that tem-
plate will match some string in S . Also, for all the templates with nonzero entries in D ,
the corresponding strings do not match with any string in S .

NS Algorithm 3: A greedy approach

Phase I: Generate valid detector templates

In this stage, two arrays, denoted as D S and D R , are created. Array D S
is used to keep track of the templates that the algorithm picks from
during the detector construction process. h e detectors with nonzero
entries in D S will be called “valid detector templates.”

Phase II: Generate strings unmatched by S

D R indicates, for each template, the number of yet unmatched strings
by previously generated detectors. To generate a new detector, those
templates matching the most unmatched nonself strings are selected.
h e array D R is updated each time a new detector is generated by
keeping C R and C

R (instead of D R ) and updating them incrementally.