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

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

394 13 Morphological Features of Protein Spatial Structure

2. To solve (13.28) and (13.29), substitute (13.29) into (13.28), so that

− x

+ λx

+(y

− y

+ λy

+(z

− z

+ λz

=0.

To solve

λ = r

, r

/r

, (13.30)

in which r

= r

−r

, we substitute (13.30) into (13.28), and the solution

r =(x, y, z) is the coordinate of d



13.6 Exercises

Exercise 64. In the 2D case, generalize the main theorems and computa-

tional formulas presented in this chapter as follows:

1. Write down the deﬁnition and properties of the γ-accessible radius of the

particles in the plane particle system A, and elaborate on Deﬁnitions 43

and 44, and prove Theorems 43–45 in the 2D case.

2. Write down the recursive algorithm of the γ-accessible radius in the plane

particle system A.

3. Write down the computational algorithm for the cavity in the plane parti-

cle system A, and write down the deﬁnition and computational algorithm

of channel network (including connected circle and connected radius).

Exercise 65. Let a, b, c be three points on a plane, and let their coordinates

be r

=(x

), s =1, 2, 3. Obtain formulas for the following objects:

1. Circumcenter and circumradius of three points a, b, c.

2. Coordinates of the projection of point c onto the line segment ab.

3. Rectangle such that the points a, b, c are on its edges.

Exercise 66. For the plane particle system A formed by the ﬁrst 80 atoms

in Table 12.6 on the XY-plane, calculate the following properties:

1. Depth function and level function of each particle in particle system A.

2. All boundary line segments and vertices of convex closure Ω(A).

3. γ-function of all points in set A.

Exercise 67. For the plane particle system A formed by the ﬁrst 80 atoms

in Table 12.6 on the XY-plane, calculate:

1. Depth function and level function of each particle in particle system A.

2. All boundary triangles, edges, and vertices of convex closure Ω(A).

3. γ-function of all points in set A.

Semantic Analysis for Protein Primary

Structure

14.1 Semantic Analysis for Protein Primary Structure

14.1.1 The Deﬁnition of Semantic Analysis for Protein Primary

Structure

Semantic analysis refers to analyzing grammar, syntax, and the construtction

of words. Semantic analysis for common languages (such as English, Chinese,

etc.) is what we are familiar with. If protein primary structure is considered

to represent a special kind of biological language, then a protein structure

database would be a kind of biological language library, and semantic analysis

should aim to analyze the grammar, syntax, and semantics based on such

a library.

Diﬀerences and Similarities Between Semantic Analysis

for Protein Primary Structure and that for Human Languages

There are many similarities between protein primary structures and human

languages. There are also signiﬁcant diﬀerences. We list the similarities below:

1. Protein primary structures have the same language structure as human

languages, especially English, French, and German. They are both com-

posed of several basic symbols as building blocks. For example, English is

composed of 26 letters, while proteins are composed of 20 common amino

acids. A protein sequence can be considered to represent a sentence or

a paragraph, and the set of all proteins can be considered to represent the

whole language. Therefore, the semantic structure is similar to a language

structure which goes from “letters” to “words,” then to “sentences,” to

“chapters,” “books,” and ﬁnally to a “language library.”

2. There are abundant language libraries to be studied and analyzed both

for protein primary structures and human languages. Some of them have

already been standardized, as in several kinds of language libraries in

English, the PDB-Select database of protein, etc. These language libraries

provide us with an information basis for the semantic analysis.

396 14 Semantic Analysis for Protein Primary Structure

3. The goals of semantic analysis for protein primary structure and that for

human languages are basically the same. That is, to ﬁnd the basic words

they are composed of, the meanings of these words and the role they

play in the whole language system. It then goes on to the analysis of the

structure of grammar, syntax and semantics.

4. Protein primary structure and human languages are both evolving. Two

types of problems also occur in protein structures; problems when trans-

lating between diﬀerent languages, and how the same language engenders

diﬀerences between its regional dialects; adding diﬃculties to the semantic

analysis for protein primary structure.

The vital diﬀerence between the semantic analysis for protein primary struc-

ture and that for human languages is that we are familiar with the semantics,

grammar, syntax and word origin for human languages. The meanings of

nouns, verbs and adjectives are clear, thus the semantic analysis for human

languages is straightforward. Semantic analysis for protein primary structure

is to ﬁnd these kinds of words and to determine their meaning and grammar,

syntax and word-building structures. Thus it is much harder to analyze the

semantics of protein primary structure than it is to analyze the semantics of

human languages.

Basic Methods of Semantic Analysis

The basic methods of semantic analysis for protein primary structure and

those for human languages can be derived from information and statistics,

together with methods based on permutation and combination operations.

Statistical methods used in the semantic analysis for human languages are

frequently used nowadays in computer semantic analysis. For example, the

statistics-based analyses for single letters, double letters and multiple letters,

those for letters and words, and those for the millennium evolution rate of

important words are all results of statistical computation.

Information-based analysis methods rely on the information found in

databases. For example, we use the relative entropy density theory to achieve

systematic analysis and a series of results is obtained. Permutation and

combination methods are commonly used in biology. This is called sym-

bolic dynamics in some publications [7]. In this book, we use the cryp-

tography analysis method for our computation, which has a deﬁnitive ef-

fect.

Moreover, in some commonly used small-molecule databases, such as the

biological molecule and drug molecule libraries in combinatorial chemistry,

peptide libraries and non-peptide small-molecule libraries (a general intro-

duction of several libraries may be found in [86]), conformational libraries; in

addition to the illustrations of their chemical composition, three-dimensional

structures and biological functions [70] are given. They play an important role

in drug design. A typical example from the area of biomedical materials is the

14.1 Semantic Analysis for Protein Primary Structure 397

synthesis of anti-HIV-1 protease inhibitors which was performed according

to the molecular combination theory (a general introduction may be found

in [20]).

Databases Used in Semantic Analysis

In semantic analysis for protein primary structures, the database we mainly

use is the Swiss-Prot database. As of 19 September 2006 [8, 33], there were

232345 proteins (or polypeptide chains) and 85,424,566 amino acids stored in

this database.

14.1.2 Information-Based Stochastic Models in Semantic Analysis

We begin with the introduction of the method using probability, statistics

and information for our analysis. To give a clear description of semantics for

protein primary structure sequences, we provide uniﬁed deﬁnitions for the

related terms and elements.

Symbol, Vector, and Word

In human languages, symbols, words, and sentences are the basic elements of

semantic analysis. They are also the basic elements of semantic analysis for

biological sequences:

1. Symbols, also called single letters, are the basic unit of semantic structure

analysis. The set of all possible symbols used is called the alphabet. In

English, the basic alphabet is composed of 26 letters, while in a computer

language, the alphabet of English text is the ASCII alphabet. In protein

primary structure analysis, the 20 commonly occurring amino acids are

considered to be single letter codes forming the alphabet. Their single

letter codes were given in Chap. 8, and are

= {A, R, N, D, C, Q, E, G, H, I, L, K, M, F, P, S, T, W, Y, V} .

If each single letter code in V

is denoted by a number, then the corre-

sponding alphabet would be V

= {1, 2, ···,q}, q = 20. In the PDB or

Swiss-Prot databases, codes B, Z, X, and other amino acids that are not

common sometimes do occur, but will not be introduced here.

2. Vectors and words. Several symbols arranged in a certain order are collec-

tively called a vector, and we denote it by b

(k)

=(b

, ··· ,b

), b

∈ V

where each component represents one amino acid and k is the length of

this vector, called the rank of the vector. The collection of vectors b

(k)

denoted by V

(k)

In the English language, a vector is not usually a word, unless it has

a speciﬁc meaning. Therefore the vectors of speciﬁc biological signiﬁcance

398 14 Semantic Analysis for Protein Primary Structure

are called biological words. In protein primary structure sequences, we

will discuss what kinds of combinations of amino acids can represents

words, what their structures and meanings are, and how to determine

their properties.

3. Local words. In the English language, besides their meaning, words have

some special properties in the aspect of symbol structure relationships.

For instance, in English words, the letter q must be followed by u, and

the frequency of the three letters ordered to form the word “and” must

be much higher than that of adn, nad, nda, dan, dna. Thus, vectors with

these special statistical properties are called local words.

Local words and biological words are diﬀerent concepts, but many biolog-

ical words may be or contain local words. For instance, “qu” has a special

mathematical structure, hence it is a local word, but is not an English

word. It can be a component of many English words (for example, “queen”

contains local word “qu” and “and” is both a local word and an English

word). Local words can be found by mathematical means, while biological

words should be given deﬁnite biological content, which is the fundamen-

tal purpose of semantic analysis. Our point is that the analysis and search

for local words will promote the search and discovery of biological words.

4. Phrases. They are composed of several words arranged in a certain order.

They may be the superposition of several words or a new word. In math-

ematics, a phrase can be considered to be a compound vector composed

of several vectors. Normally, idioms can be regarded as special words or

phrases.

Databases and the Statistical Distribution of Vectors

Lexical analysis on biological sequences begins with statistical computation

on a database of protein primary structures. We construct the following math-

ematical model for this purpose:

1. Mathematical description of the database. We denote Ω to be a database

of protein primary structures, such as the Swiss-Prot database, etc. Here

Ω consists of M proteins. For instance, in the Swiss-Prot database version

2000, M = 107,618. Thus, Ω can be denoted by a multiple sequence: Ω =

, s =1, 2, ··· ,M},whereA

=(a

s,1

s,2

, ··· ,a

s,n

) is the primary

structure sequence of a single protein, its component a

s,i

∈ V

are amino

acids, and n

is the length of the protein sequence.

2. Frequency numbers and frequencies determined by a database. If Ω is

given, the frequency numbers and frequencies of diﬀerent vectors occurring

in this database can be obtained.

Inthefollowing,wedenotebyb

(k)

the ﬁxed vector of rank k in V

(k)

.The

number of times it occurs in the database Ω is the frequency number, denoted

by n(b

(k)

). Denote by n

the sum of the frequency numbers of all the vectors of

rank k.Thenp(b

(k)

n(b

(k)

)

will be the normalized frequency or probability

14.1 Semantic Analysis for Protein Primary Structure 399

Table 14.1. Frequency numbers and probabilities of the commonly occurring amino

acids

ARNDCQEG

n(b) 3010911 2049696 1707483 2067196 641622 1551221 2549016 2706769

p(b) 0.07629 0.05193 0.04326 0.05238 0.01626 0.03930 0.06458 0.06858

HI L KMFPS

n(b) 888197 2302697 3761963 2345725 932473 1612406 1928666 2780793

p(b) 0.02250 0.05834 0.09532 0.05943 0.02363 0.04085 0.04887 0.07046

TWYV

n(b) 2190245 476445 1240969 2608996

p(b) 0.05549 0.01207 0.03144 0.06610

with which vector b

(k)

occurs in database Ω. For instance, when k =1,in

the Swiss-Prot database, the frequency numbers and probabilities of the 20

common amino acids are as given in Table 14.1.

=39,467,963 is the total number of the amino acids (except B, Z, X)

occurring in database Ω,andn(b) is the frequency number of amino acid b

occurring in Ω. Then, p(b)=

n(b)

is the probability of amino acid b occurring

in Ω.

We can also obtain the frequency number and frequency distribution of

k =2, 3, 4 ranked vectors in database Ω. See [99].

Characteristic Analysis for Words

In human languages, if vector b

(k)

is a word, then normally it has the following

characteristics:

1. The occurrence of each component in vector b

(k)

has certain dependence

on the context. For instance, in English words, q must be followed by u,

and the possibility of letter f, or t following an i must be higher than that

of any other two-letter combinations among these three. This statistical

characteristic of words is called the statistical correlation between letters.

2. Changing the order of the components in vector b

(k)

may inﬂuence their

frequency of occurrence. For instance, in English, the frequency of the

three letters “and” is much higher than that of “nad,” “nda,” “nad,” or

“dan.” This statistical characteristic of words is called the statistical order

preservation between letters.

Statistical correlation and statistical order preservation are the two char-

acteristics of word-building. Hence, they are an important factor in the

determination of local words.

400 14 Semantic Analysis for Protein Primary Structure

14.1.3 Determination of Local Words Using Informational

and Statistical Means and the Relative Entropy Density Function

for the Second and Third Ranked Words

Principle of the Analysis of Local Words Using Informational

and Statistical Means

To determine local words, the information-based and statistics-based ap-

proaches can be used. In this analysis we use the probability distribution of

the vectors and their relative entropy density function. In informatics, relative

entropy is also called Kullback–Leibler entropy. Its deﬁnition is as follows:

1. If p(b

(k)

)andq(b

(k)

) are two frequency distributions of V

(k)

,thenwe

deﬁne



p, q; b

(k)



=log



(k)





(k)



(14.1)

to be the relative entropy density function of the frequency distribution q

concerning p, or the relative entropy density function for short, where

(k)

∈ V

(k)

is the independent variable of the function. The relative en-

tropy density function is the measurement of the diﬀerences between dis-

tribution functions p and q. In informatics, many discussions are presented

on the properties of the Kullback–Leibler entropy [23, 88]). In this book,

we mainly discuss the relative entropy density function deﬁned by for-

mula (14.1), as it possesses a much deeper meaning than that of Kullback–

Leibler entropy.

2. The mean (or expectation), variance and standard deviation of the relative

entropy density function are denoted respectively by: μ(p, q), σ

(p, q)and

σ(p, q)=

(p, q). Here

μ(p, q)=



(k)

∈V

(k)



(k)





p, q; b

(k)



is the Kullback–Leibler entropy which is common in informatics. In infor-

matics, it has been proved that μ(p, q) ≥ 0 always holds, and the equality

holds if and only if p(b

(k)

) ≡ q(b

(k)

)holds.

3. The frequency number distribution of the relative entropy density func-

tion. In addition to the eigenvalue, the relative entropy density function

has another property, namely the frequency distribution function. We de-

note by F

(p,q)

(x)theset{a

(k)

∈ V

(k)

: k(p, q; a

(k)

) ≤ x}. Then, from

(p,q)

(x), a histogram can be drawn. This is a common method in statis-

tics.

Relative Entropy Density Function

When using the relative entropy density function k(p, q; b

(k)

) in formula (14.1),

frequency distributions p, q can be chosen by diﬀerent methods. The value of

14.1 Semantic Analysis for Protein Primary Structure 401

the relative entropy density function k(p, q; b

(k)

) then reﬂects diﬀerent aspects

of the diﬀerent internal structure characteristics of vector b

(k)

in database Ω.

Then p, q can be chosen as follows:

1. Let q(b

(k)

)=p(b

)p(b

) ···p(b

). The value of the relative entropy den-

sity function k(p, q; b

(k)

) then reﬂects the “aﬃnity” of each amino acid in

vector b

(k)

=(b

, ··· ,b

). The concept of “aﬃnity” reﬂects “correla-

tion” or “cohesion” and “attraction” between the amino acids in vector

(k)

.Thatis,k(p, q; b

(k)

) > 0, k(p, q; b

(k)

) < 0, or k(p, q; b

(k)

) ∼ 0, express

that each amino acid in vector b

(k)

is in a relation of cohesion, exclusion

or neutral reaction (in which case it is neither cohesion nor exclusion),

respectively.

2. If γ represents a permutation in set {1, 2, ··· ,n},wedenoteas



(k)





γ(1)

γ(2)

, ··· ,b

γ(n)



, (14.2)

the permutation on the position of each amino acid in vector b

(k)

.Ifwe

take q(b

(k)

)=p[γ(b

(k)

)], then the value of the relative entropy density

function k(p, q; b

(k)

) reﬂects the “order orientation” of the order of each

amino acid in vector b

(k)

3. “Conditional aﬃnity.” We take k = 3 as an example. Here we denote

(3)

=(a, b, c), and take

k(p, q; a, c|b)=log

p(a, b, c)p(b)

p(a, b)p(b, c)

=log

p(a, c|b)

p(a|b)p(c|b)

, (14.3)

which denotes the aﬃnity of a and c on the condition when b is given.

Here k(p, q; a, b|c) > 0, k(p, q; a, b|c) < 0, and k(p, q; a, b|c) ∼ 0, denote,

respectively that amino acids a, c are of cohesion, exclusion or neutral

reaction on the condition of the given b.Ifaminoacidsa, c are of neutral

reaction on the condition of the given b, then we say the tripeptide (a, b, c)

is a Markov chain.

The three diﬀerent types of relative entropy density functions above reﬂect the

stability of the protein primary structure in three diﬀerent aspects. Normally,

if q(b

(k)

) is considered to be the replacement of the polypeptide chain struc-

ture p(b

(k)

), then k(p, q; b

(k)

) > 0, expresses the fact that the stability of the

original polypeptide chain b

(k)

is higher than that of the other replacements.

The Generation of Local Words

It has been shown in the above text that there are eigenvalues and distribution

functions of the relative entropy density function k(p, q; b

(k)

). For diﬀerent

choices of p, q, the relative entropy density function may reﬂect the stability

of the protein primary structure in diﬀerent aspects. Thus we refer to the

conditions of k(p, q; b

(k)

)  0, or k(p, q; b

(k)

)  0 as the “strong stability”

402 14 Semantic Analysis for Protein Primary Structure

state or “strong nonstability” state, respectively. The “strong stability” state

or “strong unstability” state is often assessed by τσ determination in statistics.

That is,





p, q; b

(k)



− μ(p, q) ≥ τ

σ(p, q) ,b

(k)

is said to be τ

stable ,



p, q; b

(k)



− μ(p, q) ≤−τ

σ(p, q) ,b

(k)

is said to be τ

nonstable ,

(14.4)

where b

(k)

is a polypeptide chain, τ

is taken to be constant and μ(p, q),

σ(p, q) are the mean and standard deviation of k(p, q; b

(k)

), respectively. The

determination of local words using the formula (14.4) is called the (p, q, τ)

determination, or (τ,σ) determination for short. It is a common method in

statistics, while the theories of data analysis and data mining do not commonly

employ several types of relative entropy density functions.

14.1.4 Semantic Analysis for Protein Primary Structure

As stated above, protein primary structures are the sequence structures com-

posed of amino acids. Their structure characteristics are similar to human

languages we use, thus the research on protein primary structures can be con-

sidered a branch of research on semantic structures. We now use the determi-

nation of local words given above and the Swiss-Prot database to construct

a table of relative entropy density functions of protein primary structures and

the local words of second, third, and fourth rank. The computation process is

described below.

Table of Relative Entropy Density Functions of Dipeptides

Tables of relative entropy density functions of dipeptides can come in one of

two types. When k = 2, for the ﬁxed distribution p(a, b), a, b ∈ V

,wetake

(a, b)=p(a)p(b), q

(a, b)=p(b, a), and the corresponding relative entropy

density functions are, respectively,

(a, b)=log

p(a, b)

p(a)p(b)

(a, b)=log

p(a, b)

p(b, a)

. (14.5)

In the Swiss-Prot database, the computational results of k

(a, b),k

(a, b)are

listed as in Tables 14.2, 14.3, 14.4, and 14.5.

From Tables 14.4 and 14.5, the eigenvalues of k

are obtained, and are

shown in Table 14.6.

Searching for the Second Ranked Local Words

When k = 2, from Tables 14.4, 14.5, and 14.6 we can ﬁnd the second ranked

local words. For example, when we take τ = 2, the dipeptides of the sec-

ond ranked local words and their types can be obtained, and are listed in

Table 14.7.

14.1 Semantic Analysis for Protein Primary Structure 403

In Table 14.7, type 1 is the aﬃnitive type, where the dipeptides are at-

tractive. Type 2 is the repulsive type, where the dipeptides are repulsive.

Type 3 is the ordered type, where the probability of the dipeptides occurring

is obviously related to the order.

(p, q; a, b)=−k

(p, q; b, a) is antisymmetric; for example, if

(p, q; M, W)=0.3535 ,

then

(p, q; W, M )=−0.3535 .

Thus the probability of dipeptide MW occurring is much higher than that of

WM.

Determination of the Third Ranked Local Words

The determination of the third ranked local words is generally the same as

that for the second ranked ones. This is discussed as follows.

From database Ω, we can determine the frequency distribution p(a, b, c)

of the third ranked vector b

(3)

=(a, b, c), a,b,c ∈ V

, and compute its ﬁrst

and second ranked marginal distributions p(a, b), p(b, c), p(a), p(b), and p(c).

From this, eight types of relative entropy density functions can be generated:

(a, b, c)=log

p(a, b, c)

p(a)p(b)p(c)

(a, b, c)=log

p(a, b, c)

p(a)p(c, b)

(a, b, c)=log

p(a, b, c)

p(b)p(a, c)

(a, b, c)=log

p(a, b, c)

p(c)p(a, b)

(a, b, c)=log

p(a, b, c)

p(b, a, c)

(a, b, c)=log

p(a, b, c)

p(c, b, a)

(a, b, c)=log

p(a, b, c)

p(a, c, b)

(a, b, c)=log

p(a, b, c)

p(b, c, a)

(a, b, c)=log

p(a, b, c)

p(c, a, b)

(14.6)

Their eigenvalues are given in Table 14.8, where the number of the local words

of type I refers to the number of tripeptide chains following k

(a, b, c) >

+3.5σ

, and the number of the local words of type II refers to the number

of tripeptide chains which follow k

(a, b, c) <μ

− 3.5σ

We comment on the following aspects for Table 14.9:

1. In this table, the capital letter is the tripeptide and the number is function

.Whenk

> 0, it is a chain of peptides of type I, which attract each

other, and when k

< 0, it is a chain of peptides of type II, which repel

each other. There are in total 54 local words in Table 14.9.

2. Data in this table are obtained on the condition of τ =3.5. If we lower

the value of τ, there will be an increase in the number of local words.

3. For each type of dynamic function k

−k

, we can also obtain the vocab-

ulary of local words in tripeptide chains, which will not be listed here.