|
Analyse
bioinformatique des séquences
L'algorithme de Smith et Waterman Une des méthodes d'alignement local les plus utilisées fut introduite par Smith et Waterman (1981). La différence essentielle avec l'algorithme de Needleman et Wunsch que nous venons de décrire est que n'importe quelle case de la matrice de comparaison peut être considérée comme point de départ pour le calcul des scores sommes et que tout score somme qui devient inférieur à zéro stoppe la progression du calcul des scores sommes. La case pointée est alors réinitialisée à zéro et peut être considérée comme nouveau point de départ. Cela implique que le système de scores choisi possède des scores négatifs pour les mauvaises associations qui peuvent exister entre les éléments des séquences. L'équation utilisée pour le calcul de chaque score somme pendant la transformation de la matrice initiale prend alors l'expression suivante:  où S(i,j) est le score somme de la case d'indice i et j, se le score élémentaire de la case d'indice i et j de la matrice initiale et P la pénalité donnée pour une insertion. La Figure ci-dessous illustre un tel alignement.  Ce genre de méthode est souvent considéré comme plus sensible que celles directement inspirées de Needelman et Wunsch surtout lorsque les séquences à comparer sont inconnues ou de longueurs différentes. De plus, si les régions trouvées entre les deux séquences recouvrent la totalité de celles-ci, alors on peut considérer l'alignement local comme étant un alignement global. |
