Shen S., Tuszynski J.A. Theory and Mathematical Methods for Bioformatics
Подождите немного. Документ загружается.
88 3 Modulus Structure Theory
1. Let Δ
1
and Δ
2
be the expanded part of sequence C related to sequences
A and B, respectively. Then, c
N
c
−Δ
1
= A, c
N
c
−Δ
2
= B. Following from
the basic assumption on shifting mutations, we have that Δ
1
is disjoint
from Δ
2
, i.e., Δ
1
∩ Δ
2
= ∅.
2. Let Δ
0
= {N
c
−Δ
1
}∩{N
c
− Δ
2
} = N
c
−Δ
1
− Δ
2
,thenΔ
0
and Δ
1
,Δ
2
are disjoint and Δ
0
∪ Δ
1
∪ Δ
2
= N
c
. We can then obtain the following
expressions:
c
Δ
0
,c
Δ
1
= A,
c
Δ
0
,c
Δ
2
= B. (3.48)
We call (Δ
0
,Δ
1
,Δ
2
) the decomposition of the shifting mutation procedure
A → C → B,inwhich,Δ
0
is the nonshifting mutation region, Δ
1
is the
inserting region and Δ
2
is the deleting region.
3. Regions Δ
0
,Δ
1
and Δ
2
can be decomposed into small intervals as follows:
Δ
τ
= {δ
τ,k
,k=1, 2, ··· ,k
τ
},τ=0, 1, 2 . (3.49)
They are disjoint from each other. If we arrange these small intervals
according to their lengths, we then have
Δ
= {δ
0
,δ
1
,δ
2
, ··· ,δ
k
a
} , (3.50)
where k
a
= k
0
+ k
1
+ k
2
. Since the nonshifting mutation and shifting
mutation occur in the small intervals Δ given in (3.49), it follows that
Δ
0
=(δ
1
,δ
3
, ··· ,δ
2k
0
−3
,δ
2k
0
−1
) ,
Δ
1
∪ Δ
2
=(δ
0
,δ
2
, ··· ,δ
2k
0
−2
,δ
2k
0
) .
(3.51)
So, k
a
=2k
0
, and δ
0
and δ
k
a
may be empty sets. Similarly, we call (3.50)
and (3.51) the decomposition of the shifting mutations, so the sequence C
given in (3.47) satisfies c
N
c
−Δ
1
= A, c
N
c
−Δ
2
= B.
Modulus Structure of Shifting Mutation
If sequence B is mutated from A through shifting mutations, then we may
express (3.47) using a shifting mutation T , and denote this by A
T
−→ B,with
the associated mutation mode denoted as follows:
T = {(i
k
,
k
),k=1, 2, ··· ,k
a
},
k
=0,
T
=(γ
1
,γ
2
, ··· ,γ
n
a
) ,γ
i
∈ Z ,
(3.52)
where Z = {··· , −2, −1, 0, 1, 2, ···} is the set of all integers. More details
about (3.52) follow:
1. The k
a
in T is the total number of shifting mutations in sequence A.The
notation (i
k
,
k
) represents the position and length of the kth shifting
mutation, where i
k
is the position of shifting mutation, and
k
includes
the information of both the type and length of the kth shifting mutation.
Typically, it is a type-III mutation if
k
> 0, and a type-IV mutation if
k
< 0. |
k
| is the length of the inserted or deleted segment.
3.3 Analysis of Modulus Structures from Sequence Mutations 89
2. Similarly, γ
i
in T
includes information about the length and type of the
shifting mutation at position i. Typically, there is no shifting mutation
after a
i
if γ
i
= 0. There is a type-III mutation occurring after a
i
if γ
i
> 0,
i.e., a fragment with γ
i
length is inserted after a
i
if γ
i
< 0. There is a type-
IV mutation occurring after a
i
, i.e., a vector with |γ
i
| length is deleted
after a
i
.
3. Let I
T
= {i
k
, k =1, 2, ··· ,k
a
} denote the set of all the positions of the
shifting mutations. We arrange them according to their values in increas-
ing order as follows:
i
0
=0≤ i
1
<i
2
< ···<i
k
a
≤ i
k
a
+1
= n
a
. (3.53)
Since the regions of type-III mutation and type-IV mutation may not
overlap, we assume that
i
k
+ |
k
| <i
k+1
,i=1, 2, ··· ,k
a
. (3.54)
4. Similarly, for the two mutation modes T,T
given in (3.54), one determines
the other. The corresponding expression is found as follows: If T is given,
then
γ
i
=
i
k
, if i = i
k
∈ I
T
,
0 , otherwise .
(3.55)
On the other hand, if T
is given, the variables in T are rewritten as
follows:
I
T
= {i ∈ N
a
: |γ
i
| > 0} ,
k
= γ
i
k
, if i = i
k
∈ I
T
,
(3.56)
where set I
T
arranged in the order of increasing values. The expression
showing how T and T
determine each other is given in (3.55) and in
(3.56), with T and T
as the two equivalent mutation modes, with both
mutation modes relying on A.
Definition 18. With T and T
defined as in (3.52) and the mutations deter-
mined by the values of γ
i
,i
k
,
k
, we have T and T
as two equivalent modes of
shifting mutation. Because T and T
determine each other, we will use T and
T
interchangeably in the future. In addition, the final result B is not unique
if the mutation mode (A, T ) is given. This is because there is no restriction
on the insertion of nucleotides following from (A, T ), so we must add rules to
restrict the insertion data.
Definition 19. 1. Let T and T
be two shifting mutation modes of a sequence
based on A;sequenceA is then called the initial data (or initial template)
of the corresponding type-III mutation.
2. For a type-III mutation with initial template A, if the inserted data is
selected from a fixed sequence A
=(a
1
,a
2
, ···) in order, then A
is called
the inserted data template.
90 3 Modulus Structure Theory
Example 11. In Example 6, let B be mutated from sequence A, so the mutation
result B is uniquely determined if T along with the original and inserted data
templates are both known. By inserting 320 and 0333 and deleting 22012
in sequence A, we obtain sequence B. This mutation mode is described as
follows: T = {(9, +3), (20, −5), (29, 4)},
T
= (000000000300000000000, −5, 0000000004) .
Here the inserted data template is A
= (320333).
The Decomposition of the Modulus Structure of Shifting Mutation
The mutation modes T and T
defined in (3.52) can be decomposed further
according to the signs of the parameters γ
i
:
T
τ
= {(i
τ,k
,
τ,k
),k=1, 2, ··· ,k
τ
},T
τ
=(γ
τ,1
,γ
τ,2
, ··· ,γ
τ,n
a
) , (3.57)
where τ =+, −,and
γ
i
=
γ
i
, if γ
i
> 0 ,
0 , otherwise ,
γ
−,i
=
−γ
i
, if γ
i
< 0 ,
0 , otherwise .
(3.58)
If
θ
τ,i
=0, if γ
τ,i
=0,
1 , if γ
τ,i
> 0 ,
we can obtain the value of (i
τ,k
,
τ,k
) restricted by
i
τ,k
=min
i:
i
i
=1
θ
τ,i
≥ k
,
τ,k
= γ
τ,k
. (3.59)
Therefore, γ
τ,i
and (i
τ,k
,
τ,k
) in (3.57) can determine each other according to
(3.58) or (3.59). The following relationships are also satisfied:
1. k
+
+ k
−
= k
a
, where k
a
,k
+
,k
−
are the number of mutations described in
mutation modes T , T
+
, T
−
.
2. In (3.57), (i
+,k
,
+,k
) is the binary of the position and length of the type-
III mutation, while (i
−,k
,
−,k
) is the position and length of the type-IV
mutation, satisfying the following relationship:
1=i
τ,0
≤ i
τ,1
<i
τ,2
< ···<i
τ,k
τ
≤ i
τ,k
τ
+1
= n
a
. (3.60)
3. T
τ
and T
τ
determine each other and the corresponding expressions are
similar to (3.55) and (3.56).
Definition 20. The pairwise (T
+
,T
−
) defined in (3.57) is called the decom-
position of mutation mode T . Conversely, T is called the combination of
(T
−
,T
+
). T
+
,T
−
,T are respectively called the mutation mode of the type-III
mutation (insertion), type-IV mutation (deletion), and the shifting mutation,
alternatively to T
,T
+
,T
−
.
3.3 Analysis of Modulus Structures from Sequence Mutations 91
The Decomposition of Modulus Structure of Purely Shifting
Mutation
The purely shifting mutation defined in Sect. 3.3.1 can be decomposed as
follows:
A =
c
Δ
0
,c
Δ
1
I(c
Δ
2
)
−→ C =
c
Δ
0
,c
Δ
1
,c
Δ
2
D(c
Δ
1
)
−→ B =
c
Δ
0
,c
Δ
2
, (3.61)
where I(c
Δ
2
) is insertion sequence c
Δ
2
, D(c
Δ
1
) is deletion c
Δ
1
.Next,we
discuss the relationship between this decomposition and the modulus structure
T =(T
+
,T
−
):
1. The region demonstrated in (3.50) can be decomposed as follows:
Δ
= {j
0
,j
1
,j
2
, ··· ,j
k
a
,j
k
a
+1
} , (3.62)
where Δ
is defined by (3.50) and
j
0
=0≤ j
1
<j
2
< ···<j
k
a
≤ j
k
a
+1
= n
a
,
δ
k
=[j
k
+1,j
k+1
]=(j
k
+1,j
k
+2, ··· ,j
k+1
) . (3.63)
Since C is the expansion of D = c
Δ
0
, then the expanded mode from C to
D can be determined by (3.51) and is written as
H
0
= {(i
0,k
,
0,k
) ,k=1, 2, ··· ,k
a
} , (3.64)
where k
a
is the number of mutations in sequence A and 2k
a
= k
a
+1. We
then have
0,k
= j
2k+1
− j
2k
,
i
0,k
= j
2k
− L
k
,
(3.65)
where L
k
=
k−1
k
=1
d,k
. In view of the theory of expanded sequences, we
infer that (3.50), (3.62), and H
0
determine each other.
2. D is the compressed sequence from A; its compressed mode is the same as
the mode caused by type-IV mutation on sequence A. Let the expanded
mode from D to A be H
1
,then
H
1
=(T
−
)
−1
= {(i
1,k
,
1,k
),k=1, 2, ··· ,k
−
} , (3.66)
where (T
−
)
−1
is the inverse of T
−
. According to the definition of (3.7), we
have the formula for shifting mutation as follows:
1,k
=
−,k
,i
1,k
= i
−,k
− L
−,k
, (3.67)
where L
−,k
=
k−1
k
=1
−,k
. The symbols in (3.63) and (3.67) are defined
as follows.
92 3 Modulus Structure Theory
3. C is the expanded sequence of A and its expanded mode is just the muta-
tion mode of the type-III mutation on A. Therefore, the expanded mode
from A to C is H
2
= T
+
, and we can obtain the transformation relation-
ship of sequence A in C as follows: a
i
= c
j
if
j = i + L
+
(i) ,L
+
(i)=
k:i
+,k
<i
+,k
. (3.68)
4. B is the compressed sequence of the intermediate sequence C.Infact,
there is a type-III mutation which mutates A to C, and a type-IV mutation
which mutates C to B.LetH
3
bethecompressedmodefromC to B,so
we have
H
3
= {(i
3,k
,
3,k
),k=1, 2, ··· ,k
−
} , (3.69)
where
1,k
=
−,k
,i
3,k
= i
−,k
+ L
+,k
(3.70)
and L
+,k
=
k−1
k
=1
+,k
. As a result, the decomposition of (3.50) and
(3.51) and mutation mode T =(T
+
,T
−
) determine each other.
Their transformation is described in Steps 1–4. Keeping in mind the above
notation, we note the difference between L
τ,k
and L
τ
(i), in which, L
τ,k
is the
total length of the first k − 1 occurrences of type-τ mutations, but L
τ
(i)is
the total length of all the mutation types τ that happened before position i.
The modulus structure is demonstrated in Fig. 3.3.
Sequence B is mutated from A, and the mutation mode is
T = {(i
1
,
1
), (i
2
,
2
)} ,
in which i
1
,i
2
are the mutated positions. The mutation is a type-III mutation
if
1
> 0 and it is a type-IV mutation if
2
< 0. In light of Fig. 3.3, the
Fig. 3.3. The modulus structure of sequence mutation
3.4 The Binary Operations of Sequence Mutations 93
relationships are as follows: If we insert segment b
δ
b,2
into A after position i
1
,
we obtain sequence C, which is just the envelope of sequences A and B.Ifwe
delete the segment c
δ
c,4
from C after position i
2
+ l
1
,weobtainB,whichis
just is the output mutated from A directly. If we delete segment a
δ
a,3
from A
after position i
2
,wegetD, which is the core of sequences A and B.
3.3.3 Structural Representation of Mixed Mutation
If B is mutated from A by type-I, type-II, type-III, and type-IV mutations in
a hybrid, we must describe the procedure leading to the mutations. From the
basic assumption of shifting mutations, we begin to determine the modulus
structure of the shifting mutation, T =(T
+
,T
−
). Then,
A
T
+
−→ C
T
−
−→ D
T
0
−→ B, (3.71)
in which T =(T
+
,T
−
) is the shifting mutation, and T
0
is the nonshifting mu-
tation. According to the decomposition expression for the modulus structure
of shifting mutations, we decompose sequence C into three parts as follows.
C =(c
Δ
0
,c
Δ
1
,c
Δ
2
), in which c
Δ
2
is directly drawn from B.Sincec
Δ
1
is
deleted by the operation T
−
, it follows that mutations of type-I and type-II
only occur in c
Δ
0
. Therefore, the effect of a hybrid of four types of mutation is
equivalent to a hybrid of a purely shifting mutation and a nonshifting muta-
tion, and the type-I and type-II mutations only occur in Δ
0
. This illustrates
the data structural relationship of hybrid mutations.
3.4 The Binary Operations of Sequence Mutations
Operations of sequence mutations include all operators caused by the modulus
structure of the mutations and the transformations between the mutation
modes.
3.4.1 The Order Relationship Among the Modes of Shifting
Mutations
In Sect. 3.1, we mentioned the order relationship and binary operations for
expanded modes. Here, we expand it to the modes of the shifting muta-
tions.
The Order Relationship and Binary Operations for Shifting
Mutations
Let us begin with the definitions of relationships between and operations on
the modes caused by sequence mutations. Let T, T
,T
be three different
94 3 Modulus Structure Theory
mutation modes; following from (3.52) their expressions are as follows:
⎧
⎪
⎨
⎪
⎩
T =(γ
1
,γ
2
, ··· ,γ
n
a
)={(i
k
,
k
) ,k=1, 2, ··· ,k
a
} ,
T
=
γ
1
,γ
2
, ··· ,γ
n
a
= {(i
k
,
k
) ,k=1, 2, ··· ,k
a
} ,
T
=
γ
1
,γ
2
, ··· ,γ
n
a
= {(i
k
,
k
) ,k=1, 2, ··· ,k
a
} .
(3.72)
The notations γ
k
,γ
k
,i
k
,i
k
in T
, T
are similar to
k
,
k
in T .ThenT , T
,
T
satisfy the condition in (3.54) since they are shifting mutations. We can
then define the binary operations and order relationship.
Definition 21. Let T , T
be two shifting mutation modes based on the initial
template A.Then:
1. T and T
are consistent if for each i =1, 2, ··· ,n
a
, γ
i
> 0 implies γ
i
≥ 0,
and γ
i
< 0 implies γ
i
≤ 0. The converse is also true.
2. We say that T is included in T
if T, T
are consistent and |γ
i
|≤|γ
i
|
for each i =1, 2, ··· ,n
a
. In this case, we say that T is less than T
,and
denote it by T ≤ T
or T ⊂ T
.
Definition 22. Let T and T
be two consistent modes of shifting mutation.
We then define the binary operations as follows:
1. Union: The union operation is denoted by T
= T ∨ T
,andeachterm
of T
is a new mode defined by
γ
i
=
max{γ
i
,γ
i
}, if γ
i
,γ
i
≥ 0 ,
min{γ
i
,γ
i
}, if γ
i
,γ
i
≤ 0 .
(3.73)
2. Intersection: The intersection operation is denoted by T
= T ∧T
,and
each term of T
is defined by
γ
i
=
min{γ
i
,γ
i
}, if γ
i
,γ
i
≥ 0 ,
max{γ
i
,γ
i
}, if γ
i
,γ
i
≤ 0 .
(3.74)
3. Subtraction: Subtraction is denoted by T
= T
T ,andeachtermof
T
is defined by
γ
i
=
max{γ
i
− γ
i
, 0}, if γ
i
,γ
i
≥ 0 ,
min{γ
i
− γ
i
, 0}, if γ
i
,γ
i
≤ 0 .
(3.75)
Typically, if T ≤ T
, then the expression γ
i
= γ
i
− γ
i
holds.
4. Symmetric subtraction: Symmetric subtraction is denoted by T
=
T
ΔT ,andeachtermofT
is defined by
γ
i
=
max{γ
i
,γ
i
}−min{γ
i
,γ
i
}, if γ
i
,γ
i
≥ 0 ,
min{γ
i
,γ
i
}−max{γ
i
,γ
i
}, if γ
i
,γ
i
≤ 0 .
(3.76)
3.4 The Binary Operations of Sequence Mutations 95
Remark 1. Binary operations on the modes for shifting mutations are different
from those on modes for expanding sequences. Here, the binary operations are
only defined on the set of all consistent modes for shifting mutations. It would
be more complicated if we removed this restriction.
Properties of the Binary Operations and Order Relationships
on the Set of Modes
1. The order relationship satisfies transferability and self-reflectivity proper-
ties described below. Transferability:IfT ≤ T
and T
≤ T
,thenwe
have T ≤ T
. Self-reflectivity:IfT ≤ T
and T
≤ T ,thenwehave
T = T
.
2. The operations of intersection and subtraction defined in Definition 22
are closed. In other words, for any pair of consistent modes T and T
,
intersection and subtraction are still consistent modes.
3. The union operation defined in Definition 22 is not closed. For example,
let
T = {(3, 4), (10, −4)} T
= {(3, 2), (7, −5)} .
These satisfy the consistency condition of Definition 21, but their union
T
= T ∨ T
= {(3, 4), (7, −5), (10, −4)}
does not satisfy the basic assumption of shifting mutation because
i
2
+ |
2
| =12>i
3
=10.
4. If the modes T and T
of a shifting mutation are consistent and their
intersection, union and subtraction are closed, the following properties
are satisfied:
Commutative law of intersection and union:
T ∧ T
= T
∧ T, T∨T
= T
∨ T.
Associative law of intersection and union:
(T ∧ T
) ∧ T
= T ∧ (T
∧ T
) , (T ∨ T
) ∨T
= T ∨ (T
∨T
) .
Distributive law:
(T ∨ T
) ∧T
=(T ∧ T
) ∨ (T
∧ T
) .
These properties can be verified using Definition 22; we omit this discus-
sion here. As a result, we conclude that the set of all consistent modes
endowed with the operations of intersection, union and subtraction does
not form a Boolean algebra.
96 3 Modulus Structure Theory
3.4.2 Operators Induced by Modes of Shifting Mutations
In expression (3.71), we showed how A becomes B, and the corresponding op-
erators T, T
+
, T
−
, T
0
induced by the modes T =(T
+
,T
−
,T
0
), respectively.
If B is mutated from A by a purely shifting mutation, then T
0
is an iden-
tical operation. We discuss the data structural characteristics for these four
operators.
The Representation of Operators of Shifting Mutations
Since C is the expanded sequence of both A and B determined by shifting
mutation T , its decomposition is C =(c
Δ
0
,c
Δ
1
,c
Δ
2
) in Sect. 3.3.2, in which,
Δ
τ
is composed of several small intervals δ
τ,k
. Then,
A =
a
Δ
a,0
,a
Δ
a,1
=
c
Δ
0
,c
Δ
1
,B=
b
Δ
b,0
,b
Δ
b,1
=
c
Δ
0
,c
Δ
2
. (3.77)
This relationship is described in expressions (3.61)–(3.70). The corresponding
operators are
C = T
+
(A, B)=
c
Δ
0
,c
Δ
1
,c
Δ
2
=
a
Δ
a,0
,a
Δ
a,1
,b
Δ
b,2
,
B = T
−
(C)=
c
Δ
0
,c
Δ
2
=
b
Δ
b,0
,b
Δ
b,1
,
(3.78)
where a
Δ
a,0
= b
Δ
b,0
.
The Commutative Property of Operators of Shifting Mutations
In (3.71), the procedure that mutates A to B is chosen as follows: first ap-
ply T
+
and then T
−
. An alternative procedure would be first apply T
−
and
then T
+
. The commutative property is that the result of B is independent
of the order. While discussing shifting mutations, we always assume that the
modulus structure T in (3.72) satisfies
i
k+1
≥ i
k
+ |
k
|,k=1, 2, ··· ,k
a
, (3.79)
where i
k
a
+1
= n
a
.
Theorem 17. 1. Let T
+
, T
−
be the operators induced by type-III and type-
IV mutation based on the initial template A,andletT be the modulus
structure determined by (3.72). If T satisfies the condition of (3.79), the
operators are commutative.
2. The theorem can be expanded to address hybrid mutation. If shifting mu-
tations T
+
, T
−
of a hybrid mutation satisfy the conditions in expression
(3.72), then the operations of operators T
+
, T
−
, T
0
are all commutative,
where T
0
are operators induced by type-I or type-II mutations.
3.4 The Binary Operations of Sequence Mutations 97
Proof. Omitting the details of the proof, we use the following examples to
explain the theorem. Let k
1
= k
2
=2,n
a
= 20, and
T
+
= {(4, 2), (12, 4)},T
−
= {(7, 4), (16, 3)} .
Then, T = {(4, 2), (7, −4), (12, 4), (16, −3)}. It follows that T is a purely shift-
ing mutation from 12 > 7 + 4 = 11. The shifting mutation is decomposed as
follows:
A =(a
1
,a
2
, ··· ,a
20
)
T
+
−→ C
1
=(a
1
,a
2
,a
3
,a
4
,a
1
,a
2
,a
5
,a
6
, ··· ,a
12
,a
3
,a
4
,a
5
,a
6
,
a
13
,a
14
, ··· ,a
20
)
T
−
−→ B
1
=(a
1
,a
2
,a
3
,a
4
,a
1
,a
2
,a
5
,a
6
,a
7
,a
12
,a
3
,a
4
,a
5
,a
6
,
a
13
,a
14
,a
15
,a
16
,a
20
) ,
where (a
1
,a
2
,a
3
,a
4
,a
5
,a
6
) are the inserted data. If we exchange the operation
order of T
+
and T
−
, we find
A =(a
1
,a
2
, ··· ,a
20
)
T
−
−→ C
2
=(a
1
,a
2
,a
3
,a
4
,a
5
,a
6
,a
7
,a
12
,a
13
,a
14
,a
15
,a
16
,a
20
)
T
+
−→ B
2
=(a
1
,a
2
,a
3
,a
4
,a
1
,a
2
,a
5
,a
6
,a
7
,a
12
,a
3
,a
4
,a
5
,a
6
,
a
13
,a
14
,a
15
,a
16
,a
20
) .
Thus, B
1
= B
2
. That is, the mutation operations T
+
and T
−
are commutative.
In addition, the operator T
0
only acts on the region of Δ
0
, since it cannot act
on the region of Δ
1
and is useless if it happens in the region of Δ
2
because
its action will be deleted. Therefore, it is commutative with the operators of
T
1
, T
2
. The theorem is therefore proved.
As a consequence of this theorem, we find that the mode T of a shifting muta-
tion may be decomposed into several locally commutative shifting mutations
if T satisfies condition (3.79).
The Inverse of Shifting Mutation Operator T
If B is mutated from A by the shifting mutation operator T
a
, then the operator
induced by the mode of the shifting mutation that mutates B to A is the
inverse of T
a
.WedenotethisbyT
b
giving T
b
= T
−1
a
.
If the shifting mutation operator T is defined by (3.72), then we have
T
a
=(γ
1
,γ
2
, ··· ,γ
n
a
)={(i
k
,
k
) ,k=1, 2, ··· ,k
a
} ,
where γ
i
∈ Z,
k
=0andi
k
is the mutation position of sequence A.