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

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

1.6 Exercises, Analyses, and Computation 27

1.6 Exercises, Analyses, and Computation

Exercise 1. For the RNA sequences E.co and B.st given in Table 4.5, use

the dynamic programming-based algorithm to compute their minimal penalty

alignment based on the Hamming penalty matrix.

Exercise 2. For the RNA sequences Mc. vanniel and Mb. tautotr given in

Table 4.5, use the dynamic programming-based algorithm to determine the

optimal alignment sequences based on the following requirements:

1. Compute the minimal penalty alignment based on the Hamming penalty

matrix and the WT-penalty matrix, respectively.

2. If d

(a, b), a, b ∈ V

is the Hamming penalty matrix, then g

(a, b)=

1 − d

(a, b), a, b ∈ V

is the corresponding scoring matrix. Compute the

maximal score alignment.

3. Compare the computational results of the minimal penalty alignment and

the maximal score alignment.

Exercise 3. Continuing from Exercise 2, for RNA sequences Mc. vanniel and

Mb.tautotr, compute the optimal alignment by using the dynamic program-

ming-based algorithm, based on the three criteria of the Hamming penalty

matrix, the WT-penalty matrix and the Hamming scoring matrix, respec-

tively. Compare the corresponding results.

Exercise 4. For an arbitrary pair of sequences with diﬀerent lengths, com-

pute the optimal alignment using the dynamic programming-based algorithm,

based on the penalty matrix and the scoring matrix, respectively.

Exercise 5. Test your dynamic programming-based algorithm for the optimal

pairwise alignment according to the following indices:

1. For data with length 1 kbp, such as the sequences Mc.vanniel and

Mb.tautotr given in Table 4.5, visually check whether they arrive at the

target.

2. For data with length 1–100 kbp (such as sequences 1–10 given in Table

4.4), use your dynamic programming-based algorithm to test the relation-

ship between the length of the sequence and the CPU time required for

computation.

3. Analyze the relationship between similarity and the CPU time required

for computation.

Hint

1. Data for the two sequences Mc.vanniel and Mb.tautotr given in Table 4.5

may be downloaded from the Web site [99].

28 1 Introduction

2. The dynamic programming algorithm for the optimal alignment of se-

quence pairs should be done following Sect. 1.3. If this proves too diﬃ-

cult, the algorithm from our Web site [99] may be downloaded, and your

program may be based on it.

Stochastic Models of Mutations

and Structural Analysis

The mathematical methods used to study mutation and alignment fall mainly

into three groups – stochastic analysis, modulus structure and combinational

graph theory. In this chapter we introduce stochastic analysis and show how

this theory is used to understand the characteristics of biological structures.

Stochastic analysis of mutations includes three aspects: the randomness of

sequence structure, the randomness with which mutation ﬂows happen, and

the randomness with which each type of mutation occurs.

2.1 Stoc hastic Sequences and Independent

Sequence Pairs

At ﬁrst glance, a DNA sequence may seem disorderly and unsystematic, and

the nucleotides at each position (or a group of positions) are not ﬁxed. That

is to say that a biological sequence is a stochastic sequence. Statistically, we

may ﬁnd that the frequency of observing small molecules or segments changes

based on a diﬀerent benchmark dataset of biological sequences. Therefore, we

may use stochastic models to describe biological sequences.

2.1.1 Deﬁnitions and Notations of Stochastic Sequences

Random Vectors, Stochastic Sequences, and Stochastic Processes

Random variables, random vectors, stochastic sequences and stochastic pro-

cesses are the fundamental concepts of probability theory and stochastic pro-

cesses theory. For convenience, we brieﬂy summarize their deﬁnitions, nota-

tions, and properties as follows.

ξ =(ξ

,ξ

, ··· ,ξ

) , ˜η =(η

,η

, ··· ,η

) (2.1)

∗



∗

, ··· ,a

∗



∗



∗

, ··· ,b

∗



30 2 Stochastic Models of Mutations and Structural Analysis

denote stochastic sequences, in which ξ

,η

or a

∗

are random variables

whose range is the integral set V

,andn

are the lengths of the

corresponding sequences. In this book, these two kinds of symbols will be

used interchangeably.

In (2.1), N

= {1, 2, ··· ,n

},N

= {1, 2, ··· ,n

} are sets of subscripts or

positions of sequences

ξ and ˜η, respectively. If n

are large, we consider

= N

= {1, 2, 3, ···}to be the set of all natural numbers. Then

ξ and ˜η

given in (2.1) are considered to be inﬁnite stochastic sequences and we rewrite

them as follows:

ξ =(ξ

,ξ

, ···) , ˜η =(η

,η

, ···) . (2.2)

Biological sequences are generally very long. Thus, the symbols deﬁned in

(2.1) and (2.2) are frequently considered to be equivalent. In addition to the

stochastic sequence notation of

ξ in (2.2), we use the symbols {ξ

,ξ

, ···},

and therefore the sequence

ξ can be regarded as an ordered set.

Frequently, the DNA sequence to be processed is very long, e.g., the length

of the human genome is 3.2×10

bp. The sequence

ξ can then be regarded as an

isochronously sampled sequence drawn from a continuous stochastic process

with the same identiﬁed distribution. Therefore, the mother stochastic process

ξ is denoted by

ξ = {ξ

,t∈ (0, ∞)} . (2.3)

If ξ

is a component of the sequence in (2.2), then the corresponding random

variable in (2.3) is ξ

= ξ

i/n

. In this book, we will use (2.1)–(2.3) inter-

changeably. We can consider the other related notations in a similar fashion,

and hence we do not repeat them here.

The Family of Probability Distributions of a Stochastic Process

The structural characteristics of a stochastic sequence are determined by its

family of probability distributions. For an arbitrary k, ξ

(k)

=(ξ

,ξ

, ··· ,ξ

)

is a random vector that is a segment of

ξ. For any given vector

(k)

=(a

, ··· ,a

),a

∈ V

, the probability of ξ

(k)

= a

(k)

is deﬁned as:

(k)

)=P

{ξ

(k)

= a

(k)

}. We denote the probability of ξ

(k)



(k)



(k)



: a

(k)

∈ V

(k)



(2.4)

in which V

(k)

is the set of a

(k)

. Following from probability theory, we have

(k)

) ≥ 0 for all a

(k)

∈ V

(k)

and



(k)

∈V

(k)

)=1.

As k =1, 2, 3, ··· is changing, we can obtain the probability distribution

family

= {P

(k)

,k =1, 2, 3, ···} (2.5)

which is referred to as the probability distribution family determined by the

stochastic sequence

ξ.

2.1 Stochastic Sequences and Independent Sequence Pairs 31

It is a necessary condition that the probabilities within the probability

distribution family determined by a stochastic sequence must satisfy compati-

bility. That is, the probability distribution P

(k)

is a marginal distribution



)

for any positive integer k



>k.Itisequivalentto

(k)



(k)







−k)

∈V



−k)



)



(k)



−k)



, (2.6)

for all a

(k)

∈ V

(k)

,inwhich(a

(k)



−k)

)=a



)

∈ V



Based on the famous Kolmogorov theorem, we may construct a stochastic

sequence derived from given probability distributions P, with compatibility

conditions. Moreover, we can build diﬀerent kinds of stochastic sequences or

stochastic processes using this Kolmogorov theorem. The most typical stochas-

tic sequences or stochastic processes are: independently and identically dis-

tributed (i.i.d.) sequences, Markovian sequences, Poisson processes and re-

newal processes. In this book, we begin by discussing i.i.d. sequences. A DNA

sequence is frequently approximated as an i.i.d. sequence, if the sequence is

suﬃciently long.

2.1.2 Independently and Identically Distributed Sequences

Deﬁnition of i.i.d Sequences

Let

ξ be a stochastic sequence. Then

ξ is referred to as:

1. An independent sequence if the probability distribution of the stochastic

vector ξ

(k)

satisﬁes

(k)



(k)



= P



(k)

= a

(k)





i=1

) , (2.7)

where p

(a)=P

{ξ

= a}.

2. An identically distributed sequence if p

(a)=p(a),a∈ V

is the same for

all k.

3. An i.i.d. sequence if it is both an independent sequence and an identically

distributed sequence, in which p(a)=P

{ξ

= a} is the probability dis-

tribution of ξ

. For independently and identically distributed sequences,

(2.7) becomes



(k)



= P



(k)

= a

(k)





i=1

p(a

) , (2.8)

and p(a), a ∈ V

is called the generation distribution of

ξ.Ifp(a)=1/q

for all a ∈ V

,thenp(a), a ∈ V

is a uniform distribution.

32 2 Stochastic Models of Mutations and Structural Analysis

Deﬁnition 5. If

ξ is an i.i.d. sequence and its generating distribution p(a) is

a uniform distribution, then

ξ is referred to as a perfectly stochastic sequence.

Therefore, a stochastic sequence

ξ is a perfectly stochastic sequence if and

only if p

(k)

holds for all k =1, 2, 3, ···,anda

(k)

∈ V

(k)

Penalty Functions

For a given penalty matrix W = w(a, b), a, b ∈ V

deﬁned in (1.5), we deﬁne

two indices for this matrix as follows:

⎧

⎪

⎨

⎪

⎩



a∈V

w(a, a) ,



a,b∈V

w(a, b) .

(2.9)

Deﬁnition 6. A penalty matrix W is called strongly symmetric if w(a, b)=

w(b, a),andw(a, a)=0holds for any a, b ∈ V

, if every row is the permutation

of another row, and if each column is the permutation of another column.

Obviously, the Hamming matrix and the WT-matrix are both strongly sym-

metric, with average penalties deﬁned as follows:



)=(0, 3/4) , if W is the Hamming matrix ,

)=(0, 0.4975) , if W is the WT-matrix .

(2.10)

Theorem 1. If the penalty matrix W is strongly symmetric, then w

=0and

{w(a, ζ)=c} = ρ(c) for any uniformly random variable ζ deﬁned on V

Proof. w

= 0 follows directly because the matrix W is strongly symmetric.

To prove that P

{w(a, ζ)=c} = ρ(c), we consider the number of elements of

a,c

= {b ∈ V

: w(a, b)=c} .

It is invariant for diﬀerent a due to symmetry. Consequently,

{w(a, ζ)=c} =

 D

a,c



is constant if ζ is a uniform distribution on V

Locally Random Correlation Functions

Let

ξ, ˜η be two stochastic sequences and let

(n)

=(ξ

i+1

,ξ

i+2

, ··· ,ξ

i+n

) ,η

(n)

=(η

j+1

,η

j+2

, ··· ,η

j+n

) .

2.1 Stochastic Sequences and Independent Sequence Pairs 33

be their local vectors. Their local correlation function is then deﬁned as fol-

lows:



ξ;˜η; i, j; n



= w



(n)

,ξ

(n)





k=1

w (ξ

i+k

,ξ

j+k

) . (2.11)

Since this w(

ξ, ˜η; i, j; n) is a random variable, it is called the locally random

correlation function. Speciﬁcally, it is known as the locally random autocor-

relation function if

ξ =˜η.

ξ is a perfectly stochastic sequence, then its locally random autocorre-

lation function satisﬁes:

E{w(

ξ; i, j; n)} = E{w(ξ

,ξ

)} =



, if i = j,

, otherwise .

(2.12)

Equation (2.12) is implied by the deﬁnitions of perfect sequences and

penalty functions, so we omit the proof. An important characteristic of a per-

fect sequence is that expressed by (2.12).

2.1.3 Independent Stochastic Sequence Pairs

Since independent stochastic sequence pairs are deﬁned with respect to both

mutation and the structural analysis of alignment, we will discuss them in

more detail here.

Deﬁnition 7. Let

ξ =(ξ

,ξ

, ··· ,ξ

), ˜η =(η

,η

, ··· ,η

) be two sequences

deﬁned on V

. These are referred to as independent stochastic sequence pairs,

if the following conditions are satisﬁed:

ξ and ˜η are two perfectly stochastic sequences.

2. {(ξ

,η

), (ξ

,η

), (ξ

,η

), ···}is an i.i.d. two-dimensional sequence.

3. There is a ﬁxed >0 such that for every pair (ξ

,η

), the joint probability

distribution satisﬁes the following:

{ξ

= η

} = , or P

{ξ

= η

} =1− . (2.13)

If the two sequences are both mutated sequences resulting from type-I muta-

tion, then (˜η,

ξ) is an independent sequence pair. Speciﬁcally, if  =0,then˜η

and

ξ are two identical sequences, and (˜η,

ξ) is an independent sequence pair.

The following are basic characteristics of independent sequence pairs, and are

deﬁned in the context of structure analysis.

Theorem 2. If (

ξ, ˜η) is an independent sequence pair and w(a, b) is a function

deﬁned on V

which satisﬁes the strong symmetry condition, then

= w(ξ

i+k

,η

j+k

) ,k=0, 1, 2, ··· (2.14)

is an i.i.d. sequence for all i, j ≥ 0.

34 2 Stochastic Models of Mutations and Structural Analysis

Proof. If i = j, the proof can be deduced from condition 2 of Deﬁnition 3 and

the characteristic of independent random variables (a function of an indepen-

dent random variable is itself an independent random variable).

Here we discuss the special condition of i = j.

We begin with the probability distribution ζ

= w(ξ

i+k

,η

j+k

). Let

(z)=P

{ζ

= z} = P

{w(ξ

i+k

,η

j+k

)=z}



a∈V

{ξ

i+k

= a}P

{w(ξ

i+k

,η

j+k

)=z|ξ

i+k

= a}



a∈V

{w(a, η

j+k

)=z} =



a∈V

ρ(z)=ρ(z) . (2.15)

The fourth equation is deduced from the strongly symmetric character of

w(a, b) and Theorem 1. The third equation is deduced by i = j and ξ

i+k

independent of η

j+k

. Consequently, the probability distribution of ζ

does not

depend on k.

Now, we prove the independence of the sequence

= w(ξ

i+k

,η

j+k

) ,

where k =0, 1, 2, ···. To do this, we calculate the probability distribution

ζ =(ζ

,ζ

, ··· ,ζ

). For simplicity, we only discuss the situation where

i =1,j =2,n=4,sothat

= w(ξ

,η

) ,ζ

= w(ξ

,η

) ,ζ

= w(ξ

,η

) ,ζ

= w(ξ

,η

) .

Note that the random variables ξ

, {ξ

,ξ

,η

},η

are independent.

We denote

p(¯z)=P

{

ζ =¯z} = P

{¯w

∗

=¯z} ,

in which ¯w

∗

=(w

∗

)andw

∗

= w(ξ

,η

j+1

),j =1, 2, 3, 4. If we

denote

ξ =(ξ

,ξ

) , ¯η =(η

,η

) ,

d =(a, b, c) ∈ V

then

p(¯z)=



d∈Z

{

ξ =

d}P

{¯w

∗

=¯z|

ξ =

d} =



d∈Z

{¯w

∗

=¯z|

ξ =



d∈Z

{w(ξ

,η

)=z

,w(a, η

)=z

,w(b, η

)=z

,w(c, η

)=z

ξ =



c∈V



b∈V



a∈V

{w(ξ

,η

)=z

|ξ

= a}P

{w(a, η

)=z

|ξ

= b}

{w(b, η

)=z

|ξ

= c}P

{w(c, η

)=z

}] . (2.16)

2.1 Stochastic Sequences and Independent Sequence Pairs 35

In (2.16), the last equation is obtained from the independence of η

and

(ξ

,ξ

). The strong symmetry of the w(a, b) function turns (2.16) into

p(¯z)=

ρ(z

)



d∈Z



{w(ξ

,η

)=z

,w(a, η

)=z

,w(b, η

)=z

ξ =



ρ(z

)



¯a,b∈V



{w(ξ

,η

)=z

,w(a, η

)=z

w(b, η

)=z

|ξ

= a, ξ

= b}



ρ(z

)



¯a,b∈V



{w(ξ

,η

)=z

,w(a, η

)=z

|ξ

= a, ξ

= b}

{w(b, η

)=z

}



iii

ρ(z

)



¯a,b∈V

{w(ξ

,η

)=z

,w(a, η

)=z

|ξ

= a, ξ

= b}

ρ(z

)



¯a∈V

{w(ξ

,η

)=z

,w(a, η

)=z

|ξ

= a}

ρ(z

)



¯a∈V

{w(ξ

,η

)=z

|ξ

= a}p

{w(a, η

)=z

}

ρ(z

)



¯a∈V

{w(ξ

,η

)=z

|ξ

= a}

vii

= ρ

ρ(z

{w(ξ

,η

)=z

}

viii

= ρ

ρ(z

) (2.17)

in which equations i, iv, vii are obtained using the relationship of joint prob-

ability distribution and marginal distribution respectively; equations ii, v are

obtained from the independence of η

,η

and (ξ

,ξ

),ξ

; and equations iii, iv,

viii are obtained from

{w(ξ

,η

τ +1

= z

} = ρ(z

) ,τ=3, 2, 1 .

Consequently, p(¯z)=ρ(z

) ·ρ(z

) holds. Since the joint prob-

ability distribution of

ζ =(ζ

,ζ

, ··· ,ζ

) is the product of the marginal dis-

tributions of ζ

,ζ

, ··· ,ζ

, it implies that

ζ is an i.i.d. sequence. The theorem

is thus proved.

From the proof of this theorem, we may ﬁnd that independent stochastic

sequence pairs can be broadened. Typically, under the conditions of Deﬁni-

tion 3, if requirement 1 were deleted, the conclusion of Theorem 2 holds as

well.

36 2 Stochastic Models of Mutations and Structural Analysis

2.1.4 Local Penalty Function and Limit Properties

of 2-Dimensional Stochastic Sequences

Based on Theorem 2, we can give the local penalty function and the limit

properties of two-dimensional stochastic sequences.

Deﬁnition 8. For a two-dimensional stochastic sequence (

ξ, ˜η) and a ﬁxed

penalty function w(a, b), we deﬁne the local penalty function by

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

, ¯η

n−1



k=0

w(ξ

i+k

,η

j+k

) . (2.18)

It is the average of the penalty of local vectors ξ

[i,i+n−1]

and η

[j,j+n−1]

,andis

simply referred to as the local penalty function.

Lemma 1. If (

ξ, ˜η) is a double independent stochastic sequence, then the local

penalty function is

= E{w(

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



, if i = j,

, otherwise ,

(2.19)

in which

⎧

⎪

⎨

⎪

⎩

= E{w(ξ

,η

)} =



a,b∈V

w(a, b)p

,η

(a, b) ,

= E{w(ξ

,η

)} =



a,b∈V

w(a, b) .

(2.20)

If w(a, b)=d

(a, b) is the Hamming function, then μ

= , μ

=3/4.

Theorem 3. If (

ξ, ˜η) is an independent stochastic sequence pair and the

penalty function w(a, b) is strongly symmetric, then the following limit the-

orems hold.

1. As n →∞, following from the law of large numbers, we have the limit

formula as follows:



ξ, ˜η, i, j,n



−→ μ

, a.e., (2.21)

in which μ

is given in (2.19) and a.e. is the abbreviation of almost ev-

erywhere convergence.

2. Central limit theorem: If n is large enough, then

√

nσ

n−1



k=0

[w(ξ

i+k

,η

j+k

) −μ

] ∼ N (0, 1) , (2.22)