Shen S., Tuszynski J.A. Theory and Mathematical Methods for Bioformatics

Подождите немного. Документ загружается.

2.4 Type-II Mutated Sequences 57

holds. It implies that

ξ, ˜η; i, j, n)=



k∈Δ

∗

(n)

w(ξ

,η

) ∼

E{ψ

∗

2,n

} =

3





(2.88)

holds. Relation (2.88) can be proved by the Markov large number theorem.

We can regard the sum of {w(ξ

,η

),k∈ δ

∗

} as the sum of a group of

independent sequences

∗



j∈δ

∗

2,1;k

∪δ

∗

2,2;k

w(ξ

,η

) ,k=1, 2, 3, ···

so we can use the large number theorem to obtain (2.88).

3. If i = j, we can also get

ξ, ˜η; i, j, n) ∼

[w(0, 1) + w(0, 2) + w(0, 3)] . (2.89)

Using the central limit theorem, we can accurately estimate the relation-

ship (2.89). Details of the calculation are omitted here.

2.4.4 The Mixed Stochastic Models Caused

by Type-I and Type-II Mutations

We have already described type-I and type-II mutated sequences. Now we

consider the combination of these two types.

The Mixed Stochastic Models for Both Type-I and Type-II

Mutated Sequences

The mixed stochastic models for both type-I and type-II mutated sequences

are described as follows. Here, the mixed stochastic model is denoted by

∗

I,II

= {

ξ,



∗

, ˜η, τ =1, 2} (2.90)

in which:

ξ is the initial sequence, which is also a perfect sequence.

, τ =1, 2 are two Bernoulli processes representing the ﬂows caused by

type-I and type-II mutations, respectively.

is the sequence added by all type-I mutated errors given in (2.49).



∗

, τ =1, 2 are the sequences consisting of the lengths of the permutated

segments of type-II mutation, given by (2.65).

All stochastic sequences in E

∗

I,II

are therefore independent, and their mutation

types can be determined based on the regulations I-1, I-2, II-1,andII-2.

The mutated sequence ˜η is then produced by the following rules.

58 2 Stochastic Models of Mutations and Structural Analysis

5. Let η

= ξ

if ζ

1,j

= ζ

2,j

=0.

6. Using the rules I-1 and I-2 to determine η

if ζ

1,j

=1 and ζ

2,j

=0.

7. We follow the rules II-1 and II-2 to determine the values of η

2,0

and

∗

2,1

∪δ

∗

2,2

if ζ

1,j

=0 andζ

2,j

=1.

8. We assume that ζ

1,j

=1,ζ

2,j

= 1 do not occur simultaneously.

Error Analysis of Type-I and Type-II Mutations

If ˜η is a sequence caused by type-I and type-II mutations, then the local

penalty functions w(

ξ, ˜η; i, j, n) about both ˜η and

ξ are estimated as follows:

1. If i = j, we can see from (2.61) and (2.88) that

ξ, ˜η; i, j, n) ∼





−

w









, (2.91)

in which 

,

are the strengths of the Bernoulli processes, and

, τ =1, 2

and p

are parameters of the geometric distribution of



∗

, τ =1, 2and

w = w(0, 1) + w(0, 2) + w(0, 3).

2. If i = j, from (2.77) and (2.89) we obtain

ξ, ˜η; i, j, n) ∼



. (2.92)

2.5 Mutated Sequences Resulting from Type-III

and Type-IV Mutations

Deﬁnitions of type-III and type-IV mutations are given in Chap. 1. They are

referred to as displacement mutations. We discuss the stochastic models of

type-III and type-IV mutated sequences below.

2.5.1 Stochastic Models of Type-III and Type-IV Mutated

Sequences

The deﬁnition of the stochastic model for type-III and type-IV mutated se-

quences is as follows:



∗

= {

ξ,



∗

, ˜η},

∗

= {

ξ,



∗

, ˜η} .

(2.93)

These satisfy the following conditions:

III-1 For a ﬁxed τ =3, 4, the three stochastic sequences

ξ,



∗

are i.i.d.

processes, in which:

ξ is the initial process, which is a perfectly stochastic sequence

on V

2.5 Mutated Sequences Resulting from Type-III and Type-IV Mutations 59

is a Bernoulli process with strength 

in which each ζ

τ,j

de-

notes the random variable that describes whether or not the type-τ

mutation occurs.



∗

is a stochastic sequence obeying geometric distribution with the

parameter p

.Each

∗

τ,j

then denotes the sequence of the lengths

of segments in the jth insertion or deletion.

is a perfectly stochastic sequence on V

. It is a type-III mu-

tated sequence. That is, it is mutated from the initial sequence by

insertion of some “−”.

III-2 For a ﬁxed τ =3, 4, the three stochastic sequences

ξ,



∗

are inde-

pendent, and

is independent of

ξ,



∗

Let ˜v

∗

be the renewal process of

and let

∗

be the corresponding

dual renewal process (deﬁnitions are given in Sect. 2.2). Let



= {˜a, ˜z



, ˜u

= {˜a, ˜z



}

(2.94)

be the sample of E

∗

. The procedure to determine E

∗

based on E

or E

is stated as follows:

1. Determine the renewal sequence ˜v

and its corresponding dual re-

newal process

based on ˜z

.Then

1 ≤ j

τ,1

τ,2

τ,3

< ··· (2.95)

divides the whole set of positive integers V

=(1, 2, 3, ···)into

several segments.

2. The role of the type-IV mutation is to delete the segment

4,k

+

4,k

+1)

=(a

4,k

, ··· ,a

4,k

+

4,k

)

from the initial sequence ˜a =(a

, ···).

3. The role of the type-III mutation is to insert the segment

(ψ

4,k−1

,ψ

4,k

+1)

=(u

4,k−1

, ··· ,u

4,k

)

into ˜a =(a

, ···) following a

3,k

in which ψ

4,k



i=1



4,j

and u

∈ V

belongs to ˜a.

Consequently, we can ﬁnd the type-III and type-IV mutated sequences from

based on the various sequences and generation rules III-1 and III-2.

2.5.2 Estimation of the Errors Caused by Type-III and Type-IV

Mutations

We can estimate the local penalty function w(

ξ, ˜η; i, j, n) of the type-III and

type-IV mutated sequence ˜η as follows.

60 2 Stochastic Models of Mutations and Structural Analysis

Estimation of the Lengths of the Inserted or Deleted Segments

in Type-III and Type-IV Mutated Sequences

We can estimate the lengths of the inserted or deleted segments in type-III

and type-IV mutated sequences using renewal processes. Let ψ

τ,i,n

be the

total number of inserted or deleted segments within the region [i +1,i+ n]=

{i +1,i+2, ··· ,i+ n}, so that the probability of ψ

τ,i,n

is independent of i

because of the homogeneous nature of stochastic models. Thus, it is enough

that we consider

τ,n

∗

τ,n



j=1



∗

τ,j

. (2.96)

Using the limitation property of the compound renewal process, we have

E{ψ

τ,n

} = E{v

∗

τ,n

}E{

∗

τ,1

} =



,τ=3, 4 . (2.97)

Following from the law of large numbers for compound renewal processes, we

have

τ,n

∼ E{ v

∗

τ,n

}E{

∗

τ,1

} =



,τ=3, 4 . (2.98)

3,n

is then the combined length of all inserted segments in the region

[1,n], and ψ

4,n

isthecombinedlengthofalldeletedsegmentsinregion[1,n].

Estimation of Local Penalty Function w(

ξ, ˜η; i, j, n)

Without loss of generality, we discuss the estimation of the local penalty

function w(

ξ, ˜η; i, j, n) on type-III mutated sequences as follows:

1. In the case i = j =1,let

be the dual renewal process of ˜v

∗

.Ifv

∗

3,1

v<n, then there is no mutation in the region δ

=[1,v]=(1, 2, ··· ,v)

but there is a displacement mutation in the region δ =[v +1,n]=(v +1,

v +2, ··· ,n). Consequently, following from the large number law, we have

ξ, ˜η; i, j, n|v

∗

3,1

= v) ∼

(n − v)w

(2.99)

and

ξ, ˜η; i, j, n)=



v=1

∗

3,1

= v}w(

ξ, ˜η; i, j, n|v

∗

3,1

= v)

∼



v=1



(1 − 

)

v−1

(n −v)w

If n is large enough, we have the relationship

ξ, ˜η; i, j, n) ∼



1 −

n



. (2.100)

2.5 Mutated Sequences Resulting from Type-III and Type-IV Mutations 61

2. In the case where i<j,since˜η is a type-III mutated sequence of

ξ,we

ﬁnd

ξ, ˜η; i, j, n) ∼

. (2.101)

3. In the case where i>j,let˜v

∗

be the dual renewal process of

.Ifthere

is a k>0 such that v

∗

3,k

= i − j, then following from (2.100), we have

ξ, ˜η; i, j, n|v

∗

3,k

= i − j) ∼



1 −

n



, (2.102)

otherwise (2.100) holds. Following from (2.100) and (2.101), we may ob-

tain an estimate of w(

ξ, ˜η; i, j, n). However, we omit this here because the

computation is far too complex.

2.5.3 Stochastic Models of Mixed Mutations

A stochastic model of mixed mutations is the stochastic model that results

when we have type-I, type-II, type-III, and type-IV mutations all occurring

at the same time.

Deﬁnition of Stochastic Model of Mixed Mutations

Stochastic models of mixed mutations can be described by the following rela-

tionship:

∗



ξ,



∗



,τ=1, 2, 3, 4; τ



=1, 3



(2.103)

satisfying the following conditions:

IV-1 Sequences of E

∗

are homogeneous and i.i.d. processes, in which:

ξ is a perfectly stochastic sequence on V

as the initial sequence.

is a Bernoulli process with strength 

,inwhich,eachζ

τ,j

a random variable describing whether or not type-τ mutation oc-

curs.



∗

is a stochastic sequence obeying a geometric distribution with

a parameter p

,inwhich,

∗

1,j

, 

∗

2,j

are the lengths of the per-

mutated segments if the jth mutation is type-II, while 

∗

3,j

, 

∗

4,j

represent the length of the inserted or deleted segment if the jth

mutation is type-III or type-IV, respectively.

is the additional error sequence resulting from type-I mutations,

andisdeﬁnedinI-3.

is a perfectly stochastic sequence on V

which is the inserted sequence resulting from type-III mutation.

IV-2 All stochastic sequences in E

∗

are independent. For any τ =1, 2, 3, 4,

the sequence ˜v

∗

is the renewal process of the sequence

,and

∗

is the

dual renewal process of

62 2 Stochastic Models of Mutations and Structural Analysis

IV-3 In the mixed stochastic model E

∗

, {

,τ =1, 2, 3, 4} is the param-

eter set, in which, 

, τ =1, 2, 3, 4 represents the strengths of the four

types of mutations, p

are parameters of the geometric distribution

that describes the type-II mutated sequences, and p

are parameters

of the geometric distribution that describes the type-III and type-IV

mutated segments, respectively.

Samples of the Stochastic Model of Mixed Mutations

Let

E = {˜a, ˜z



, ˜u



,τ=1, 2, 3, 4; τ



=1, 3} (2.104)

be the sample of E

∗

, so that we may obtain the mutated sequences through

the following steps:

1. Determine the renewal sequence ˜v

and the dual renewal process

,based

on ˜z

2. Determine the type-I mutated sequence b

according to steps I-1–I-4 in

case z

1,j

=1.

3. Determine the type-II mutated sequence b

(j,j+

2,k

)

, according to steps II-1

and II-2 in the case z

2,j

=1,inwhichk = v

2,j

4. Determine the type-III or type-IV mutated sequences according to steps

III-1 and III-2 in the cases z

3,j

=1orz

4,j

=1.

5. For the same j, we assume that there are no more than two types such

that the state of z

τ,j

,τ =1, 2, 3, 4 is 1, which is based on the following.

Since

1,j

+ z

2,j

+ z

3,j

+ z

4,j

≥ 2}≤



i=j∈{1,2,3,4}



and 

+ 

 1, we have P

1,j

+ z

2,j

+ z

3,j

+ z

4,j

≥ 2}∼0.

Estimation of Crossed Probability of Mixed Mutations

Since type-II, type-III, and type-IV mutations involve only a segment (if the

mutation does in fact occur), it implies that diﬀerent mutation types could

happen in the same regions. This is what is meant by the term “crossed mu-

tations”. We can estimate the probability of this occurring, which is referred

to as the crossed probability of mixed mutations. Typically, the crossed prob-

ability of type-III and type-IV is

{in region N, type-III and type-IV mutations both happen}

= P

{Δ

∗

(n) ∩ δ

∗

(n) = φ} , (2.105)

in which φ is the empty set and Δ

∗

(n), τ =3, 4 are the same as that deﬁned

in (2.87), then

∗

(n)=Δ

∗

∩ N, τ=3, 4 , (2.106)

2.5 Mutated Sequences Resulting from Type-III and Type-IV Mutations 63

∗

=(δ

∗

τ,1

,δ

∗

τ,2

,δ

∗

τ,3

, ···)and

τ,k

=(j

∗

τ,k

+1,j

∗

τ,k

+2, ··· ,j

∗

τ,k

+ 

∗

τ,k

) .

We compute the values of (2.104) as follows:

1. Let the value of (2.104) be Γ ;wethenhave

Γ ≤ P

{there is a j ∈ Δ

∗

(n) , such that ζ

4,j

=1}

+ P

{there is a j ∈ δ

∗

(n) , such that ζ

3,j

=1} . (2.107)

2. Let the two items on the left hand side of (2.107) be Γ

,Γ

,thenwe

estimate the values of Γ

,Γ

as follows.

Using the limit property of compound renewal processes, we have that the

length of δ

∗

3,n

is close to

n

. Consequently, the probability that ζ

∗

3,n

the 0-vector is (1 − 

)

n

. Then,

=1−(1 − 

)

n

=[1− (1 − 

)

1/

]

(n



)/p

∼ 1 − exp



−

n





Similarly,

∼ 1 − exp



−

n





Therefore,

Γ ≤ 2 − exp



−

n





− exp



−

n





. (2.108)

Based on (2.107), we can say that the combined probability of type-III and

type-IV mutations happening in the region [1,n] at the same time is very

small if n 



. We do not give the proof here.

Semistochastic Models of Mutations

We have introduced the stochastic models of mutated sequences, which show

many factors aﬀecting the mutations, as well as descriptions of the randomness

of these factors. Following from these descriptions, we ﬁnd some character-

istics of the stochastic models of mutated sequences, as well as how to use

these stochastic analysis approaches in bioinformatics. Of course, there are

many problems still to be solved before these models can become useful in

practice.

In the model E

∗

of (2.102), we still regard

ξ as a stochastic sequence and

let

∗





∗



,τ=1, 2, 3, 4,τ



=1, 3



(2.109)

64 2 Stochastic Models of Mutations and Structural Analysis

be the stochastic model of E

∗

.IfT is a ﬁxed sample

T =



˜z





,τ=1, 2, 3, 4,τ



=1, 3



(2.110)

then E



= {

ξ,T} is a hybrid model of the four types of mutations. We refer to



= {

ξ,T} as the semistochastic model of mutated sequences. We will discuss

the structure and analysis of hybrid mutations T in the following chapters.

2.6 Exercises

Exercise 6. Explain the diﬀerences between the following terms: i.i.d. se-

quences, Bernoulli process, Poisson process, geometric distribution sequence,

additive sequence, Markov process, and renewal process. Explain the advan-

tages and disadvantages of using each of the above to describe biological se-

quences.

Exercise 7. Try to extend the application of the Bernoulli process and Pois-

son process to the case of nonhomogeneous sequences, and use it to describe

the model of type-III mutated sequences.

Exercise 8. List some of the important laws of large number and central limit

theorems in probability theory, and give examples showing how they apply to

biological sequences.

Exercise 9. Prove the following propositions:

1. Properties 1, 2, and 3 of the renewal process given in Sects. 2.2.1–2.2.3

2. Theorems 5 and 7.

3. Formulas (2.82), (2.86) (2.100), (2.101), and (2.102).

Exercise 10. For the stochastic sequences in model (2.103), perform a simu-

lation according to the following cases:

1. The range of the sequence lengths is 1 kbp–1 Mbp (i.e., n =1× 10

1 × 10

, 1 × 10

, 5 × 10

, 1 × 10

, etc.); the range of 

is 0.01–0.4 (i.e.,



=0.01, 0.02, 0.05, 0.1, 0.2, 0.3, 0.4, etc.); the range of 

,

is 0.01–0.1

(i.e., 0.01, 0.02, ···, 0.1 etc.); and the range of p

–p

is 0.1–0.5 (i.e., 0.1,

0.2, 0.3, 0.4, 0.5, etc.).

2. For the sequence

ξ in (2.103), construct the i.i.d. sequence deﬁned on V

which obeys uniform distribution.

3. Create the stochastic sequences of model (2.103) according to the param-

eters given in case 1.

Exercise 11. Based on the simulation results from Exercise 10, align the mu-

tated sequences using the dynamic programming-based algorithm, and com-

pare the time taken by the CPU with the parameters listed as follows:

2.6 Exercises 65

1. For the parameter 

–

, p

–p

, ﬁnd the relationship between the length

of the sequences and the time taken by the CPU, where the length ranges

from 1 × 10

to 1 × 10

2. For a sequence of ﬁxed length (such as 1 ×10

), compare the average error

of the model (2.103) deﬁned in (2.108) with the time taken by the CPU.

Hint

The simulation of the stochastic sequence and mutated sequences is achieved

through the generation of a sequence of random numbers.

Modulus Structure Theory

In Chap. 2, we presented the stochastic model of mutated sequences. If sam-

ples of a stochastic model are available, then we should be able to estimate

its characteristics. To do this, we introduce a new concept called modulus

structure, which is a powerful tool for describing the characteristics of these

stochastic models. The modulus structure may be determined in many ways,

and we will introduce three of these: by expanding or compressing a sequence

onto a new sequence; by sequence alignment, and by sequence mutation. The

usefulness of modulus structure will become clear after we have discussed

these methods. Alternate concepts, such as modulus structure and mode, will

also be involved.

3.1 Modulus Structure of Expanded and Compressed

Sequences

Expansion and compression are frequent occurrences in mutated sequences

and in aligned sequences. They have been deﬁned in Sect. 1.1, and here we

give a more detailed description and discussion of their structures.

3.1.1 The Modulus Structures of Expanded Sequences

and Compressed Sequences

Deﬁnitions of Expansion and Compression

Let A and C be two sequences on V

as deﬁned in (1.1), and let N

{1, 2, ··· ,n

}, N

= {1, 2, ··· ,n

} be the sets of the positions of sequences A

and C, respectively. We begin with the deﬁnitions of expansion and compres-

sion as follows:

Deﬁnition 10. 1. If A is a subsequence of C,thenC is an expansion of A.

Conversely, A is a compression of C.IfA is a real subsequence of C,the