Algorithmes d'alignement de séquences

Les algorithmes d'alignement de séquences mesurent et affichent la similarité entre deux chaînes de caractères en déterminant la transformation la moins coûteuse de l'une en l'autre, en utilisant la programmation dynamique pour les insertions, les suppressions et les substitutions.

Definition

L'alignement de séquences est l'agencement de deux (ou plusieurs) chaînes de caractères afin de maximiser leur correspondance en insérant des lacunes (gaps) et en faisant correspondre, en ne faisant pas correspondre ou en substituant des caractères ; un algorithme d'alignement calcule un alignement optimal et son score selon un modèle de coût ou de score donné, généralement via la programmation dynamique.

Scope

Ce sujet aborde les algorithmes de programmation dynamique pour la comparaison de chaînes de caractères : la distance d'édition (Levenshtein) et la plus longue sous-séquence commune, l'alignement global (Needleman-Wunsch), l'alignement local (Smith-Waterman), ainsi que les schémas de score (pénalités d'écart, matrices de substitution) qui façonnent les alignements biologiques. Il traite de la récurrence sous-jacente et de son coût quadratique en temps et en espace, ainsi que des améliorations permettant d'économiser de l'espace. Les méthodes basées sur des index et la correspondance exacte sont abordées dans des sujets connexes.

Core questions

• Comment la similarité entre deux chaînes de caractères est-elle quantifiée en tant que distance d'édition ou score d'alignement ?
• Comment une table de programmation dynamique calcule-t-elle un alignement optimal ?
• Qu'est-ce qui distingue l'alignement global de l'alignement local, et quand chacun est-il approprié ?
• Comment les pénalités d'écart et les matrices de substitution influencent-elles l'alignement résultant ?
• Comment l'exigence d'espace quadratique peut-elle être réduite pour les longues séquences ?

Key concepts

• distance d'édition (Levenshtein)
• plus longue sous-séquence commune
• alignement global
• alignement local
• algorithme de Needleman-Wunsch
• algorithme de Smith-Waterman
• pénalités d'écart
• matrices de substitution

Key theories

Alignement global par programmation dynamique

L'algorithme de Needleman-Wunsch remplit une table de programmation dynamique dont les entrées donnent le meilleur score d'alignement des préfixes de chaînes, produisant un alignement optimal de bout en bout (global) de deux séquences en un temps proportionnel au produit de leurs longueurs.

Alignement local pour les sous-séquences partagées

L'algorithme de Smith-Waterman modifie la récurrence pour permettre aux alignements de commencer et de se terminer n'importe où, trouvant la région de correspondance la mieux notée (alignement local), ce qui est essentiel pour détecter les fragments conservés au sein de séquences par ailleurs dissemblables.

Clinical relevance

L'alignement de séquences est une pierre angulaire de la biologie computationnelle, utilisé pour comparer les séquences d'ADN, d'ARN et de protéines à des fins d'homologie, d'inférence évolutive et de recherche dans des bases de données (l'heuristique BLAST s'appuie sur l'alignement local). En dehors de la biologie, le même mécanisme de distance d'édition est à la base de la correction orthographique, de la correspondance de texte approximative (fuzzy text matching), des différences de contrôle de version (diffs) et de la comparaison de la parole et de l'écriture manuscrite.

History

Levenshtein a introduit la distance d'édition en 1965. Needleman et Wunsch ont présenté le premier algorithme d'alignement global par programmation dynamique pour les protéines en 1970, et Smith et Waterman ont introduit l'alignement local en 1981. La technique à espace linéaire de Hirschberg (1975) et des heuristiques ultérieures telles que BLAST ont étendu l'alignement à une utilisation pratique à grande échelle.

Key figures

• Saul Needleman
• Christian Wunsch
• Temple Smith
• Michael Waterman
• Vladimir Levenshtein

Seminal works

• needleman1970
• smith1981
• gusfield1997

Frequently asked questions

Quelle est la différence entre l'alignement global et l'alignement local ?

L'alignement global (Needleman-Wunsch) aligne deux séquences de bout en bout et est approprié lorsqu'elles sont de longueur similaire et qu'elles sont censées être apparentées sur toute leur étendue. L'alignement local (Smith-Waterman) trouve la sous-région la mieux correspondante et est approprié lorsque seules des parties des séquences sont similaires, comme un domaine conservé au sein de séquences plus grandes.

L'alignement de séquences est-il identique à la plus longue sous-séquence commune ?

Ils sont étroitement liés. La plus longue sous-séquence commune est un cas particulier d'alignement avec un score spécifique (les correspondances sont récompensées, les lacunes sont gratuites, les non-correspondances sont interdites). L'alignement général utilise un score plus riche avec des coûts de substitution et des pénalités d'écart, mais les deux sont résolus par le même type de récurrence de programmation dynamique.