Alignement local optimal

Le but est à présent de trouver une région de forte homogénéité. On va donc privilégier les alignements locaux, et donc empêcher le non-aligné en affectant des poids négatifs en cas de trous ou de misappariements. Ce sont Smith et Waterman qui proposent un algorithme en 1980 [35]. Après avoir réalisé la matrice de score élémentaire, que l'on appellera $ H$, on complète la matrice de score avec la formule suivante :

$\displaystyle M(i,j) = \max \{(H(i,j) + M(i-1,j-1)), \max_{\substack{k \geq 1}} \{H(i-k,j) - W_{k}\}, \max_{\substack{l \geq 1}} \{H(i,j-l) - W_{l}\}, 0\}
$

avec par exemple :

$\displaystyle W_{k} = 1 + \frac{1}{3}k
$

La matrice obtenue permet de repérer les alignements locaux. Et l'algorithme se fait en temps cubique sur la taille des 2 séquences: quadratique pour visiter toutes les cases de la matrice, et linéaire pour calculer $ M(i,j)$.



Philippe Gambette 2005-06-30