Information Technology Reference
In-Depth Information
The Hamming shape-space
U
l
is built from all elements of length
l
over a
finite alphabet
Σ
.
Example 1.
Σ
=
{
0
,
1
}
Σ
=
{
A, C, G, T
}
000
...
000
000
...
001
..........
..........
111
...
111
AAA . . . AAA
AAA . . . AAC
............
............
TTT ...TTT
l
l
In example 1 two Hamming shape-spaces for different alphabets and alphabet
sizes are presented. On the left, a Hamming shape-space defined over the binary
alphabet of length
l
is shown. On the right, a Hamming shape-space defined over
the DNA bases alphabet (Adenine, Cytosine, Guanine, Thymine) is presented.
2.2
R-Contiguous and R-Chunk Matching
A formal description of antigen-antibody interactions not only requires a repre-
sentation (encoding), but also appropriate anity functions. Percus et. al [12]
proposed the
r-contiguous
matching rule for abstracting the anity of an anti-
body needed to recognize an antigen.
U
l
with d
=
d
1
d
2
...d
l
,matchwithr-contiguous rule, if a position p exists where
e
i
=
d
i
for i
=
p,...,p
+
r
U
l
Definition 1.
An element e
∈
with e
=
e
1
e
2
...e
l
and detector d
∈
−
1
, p
≤
l
−
r
+1
.
Informally, two elements, with the
same length
, match if at least
r
contiguous
characters are identical.
An additional rule, which subsumes
1
the
r
-contiguous rule, is the
r
-chunk
matching rule [13].
U
l
Definition 2.
An element e
∈
with e
=
e
1
e
2
...e
l
and detector
D
r
with d
=(
p
d
r
+1
match with r-chunk
rule,ifapositionp exists where e
i
=
d
i
for i
=
p,...,p
+
r
∈
N
×
|
d
1
d
2
...d
r
), for r
≤
l, p
≤
l
−
−
1
.
Informally, element
e
and detector
d
match if a position
p
exists, where all
characters of
e
and
d
are identical over a sequence of length
r
.
We use the term
subsume
as any
r
-contiguous detector can be represented as a
set of
r
-chunk detectors. This implicates that any set of elements from
U
l
that
can be recognized with a set of
r
-contiguous detectors can also be recognized
with some set of
r
-chunk detectors. The converse statement is surprisingly
not
true, i.e. there exists a set of elements from
U
l
that can be recognized with a set
1
Include within a larger entity.
