Applications of Pattern Recognition To Protein Classification

Angel Kuri Instituto Tecnolgico Autnomo de Mxico akuri@[Link]

CANCN, MXICO May, 2004

Motivation
The basic idea is to achieve unbiased protein classification. In our agenda we would like to: a) Classifiy sets of proteins from simple organisms (E. coli and S. cerevisiae) - We use Kohonens self-organizing maps b) Analyze the clusters in order to determine the reasons why the proteins in the said clusters appear as they do - We use specific pattern recognition techniques now under development

Agenda
1. We make a brief review of - Proteins - The genetic code - Aminoacids 2. We talk a little about the SOMs 3. We discuss lossless compression algorithms and their relationship to the problem

Proteins (basic concepts)

Proteins (...basic concepts)

Proteins (...basic concepts)

Proteins (..basic concepts)

Proteins (...basic concepts)

Protein Expression
The following sequence is the expression of a protein of E. coli: MARKTKQEAQETRQHILDVALRLFSQQGVSSTS LGEIAKAAGVTRGAIYWHFKDKSDLFSEIWELF RPCKRCQPEKANAQQHRLDKITHACRLLEQETP VTLEALADQVAMSPFHLHRLFKATTGMTPKAWQ QAWRARRLRESLAKGESVTTSILNAGFPDSSSY YRKADETLGMTAKQFRHGGENLAVRYALADCEL GRCLVAESERGICAILLGDDDATLISELQQMFP AADNAPADLMFQQHVREVIASLNQRDTPL

Protein Structure

Protein Structure

Protein Classification

Protein Classification

...Protein Classification

...Protein Classification

...Protein Classification

...Protein Classification

Hypothesis
It is possible to achieve classification of the proteins of a living organism (we shall focus on E. coli and S. cerevisiae) paying attention solely to the structural characteristics (strings of aminoacids) of the proteins.

Clustering
The first problem is to attain the automatic clustering of the diverse proteins. To do this, we shall use self-organizing maps in which the determination of the cluster membership is achieved using genetic algorithms.

Step 1:
In this map all neighbouring neurons belong to a cluster. But we do not know the clusters boundaries.

An Example of a SOM
In this map the neurons have been labeled, so that we know to which cluster each neuron belongs.

Present Status
! As

of today, we have achieved initial success by finding sets of proteins whose basic clustering is derived from structural relationships between the aminoacids ! Much work remains to be done

Explaining the Clusters

By using SOMs we may find non-biased clusters. To explain why they cluster in such way it is possible to apply meta-symbolic search algorithms.

Explaining the Clusters

Our second task is, perhaps, more challenging than the first one Once we achieve structural clustering, we would like to find common structures in the proteins in each cluster To this effect we apply data compression techniques The basic idea is to remove redundancy from the proteins and THEN look for similarities

A Protein as a Message
As stated, a protein may be expressed as a string of symbols (aminoacids) In this sense, what we assume is that the original expression of any such protein may be replaced by a shorter, more compact way We propose to identify the underlying patterns in order to uncover a similarity measure between different proteins

Lossles Data Compression

Symbol S1 S2 S3 S4 S5 S6 S7 S8 P(Si) 0.50000000 0.25000000 0.12500000 0.06250000 0.03125000 0.01562500 0.00781250 0.00781250 Sum Code Length Avg(L) 1.00000 0 1 0.500 0.50000 10 2 0.500 0.25000 110 3 0.375 0.12500 1110 4 0.250 0.06250 11110 5 0.156 0.03125 111110 6 0.094 0.01563 1111110 7 0.055 1111111 7 0.055 SUMA 1.984 Std 3 3 3 3 3 3 3 3 3

Information Theory
The information of a symbol (as per Shannon), is given by: I(Si ) = log2 (Pi ) where Pi=probability that symbol Si appears. The average information (Entropy) is given by:
H(S) = Pi I(Si )
i

Lossles Data Compresion

Symbol S1 S2 S3 S4 S5 S6 S7 S8 P(Si) 0.50000000 0.25000000 0.12500000 0.06250000 0.03125000 0.01562500 0.00781250 0.00781250 I(Si) 1.00000 2.00000 3.00000 4.00000 5.00000 6.00000 7.00000 7.00000 Entropy Avg. Information 0.50000 0.50000 0.37500 0.25000 0.15625 0.09375 0.05469 0.05469 1.98438

Lossles Data Compression

Notice that the optimal average length is bounded by the entropy. When as here, the probabilities are powers of 2, it is possible to reach this limit. When such is not the case, the theoretical bound cannot be reached using this kind of encoding (Huffman Coding, after its creator).

The limitations of Information Theory

One of the tacit premises in classical IT is that the symbols are entities defined a priori (bytes, words, etc.) whose grouping relationship implies a topologic closeness. For example, if we consider letter couples, we normally consider them to be neighbours. In English, the couple th implies that P(e|th) is very high.

Ergodicity
One of the assumed characteristics of the data source, for the encoding to be effective, is ergodicity. Intuitively, a source is ergodic if its probabilities stabilize after a bounded period of time. A counter-example would be the one where we transmitted a block of English text, followed by an image (i.e. jpg).

Ergodicity
In the last example clearly, the probabilities of the first block will differ from the ones in the second block. We emphasize the fact that we have called probabilities, in practice, refers to the proportions gotten from the statistical analysis of data blocks.

Transformation of non-ergodic into ergodic Sources

The agenda we have set is to find sets of not necessarily neighboring symbols in a nonergodic source. If we achieve this, every set of such symbols (called a metasymbol) will replace a symbol in an equivalent ergodic source and will allow us to apply first order techniques to independent clusters.

Huffman
Assume the sample: A A A B A A A A B A A B A A B B A appears 11 times B appears 5 times Only two symbols. Huffman assigns: A = 0, B = 1.

Higher Orders
digram fre cH 0 10 3-gram fre cH 0 10 4-gram fre cH 00 01 10 11

AA AB BA BB Total

4 2 1 1

AAB AAA

3 1 1 1

AAAB AAAA

1 1 1 1

111 BAA 110 B##

111 BAAB 110 AABB

14 bits

11 bits

8 bits

Dictionary Methods
!A

dictionary with frequent strings is built. ! Every instance of the string is replaced by a reference to the dicionary.

Example (a piece of a poem by Sor Juana)

AL QUE INGRATO ME DEJA, BUSCO AMANTE; AL QUE AMANTE ME SIGUE, DEJO INGRATA; CONSTANTE ADORO A QUIEN MI AMOR MALTRATA; MALTRATO A QUIEN MI AMOR BUSCA CONSTANTE
1. 2. 3. 4. 5.

AL_QUE_ INGRAT _ME_ _AMANTE _A_QUIEN_MI_AMOR_

6. 7. 8. 9.

MALTRAT CONSTANTE DEJ BUSC

Result

12O38A, 9O 4; 143SIGUE, 8O 2A; 7 ADORO56A; 6O59A 7

Or else...
AL_QUE_INGRATO_ME_DEJA,_BUSCO_AMANTE;_ AL_QUE_AMANTE_ME_SIGUE,_DEJO_INGRATA;_ CONSTANTE_ADORO_A_QUIEN_MI_AMOR_MALTRATA;_ MALTRATO_A_QUIEN_MI_AMOR_BUSCA_CONSTANTE

Build a dictionary with patterns, not merely with strings.

A possibility...

...but not the only one

Metasymbol compression process

1.

2.

3. 4.

A message is given. Find the set of patterns which more frequently appear in the message. Find the set of patterns which allows the shortest expression of the message including the catalog (a description of the metasymbols). Encode the message using the patterns in the catalog Optionally also encode such catalog in the shortest possible way.

Finding Patterns...
! Characteristics

of the Patterns:

They are NOT strings of consecutive symbols. They show gaps. The size of the patterns and of the gaps are arbitrary. ! Reported algorithms to search for these sort of patterns have exponential complexity (on the size of the message).

...is hard!
Look for the place where the pattern overlaps with itself; find patterns of frequency = 2. ! Find the intersections of these; then the intersections of the intersections...and so on. ! The number of intersections grows exponentially. ! We have proven that finding the largest arbitrary pattern of maximum length is NPcomplete.
!

The MaximumCommonPattern Problem

It is P-verifiable: given a maximum length pattern proposal it takes polinomial time to determine whether it is really common to all strings. ! Reduction: given any other NP-complete problem, show that it may be mapped in polinomial time to the MaximumCommonPattern ! VertexCover was chosen as the NP-complete template.
!

Finding a subset
! If

we assume that we already have a set of frequent patterns we must then find a subset of them which allows us to express the message and the catalog in the shortest possible way. ! We proved that this problem is also NPcomplete.

The OptimalPatternSubset Problem

It is P-verifiable: given a proposal of a subset and the optimal compression ratio we may verify in polinomial time whether the subset is really optimal. ! Reduction: given any instance of an NPcomplete problem known to be NP-complete, show that it can be mapped to an instance of the OptimalPatternSubset. ! Knapsack 0-1 was selected.
!

To wrap up
! We

need approximation algorithms and/or heuristics.

To find the subset we found a promising cover-based heuristic. We must find those patterns which better cover the message We may then refine with hill-climbers

Heuristics and Meta-heuristics

Given the above, we have complemented the heuristics with a genetic algorithm. This GA is not Hollands Simple Genetic Algorithm but, rather, one we have called Vasconcelos GA (VGA) Putting the heuristics and VGA together we have found some interesting results.

Mini-agenda
! Vasconcelos ! Encoding ! Mutation ! Crossover ! Experiments

Genetic Algorithm

and some results

Vasconcelos GA
To overcome the limitations of a SGA we introduced the so called Vasconcelos GA. It displays:
a) Deterministic (i -> n-i+1) coupling b) Full elitism c) Annular crossover d) Uniform mutation

VGA

VGA

VGA

Encoding
The message is looked upon as an array of symbols A0B1d2C3A4B5e6C7f8 The genome is made up of the indices of the symbols 013 457 268 A0B1C3 A4B5C7 d2e6f8

Mutation
It consists of a permutation of two indices 457013268 427013568

Crossover
4570 18 263 8413 20 765 4573 18 263 8410 20 765 4573 18 260 8410 23 765
Individual A Individual B

Individual A Individual B

Individual A Individual B

Catastrophe
cuando_cuentas_cuentos_cuantos_cuentos_cuentas cuando_*uentas_*uentos_*uantos_*uentos_*uentas cuentas_*uentos_*uantos_*uentos_*uentas cuentos_*uantos_*uentos_*uentas cuantos_*uentos_*uentas cuentos_*uentas cuentas

Catastrophe
cuando_cuentas_cuentos_cuantos_cuentos_cuentas cuando_**entas_**entos_**antos_**entos_**entas cuentas_**entos_**antos_**entos_**entas cuentos_**antos_**entos_**entas cuantos_**entos_**entas cuentos_**entas cuentas

Catastrophe
cuando_cuentas_cuentos_cuantos_cuentos_cuentas cuando_**e*tas_**e*tos_**a*tos_**e*tos_**e*tas cuentas_**e*tos_**a*tos_**e*tos_**e*tas cuentos_**a*tos_**e*tos_**e*tas cuantos_**e*tos_**e*tas cuentos_**e*tas cuentas

Catastrophe
cuando_cuentas_cuentos_cuantos_cuentos_cuentas cuando_**e*tas_**e**os_**a**os_**e**os_**e**as cuentas_**e*tos_**a**os_**e**os_**e**as cuentos_**a*tos_**e**os_**e**as cuantos_**e*tos_**e**as cuentos_**e*tas cuentas

Garbage collector
cuando_cuentas_cuentos_cuantos_cuentos_cuentas cuando_**e**as_**e**os_**a**os_**e**os_**e**as cuentas_**e**os_**a**os_**e**os_**e**as cuentos_**a**os_**e**os_**e**as cuantos_**e**os_**e**as cuentos_**e**as cuentas

Catastrophe
cuando_cuentas_cuentos_cuantos_cuentos_cuentas cuando_**e**a*_**e**o*_**a**o*_**e**o*_**e**a* cuentas_**e**o*_**a**o*_**e**o*_**e**a* cuentos_**a**o*_**e**o*_**e**a* cuantos_**e**o*_**e**a* cuentos_**e**a* cuentas cuando_ cuentas _ cuentos _ cuantos _ cuentos _ cuentas

Catastrophe
cuando_cuentas_cuentos_cuantos_cuentos_cuentas cuando_**e**a*_**e**o*_**a**o*_**e**o*_**e**a* cuentas_**e**o*_**a**o*_**e**o*_**e**a* cuentos_**a**o*_**e**o*_**e**a* cuantos_**e**o*_**e**a* Metasmbolo cuentos_**e**a* c1u2n1t2s cuentas cuando_ cuentas _ cuentos _ cuantos _ cuentos _ cuentas

Finding the Metasymbols

! Applying

the previous operators of coupling, selection, crossover and mutation to arbitrary messages it is possible to find the solution to the compression problem by using the metasymbolic transform

Comparing compression methods

! It

is now possible to establish a comparison of several compression schemes ! In the following table we show the results of compressing sets of size 512 and 1,024

Results

...Results

Explaining the messages

To these algorithms a string of aminoacids is not distinguishable from a string of letters, or pixels, or... Hence, the meta-symbols embedded in the clusters may explain why the clusters arise as they do.

Conclusions
It is possible to find unbiased clusters of proteins from protein expression as aminoacids It is possible (and hard) to find metasymbols in arbitrary sets of data Applying genetic algorithms + heuristics we are able to approximate the solution of these NP problems

Conclusions
Once proteins are re-expressed as collections of metasymbols the underlying patterns are easier to detect Applying search techniques originally stemming from lossless data compression it is possible to find the reasons behind protein clustering