Programmation dynamique, récurrences Flashcards
(44 cards)
Quels sont les trois types d’alignements étudiés ?
Alignement global (aligner les séquences entièrement), alignement local (trouver les meilleures sous-séquences), et recherche de motif (trouver un petit motif dans une grande séquence avec erreurs).
Quelle est l’idée de l’alignement global ?
L’alignement global vise à aligner deux séquences S et T dans leur totalité, en minimisant une distance d’édition ou en maximisant une mesure de similarité globale.
Quelle est l’idée de l’alignement local ?
L’alignement local cherche les sous-séquences de S et T qui sont les plus similaires selon une mesure donnée, en ignorant les autres parties.
Quelle est l’idée de la recherche de motif ?
La recherche de motif vise à détecter toutes les occurrences approximatives (avec erreurs) d’un motif court P dans une longue séquence T.
Quel algorithme est utilisé pour l’alignement global avec distance d’édition ?
L’algorithme de Levenshtein calcule le coût minimal pour transformer une chaîne S en une autre chaîne T en utilisant insertion, suppression et substitution.
Quel algorithme est utilisé pour l’alignement global avec similarité ?
L’algorithme de Needleman-Wunsch maximise une mesure de similarité entre deux séquences complètes à l’aide d’un tableau de scores et de pénalités.
Quel algorithme est utilisé pour l’alignement local ?
L’algorithme de Smith-Waterman maximise la similarité entre deux sous-séquences locales à l’aide d’un tableau de scores avec une contrainte d’alignement local.
Quelle est la différence clé entre Needleman-Wunsch et Smith-Waterman ?
Needleman-Wunsch produit un alignement optimal global (des séquences entières) tandis que Smith-Waterman cherche un alignement optimal local (entre sous-séquences).
Quelles sont les conditions d’initialisation pour la distance d’édition (Levenshtein) ?
D(i,0)=i et D(0,j)=j, représentant le coût pour insérer ou supprimer tous les caractères.
Quelles sont les conditions d’initialisation pour l’alignement global par similarité (Needleman-Wunsch) ?
V(i,0) = somme des pénalités pour aligner S[1..i] avec des ‘-’, et V(0,j) pour T[1..j] avec des ‘-’.
Quelles sont les conditions d’initialisation pour l’alignement local (Smith-Waterman) ?
V(i,0) = 0 et V(0,j) = 0, car l’alignement peut commencer n’importe où.
Quelles sont les conditions d’initialisation pour la recherche de motif (approximate matching) ?
D(i,0) = i, car on peut supprimer tous les caractères du motif ; D(0,j) = 0, car on peut commencer n’importe où dans T.
Comment remplir une matrice pour l’alignement global par distance d’édition ?
Pour chaque cellule (i,j), on choisit le minimum entre suppression (haut), insertion (gauche), et substitution (diagonale).
Comment remplir une matrice pour Needleman-Wunsch ?
Chaque cellule (i,j) contient le max entre gauche + pénalité insertion, haut + pénalité suppression, diagonale + score match/mismatch.
Comment remplir une matrice pour Smith-Waterman ?
Pareil que Needleman-Wunsch mais en ajoutant 0 comme option pour permettre de commencer un nouvel alignement local.
Quel est le point de départ pour reconstruire l’alignement dans Needleman-Wunsch ?
La cellule (m,n), coin inférieur droit, est le début de la reconstruction de l’alignement global.
Quel est le point de départ pour reconstruire l’alignement dans Smith-Waterman ?
La cellule contenant la valeur maximale dans toute la matrice représente la fin du meilleur alignement local.
Quel est le point de départ pour la reconstruction du motif approximatif ?
Une cellule dans la dernière ligne correspondant à une distance d’édition inférieure ou égale au seuil k.
Quelle est la récurrence pour l’alignement global par distance d’édition (Levenshtein) ?
D(i, j) = min(D(i−1, j) + 1, D(i, j−1) + 1, D(i−1, j−1) + [0 si Si=Tj, 1 sinon]).
Quelle est la récurrence pour l’alignement global par similarité (Needleman-Wunsch) ?
V(i, j) = max(V(i−1, j) + P(Si,−), V(i, j−1) + P(−,Tj), V(i−1, j−1) + P(Si, Tj)).
Quelle est la récurrence pour l’alignement local (Smith-Waterman) ?
V(i, j) = max(0, V(i−1, j) + P(Si,−), V(i, j−1) + P(−,Tj), V(i−1, j−1) + P(Si, Tj)).
Quelle est la récurrence pour la recherche de motif (approximate pattern matching) ?
D(i, j) = min(D(i−1, j) + 1, D(i, j−1) + 1, D(i−1, j−1) + [0 si Pi=Tj, 1 sinon]).
Quelle est la récurrence du problème de la monnaie ?
C[i, j] = min(C[i−1, j], C[i, j−vi] + 1), en considérant la i-ème pièce.
Quelle est la récurrence du problème du sac à dos 0-1 ?
V[i, j] = max(V[i−1, j], V[i−1, j−wi] + vi), on choisit de prendre ou non l’objet i.
