Information Technology Reference
In-Depth Information
is defined, which is called a
blunt
double string and is denoted by
<
α
>
. We note
that:
α
rev
α
))
=
α
<
α
>
=
α
)
=
(
¯
rev
(
rev
(
α
c
α
c
and, as a consequence of the equations above we obtain:
¯
<
α
>
=
<
α
>
infact,wehavethat:
α
rev
¯
α
rev
¯
α
rev
α
<
α
>
=
¯
α
)
=
(
α
)
=
α
)
=
))
=
<
α
>.
¯
c
(
¯
(
rev
(
rev
(
α
Γ
∗
/
Γ
∗
are summarized in Table 2.1.
We call
strand
any object
s
on which an operation
type
is defined which assigns
to it a string in
Operations on DNA strings
Γ
∗
/
Γ
∗
. In particular, if
type
(
s
)
is a single string, then we say that
s
is a
single strand
, while if
type
is a double string, then we say that
s
is a
double strand
.
Intuitively, strands are DNA molecules which, as physical objects, are different from
the base sequence they realize. Therefore, in our terminology, strands having the
same base sequence are strands with the same type. We restrict ourselves to consider
only single or double strands. In fact, for the needs of the following discussion, we
may avoid considering more complex forms of DNA molecules that combine more
than two DNA strands.
We consider a DNA pool
P
as a set of strands, or equivalently, as a
multiset
of
single or double strings of
(
s
)
Γ
∗
/
Γ
∗
, which is specified by a
multiplicity
function
mult
P
Γ
∗
/
Γ
∗
to natural numbers. In fact,
mult
P
(
η
)=
from
n
means that the pool
P
contains
n
(indiscernible) strands of type
η
. We write
P
=
{
n
1
:
η
1
,
n
2
:
η
2
, ...,
n
k
:
η
k
}
when
mult
P
(
η
1
)=
n
1
,
mult
P
(
η
2
)=
n
2
,...,
mult
P
(
η
k
)=
n
k
and
mult
P
(
η
)=
0for
η
∈{
η
,
η
,...,
η
k
}
. Mixing and splitting DNA pools correspond to the standard
multiset operations of sum and difference, denoted by
1
2
+
,−
( sum and difference of
their multiplicity functions).
In virtue of these two ways of considering a pool, we can use (ambiguously) both
notations:
η
∈
Γ
∗
/
Γ
∗
, meaning
mult
P
η
∈
P
, for a string
(
η
)
=
0, and
s
∈
P
,when
s
is a strand of
P
. The type of pool
P
is the set of strings (a language):
)=
{
η
∈
Γ
∗
/
Γ
∗
|
η
∈
)
∈
Γ
∗
/
Γ
∗
|
Type
(
P
P
}
=
{
type
(
s
s
∈
P
}.
We remark the difference between
type
, which assigns a string to a strand, and
Type
(with capital
T
) which assigns, to a pool of DNA strands, the set of types of its
strands. Although strings and strands are different things, very often the two terms
are used almost synonymously. In fact, any string is physically implemented by
strands having its type, and conversely, the expression “a string”, in a given context,
could refer to a physical occurrence of a string, which is just a strand.
