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

h is dynamic programming approach (D'haeseleer et al., 1996) runs in linear time
with the size of self. To present the algorithm, some notation should be introduced
fi rst: let s denote a binary string and ˆ the string s stripped of its leftmost bit, s

⋅

b ,

∊

where b {0,1} denotes s appended with b .

Also, “a template” of order r is a size l string consisting of l

−

r blank symbols
and r fully specifi ed contiguous bits. t i ,s denotes a template in which the r specifi ed
bits start at position i and are given by the r -bit substring of s . A right (left) comple-
tion of a template t is a template with all the blanks to the right (left) replaced by
bits. h erefore, ( a , b ] denotes the integer interval ( a

+

1) … b .

4.3.2.1 Phase I: Solving the Counting Recurrence

Let C i [ s ] be the number of right completions of t i , s unmatched by any string in S , for
1

≤ ≤ − +

1). h e templates in the array C i [ s ] will enumerate all the possible
ways two strings can match each other over rcb . C i [ s ] can be computed recursively,
the number of unmatched right completions at i can be computed based on the
number of right completions at i

i ( l r

+

1 as follows: if t i,s is directly matched in S ,
C i [ s ] is 0, otherwise, the completions of t i,s consist of those with a 0 bit following
the r bits of s , and those with a 1 bit instead. h ese are exactly the number of right
completions for ˆ

⋅ ⋅

0 and ˆ 1, respectively.

0 , is matched in

otherwise

t S

is ,

=

cs []

i

⋅ ⋅

cs [ 0 ] cs [ 1 ],

i + 1 i + 1

Also, C l − r + 1 [ s ] will be 0, if the template t l - r + 1 ,s is matched in S , and 1 otherwise

0
1

,
,

t

, is matched in
otherwise

S

lr s 1

c [] s

lr 1

To illustrate the preceding recurrence equations, an example is presented in the
following text (taken from D'haeseleer, 1996).
Let l

= =

3. Let s 1 = 11010 0 a nd s 2 =

100101 are strings in S . Consider
the patterns 110***, *101**, **010*, and ***100. h ese patterns are matched by s 1 .
h us, C 1 [110]

6 and r

= = = =

0. Now consider the pattern
**110*. h is template is matched by neither s 1 nor s 2 . However, the pattern **110*
does not have any unmatched right completions C 3 [110]

C 2 [101] C 3 [010] C 4 [10 0]

= + =

0.
h e right completions of **110* are **1100 and **1101, which are matched by s 1
and s 2 , respectively.

C 4 [10 0] C 4 [101]