4-AlignementMultiple

Question 1

Quel est le problème principal lié à l’étiquetage des nœuds internes d’un arbre phylogénétique T?

Answer 1

Minimiser le score de T (somme des poids des arêtes)

Un étiquetage optimal est appelé alignement phylogénétique.

Question 2

Qu’est-ce qu’un alignement phylogénétique?

Answer 2

Un arbre T avec étiquetage de ses nœuds internes

Il induit un alignement de S consistant avec T.

Question 3

Le problème de l’étiquetage est classé comme NP-complet. Vrai ou faux?

Answer 3

VRAI

Cela signifie qu’il n’existe pas de solution efficace connue pour ce problème.

Question 4

Qu’est-ce qu’un alignement consistant avec un arbre T?

Answer 4

Alignement multiple de S tel que pour tout couple de séquences S_i, S_j reliées par une arête, S_i et S_j sont alignées de façon optimale

Cela garantit que l’alignement respecte la structure de l’arbre.

Question 5

Quelle est la complexité d’alignement pour k séquences de taille n?

Answer 5

O(kn²)

Cela reflète le coût computationnel de l’alignement multiple.

Question 6

Qu’est-ce qu’un arbre étoile?

Answer 6

Un arbre connectant toutes les séquences de S, avec une racine S_c

S_c est la séquence centrale qui minimise la somme des distances à toutes les autres séquences.

Question 7

Comment est calculée la complexité pour trouver la séquence centrale S_c?

Answer 7

O(k²n²)

Cela implique de calculer les distances entre toutes les paires de séquences.

Question 8

Qu’est-ce qu’une heuristique bornée?

Answer 8

Algorithme qui n’est pas garanti d’obtenir la solution optimale, mais dont on sait dans quel intervalle se situe la solution

Utilisée pour des problèmes difficiles comme ceux de type NP-complet.

Question 9

Quel est le score d’un alignement multiple A par rapport à un alignement optimal A*?

Answer 9

Au plus deux fois plus élevé que le score d’un alignement optimal

Cela garantit une approximation raisonnable.

Question 10

Quel est le rôle de l’algorithme de Carillo & Lipman en 1988?

Answer 10

Calculer les alignements optimaux pour chaque paire de séquences

Il a été implémenté dans MSA pour améliorer l’efficacité des alignements.

Question 11

Qu’est-ce que la méthode d’alignement par points d’ancrage?

Answer 11

Basée sur la recherche de motifs communs à une majorité de séquences

Exemple: MACAW, qui divise le problème en parties gauche et droite par rapport au motif.

Question 12

Quelle est la complexité de l’alignement optimal d’un sous-arbre de racine v?

Answer 12

O(k²n²)

Cela inclut le calcul des distances entre les séquences.

Question 13

Qu’est-ce que le score SP d’un alignement multiple A?

Answer 13

Score d’un alignement optimal de S_i et S_j

Il est utilisé pour évaluer la qualité de l’alignement.

Question 14

Quel est le but de l’algorithme de Barton-Stenberg (MultAlign)?

Answer 14

Choisir l’alignement de score max et construire une matrice consensus

Il itère jusqu’à épuisement des séquences.

Question 15

La complexité de l’algorithme pour calculer tous les D(Si,Sj) est de _______.

Answer 15

O(k²n²)

Cela se produit lors d’un prétraitement.

Question 16

Pour chaque nœud v, le calcul de d(v,S) a une complexité de _______.

Answer 16

O(k)

La complexité totale devient O(k²n² + k³).

Question 17

L’alignement phylogénétique optimal est noté T* et on veut construire un alignement soulevé TS à partir de _______.

Answer 17

T*

Dans TS, v est étiqueté par la séquence de S la plus proche de Sv*.

Question 18

Le score de TS est inférieur ou égal à _______ fois le score de T*.

Answer 18

2

Cela indique une relation entre les scores d’alignement.

Question 19

Nommez quelques outils d’alignement multiple utilisés dans l’alignement phylogénétique.

Answer 19

• MultAlign
• ClustalW
• Pileup
• T-Coffee
• DIALIGN

Ces outils diffèrent principalement par la méthode de construction de l’arbre guide.

Question 20

L’algorithme ClustalW utilise la méthode de _______ pour construire un arbre guide.

Answer 20

Neighbour-Joining

Cet algorithme est le plus utilisé pour le calcul des scores d’alignement.

Question 21

L’alignement d’une séquence avec une matrice consensus utilise une méthode _______.

Answer 21

itérative

Cela implique d’améliorer un alignement de basse qualité par des itérations.

Question 22

La complexité de l’alignement optimal entre S[1..i] et C[1..j] est de _______.

Answer 22

O(|S| mn)

Ici, n est le nombre de colonnes de C et m est la taille de S.

Question 23

Le score d’un alignement optimal D(i,j) est calculé comme suit : D(i,j) = max [D(i-1,j-1) + p(Si,Cj), D(i-1,j) + p(Si,-), D(i,j-1) + p(-,Cj)]. Vrai ou faux?

Answer 23

VRAI

Cela décrit la formule de calcul du score d’alignement optimal.

Question 24

Le score d’appariement entre S[i] et T[j] est noté _______.

Answer 24

c(i,j)

Cela fait partie du calcul du score d’alignement.

Question 25

Les méthodes itératives sont souvent utilisées pour résoudre le problème des alignements intermédiaires **figés**. Vrai ou faux?

Answer 25

VRAI ## Footnote Ces méthodes permettent d'améliorer les alignements en évitant la rigidité.

Question 26

Le score d'un alignement optimal D(i,j,k) est calculé en examinant _______ cases voisines.

Answer 26

7 ## Footnote Cela inclut des calculs basés sur les distances d'édition avec pondération.

Question 27

What is the **purpose** of **multiple alignment**?

Answer 27

* Trouver des contraintes de structures pour les ARN * Trouver des caractéristiques communes à une famille de protéines * Caractériser les régions conservées et les régions variables * Relier la séquence à la structure et à la fonction * Reconstituer des phylogénies * Sélectionner des séquences homologues * Trouver un alignement multiple * L’utiliser pour construire l’arbre phylogénétique * Inférer des scénarios d’évolution ## Footnote L’alignement multiple joue un rôle central pour comprendre les relations entre fonction, évolution, séquence et structure d’une famille de gènes ou de protéines.

Question 28

True or false: The **score SP** is the most commonly used score for alignment.

Answer 28

TRUE ## Footnote Le score SP a de bonnes propriétés théoriques et pratiques.

Question 29

What does the **score SP** of an alignment represent?

Answer 29

La somme des scores des alignements induits pour chaque paire de séquences dans A ## Footnote C'est une généralisation du score utilisé pour l’alignement de deux séquences.

Question 30

Fill in the blank: Un bon alignement reflète le **modèle d’évolution** qui a donné lieu aux séquences, en supposant que les séquences à aligner descendent d’un _______.

Answer 30

ancêtre commun ## Footnote Les séquences ont évolué par mutations ponctuelles.

Question 31

What are the **usual heuristics** for multiple alignment?

Answer 31

* Méthodes progressives * Méthodes itératives * Méthodes par point d’ancrage ## Footnote Ces méthodes sont utilisées pour résoudre le problème d’alignement multiple.

Question 32

What is the **complexity** of the exact solution for multiple alignment?

Answer 32

O(n^m) ## Footnote Très inefficace dès que m > 5 et n ~ 100.

Question 33

What is the **alignment matrix** A in multiple alignment?

Answer 33

A = (a_ij), 1 ≤ i ≤ k; 1 ≤ j ≤ l ## Footnote a_ij symboles de l’alphabet ou ‘-’, où la concaténation des caractères à la ligne i produit S_i.

Question 34

What is the **goal** of multiple alignment?

Answer 34

* Trouver des contraintes de structures pour les ARN * Caractériser les régions conservées et les régions variables * Relier la séquence à la structure et à la fonction * Reconstituer des phylogénies ## Footnote L’alignement multiple aide à comprendre les relations entre fonction, évolution, séquence et structure.

Question 35

What is the **NP-complete** problem in multiple alignment?

Answer 35

Trouver un alignement multiple ayant un score SP minimum ## Footnote Ce problème a été identifié par Wang et Jiang en 1994.

Question 36

What is the **importance** of weighting in multiple alignment?

Answer 36

Garder l’alignement qui produit l’arbre de poids minimal ## Footnote La pondération d’un alignement multiple est essentielle pour la construction d’arbres phylogénétiques.

Question 37

What does the **function G** represent in multiple alignment?

Answer 37

Une fonction de pondération des indels ## Footnote La pondération affine est souvent utilisée, avec un coût supérieur pour l’ouverture d’un « gap » que pour son élongation.