Shen S., Tuszynski J.A. Theory and Mathematical Methods for Bioformatics
Подождите немного. Документ загружается.
78 3 Modulus Structure Theory
3. Relationships between the parameters of H
s
and K
s
are stated as follows:
⎧
⎪
⎨
⎪
⎩
s,k
= j
s,2k+1
− j
s,2k
,
L
s,k
=
k−1
k
=1
s,k
,
i
s,k
= j
s,2k−1
− L
s,k
.
(3.26)
The shifting formula of each position in sequence A
s
and A
s
is stated as
follows:
δ
s,k
= δ
s,2k−1
−L
s,k
=(j
s,2k−1
+1−L
s,k
,j
s,2k−1
+2−L
s,k
, ··· ,j
s,2k
−L
s,k
) .
(3.27)
4. Vector
a
s,δ
s,2k
=(
s,k
( )* +
4, 4, ··· , 4)
is a virtual vector with length
s,k
,anda
s,δ
s,2k−1
is a subvector of A
s
.
5. Let
⎧
⎨
⎩
Δ
s,1
=
δ
s,1
,δ
s,3
, ··· ,δ
s,2h
s
−1
,
Δ
s,2
=
δ
s,0
,δ
s,2
,δ
s,4
, ··· ,δ
s,2h
s
,
(3.28)
where Δ
s,1
, Δ
s,2
are the noninserted part and the inserted part of sequence
A
s
, respectively. Since a
s,j
, s =1, 2, ··· ,m has no m connected virtual
symbols for every fixed j, we find that
m
,
s=1
Δ
s,2
= φ (3.29)
is an empty set.
Theorem 14. H, H
and K are three equivalent representations of modes.
Proof. It follows from (3.4) and (3.5) that H and H
can be determined from
each other. It also follows from (3.27) that H and K can be determined from
each other.
3.2.2 Structure Analysis of Pairwise Alignment
In the case m =2,H and K are defined by (3.18) and (3.24), respectively,
and are referred to as the modes of pairwise alignment. We then represent
(A
1
,A
2
)and(A
1
,A
2
)by(A, B)and(A
,B
), respectively. Since (A
,B
)is
the expanded sequence of (A, B), their modes are stated as follows:
H =(H
1
,H
2
)=(H
a
,H
b
) ,K=(K
1
,K
2
)=(K
a
,K
b
) .
Following from (3.28) and (3.29), we have that Δ
1,2
∩ Δ
2,2
= φ.Next,we
process (A
,B
) as follows:
3.2 Modulus Structure of Sequence Alignment 79
Make A
and B
the Same Length
In this process, we make A
and B
have the same length by inserting virtual
symbols into the shorter sequence, so that n
a
= n
b
= n
are the common
length of A
and B
. Similarly, let N
a
= N
b
= N
= {1, 2, ···,n
} be the
regions of positions of A
and B
.
Decomposition of the Region N
Resulting from Alignment
Definition 16. N
=(Δ
0
,Δ
1
,Δ
2
) is called the decomposition of region N
,
in which
Δ
1
= Δ
1,2
,Δ
2
= Δ
2,2
,Δ
0
= N
a
− (Δ
1
∪ Δ
2
) , (3.30)
and Δ
s,2
is defined in (3.28).
Details about the decomposition of N
=(Δ
0
,Δ
1
,Δ
2
)arestatedbelow:
1. Since Δ
τ
,τ=0, 1, 2aredisjoint,wehaveΔ
0
∪ Δ
1
∪ Δ
2
= N
and
Δ
τ
∩ Δ
τ
= φ, τ = τ
∈{0, 1, 2}.
2. Following the definitions of Δ
1,2
and Δ
2,2
, we have that the values of A
on region Δ
1
and B
on region Δ
2
are both 4. In the region Δ
0
, there is no
virtual symbol in the sequences C and D. Therefore, the decomposition
of N
=(Δ
0
,Δ
1
,Δ
2
) actually classifies N
into three parts:
(a) Part 1 (Δ
1
): In this region, the sequence A
is composed of virtual
symbols while B
does not contain virtual symbols.
(b) Part 2 (Δ
2
): In this region, B
is composed of virtual symbols while
A
has no virtual symbols.
(c) Part 3 (Δ
0
): In this region, both A
and B
have no virtual symbols.
Definition 17. In the decomposition, Δ
0
is called the noninserted region for
both A
and B
,whileΔ
1
and Δ
2
are referred to as the dual inserting regions
of A
and B
. This means that Δ
1
is the inserting region of A
but not the
inserting region of B
,andΔ
2
is the inserting region of B
but not the inserting
region of A
.
Structure Analysis of Decomposition
Each of the three regions Δ
τ
, τ =0, 1, 2 is composed of many smaller regions.
We denote them as follows:
Δ
τ
=
δ
τ,1
,δ
τ
,2
, ··· ,δ
τ,k
τ
,τ=0, 1, 2 . (3.31)
These smaller intervals are disjoint from each other, and their union is N
.
Furthermore, we have δ
τ,k
∩ δ
τ
,k
= φ and
-
2
τ =0
-
k
τ
k=1
δ
τ,k
= N
for all
(τ
,k
) =(τ, k). Following (3.31), we can alternatively represent all the regions
80 3 Modulus Structure Theory
using smaller intervals as follows:
Δ
= {Δ
τ
,τ=0, 1, 2} = {δ
τ,k
,k=1, 2, ··· ,k
τ
,τ=0, 1, 2} . (3.32)
If we arrange them according to their size, they are disjoint with each other
and fill all the regions of N
. Thus, we can decompose N
as follows:
N
=
δ
1
,δ
2
, ··· ,δ
k
a
=
j
1
,j
2
, ··· ,j
k
a
, (3.33)
in which k
a
= k
0
+ k
1
+ k
2
and
j
1
=0<j
2
<j
3
< ···<j
k
a
≤ j
k
a
+1
= n
,
and
δ
k
=[j
k
+1,j
k+1
]={j
k
+1,j
k
+2, ··· ,j
k+1
}
Consequently, δ
j
is included in Δ defined in (3.32), and satisfies the following
conditions:
1. δ
1
∈ Δ
0
,andδ
1
may be empty.
2. For every j =1, 2, ··· ,k
a
,ifδ
j
∈ Δ
1
∪ Δ
2
,wemusthaveδ
j+1
∈ Δ
0
.
Consequently, in the decomposition of (3.33), we have that
δ
2k−1
∈ Δ
0
,δ
2k
∈ Δ
1
∪ Δ
2
holds.
3. Let k
0
= k
1
+ k
2
,k
a
=2k
0
,thenδ
2k
0
may be an empty set. Then, (3.33)
is called the decomposition of region N
a
of (A
,B
). As well, we may
represent the mode of the alignment as follows:
K
0
= {(δ
k
,τ
k
),k=1, 2, ··· ,k
a
} = {(j
k
,
k
,τ
k
),k=1, 2, ··· ,k
a
} ,
(3.34)
in which
k
= j
k+1
− j
k
, j
k
,andδ
k
are defined by (3.33), and τ
k
=
0, 1, 2 is determined by the fact that δ
2k
belongs to one of ∈ Δ
0
, Δ
1
and Δ
2
. The vector ¯τ =(τ
1
,τ
2
, ··· ,τ
k
a
) is called the structure model
of the aligned sequence. Following from (3.34), we have that K
0
has an
alternative representation given by:
H
0
= {(i
k
,
k
),k=1, 2, ··· ,k
0
} , (3.35)
in which j
k
= i
2k
+ L
k
, and
k
=
||δ
2k
||, if τ
2k
=1,
−||δ
2k
||, if τ
2k
=2.
It is easy to prove that H
0
and K
0
as defined in (3.34) and (3.35) are two
equivalent modes.
3.2 Modulus Structure of Sequence Alignment 81
3.2.3 Properties of Pairwise Alignment
If the alignment mode K
0
of the aligned sequence (A
,B
)isgiven,then
(A
,B
) can be decomposed as follows:
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
A
=
a
δ
1
,a
δ
2
, ··· ,a
δ
k
a
,
B
=
b
δ
1
,b
δ
2
, ··· ,b
δ
k
a
,
¯τ =
τ
1
,τ
2
, ··· ,τ
k
a
,
(3.36)
in which τ ∈{0, 1, 2} and the vector ¯τ is called the structure type of the
aligned sequence. More details are provided below. Let n =max{n
a
,n
b
},and
H
s
=(γ
s,1
,γ
s,2
, ··· ,γ
s,n
), s = a, b, then the alignment mode of (H
a
,H
b
)can
be rewritten as
H
0
= {(i
h
,
h
),h=1, 2, ··· ,h
a
+ h
b
} H
0
=(γ
1
,γ
2
, ··· ,γ
n
0
) , (3.37)
where
γ
j
=
⎧
⎪
⎨
⎪
⎩
0 , if γ
1,j
= γ
2,j
=0,
γ
1,j
, if γ
1,j
> 0, γ
2,j
=0,
−γ
2,j
, if γ
1,j
=0,γ
2,j
> 0 .
Since γ
1,j
and γ
2,j
are not greater than 0 simultaneously, it follows that the
alignment modes (H
1
,H
2
)andH
0
can be determined from each other. Let
I
0
= {i ∈ N
a
: γ
i
=0}
so that i
h
∈ H
0
implies i
h
∈ I
0
.Next,let
h
= γ
i
h
if i
h
∈ I
0
,andlet
L
s
(j)=
j−1
j
=1
γ
s,j
,j=1, 2, ··· ,n
s
,s=1, 2 . (3.38)
These are referred to as the inserted functions of the expanded sequence A
,B
.
Consequently, we define
L
0
(j)=L
1
(j) − L
2
(j) ,L(j)=L
1
(j)+L
2
(j) ,j=1, 2, ··· ,n
0
, (3.39)
which are referred to as the relatively inserted length function and the ab-
solutely inserted length function of (A
,B
), respectively, in which, n
0
=
max{n
1
,n
2
}.
Theorem 15. If H
0
is the alignment mode defined by (3.38), then we have
L
0
(j)=
j−1
j
=1
γ
j
,L(j)=
j−1
j
=1
|γ
j
| , (3.40)
in which || is the absolute value of . The alignment mode H
0
and function
L
0
(j) can be determined from each other.
82 3 Modulus Structure Theory
Proof. Formula (3.40) follows from the definition of H
0
,thatis,H
0
determines
L
0
(j). Conversely, γ
j
= L
0
(j +1)− L
0
(j) follows from (3.38). Thus, H
0
is
determined. Therefore, each of H
0
and L
0
(j) can be determined by the other.
Expression (3.36) decomposes (A
,B
) into three parts: the noninserting part,
the inserting part and the dual-inserting part. Their relationship is demon-
strated in Fig. 3.2 using a bold line, a normal line and a broken line.
In this figure, A
,B
are the aligned sequences of sequences A and B,
respectively, where:
1. The alignment modes are:
H
a
= {(i
a,1
,
a,1
), (i
a,2
,
a,2
)} H
b
= {(i
b,1
,
b,1
), (i
b,2
,
b,2
)} .
2. One of the decompositions of A
and B
resulting from alignment is Δ
=
{δ
1
,δ
2
, ··· ,δ
9
},inwhich
δ
k
=[j
k
+1,j
k
]=(j
k
+1,j
k
+2, ··· ,j
k+1
) .
3. In the decomposition Δ
,
Δ
0
= {δ
1
,δ
3
,δ
5
,δ
7
,δ
9
} and Δ
3
= {δ
2
,δ
4
,δ
6
,δ
8
}
Fig. 3.2. The modulus structure of sequence alignment
3.2 Modulus Structure of Sequence Alignment 83
are the noninserted part and the inserted part of the alignment, respec-
tively, where δ
7
is an empty set, and Δ
1
= {δ
4
,δ
8
}, Δ
2
= {δ
2
,δ
6
} are the
common inserted part of both A
and B
.
By using positive and negative signs, K
0
canbeexpressedasfollows:
K
0
=(θ
1
,θ
2
, ··· ,θ
n
a
) , (3.41)
where θ
j
= τ
k
∈{0, 1, 2} if j ∈ δ
k
and (δ
k
,τ
k
) is determined by K
0
in (3.35).
We then have
Δ
τ
= {j ∈ N
a
,θ
j
= τ},τ=0, 1, 2 ,
where Δ
τ
is defined in (3.30).
Example 6. If
A = (11231003221000232103220121120) ,
B = (1123100323202100023210311200333) ,
the aligned sequences are
A
= (112310032[444]21000232103[22012]1120[4444]) ,
B
= (112310032[320]21000232103[44444]1120[0333]) ,
where the corresponding noninserted part, inserted part and the dual part are
indicated by brackets. The part whose value is 4 is the inserted part, the part
whose value is not 4 is the dual part, and the rest is the noninserted part. By
using the corresponding formula for alignment modes, the decompositions are
as stated as follows:
1. The length of sequence A is n
1
= 29, and the length of sequence B is
n
0
= n
2
= 31.
2. Their alignment mode is
H
1
= {(9, 3), (29, 4)} = (000000000300000000000000000004) ,
H
2
= {(23, 5)} = (00000000000000000000000500000000) .
The alternative form is H
0
= (0000000030000000000000(−5)00000400).
3. Following from (3.33) as k
a
= 6, we get the decompositions of K
0
as
follows:
K
0
= {(9, 0), (3, 1), (11, 0), (5, 2), (4, 0), (4, 1)}
= {(0, 0), (9, 1), (12, 0), (23, 2), (28, 0), (32, 1)}
These are the two alternative decompositions about K
0
stated in (3.33).
84 3 Modulus Structure Theory
4. The corresponding decomposition function is
⎧
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎩
¯
L
1
= (00000000333333333333333333337) ,
¯
L
2
= (0000000000000000000000444444444) ,
¯
L
0
= (0000000033333333333333, −1, −1, −1, −1, −1, −1, −1, −1, 3) ,
¯
L = (000000003333333333333377777777, 11) ,
in which
¯
L
z
=(L
z
(1),L
z
(2), ··· ,L
z
(n
0
)). In the vector
¯
L
z
,weonlyuse
the comma to separate the negative components and the components
whose values exceed 10.
5. The decomposition K
0
can be written as:
K
0
= (000000000111000000000002222200001111)
and
Δ
0
= {1, 2, 3, 4, 5, 6, 7, 8, 9, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 29, 30, 31, 32} ,
Δ
1
= {10, 11, 12, 33, 34, 35, 36} ,
Δ
2
= {24, 25, 26, 27, 28} .
These are the noninserted and inserted parts of both C and D, respec-
tively.
3.2.4 The Order Relation and the Operator Induced by Modulus
Structure
We can expand the order relation and the operator to apply to the modulus
structures induced by multiple alignments as follows:
1. Let H =(H
a
,H
b
)andH
=(H
a
,H
b
) be two modulus structures induced
by pairwise alignment. We can say that H ≤ H
if both H
a
≤ H
a
and
H
b
≤ H
b
hold.
2. The union operation between two modulus structures H, H
given in con-
dition 1 is defined as H ∨H
=(H
a
∨ H
a
,H
b
∨H
b
).
3. Similarly, we can define other binary operations such as intersection and
subtraction between two modulus structures H, H
, such that the set of all
modulus structures obey Boolean algebra with these binary operations.
4. With a similar argument, we may find that corresponding operators can
also be induced by the modulus structure. Let (A, B) be a pair of sequences
and H =(H
a
,H
b
) be the corresponding modulus structure pair. There is
then a pair of aligned sequences (A
,B
), and the corresponding operators
H are induced as
(A
,B
)=H(A, B)=(H
a
(A), H
b
(B)) . (3.42)
3.3 Analysis of Modulus Structures from Sequence Mutations 85
3.3 Analysis of Modulus Structures Resulting
from Sequence Mutations
We have noted in Chap. 1 that there are four types of biological mutations,
and we called them type-I, type-II, type-III, and type-IV mutations. Recall
that type-I and type-II mutations do not change the lengths of sequences, and
thus they are also called nonshifting mutations. On the other hand, type-III
and type-IV mutations necessarily change the lengths of sequences, so they
are referred to as shifting mutations. In this chapter, we focus on type III and
type IV mutations.
3.3.1 Mixed Sequence Mutations
Following the definitions of type-III and type-IV mutations, their mathemat-
ical representations are just a mixture of expanding and compressing opera-
tors. That is, the shifting mutations are mixed operations of expanding and
compressing operations. Since the cases in which mixed operations occur are
more complicated than the operations themselves, we discuss the possible sit-
uations in which mixed operations occur. From their definitions, we know
that type-I and type-II mutations are different from type-III and type-IV
mutations. However, it is possible to consider one type as the combination
of other types. This may at first seem counter-intuitive, but it is true. For
example:
Example 7. Assume a type-I mutation occurs at the second nucleotide of se-
quence acg, i.e, it changes acg into aug. This is a type-I mutation, but it can
be regarded as the combination of a type-IV mutation that deletes c so that
acg becomes ag, followed by a type-III mutation that inserts u into ag, mak-
ing ag become aug. This demonstrates that type-III and type-IV mutations
can be represented by type-I and type-II mutations, and vice versa. Next, we
consider the following cases:
1. At the same position, if a type-III mutation (insertion) occurs times,
and a type-IV mutation (deletion) occurs times, then all insertions and
all deletions will counteract each other, and there is no shifting.
2. At the same position, if a type-IV mutation occurs times and a type-III
mutation occurs times, but the inserted characters and deleted charac-
ters are different, it is as if a type-I mutation occurred. Above all, we may
conclude that for mixtures of the four types of mutations, type-III and
type-IV have no intersection, and intersection regions can be replaced by
type-I and type-II mutations.
Example 8. The shifting mutations from sequence A = (acccccuuuuu) to
A
= (aggguuuuu) can be divided as follows: deleting five nucleotides c after
position 1 and then inserting three nucleotide g after position 1. The mixed
86 3 Modulus Structure Theory
mutation can be divided into a type-IV mutation and a type-III mutation
acting on the sequence A as follows:
acccccuuuuu
IV
−→ auuuuu
III
−→ aggguuuuu . (3.43)
The combined effect of the two mutations is the same as that of a type-I
mutation, ccc → ggg, and a type-IV mutation that deletes the cc at positions 5
and6.Theprocessisasfollows:
acccccuuuuu
I
−→ agggccuuuuu
IV
−→ aggguuuuu . (3.44)
Based on this example, we can conclude that a pair of type-III and type-
IV mutations can be decomposed as a nonshifting mutation and a shifting
mutation if type-III mutation occurs in the region of the type-IV mutation.
Example 9. In Example 8, if type-III mutation occurs first and type-IV muta-
tion occurs later, then the effect of these two shifting mutations is as follows:
acccccuuuuu
III
−→ accccgggcuuuuu
IV
−→ aggcuuuuu . (3.45)
The effect is the same as inserting the nucleotide triplet ggg after position 5
and then deleting nucleotides ccccg at positions 2–6. The final result is the
same as: acccccuuuuu → aggcuuuuu. It is different from the result: aggguuuu,
which is given in Example 8.
Therefore, the results are related to the order in which the type-III mu-
tation and type-IV mutation occur if the regions of the type-III and type-IV
mutations intersect. Generally, a different ordering of the type-III and type-IV
mutations will lead to different results. On the other hand, the result of the
first mutation of (3.44) can be considered as a mixture of a type-I mutation
plus a type-IV mutation as follows:
acccccuuuuu
I
−→ agccccuuuuu
IV
−→ agccuuuuu . (3.46)
Basic Assumptions About Hybrid Mutation
If B is mutated from sequence A, then the type-III and type-IV mutation
regions do not intersect. This means that there is no type-III mutation occur-
ring in the interval [i +1,i+ ] if a type-IV mutation of length occurs at
position i of sequence A. The inverse is also true.
Theorem 16. If a mixed mutation satisfies the basic assumptions, then it can
be decomposed into several single mutation types and the result is invariant
with respect to the mutation order.
The theorem will be proved later. Assuming that the sequence mentioned here
satisfies this basic assumption, the result of Theorem 16 will always hold. Since
3.3 Analysis of Modulus Structures from Sequence Mutations 87
it is more difficult to deal with a case involving shifting mutation based on
the above mentioned sequence mutation theory, we will discuss hybrid mu-
tations without type-I and type-II mutations. This hybrid mutation is called
the purely shifting mutation.
Example 10. We begin by discussing the sequence
A = (00000 11111 11111 22222 22222 22222 33333 33333) .
We perform type-II, type-III, and type-IV mutations defined respectively as
follows: (1) type-II mutation – mutually exchanging the data within [11, 15]
to that within [16, 20], and mutually exchanging the data within [26, 30] to
that within [31, 35]; (2) type-III mutation – inserting the segment 00112233
after position 13; (3) type-IV mutation – deleting a segment with length 3
after position 27. We then have the following output for each stage:
1. On one hand, the type-II mutation mutates A to B,
B = (00000 11111 22222 11111 22222 33333 22222 33333) ,
and then type-III mutation and type-IV mutation continuously mutate B
to C,
C = (00000 11111 222[00 11223 3]2211 11122 22233 22222 33333) .
2. On the other hand, the type-III and type-IV mutations mutate A to D,
D = (00000 11111 111[00 11223 3]1122 22222 22222 33333 33333) ,
and then the type-II mutation continuously mutates D to E,
E = (00000 11111 112[23 11100 3]1122 22222 33333 22222 33333) .
Then C and E are different. As a result, we conclude that the action order
between type-II mutations and type-III and type-IV mutations do not gen-
erally permit an exchange. However, an exchange is permitted if there is no
type-II mutation in any region of insertion.
3.3.2 Structure Analysis of Purely Shifting Mutations
Decomposition of Shifting Mutations
If sequence B is mutated from A through purely shifting mutations, we then
denote the intermediate result as C =(c
1
,c
2
, ··· ,c
n
a
) mutated from A
through type-III mutation, and then to B through type-IV mutation. The
procedure is represented as follows:
A =(a
1
,a
2
, ··· ,a
n
a
)
III
−→ C =(c
1
,c
2
, ··· ,c
n
c
)
IV
−→ B =(b
1
,b
2
, ··· ,b
n
b
) .
(3.47)
The sequence C is an envelope of (A, B), and we may decompose C as follows: