Accardi L., Freudenberg W., Obya M. (Eds.) Quantum Bio-informatics IV: From Quantum Information to Bio-informatics

130

the

performance evaluation

of

our

algorithm

against

other

six alignment

methods.

2. A

new

measure

taking

entangled

effects

of

two

consecutive

pairs

in

residues

First,

let us establish some notations.

Let

[2

be

the

set

of

all

amino

acids,

and

[2*

be

the

[2

with

the

indel (gap) "*":

[2*

==

[2

u {*}. Let

[[2*]

be

the

set

of

all sequences of

the

elements

in

[2*.

We call

an

element

of

[2

a residue

and

an

element of

[2*

a symbol.

In

addition, let f

==

[2

x

[2

be

the

direct

product

of

two

[2s

and

f*

==

[2*

x

[2*.

Consider two

arranged

sequences, A = ala2 ·

··

an

and

B = b

l

b

2

·

..

b

n

,

both

of

length

n, where ai, b

j

E[2*

. We also

denote

the

sequences by

UI

U2···

Un,

where

Ui

= (ai, b

i

)

E

f*,

and

we call

Ui

a site in

the

following

discussion.

In

general,

the

relative likelihood

that

the

sequences

are

to

being

unrelated

is known as

the

"odds

ratio":

p(A;B)

R(A,B)

=

p(A)p(B)

p(al,a2,···

,a

n

;b

l

,b

2

,···

,b

n

)

p (aI,

a2,···

,an)

p

(b

l

,

b

2

,···

,b

n

)"

(1)

Here, p

(a)

is

the

occurrence probability

of

the

given segment

and

p

(a;

b)

is

the

joint probability

that

the

two segments occur.

In

order

to

arrive

at

an

additive scoring system,

Equation

(1) is typically simplified by as-

suming

that

the

substitutions

are

independent

of

th

e location

and

there

is no intersite correlations; namely, p (A) =

TIp

(a),

p (B) =

TIp

(b)

and

p (A, B) =

TIp

(a,

b).

Thus

the

logarithm

of

Equation

(1), known as

the

log-odds ratio, is now a

sum

of

independent

parts:

where

p

(a;

b)

s

(a,

b)

= log p

(a)

p

(b)

(2)

(3)

is

the

log likelihood

ratio

of

the

symbol

pair

(a

,

b)

occurring as

an

aligned

pair

to

that

occurring as

an

unaligned pair.

The

s

(a,

b)

is called a score

and

S =

(s

(a,

b))

is called a

substitution

matrix.

These

quantities

(Equation

(2)

and

(3))

are

used

to

define a

measure

for pairwise sequence alignment

5.

Here,

we

define a normalized

substitution

matrix

(i.e., every element

in

S takes

the

value between 0

and

1)

and

define a difference

of

A

and

B.

131

Let

fs :

[8

m

in,8

max

l

f--+

R

be

a

normalizing

function:

(

8max

- X

fs x)

==

,

0::;

fs (x)

::;

1,

Smax

-

Bmin

(4)

where

8

max

==

max

{max{s

(un,

gap

cost},

(5)

uEr

8

m

in

==

min{min{S(u

n

,

gap

cost}.

(6)

uEr

Let

put

s

(a,

b)

==

f

(8

(a,

b))

for

a,

b E

O.

This

s

(a,

b)

is a

normalized

ex-

pression

of

the

score 8

(a,

b).

By

using

this

quantity,

we define a

normalized

substitution

matrix

as

M =

(s

(a,

b)).

Then

a difference

of

A

and

B is

defined

by

(7)

When

the

sequence A is

equal

to

B

the

difference

dsub

(A,

B)

has

a

minimum

value

O.

One

of

the

essential

assumption

for

the

above

approach

(using a

sum

of

independent

parts

as

a difference

of

A

and

B)

was

the

induction

of

the

occurring

probability.

We

could

take

more

informative

approach

by

includ-

ing

the

intersite

correlations.

Crooks

et

al.

tried

one

of

such

an

approach

6.

They

introduced

a

measure

for

two

sequences

based

on

a

multivariate

probability

approximated

by

using

the

intersite

relative

likelihood.

But,

they

concluded

that

their

approach

is

statistically

indistinguishable

from

the

standard

algorithm.

We feel

that

their

measure

(equation

(4)

in

their

paper)

is different from ours. To

introduce

their

measure,

they

defined a

type

of

joint

probability. However

it

can

not

be

a probability,

because

their

quantity

is

the

multiplication

of

likelihood

"ratios",

so

it

goes

beyond

more

than

1.

Moreover, we

think

that

the

intersite

relative likelihood

may

not

describe

the

difference

of

sequence A

and

B.

Under

an

assumption

that

each

site

of

the

sequences

has

Markov

property,

we

propose

a

new

measure

for two sequences

by

adding

a

transition

effect

and

its

weight E

(a

degree

of

mixture):

Rour

(A,

B)

= R (A,

B)l-c

R

t

(A,

Bt

,

(8)

where

n-l

Rt(A,

B)

==

II

P (Ui+1 \

Ui).

(9)

i=l

132

Here we introduce a normalized

transition

i

(Ui'

UH1) called "Transition

Quantity",

in order

to

simplify

the

equation. Let i

(Ui'

uHd

be

a normal-

ized

transition

defined as

i

(Ui'

uHd

==

it (t

(Ui'

uHd

;

Ui)

,

t

(Ui'

Ui+l)

==

logp

(Ui+l \

Ui)

,

where

it (x;

u)

is

a normalizing function:

{

-x

if

x>

0

it

(x;

u)

= maxvEr*

{-t

(u,

v)}'

1,

otherwise

(10)

(11)

(12)

By

using

the

above quantity, a difference of A

and

B representing

the

"intersite transition"

is

defined as

n-1

dtrans (A,

B)

= L i

(Ui'

Ui+l) .

(13)

i=l

Consequently, we define a difference measure for two sequences by combi-

nation

of two differences d

sub

and

dtrans:

dMTRAP

(A,

B)

= (1 - c) d

sub

(A,

B)

+ cdtrans (A,

B).

(14)

The

mathematical

details

can

be

found in

the

paper

4.

3.

Evaluation

We compared

the

performance of

MTRAP

to

those of

the

most often used

six methods: ClustalW2,

MAFFT,

TCoffee, DIALIGN, MUSCLE

and

Probcons.

The

details of these nine

methods

are: (1) ClustalW2 7,

8,

a

typical progressive multiple alignment method; (2)

MAFFT

ver. 6

9,

a

fast

method

with

Fourier

transform

algorithm; (3) TCoffee ver. 5.31

10,

a

heuristic consistency-based

method

that

combines global

and

local align-

ments; (4) DIALIGN ver. 2.2

11

,

a

method with

segment-segment approach;

(5)

MUSCLE ver. 3.7

12,

a

method with

Log-Expectation algorithm

and

(6) Probcons ver. 1.12

13,

a probabilistic consistency-based method. These

programs

without

MAFFT

used

their

default

parameters

and

MAFFT

used

"L-IN-i"

strategy

mode.

To measure

the

accuracy of each

method,

we used

three

different

data-

bases:

HOMSTRAD

(version November

1,

2008)

14,15,

PREFAB

4.0 12

and

BAliBASE 3.0

16.

These are

the

databases

of

structure-based

alignments

133

for homologous families. We used

the

all 630 pairwise alignments

obtained

from

the

HOMSTRAD

for pairwise alignment

tests

,

and

used

the

all 1031

multiple alignments

obtain

ed from

this

database

for multiple alignment

tests. We also used

the

all 1682

protein

pairs

obtain

ed from

the

PREFAB

4.0 for pairwise alignment tests.

The

BAliBASE 3.0 contains 5 different

reference sets

of

alignment for

testing

multiple sequence alignment

meth-

ods. We used

the

BBS

sets

included in

the

references 1,2,3

and

5.

The

BBS

sets

are

described as being

trimmed

to

homologous regions.

In

order

to

avoid using

the

same

dataset

for

training

and

test,

We es-

timated

the

transition

quantity

by using

the

superfamilies

subset

from

the

dataset

SABmark

, which is described in

the

section

"Estimation

of

the

Transition

Quantity

". We also used

this

dataset

for optimizing

th

e

para-

meters

Alignment accuracy was calculated

with

the

Q (quality) score

12.

The

Q

score is defined as

the

ratio

of

the

numb

er

of

correctly aligned residue pairs

in

the

test

alignment (i.e.,

the

alignment

obtained

by a specified

algorithm

such as

MTRAP,

Needle, etc.)

to

the

total

number

of aligned residue pairs

in

the

reference alignment.

When

all pairs

are

correctly aligned,

the

score

have a

maximum

value

1,

and

when no-pairs

are

aligned

the

score have a

minimum

value

o.

This

score has previously been called

the

SPS

(Sum

of

Pairs

Score)

17

or

the

developer score

18.

Let

us redefined

this

score

in

our

notations. Let

Ai

(i =

1,

...

,

N)

indicates

the

ith

sequence

of

the

reference

alignment

with

length

L,

and

let

aik

E [2* indicates

the

kth

symbol in

the

sequence A i .

When

aik

=I-

*,

it

is

important

to

find

the

number

of

the

site

in

the

test

sequence corresponding

to

the

symbol

aik,

whose

numbers

are

denoted

by

nik.

When

aik

=

*,

put

n i k = 0 (i = 1,

···

,

N).

Th

en

the

Q

score is given as

4.

Results

N-l

N L

L L L

L:l.a

i

k,aJk8nik

,n j k

i=1

j=i+l

k=1

Q score =

--:'N=----I--:-N=------::-L-----

L L L

L:l.aik

,aj k

i=l

j=i

+ l k= l

L:l.

x

=

{I,

x

=I-

*

and

y

=I-

* .

,Y

0,

x = *

or

y = *

We

compared

MTRAP

with

six different alignment

methods

by

using all

1682

prot

ein pairs of

PREFAB

4.0

and

all 630

protein

pairs

of

HOM-

STRAD.

We used

GONNET250

matrix

with

the

MTRAP.

The

similar-

134

ity

between

the

test

alignment (sequence alignment by each

method)

and

the

reference alignment

(obtained

from

PREFAB

4.0

or

HOMSTRAD)

was

measured

with

the

Q score. Suppose as usual

that

the

reference alignment

is

the

optimal

alignment,

the

results

of

PREFAB

4.0 (Table

1)

and

those of

HOMSTRAD

(Table 2) indicate

that

our

method

works well

compared

with

other

methods.

Our

method

achieves

the

highest

ranking

compared

with

all

other

methods

except only one range 30-45%. Especially for

the

identity

range 0-15%,

MTRAP

is 4

cv

5%

accurate

than

the

2nd

ranking

method.

For

the

identity

range 30-45%

of

HOMSTRAD,

Probcons

performs slightly

better

(cv

1 %).

Table

1.

Average

Q

scores

on

the

PREFAB

4.0

database

Method

PREFAB

4.0

0-15%(212)

15-30%(458)

30-45%(74)

All(1682)

CPU

MTRApa

0.248

0.674 0.877

0.615

120

MAFFT

0.170 0.671

0.860 0.568 200

DIALIGNb

0.133

0.556 0.814 0.518

100

MUSCLE

0.205 0.632

0.867

0.581

35

ClustalW2

0.199 0.644

0.859 0.586

70

Probcons

0.204 0.647 0.875

0.590 120

TCoffee

0.198 0.642 0.872 0.585 180

Note:

The

average

Q

scores

of

four

testing

datasets

with

different

identity

ranges

on

PREFAB

4.0

are

shown.

The

number

in

parentheses

denotes

the

number

of

alignments

in

each

sequence

identity

range.

For

each

sequence

identity

range,

the

best

scores

are

in

bold.

CPU

is

the

total

computing

time

for

all

alignments

in

seconds.

aMTRAP

uses

GONNET250

substitution

matrix.

bDIALIGN

reported

critical

errors

for

some

testing

data.

Therefore,

the

scores

of

DIALIGN

were

calculated

by

the

partial

testing

data.

Table

2.

Average

Q scores

on

the

HOMSTRAD

database

(Pairwise

only)

Method

HOMSTRAD

(Pairwise

only)

0-15%(25)

15-30% (207)

30-45%(173)

All(630)

CPU

MTRApa

0.412

0.659

0.879

0.819

45

MAFFT

0.309 0.610 0.863 0.796

60

DIALIGN

b

0.216 0.546 0.825

0.760

35

MUSCLE

0.337

0.625 0.868 0.802 15

ClustalW2

0.313 0.619 0.867 0.800 25

Probcons

0.344

0.650

0.884

0.816

50

TCoffee

0.341 0.634 0.872 0.809 70

Note:

The

average

Q

scores

offour

testing

datasets

with

different

identity

ranges

on

HOMSTRAD

are

shown.

The

notations

are

the

same

as

Table

1.

135

5.

Conclusion

We

indicated

that

the

alignment

implementing

our

new

measure,

intro-

ducing

entangled

effects of two consecutive

pairs

in

residues, leads

to

a

significant increase in

alignment

accuracy

to

other

six

methods,

and

this

is

especially

apparent

in

low

identity

range.

We will

apply

our

new

technique

to

several

methods

studying

life from

sequences,

such

as

multiple

alignment,

motif

finding

and

phylogenetic

analysis,

where

it

is considered

that

the

residue

substitutions

in

a sequence

are

independent

of

the

location.

References

1.

T.

Hara,

K.

Sato

and

M. Ohya, QP-PQ:

Quantum

Probability and White

Noise Analysis

(Quantum

Bio-Informatics

III)

26,

443 (2010).

2.

C. B. Anfinsen, Science

181,

223(Jul

1973).

3. G.

Gonnet,

M.

Cohen

and

S.

Benner,

Biochemical and Biophysical Research

Communications

199,

489 (1994).

4.

T.

Hara,

K.

Sato

and

M. Ohya,

BMC

Bioinformatics

11,

p. 235 (2010).

5.

S.

Altschul,

1.

Mol. Bioi.

219,

555 (1991).

6. G.

Crooks, R.

Green

and

S.

Brenner,

Bioinformatics

21,

p. 3704 (2005).

7.

J.

D.

Thompson,

D. G. Higgins

and

T.

J.

Gibson, Nucleic Acids Res. 22,

4673(Nov 1994).

8. M. A. Larkin, G. Blackshields, N.

P. Brown, R.

Chenna,

P. A.

McGetti-

gan, H. McWilliam,

F.

Valentin,

1.

M. Wallace, A.

Wilm,

R. Lopez,

J.

D.

Thompson,

T.

J.

Gibson

and

D. G. Higgins, Bioinformatics

23,

2947(Nov

2007).

9.

K.

Katoh,

K. Misawa, K.

Kuma

and

T.

Miyata,

Nucleic Acids Res.

30,

3059(Ju12002).

10. C.

Notredame,

D. G. Higgins

and

J.

Heringa,

1.

Mol. Bioi.

302,

205(Sep

2000).

11. B.

Morgenstern,

Bioinformatics

15,

211(Mar

1999).

12. R.

C.

Edgar,

Nucleic Acids Res.

32,

1792 (2004).

13. C. Do, M.

Mahabhashyam,

M.

Brudno

and

S.

Batzoglou, Genome Research

15,

p. 330 (2005).

14.

K.

Mizuguchi, C. M. Deane,

T.

L. Blundell

and

J.

P.

Overington,

Protein

Sci. 7, 2469(Nov 1998).

15. L.

Stebbings

and

K. Mizuguchi, Nucleic acids research

32,

p. D203 (2004).

16.

J.

D.

Thompson,

P. Koehl, R.

Ripp

and

O. Poch, Proteins

61,

127(Oct

2005).

17.

J.

Thompson,

F.

Plewniak

and

O. Poch, Nucleic Acids Res

27,2682

(1999).

18.

J.

Sauder,

J.

Arthur

and

R.

Dunbrack

Jr,

Proteins Structure Function and

Genetics

40,

6 (2000).

This page intentionally left blankThis page intentionally left blank

Quantum

Bio-Informatics

IV

eds. L.

Accardi,

W. Freudenberg

and

M.

Ohya

World

Scientific

Publishing

Co.

(pp.

137-143)

THE

PASSAGE

FROM

DIGITAL

TO

ANALOGUE

IN

WHITE

NOISE

ANALYSIS

AND

APPLICATIONS

TAKEYUKI HIDA

Professor

Emeritus

of

Nagoya University and Meijo University

AMS 2000

Subject

Classification:

60H40

White

Noise

Theory

1.

Prologue

One

of

the

basic

idea

of

white

noise analysis is

Reduction

of

random

phenomena

(cf.

[7]), so

that

the

given

system

is

made

to

be

a

function

of

idealized elemental

random

variables

(abbr.

i.e.r.v.), for exam-

ple

B(t),

white

noise

and

Fu,

elemental Poisson system.

More precisely,

we

may

say

that

it

would

be

fine if

random

complex phe-

nomena

can

be

express as a function

of

elemental

random

variables, so

that

they

are

ready

to

be

analyzed

and

that

the

theory

would

be

developed in

line

with

stochastic

analysis.

As

soon

as

we come

to

applications

of

the

theory

to

actual

problems,

we need

to

approximate

the

i.e.r.v.

by

a

system

of

ordinary

independent

random

variables.

Naturally

follows

approximation

of

the

analysis.

Motivations

Examples

of

the

motivation

of

our

study.

i) Biological

phenomena.

There

is involved

fluctuation

which is con-

sidered

to

be

Gaussian.

Behind

it,

we

see a

Gaussian

process

that

can

be

reduced

to

white

noise.

137

138

ii) We

often

meet

probability

distributions

which have long

tailor

fat

tail,

sometimes

called

fractional

power

distribution.

They

are

not

considered

to

be

Gaussian.

Such

a

distribution

may

appear

as

that

of

a

stable

stochastic

process

evaluated

at

some

instant.

The

process

admits

the

Levy

decomposition,

or

the

Levy-Ito

decomposition,

the-

oretically.

Each

component

is

an

infinitesimal Poisson process

and

even

it

is elemental.

In

each

case, efficient

method

of

application

requires

suitable

method

of

approximations.

Before we come

to

actual

methods,

we

shall

provide some

considerations

on

a

system

of

independent

random

variables which come

from

the

effect

of

reduction.

iii)

The

third

motivation

has

somewhat

different flavor.

Good

exam-

ples

are

stable

distributions

with

some

exponent.

It

appears

as a

distribution

of

a

stable

stochastic

process

evaluated

at

some

instant.

There

a

duality

between

time

and

Poisson

components

via

the

Levy

decomposition

of

a

stable

process.

2.

An

i.i.d.

random

variables

as

a

representation

of

parameter

set

Probabilistic

properties

of a sequence

of

i.i.d.

(independent

identically dis-

tributed)

random

variables

may

be

discussed

under

the

understanding

that

the

sequence is a

representation

of

the

parameter

set

used

as

index

of

a se-

quence

of

independent

random

variables. We

assume

the

sequence

of

i.i.d.

random

variables is Gaussian.

Case

1.

Digital

We have X =

{Xn'

n E

N},

where N is

the

set

of

positive integers.

The

probability

distribution

m is

the

direct

product

of

count

ably

many

standard

Gaussian

distributions.

The

complex

Hilbert

space

L2

= L

2

(ROO,

m)

involving

square

integrable

functions of

the

form

f(X

n

,

n E

N)

is

separable,

where

Hermite

polynomials

in

X~s

form a

complete

orthonormal

base

of

L2.

Differential

operators

an

is defined as follows:

a

akf(Xn,n

E

N)

=

-a

f(xn,n

E N)lxn=x

n

·

Xk

It

is a

derivation

and,

in fact,

it

is

an

annihilation

operator.

Its

adjoint

operator

az

can

be

defined

in

the

usual

manner.

The

polynomials

in

the

139

annihilation

and

creation

operators

are

defined.

In

particular,

the

Levy

Laplacian

~i

acting

on

L2

is given

as

follows:

Its

domain

is dense

in

L2.

Case

II.

Analogue

N

Ad.

1

""::>2

L...l.L

=hm

N

LUk'

1

II.

1) Analogue and separable

Gaussian

case

The

time

parameter

space is

taken

to

be

T =

[0,

1]

to

fix

the

idea.

Let

B(t),

t E

T,

be

a

Brownian

motion

from which

white

noise

13(t)

is defined,

Formally

speaking

the

13(t)'s

are

independent

system

of

idealized

ran-

dom

variables.

The

probability

distribution

JL

is

introduced on

the

measurable

space

(E*,

B),

where

E*

is a

space

of

generalized functions on

R1

and

where B

is

the

sigma-field

generated

by

the

cylinder

subsets

of

E*.

Proposition

2.1.

The measure space

(E*,

B,

JL)

is an (abstract) Lebesgue

space

where the calculus can

be

done.

As a result,

we

have

the

Hilbert

space (L2) = L2(E*,

JL)

which is,

of

course,

separable

and

on

which analysis

can

be

carried

on.

Functionals

in (L2)

that

we shall

be

concerned

with

are

of

the

form

cp(13(t),

t E

T),

which will

be

simply

written

by

cp(13).

Approximations

can

be

done

as follows:

(1)

Take a

partition

~n

=

{~k

= [k/2

n

,

(k + 1)/2

n

]},

k = 0

~

k

~

2

n

-

I}.

Then,

we

have two ways for

the

approximation

to

white

noise.

i)

c"B

tends

to

13

(t)

as

~

n

----+

t in

He

-1)

the

space of generalized

c,,~

k

l'

linear

white

noise functionals.

ii) Use

of

c"B

~

Poisson

case

The

parameter

set is

taken

to

be

(0,

00

).

For

each u

we

associate

an

infinitesimal Poisson process F

u

,

u

ETa,

where

To

= (0, (0). As for

the

case

of

13(t),

Fu

itself is

not

an

ordinary

random

variable,

but

it

can

be

a generalized

random

variable

as

is discussed

in

the

Accardi L., Freudenberg W., Obya M. (Eds.) Quantum Bio-informatics IV: From Quantum Information to Bio-informatics

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