Et ailleurs, chez nos amis

Sommaire

Principes de l'algorithme
 Initialisation
 Remplissage de la matrice
 Déterminer l'alignement optimal
 L'algorithme
 Le programme
 Le module de manipulation de matrices

Principes de l'algorithme

Dans un autre article de ce site sont présentés des algorithmes de recherche d’un mot dans un texte, notamment celui de Knuth-Morris-Pratt (KMP). Ces algorithmes sont dévolus au problème de la recherche exacte : il s’agit de trouver, si elle existe, la première occurrence exacte de ce mot dans ce texte.

Nous allons maintenant étudier, parce que c’est un problème central en bioinformatique, une recherche approximative : il s’agit de savoir si deux mots se ressemblent, quel est leur degré de ressemblance, ou de trouver, dans un ensemble de mots, celui qui ressemble le plus à un mot-cible. Et nous allons voir que ce problème relève de solutions très différentes de celles qui valent pour la recherche exacte.

Notons d’abord que la ressemblance est une notion imprécise : la plupart des algorithmes utilisés proposent différents paramètres pour ajuster les facteurs de ressemblance aux caractéristiques du problème traité.

Les algorithmes utilisés fournissent en général deux résultats :

• pour chaque comparaison de deux chaînes, un score de ressemblance, qui permet ensuite de trouver la meilleure ressemblance parmi un ensemble de comparaisons ;
• un alignement des deux chaînes (qui n’ont pas forcément la même longueur) selon la configuration qui procure le meilleur score ; on dit bien un alignement, et non pas l’alignement, parce qu’en effet, comme nous le verrons plus loin, le problème peut admettre plusieurs solutions conduisant au même score.

Le plus caractéristique de cette famille d’algorithmes est peut-être celui de Needleman et Wunsch, que nous étudierons ici ; il réalise un alignement global de deux séquences (chaînes de caractères).

Calculer un alignement global peut être coûteux si les séquences à aligner sont longues, ou s’il y en a beaucoup. D’autres algorithmes, qui ressemblent à celui-ci, ont été conçus pour limiter la taille du problème en ne réalisant l’alignement que pour des régions « intéressantes ». La détermination des régions intéressantes est bien sûr en elle-même un problème intéressant. Citons l’algorithme de Smith et Waterman, qui réalise des alignements locaux, et le logiciel BLAST¹, qui mettent en oeuvre des méthodes similaires à celles de Needleman et Wunsch, après des optimisations éventuellement complexes.

Le problème de la comparaison de séquences est exponentiel, la solution est en O(kⁿ) ; ces algorithmes sont susceptibles d’une multiplicité de solutions ; une des techniques les plus généralement utilisées pour en réduire la complexité est la programmation dynamique, qui fait l’objet d’un autre article sur ce site.

La programmation dynamique résout des problèmes en combinant des solutions de sous-problèmes. (Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein, Introduction à l’algorithmique)

L’idée de la programmation dynamique est de mémoriser les résultats de calculs intermédiaires qui seront probablement répétés. La programmation dynamique est par exemple souvent un bon choix lorsque l’on aura besoin, après les avoir calculées, des valeurs stockées dans tous les noeuds d’un arbre ou dans toutes les cases d’un tableau. Parfois aussi cette conservation des résultats intermédiaires est imposée par un problème tel que le calcul d’une valeur se fait en fonction de toutes les précédentes. L’art algorithmique consiste à chercher des solutions qui évitent ce type de contrainte mais c’est parfois impossible. Et puis il y a des problèmes intrinsèquement récursifs pour lesquels n’existe pas d’algorithme itératif.
Nous allons donc chercher des procédés pour associer un algorithme qui calcule des valeurs successives avec une structure de données qui les archive.

Cette section doit beaucoup au travail préalable de William Saurin pour cet enseignement, ainsi qu’à une page créée par Eric C. Rouchka, de l’université Washington à Saint-Louis, et reprise par Per Kraulis au Stockholm Bioinformatics Center :

http://www.sbc.su.se/~pjk/molbioinf...

Supposons que nous souhaitions calculer un alignement global de deux séquences :
séquence n° 1 : G A A T T C A G T T A
séquence n° 2 : G G A T C G A
La séquence n° 1 a m=11 résidus, la séquence n° 2 n=7 résidus.

Nous allons ici étudier l’algorithme avec des paramètres particulièrement simples, peut-être même simplistes : pénalité nulle pour les trous (gaps)’Aubervilliers du 19 mars au 5 avril 2014.

Plus d’infos : www.cnt.fr

et les discordances (substitutions), une pénalité négative, ou prime, égale à 1 pour les concordances (matches). Le but est d’acquérir une vue d’ensemble de l’architecture de la solution, qui permettra au lecteur d’envisager ensuite des exemples plus compliqués, avec des formules de calcul plus élaborées pour les scores et pour les pénalités de gap.

Le principe de pondération que nous adopterons sera le suivant :

• la « prime de score » pour la comparaison du résidu de rang i de la première séquence avec le résidu de rang j de le seconde séquence sera S_i,j = 1 si les deux résidus sont identiques, sinon :
• S_i,j = 0 (score de discordance) ;
• w = 0 (pénalité de gap).

L’algorithme opère en trois étapes :

• initialisation ;
• calcul des scores et remplissage de la matrice ;
• calcul de l’alignement en « remontant » dans la matrice.

Initialisation

Création d’une matrice M de m+2=13 colonnes et n+2=9 lignes : la ligne et la colonne de rangs 0 contiendront les textes des séquences, la seconde ligne (de rang 1, les M_1,j) et la première colonne (les M_i,1) de M sont remplies de 0 parce que nous avons posé qu’il n’y avait pas de pénalités pour des gaps initiaux ou finals.

     G   A   A   T   T   C   A   G   T   T   A 

   0  0 0 0 0 0 0 0 0 0 0 0

 G  0                      

 G  0                      

 A  0                      

 T  0                      

 C  0                      

 G  0                      

 A  0