© Dunod – Toute reproduction non autorisée est un délit.
55
5.4 • Alignements multiples
questionnables par le biologiste. Il n’est pas rare d’optimiser « à la main » des
alignements multiples en se basant sur la connaissance biologique apportée par
l’expert du domaine biologique et de la famille de protéine concernée.
De nombreuses approches ont été envisagées pour les alignements multiples dont
la méthode d’alignement prog
it de décomposer la quesressif. En simplifiant, il s’ag
tion de l’alignement simultané de N séquences en N × (N–1)/2 alignements de toutes
les paires possibles puis de grouper les paires en partant tout d’abord des paires les
plus proches pour ensuite diverger.
Soit les quatre séquences A, B, C et D. Les six alignements par paires sont effectués par programmation dynamique et les scores obtenus sont placés sur un arbre des
scores. Plus la distance sur le dendrogramme entre deux lettres est faible, plus les
séquences sont proches.
Ensuite les alignements sont progressivement ajoutés les uns aux autres en partant
des paires ayant les plus fortes ressemblances.
Le point de départ est l’alignement B-D ensuite, l’alignement A-C est agrégé à
l’alignement B-D.
Une des premières façons d’agréger les séquences a été d’écrire chacun des deux
alignements B-D et A-C sous forme d’une séquence. Il suffit ensuite d’aligner les
deux séquences résultantes par programmation dynamique. L’inconvénient de cette
Figure 5.1 – Alignement binaire (par paires).
Figure 5.2 – Alignement multiple progressif.
55
5.4 • Alignements multiples
questionnables par le biologiste. Il n’est pas rare d’optimiser « à la main » des
alignements multiples en se basant sur la connaissance biologique apportée par
l’expert du domaine biologique et de la famille de protéine concernée.
De nombreuses approches ont été envisagées pour les alignements multiples dont
la méthode d’alignement prog
it de décomposer la quesressif. En simplifiant, il s’ag
tion de l’alignement simultané de N séquences en N × (N–1)/2 alignements de toutes
les paires possibles puis de grouper les paires en partant tout d’abord des paires les
plus proches pour ensuite diverger.
Soit les quatre séquences A, B, C et D. Les six alignements par paires sont effectués par programmation dynamique et les scores obtenus sont placés sur un arbre des
scores. Plus la distance sur le dendrogramme entre deux lettres est faible, plus les
séquences sont proches.
Ensuite les alignements sont progressivement ajoutés les uns aux autres en partant
des paires ayant les plus fortes ressemblances.
Le point de départ est l’alignement B-D ensuite, l’alignement A-C est agrégé à
l’alignement B-D.
Une des premières façons d’agréger les séquences a été d’écrire chacun des deux
alignements B-D et A-C sous forme d’une séquence. Il suffit ensuite d’aligner les
deux séquences résultantes par programmation dynamique. L’inconvénient de cette
Figure 5.1 – Alignement binaire (par paires).
Figure 5.2 – Alignement multiple progressif.