TABLES DES MATIÈRES
INTRODUCTION
I. LA PROGRAMMATION DYNAMIQUE POUR LE CACUL DE LA DISTANCE D'ÉDITION
I.1 Définition.
I.2 Les trois composantes
de la programmation dynamique.
II. RECHERCHE D'OCCURRENCES APPROXIMATIVES D'UN MOT DANS UN TEXTE
II.1 Algorithme de SELLERS.
II.2 SELLERS VS BLAST
II.3 Idée générale
du fonctionnement de BLAST et FASTA.
II.4 Exemples d'utilisation
des banques de données dans le domaine de la recherche.
III. ALGORITHMES VECTORIELS ET AUTOMATES
III.1 Algorithmes vectoriels
III.2 Automates finis.
IV. BIBLIOGRAPHIE
INTRODUCTION
Les grandes découvertes dans le domaine de la biologie notamment
la théorie sur la sélection naturelle, sont basées
sur une analyse comparative. Les travaux de Darwin qui vont être
les fondations de la biologie moléculaire actuelle reposent
sur l`observation et la comparaison morphologique de plusieurs
espèces . Aujourd'hui, nous effectuons le même type d'analyse
lorsque l' on compare des séquences biologiques ( ADN, ARN, proteines)
mais à une échelle moléculaire. Le but de ce type
d'analyse est la recherche de similarités entre séquences
afin de pouvoir en déduire leurs fonctions, structure et leurs éventuels
liens de parenté (phylogenie). Le nombre de séquences disponibles
à connu une forte croissance depuis les années 70 grâce
au developpement d'une méthode de séquençage
rapide de l'ADN.(méthode de Sanger). Cet ensemble de séquences
disponibles sur le Web sous la forme de banque à permis le developpement
d'une technique révolutionnaire accessible à chaque biologiste
. Cette technique consiste en la comparaison d'une séquence
biologique dont la structure et la fonction sont inconnues à l'ensemble
d'une banque "on-line". La taille grandissante de ces banques de données
est le résultat d'une amélioration de la rapidité
et de la sophistication des algorithmes d'alignements, mais aussi des progrés
technologiques qui ont augmenté les performances des ordinateurs,
depuis une trentaine d'années. Aujoud'hui avec le séquençage
complet du genome de nombreux organismes, nous sommes entrés dans
l'ére de la "génomique comparative".
I. PROGRAMMATION DYNAMIQUE POUR LE CALCUL DE LA DISTANCE D'ÉDITION :
I.1 Définitions :
La programmation dynamique est constituée de trois composantes
essentielles, qui suivent :
D(i, 0) = i,
D(0, j) = j.
La relation de récurrence que satisfait D(i, j) pour i et j strictement supérieurs à 0 est :
D(i, j)= min[D(i-1, j) + 1, D(i, j-1) + 1, D(i-1, j-1) + t(i, j)] (1)
où t(i, j)=1 ssi S1(i) est différent de S2(j),
t(i, j)=0 ssi S1(i)=S2(j).
Bottom-up computation
:
La méthode Bottom-up consiste, dans un premier temps, à
calculer D(0, j) et D(i,0). On calcule ensuite D(i, j) pour des valeurs
croissantes de i et j. En général, le calcul Bottom-up est
représenté sous la forme d'un tableau de dimension (n+1)
par (m+1).
Exemple:
Soit S1= TAT et S2=GATA, la première étape
consiste à remplir la ligne 1 et la colonne 1 en se référant
à la condition de base :
| - | G | A | T | A | |
| - | 0 | 1 | 2 | 3 | 4 |
| T | 1 | ||||
| A | 2 | ||||
| T | 3 |
Nb : Dans le cas d'une recherche approximative d'un mot dans un texte,
les conditions initiales sont :
D(i, 0) = i,
D(0, j) = 0.
La deuxième étape consiste à remplir le reste du
tableau en utilisant la relation de réccurrence 1 :
| - | G | A | T | A | |
| - | 0 | 1 | 2 | 3 | 4 |
| T | 1 | 1 | 2 | 2 | 3 |
| A | 2 | 2 | 1 | 2 | 2 |
| T | 3 | 3 | 2 | 1 | 2 |
La distance d'édition entre nos deux séquences est alors
D(n,m)=2.
Règles du traceback :
| - | G | A | T | A | |
| - | 0 | 1 | 2 | 3 | 4 |
| T | 1 | 1 | 2 | 2 | 3 |
| A | 2 | 2 | 1 | 2 | 2 |
| T | 3 | 3 | 2 | 1 | 2 |
L 'alignement correspondant à la distance d'édition calculée est :
GATA
TAT -
II. RECHERCHE D'OCCURRENCES APPROXIMATIVES D'UN MOT DANS UN TEXTE
Chaque fois que l'on se connecte sur le Web afin
d'y faire une recherche, ou quand on utilise un correcteur d'orthographe
on fait, sans le savoir, de la recherche d'occurrences approximatives d'un
mot dans un texte. La recherche d'occurrences approximatives est
un problème majeur qui touche de nombreuses disciplines, d'où
l'importance du developpement d'algorithmes puissants et rapides
. La nécessité d'avoir des algorithmes rapides prend tout
son sens en biologie,car nous travaillons en géneral sur des textes
contenants des millions de caractéres (brins d'ADN). J'ai tenté
de mettre en évidence la sophistication des algorithmes actuels
et leur importance en biologie par une expérience très simple
qui consite à programmer l'algorithme de Sellers et ensuite de comparer
ses performances en terme de temps avec le logiciel BLAST disponible
sur le Web.
II.1 Algorithme de SELLERS :
Cet algorithme programmé en espace lineaire ( il calcule colonne par colonne) nous donne les positions des occurrences approximatives d'un mot dans un texte .
pseudo code :
Entrée: Texte T et un motif P.
Sortie: Les positions des occurrences approximatives de P dans le texte
Pour i de 0 à n
D[i]<--i
Pour j de 1 à n
vieille<-- 0
Pour i de 1 à n
Temp<--D[i]
d[i]<-- min[ (Temp +1), (Vieille + c(xi, yi)), (D[i-1]+1) ]
Vieille<--Temp
Fin pour
Fin pour
Fin pour
En JAVA :
import java.io .*;
public class sellers
{
static int CHAMPSDESC =0;
static int CHAMPSSEQ=0 ;
public static void main(String [] args)
throws java.io.IOException
{
//declarations des entrées:
System.out.println ("entrez le nom du fichier correspondant a votre texte:");
String nomfichier=Clavier.lireString();
String y=lire(nomfichier);
System.out.println ("entrez le nom du fichier correspondant a votre motif:");
String motif=Clavier.lireString();
String x=lire(motif);
int [] d=new int [x.length()+1 ] ;
int n=x.length();
int m=y.length();
long depart= System.currentTimeMillis(); // initialisation du compteur
//initialisation du tableau à 1D
for(int i=0;i<=n;i++)
{
d [i]=i;
}
//calcul pour chaque colonne du score à la position m
for(int j=1;j<= m;j++)
{
int vieille;
vieille=0;
boolean occ=false;
for(int i=1;i<=n;i++)
{
int temp=d[i];
char a = x.charAt(i-1);
char b = y.charAt(j-1);
if( a!=b)
{
vieille++;
}
// calcul du score d[i]
int minT=Math.min(temp+1,vieille) ;
int min =Math.min(minT,d[i-1]+1);
d[i]=min;
vieille=temp ;
if (d[n]<=1)
{
occ=true;
}
}
if (occ)
{
System.out.println("occurence a la position"+ j);
}
}
//arrêt du compteur
long arrive= System.currentTimeMillis();
long tps= arrive-depart;
System.out.println(tps);
}
//méthode qui permet la lecture de fichier Fasta
public static String lire(String nomfichier)
throws IOException
{
String[][] entrees=FichierFASTA.lireSeq(nomfichier);
String desc=entrees[0][FichierFASTA.CHAMPS_DESC];
String seq=entrees[0][FichierFASTA.CHAMPS_SEQ];
return seq;
}
}
II.2 SELLERS vs BLAST :
Afin de tester la rapidité des deux algorithmes, à trouver
toutes les occurrences approximatives d'un mot P dans un texte T , je me
suis rendu sur le site du NCBI afin de télécharger une portion
du chromosome 22 (406225 nucléotides) qui constituera mon texte
T. A partir de cette séquence j'ai selectionné 100 nucleotides
qui représenteront le mot P. J' ai ensuite soumis les séquences
au logiciel BLAST 2 Sequences et à l'algorithme de SELLERS .
Résultats:
II.3 Idée général du fonctionnement de BLAST et FASTA :
BLAST ("basic local alignement search tool") et FASTA ("fast-all") sont deux programmes heuristiques d'alignements de séquences. Ces deux programmes sont une approximation du programme dynamique de SMITH & WATHERMAN qui optimise un alignement local entre une region de notre séquence et celle de la banque. Le programme dynamique de SMITH & WATERMAN nous donne des résultats exactes de l'alignement et sont donc trop lents.
II.3.1 BLAST:
On peut distinguer trois grandes étapes dans le fonctionnement de BLAST :
Etape 1 :
L'algorithme prend la sequence d'entrée
est la découpe en mots . Il génère tout les mots de
longueur comprise entre w( ex: 3 pour les proteines)et L-w+1(L=longueur
de la séquence d'entrée). Pour chaque mot de la séquence
d'entrée il calcule un score a partir d'une matrice PAM 250 , et
si le score est superieur au score T fixe , ce mot fera parti d'une
liste L.
Etape 2 :
Il compare ensuite la liste L à l'ensemble de la base de donnée. Il identifie les matches exactes entre les mots de la liste L et les mots qui peuvent être générés avec les séquences de la base de donnée.
Etape 3 :
Pour chacun des mots qui matchent avec la séquence,
il éssaye d'étendre dans les deux sens le mot afin de trouver
l'alignement optimal.
II.3.1 FASTA :
la methode FASTA , se décompose en quatre étapes:
Dans un premier temps on réalise une matrice de points
entre deux séquences 1 et 2 (chaque fois qu'un k-tuple est identique
on met un point). On peut se représenter la longueur des k-tuples
comme une fenêtre parcourant nos deux séquences. En général,
on fixe la longueur des k-tuples a six pour l'ADN et deux pour les protéines.
On appelle "hot-spot" les k-tuples de la séquence 1 qui matchent
exactement avec les k-tuples de la séquence 2.
Exemple :
SEQ 1
GTCATCA............. ..CGTACG........
SEQ 2
ATCGTAC ............. .CGTACG......
I-------I
I-------I
longueur de
les deux k-tuples
la fenêtre =6
sont identiques = "hot-spot"
Cette matrice de points va être recalculée à l'aide
d'une matrice PAM et seuls, les dix segments qui correspondent aux scores
les plus élevés, sont conservés. Ici, cette matrice
joue le rôle d'un filtre. Les matrices PAM (matrices de DAYHOFF)
sont basées sur des mutations observées dans des alignements
globaux de protéines très similaires. On réduit le
nombre de segments en ne conservant que les plus proches. La dernière
étape consiste à rejoindre les segments à l'aide de
"gap" afin d'obtenir le meillieur alignement.
II.4 Exemples d'utilisation des banques de données dans le domaine de la recherche :
1. Mise en évidence du lien entre les oncogènes et les facteurs de croissance.
Dans les années 70, des expériences de transfection de cellules en culture par un rétrovirus (virus à ARN ) ont été réalisées.Une croissance anormale est observée (elles se divisent indéfiniment) . La transformation de cellules saines en cellules cancéreuses par l'intermédiaire d'un rétrovirus suggère le fait que le même type d'infection peut être responsable de cancers chez les singes et les hommes, mais le mécanisme reste inconnu. L'hypothèse formulée est la suivante, certain gènes(oncogènes) qui codent pour des facteurs de croissance subissent un "dérèglement " lors de l'infection virale. Cela se traduit par une perte de contrôle de la croissance due à une forte production de facteurs. Cette hypothèse est assez bien acceptée, mais le lien entre les oncogènes et les facteurs de croissance n'a pas été démontré. Le lien sera fait grâce à l'utilisation des banques de données 13 ans plus tard. Le Simian sarcoma virus est un rétrovirus connu, dans les années 70, comme étant responsable de cancers chez le singe. En 1983, l'oncogène responsable, v-sis, est isolé et séquencé. Au même moment, des travaux sur un facteur de croissance très important, PDGF, aboutissent au séquençage d'une portion de ce facteur. Cette séquence à été ensuite comparée à une base de donnée. Les résultats publiés montrerons deux régions (l'une de 31 et l'autre de 39) fortement conservées entre PDGF et v-sis.
2. Identification de la fonction des gènes.
Le génome entier de l'Haemophilus infuenzae à été
séquencé et assemblé en 1995. 1743 régions
identifiées comme étant des régions codantes
potentielles ont été traduites en protéines et ensuite
soumises à SWISSPROT (banque de séquences protéiques).
Environ milles potentiels gènes ont matchés d'une façon
significatives avec des protéines dont la fonction biochimique était
connue.
Différentes stratégies peuvent être utilisées pour augmenter la vitesse de l'algorithme de Sellers, tel que l'utilisation combinée d'algorithmes vectoriels et d'automates. Dans cette partie, on abordera les algorithmes vectoriels à travers un exemple tiré de la thése de Sylvie Hamel : l'algorithme de Baeza-Yates et Gonnet.
III.1 Algorithmes vectoriels
Définition :
Un algorithme vectoriel est un algorithme qui renvoie en sortie un
vecteur en appliquant un nombre d'opérations sur le vecteur d'entrée,
indépendant de la longueur du vecteur.
Vecteurs de bits :
Soient x = x1......xm et y = y1.....ym deux vecteurs d'entiers. Si
x et y sont des vecteurs ne contenant que des valeurs booléennes
(0 ou 1), alors ils sont appelés vecteurs de bits.
Opération vectorielles:
a. Les opérations logiques.
v
= disjonction
^ = conjonction
¬ = négation
| x | y | x v y | x ^ y | ¬ x |
| 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 |
b. Addition binaire: x + by
Ici l'addition binaire se fait de gauche à droite, en ne considérant pas la dernière retenue.
Exemple d'addition binaire:
100111
110101
---------
001001(1)*
* dernière retenue qu'on oublie dans le calcul.
c. Déplacement vers la droite
Soit x = x1......xm.
Îa x =
ax1.......xm-1
Les valeurs du vecteur x ont été déplacées
d'une position vers la droite et la première valeur du vecteur devient
a.
Exemple:
Soit x = 10000001, alors on Î0 x = 01000000
d.Vecteur caractéristique:
Soit x un vecteur et a un symbole dans ce vecteur. Le vecteur caractéristique de a, noté a, est le vecteur comportant des 1 aux positions dans x où le caractère a apparaît, et des 0 partout ailleurs.
exemple:
soit x = babbaac, alors on a les vecteurs caractéristiques suivants:
a = 0100110
b = 1011000
c = 0000001
Algorithme vectoriel pour la recherche des occurrences exactes d'un mot dans un texte : Algorithme de Baeza-Yates et Gonnet
1. Fonctionnement de l'algorithme
L' idée de Baeza-Yates et Gonnet pour la recherche des occurrences exactes d'un mot P =p1...pm dans un texte T =t1..tn est, de travailler avec des vecteurs de bits de longueur m, où m est la longueur du mot cherché. Pour chaque position j dans le texte T, on définit un vecteur de bits Rj qui contient l'information sur tous les alignements exacts de préfixes du mot P se terminant en position j du texte. Plus précisément, on le defini de la façon suivante:
Pour
1 =< i =< m
Rj[i] = 1 si le préfixe
de longueur i de P est identique au suffixe de longueur i de t1.....tj
sinon Rj[i]
= 0
| Rj[i] | |
| Rj+1[i+1] |
L' idée est que lorsque l'on lit la prochaine lettre du texte, tj+1, on doit déterminer si cette lettre étend l'un des alignements exacts de l'étape précédente. Les différentes opérations de cet algorithme sont Donc :
2. Relation de récurrence pour le calcul de Rj+1.
On peut calculer le vecteur Rj+1, à partir du vecteur Rj, à l`aide de la récurrence suivante :
Soit R0 le vecteur de bits initial défini par R0[i]
=0, pour tout i, 1<= i <=m.
Si on suppose que Rj[0] =1, pour tout j, 0<= j <=n, alors
on a la transition suivante entre Rj et Rj+1:
Rj+1[i] =1, si Rj[i-1] =1 et pi = tj+1,
(1)
Rj+1[i] =0, sinon.
3. Résolution de l'algorithme par calcul vectoriel :
La relation de récurrence 1, traduite sous forme vectorielle, nous donne
Rj+1 = Î1 Rj ^ tj+1,
où tj+1 représente le vecteur caractéristique
de la lettre tj+1 dans le mot cherché P.
L'utilisation des vecteurs de bits va permettre de réduire le nombre d'opérations et donc d'augmenter la vitesse de calcul . Ici , avec 2 opérations on est capable de calculer Rj+1 (un déplacement vers la droite et une conjonction).
Exemple:
Calculons les occurrences exactes du mot P=TTA dans le texte T=ACGTTACGTAAT. Pour cela, on doit commencer par calculer les vecteurs caractéristiques de chacune des lettres, apparaissant dans le texte T, par rapport au mot P :
A=001,
C=000,
G=000,
T=110,
On a R0=000, par définition. On utilise le lemme1 pour calculer les valeurs des vecteurs Rj, 1<= j <= n=12 :
R1= Î1 R0^A=100^001=000,
R2= Î1 R1^C=100^000=000,
R3= Î1 R2^G=100^000=000,
R4= Î1 R3^T=100^110=100.
| A | C | G | T | T | A | C | G | T | A | A | T | |
| T | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| T | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 0 | 1* | 0 | 0 | 0 | 0 | 0 | 0 |
* Position de l'occurrence exacte du mot P dans le texte T.
III.2 Automates finis.
III.2.1 Définitions :
Un automate fini Aut = < A,Q, D, F, £ > est caractérisé par la donnée de cinq ensembles :
On utilise un graphe dont les sommets sont les états de l'automate et les arêtes étiquetées par les lettres de A correspondent à £.
Nomenclature :
Exemple 1: Le graphe qui représente l'automate Aut = < A, Q, D, F, £ > où
A = {x, y}, Q ={1, 2, 3}, D = {1}, F = {3}
et £ ={(1, y, 1), (1, x, 2), (2, y, 2), (2, x, 3), (3,x,3), (3, y,
3)}
Tableau de transition :
On représente les transitions £ sous la forme d'un
tableau T indicé par Q et A .
Pour l'exemple 1, la table de transition est donnée par :
| £ | 1 | 2 | 3 |
| x | 2 | 3 | 3 |
| y | 1 | 2 | 3 |
III.2.1 Langage reconnu par un automate fini :
Le langage reconnu, noté Laut, par un automate fini Aut,est l'ensemble de tous les mots reconnus par Aut. Dans l'exemple précédent Laut = y*xy*xA* (il faut au moins 2 x dans un mot pour que celui ci soit reconnus par cette automate).
NB: y* = on boucle dans l'etat 1 ou 2 avec la lettre y
A* = on boucle dans l'état
3 avec la lettre x où y
Il existe plusieurs méthodes pou obtenir une expression du langage
reconnu par un automate fini donné :
Méthode intuitive :
Il faut trouver un moyen de décomposer le langage recherché
en une succession de langages obtenus au cours du cheminement dans l'automate.Dans
l'exemple 1, on va boucler un certain temps sur l'etat 1 avec y puis, par
une transition avec x, on va passer dans l'état 2 et on ne reviendra
plus dans l'état 1. Le langage recherché est donc le produit
du langage reconnu par la boucle sur l'état 1, d'une lettre x permettant
d'aller dans l'état 2, du langage reconnu par la boucle 2, d'une
lettre x permettant d'aller dans l'état 3 et du langage reconnu
par la boucle sur l'état 3 , soit y*xy*xA*.
exemple 2:
Dans cette exemple, on peut remarquer que
l'on peut découper cette automate en deux parties. En effet après
avoir fait la transition de l`état 0 vers l'état 2, on ne
peut plus revenir dans la partie gauche de l'automate.
Tout d'abords , on isole la partie minimale de l'automate permettant
d'arriver dans l'état d'acceptation. Le langage reconnu par cet
automate est xx*yA*, ce qui signifie qu'un mot doit, pour être reconnu,
commencer par au moins un x et contenir au moins un y.Tout ceci peut être
précédé d'une possibilité de boucler sur l'état
0 grâce au morceau d'automate restant qui reconnaît le langage
suivant :yy*x. Donc le langage reconnu par l'automate est (yy*x)xx*yA*.
Exemple concret d'automate:
Le code à quatre chiffres des portes d'immeubles est un automate que l'on peut définir de la façon suivante :
A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, Q ={I, II, III, IV, V}, D = {I}, F = {V}
Si le code d'entrée de Monsieur x est 4834 l'ensemble des transitions de cet automate est :
£ ={(I, 4, II), (II, 8, III), (III, 3, IV), (IV, 4, V)} et le langage reconnu par cette automate est : Laut={4834}.
IV. BIBLIOGRAPHIE
1- A. Bergeron and S. Hamel, Vector Algorithms for Approximate String Matching, International Journal of Foundations of Computer Science (7 avril 2001).
2- D. Gusfield, Algorithms om strings, trees, and sequences, Cambridge University Press , 1999.
3- S. Hamel, Algorithmes vectoriels et bioinformatique, thèse de doctorat, 2002.
4- P. Séébold, Théorie des automates, Vuibert, Paris, 1999.
Par : Yann ARNAUD.
Dans le cadre du cours BIF7002, Séminaire de bioinformatique.
Dernière version: 13 Février 2003.