Information Technology Reference
In-Depth Information
(1
≤
i
≤
j
≤|
α
|
) is denoted by
α
[
i
,
j
]
and is called a
substring
of
α
. In particular, it
is called a
prefix
if
i
=
1, and a
suffix
if
j
=
|
α
|
. A string with prefix
α
and suffix
β
is
also denoted by
α
...
β
.The
complementation
function, denoted by the superscript
by
A
c
T
c
C
c
G
c
Γ
∗
by
=
,
=
,
=
,
=
c
,isdefinedon
Γ
T
A
G
C
. It extends naturally to
c
c
c
c
. Another operation on
Γ
∗
is the
reverse
=
λ
(
αβ
)
=
α
the conditions
λ
and
β
operation
rev
such that, for every
X
∈
Γ
,
rev
(
X
)=
X
,
rev
(
α
X
)=
Xrev
(
α
)
,and
rev
.
Reversing and complementation operations are
involutive
and
commute
,thatis:
(
λ
)=
λ
rev
(
rev
(
α
)) =
α
c
c
(
α
)
=
α
and
c
c
rev
(
α
)=(
rev
(
α
))
.
The
mirroring
of
α
is defined by:
c
mir
(
α
)=
rev
(
α
)
as
¯
and is an involutive operation. We abbreviate
mir
.
In DNA molecules, an intrinsic concatenation verse is given which goes from the
Phosphate to the Oxydryl (that respectively correspond to Carbon 5
and 3
positions
in the sugar DNA backbone). This verse is symbolically denoted by an arrow at one
side of non-null strings
(
α
)
α
α
,asin:
α
→
that can be seen as an indication of the extremity where the Oxydryl terminal is
located (while Phosphate is at the other extremity). However, when we omit the
arrow, the usual reading from left to right is assumed, which corresponds to the
5
−
3
verse.
An
exact pairing
(symmetric) relation
Γ
∗
such that:
||
is defined over
α
||
β
if
β
=
mir
(
α
)
.
respectively. Let
h
hybr
be a non-null length that we call
hybridization threshold
(it represents a bi-
ological parameter we leave unspecified). If
Let
γ
be the longest string such that
α
and
β
include
γ
and ¯
γ
|
γ
| >
h
hybr
, then we say that
α
and
β
pair by hybridizing
on
γ
(or shortly, that they
hybridize
) and write:
α
]
γ
[
β
.
In this case a double DNA string composed of
α
and
β
is defined, that will be
denoted by:
α
rev
(
β
)
.