Introduction à la bioinformatique

Mohamed NEJI
Sommaire
 Introduction à la bioinformatique
 Notions de base
 Alignement 2 à 2 de séquences
 Alignement multiple de séquences
 Phylogénie

2
Sommaire
 Introduction à la bioinformatique
 Bio-informatique?
 Notions de biologie moléculaire
 Notions de base
 Alignement 2 à 2 de séquences
 Alignement multiple de séquences
 Phylogénie

3
Bioinformatique ?
 Champ de recherche multi-disciplinaire
 où travaillent de concert biologistes, informaticiens, mathématiciens,
physiciens, chimistes…
 objectif : résoudre un problème scientifique posé par la biologie.
 Décrit également (par abus de langage) toutes les applications
informatiques résultant de ces recherches.
 l'analyse du génome
 modélisation de l'évolution d'une population animale,
 modélisation moléculaire,
 analyse d'image,
 séquençage du génome,
 reconstruction d'arbres phylogénétiques (phylogénie)…
 Cette discipline constitue la « biologie in silico », par analogie
avec in vitro ou in vivo. 4
Biologie moléculaire (cf. wikipedia) ?
 La biologie moléculaire est une discipline scientifique au croisement de la
génétique, de la biochimie et de la physique, dont l'objet est la
compréhension des mécanismes de fonctionnement de la cellule au niveau
moléculaire. Le terme « biologie moléculaire », utilisé la première fois en
1938 par Warren Weaver, désigne également l'ensemble des techniques de
manipulation d'acides nucléiques (ADN, ARN), appelées aussi techniques de
génie génétique.
 La biologie moléculaire est apparue au XXe siècle, à la suite de l'élaboration
des lois de la génétique, la découverte des chromosomes et l'identification
de l'ADN comme support chimique de l'information génétique.
 Après la découverte de la structure en double hélice de l'ADN en 1953 par
James Watson (1928- ), Francis Crick (1916-2004), Maurice Wilkins (1916-
2004) et Rosalind Franklin (1920-1958) la biologie moléculaire a connu
d'importants développements pour devenir un outil incontournable de la
biologie moderne à partir des années 1970.

5
Corps – cellules - atomes

Chaque diagramme représente

une image grossie d’un facteur
10 de la précédente :
Un doigt 
La peau 
Cellules de la peau 
Structure des cellules 
Structure d’une mitochondrie
Structure d’un ribosome 
Structure de 2 protéines 
Les protéines sont constituées
d’atomes

6
La cellule

1. Nucléole
8. Réticulum endoplasmique lisse
2. Noyau
9. Mitochondrie
3. Ribosome
10. Vacuole
4. Vésicule
11. Cytoplasme
5. Réticulum endoplasmique rugueux (granuleux)
12. Lysosome
6. Appareil de Golgi
13. Centrosome
7. Microtubule

7
Les chromosomes
L’ information génétique est contenue
dans les chromosomes situés dans le
noyau des cellules*

Chaque cellule d’un être humain

comporte 23 paires de chromosomes

Un chromosome est constitué de

molécules d'ADN

* chez les eucariotes seulement. Pour les organismes

procaryotes (organismes unicellulaires), les chromosomes
se trouvent dans le cytoplasme.
8
ADN
 ADN est l'abréviation d'acide désoxyribonucléique :
 contient sous forme codée toutes les informations relatives à la vie d'un
organisme vivant, du plus simple au plus complexe, animal, végétal,
bactérien, viral.
 La fonction de l'ADN est de fabriquer les protéines dont l'organisme a
besoin. Les protéines ainsi formées ont différentes fonctions que l'on
peut simplifier en les ramenant à deux essentielles :
 l'autonomie de l'organisme (sa croissance, sa défense)
 sa reproduction
 L'ADN contient donc toutes les informations susceptibles de
créer et de faire vivre un organisme.
 Si le contenu de la molécule d’ADN humaine était mise sous forme d'une
encyclopédie, il faudrait à peu près 500 volumes de 800 pages chacun.
 Si on étend entièrement l’ADN humain, il mesure + de 1,2 mètre

9
ADN : Taille des génomes
Mycoplasma genitalium : 0,6 Mb

Escherichia coli : 4,7 Mb Procaryotes

Saccharomyces. cerevisiae : 13,5 Mb Eucaryotes

C. elegans : 100 Mb

Fugu rubripes : 400 Mb

Homo sapiens : 3400 Mb

Amphibiens : 100 000 Mb

Amoeba dubia : 700 000 Mb

10
ADN
 Une molécule d'ADN se présente sous la forme d'une double
hélice enroulée
 macromolécule de millions/milliards d'atomes. C'est un motif identique
tout le temps répété contenant :
 des phosphates
 des sucres (désoxyribose)
 des bases azotées
 Cas du corps humain
 Dans l'ensemble des 23 paires de
chromosomes, on compte à peu près
trois milliards de bases azotées
 L’ADN humain est composée de
150 milliards d’atomes

11
ADN
 Différenciation des motifs : nature de la base azotée
 Le sucre et le phosphate ne sont pas variables
 4 bases azotées :
 Adénine (A) A C G T
 Cytosine (C)
 Guanine (G)
 Tyrosine(T)
 Propriétés :
 Support de l'hérédité (par réplication)
 Peut subir des modifications (mutations)
 Naturelles, ou via des facteurs mutagènes (radioactivité, UVs...)
 Recombinaisons génétiques (reproduction sexuée, transformation
génétique de bactéries ou artificiellement - OGMs)

12
ADN → Protéines
 Par interaction avec l'environnement, l'ADN se transforme en
protéines :
 La transcription, transfert de l'ADN vers une autre molécule, l'ARN
 La traduction, transfert depuis l'ARN vers des protéines
 L'activité des protéines détermine l'activité des cellules
 qui vont ensuite déterminer le fonctionnement des organes et de
l'organisme
 Traduction de l’ADN en protéine :
 Les quatre lettres A, C, G et T s'associent en mots de trois lettres (GGA,
CTA...) pour former un codon. Des ribosomes décodent ces codons en
acides aminés combinées pour former des protéines

13
ADN → Protéines

14
ADN → Acides aminés
 20 Acides aminés :
 Acide aspartique
 Acide glutamique
 Alanine
 Arginine
 Asparagine
 Cystéine
 Glutamine
 Glycine
 Histidine
 Isoleucine
 Leucine
 Lysine
 Phénylalanine
 Proline
 Sérine
 Thréonine
 Tryptophane
 Tyrosine
 Valine
 Méthionine/Start
 Stop
15
ADN → Acides aminés
 Acides aminés : codes à 1 et 3 lettres
 Acide aspartique (D, Asp)  Leucine (L, Leu)
 Acide glutamique (E, Glu)  Lysine (K, Lys)
 Alanine (A, Ala)  Méthionine (M, Met)
 Arginine (R, Arg)  Phénylalanine (F, Phe)
 Asparagine (N,Asn)  Proline (P, Pro)
 Cystéine (C, Cys)  Sérine (S, Ser)
 Glutamine (Q, Gln)  Thréonine (T, Thr)
 Glycine (G, Gly)  Tryptophane (W, Trp)
 Histidine (H, His)  Tyrosine (Y, Tyr)
 Isoleucine (I, Ile)  Valine (V, Val)

 Codon Stop : marque la fin de la traduction d'un gène en protéine. Il n'est en général
jamais traduit car il n'existe pas d'ARN de transfert correspondant (il existe 2 acides
aminés supplémentaires, la sélénocystéine et la pyrrolysine qui sont insérés lorsqu'un
codon STOP particulier est rencontré).

16
Structure des protéines
 La structure des protéines est la composition en acides aminés et la
conformation en trois dimensions des protéines. Elle décrit la position relative
des différents atomes qui composent une protéine donnée.
 Structure primaire : succession linéaire des acides aminés la constituant
Gly-Ile-Val-Glu-Gln-Cys-Cys-Ala-Ser-Val-Cys-Ser

 Structure secondaire : décrit le repliement local de la chaîne principale d'une

protéine. 2 structures principales : hélice alpha et feuillet beta.

Helice 

17
Structure des protéines
 Structure tertiaire : correspond au repliement de la chaîne
polypeptidique dans l'espace (structure 3D).
 La structure 3D d'une protéine est
intimement liée à sa fonction : lorsque
cette structure est cassée, la protéine
perd sa fonction (elle est dénaturée)

 Structure quaternaire : regroupe l'association

d'au moins deux chaînes polypeptidiques
(structure 3D + liens internes).

18
Séquençage de l’ADN
 Séquençage de l’ADN :
 Consiste à déterminer l'ordre d'enchaînement des nucléotides d’un
fragment d’ADN donné
 Techniques de séquençage apparues fin des années 70 (séquenceurs
automatiques : années 90)
 Méthodes de Sanger et de Gilbert
 Prix nobel de chimie en 1980
 Sanger (UK) : Synthèse enzymatique sélective
 Gilbert (USA) : Dégradation chimique sélective
 Méthode de Sanger souvent utilisée actuellement
 méthode de Gilbert : limites de taille, toxicité, difficile à mettre en œuvre
 premier organisme séquencé en 1977 : virus bactériophage X174

19
Séquençage de l’ADN
 Séquencage d’un génome complet :
 Séquencage de fragments
 Reconstitution du génome complet par alignement des séquences
 Séquençage du génome humain :
 Décidé en 1980, initié en 1987 avec 400 marqueurs connus, soit 1/10
Mb
 Réalisé chromosome par chromosome
 Chromosome 22 publié en 1999
 Chromosome 21 publié en 2000
 Ébauche du génome humain en Juin 2000
 Séquence complète publiée en avril 2003
 Actuellement
 Séquençage d’autres espèces (souris, chimpanzé…)
 Bactéries, microbes, végétaux etc…

20
Sommaire
 Introduction à la bioinformatique
 Notions de base
 Alignement 2 à 2 de séquences
 Alignement multiple de séquences
 Phylogénie

21
Vocabulaire - récapitulatif
 Les êtres humains sont composés de cellules dans le noyau
desquelles se trouvent les chromosomes constitués d'ADN - cet
ADN défini des gènes
 L'information de l'ADN est contenue dans une suite de bases
azotées (composée de quatre lettres A, T, C et G)
 Un codon est composé de 3 bases azotées
 Un codon peut être traduit en un acide aminé
 En assemblant plusieurs acides aminés, on obtient des protéines
 Les gènes représente l'ADN qui spécifie une unité d'information
génétique (≠protéines)
 Les chromosomes sont constitués de gènes
 L'ensemble des chromosomes d'un individu est le génome

22
Définitions - Alphabet
 Alphabet
 Définition : un alphabet Σ est un ensemble fini de symboles distincts {a0,
a1, …, an}. Dans le cas de séquences d'ADN ou d'acides aminés on définit
a0 comme étant le symbole vide ou gap et est représenté par le
caractère « - »
 Alphabet de l’ADN (bases azotées)
 L’alphabet des molécules d’ADN est composé de 5 symboles: ΣADN =
{−,A,C,G,T}
 {−,A,C,G,T} représentent respectivement un gap, l’Adénine, la Cytosine,
la Guanine et la Thymine
 Alphabet des Acides aminés
 L’alphabet des acides aminés est composé de 21 symboles
ΣAA ={−,A,C,D,E,F,G,H,I,K,L,M,N,P,Q,R,S,T,V,W,Y} qui représentent les
différents acides aminés

23
Définitions - Séquences
 Séquence : On appelle séquence S une suite ordonnée de
caractères S = <x1, x2, . . . , xn> pris dans un alphabet
 On note |S| = n la longueur de la séquence
 Sous-séquence : Soit S une séquence de longueur n. On appelle
sous-séquence de S toute partie de S composée d’un ensemble
de caractères consécutifs de S
 On notera S[i..j] avec 1 ≤ i ≤ j ≤ n, la sous-séquence
<xi, xi+1, . . . , xj>. En particulier S[i..i] = S[i] = <xi>
 Préfixe d’une séquence : Soit S une séquence de longueur n. On
appelle préfixe de S toute sous-séquence S[1..p] de longueur p
telle que 1 ≤ p < n

24
Généralités – événement mutationnel
 On part du postulat que l’ensemble des espèces actuelles se
sont différenciées au fil du temps grâce à des événements
mutationnels
 3 événements mutationnels élémentaires
 substitution AGACT  AGATT
 insertion AGACT  AGACAT
 délétion AGACT  AGAT

 La réalité est sensiblement plus complexe :

 Substitution/insertion/délétion par bloc
 probabilités différentes pour chaque événement mutationnel
 Taux de mutation sensible aux conditions extérieures…

25
Sommaire
 Introduction à la bioinformatique
 Notions de base
 Alignement 2 à 2 de séquences
 Introduction / Score d’un alignement
 Formulation / Résolution exacte
 Alignement global : Needlemann-Wunsch
 Alignement local : Smith-Waterman
 Modèles de gaps : autres alignements 2 à 2
 Alignement multiple de séquences
 Phylogénie

26
Alignement de séquences
 Alignement de séquences d'ADN (ou d’acides aminés) :
 opération de base en bio-informatique qui a pour but d'identifier des
zones conservées entre séquences.

CAGCA-CTTGGATTCT-GG
CAGC---TTG--TACTCGG
 Utilité de l'alignement :
 identifier des sites fonctionnels
 prédire la ou les fonctions d'une protéine
 prédire la structure secondaire (voire tertiaire ou quaternaire) d'une
protéine
 établir une phylogénie (évolution: parenté entre les organismes)

27
Alignement de séquences
 On distingue 2 types d'alignements qui diffèrent suivant leur complexité :
 l'alignement par paires : consiste à aligner 2 séquences peut être réalisé grâce à
un algorithme de complexité polynomiale. Il est possible de réaliser un
alignement :
 global, c'est à dire entre les 2 séquences sur toutes leurs longueurs
 local entre une séquence et une partie de l'autre séquence
 l'alignement multiple, qui est un alignement global : consiste à aligner plus de 2
séquences et nécessite un temps de calcul et un espace de stockage exponentiel
en fonction de la taille des données

 Alignement de genres différents :

 Alignement de séquences d’ADN CAGCACTTGGATTCT-GG---

 Alignement de séquences CAGC--TTG--TACTCGGATT

d’acides aminés RDI--SLVKNA---GIVNADI
RNILVS---DAKNVGIVN-DI

28
Alignement de séquences
 Alignement = Mise en correspondance de deux séquences (ADN
ou protéines)
 3 événements mutationnels élémentaires
 substitution AGACT  AGATT
 insertion AGACT  AGACAT
indel
 délétion AGACT  AGAT

 Score d'une opération

 substitution : score de similarité
 indel : pénalité
 Le score de l'alignement est la somme des scores élémentaires

29
Somme des paires
 Le score d'un alignement par paires A(S1,S2) est donné
par une formule w de somme des paires :
q
w( A(S1, S2 ))   w(a , a ), avec A(S1, S2 )  q
i
1
i
2
i1

 Exemple (Mismatch: -1, Match: 3, Indel: -2) :

A C C G A T G A
A C – G C T - A
3 +3 -2 +3 -1 +3 -2 +3 = 10

30
Somme des paires
 Exemple (Mismatch: -1, Match: 2, Indel: -4) :
A G T T G T T C
T G – G G T A C
-1 +2 -4 -1 +2 +2 -1 +2 = 1

- A C G T
 Exemple (matrice de substitution) : - -4 -4 -4 -4

 Favorise les mutations AT et GC A -4 5 -2 -2 -1

C -4 -2 5 -1 -2
 Favorise le match du nucléotide T
G -4 -2 -1 5 -2
T -4 -1 -2 -2 7

A G T T G T T C
T G – G G T A C
-1 +5 -4 -2 +5 +7 -1 +5 = 14

31
Alignement de séquences
 2 séquences  plusieurs alignements possibles
CAGC----ACTTGGATTCTGG CAGCACTTGGATTCT-GG---
7 CAGCTTGTACTCGGATT---- CAGC--TTG--TACTCGGATT 7
CAGCACTTGGATTCTGG---
CAGC--TTGTACTC-GGATT 10

 Bon/mauvais alignement ? matrices de substitutions

 Exemple :
 Mismatch : -1 - A C G T
 Match : 2 - -2 -2 -2 -2
 Indel : -2 A -2 2 -1 -1 -1
C -2 -1 2 -1 -1
G -2 -1 -1 2 -1
T -2 -1 -1 -1 2

32
Matrices de substitution
 Matrices nucléiques
 Il existe peu de matrices pour les acides nucléiques car il n'y a que 5 lettres pour
leur alphabet
 La plus fréquemment utilisée est la matrice dite unitaire (ou matrice identité) où
toutes les bases sont considérées comme équivalentes

- A C G T
- 0 0 0 0
A 0 1 0 0 0 Match : 1
Mismatch : 0
C 0 0 1 0 0
Indel : 0
G 0 0 0 1 0
T 0 0 0 0 1

 Matrices des acides aminés : beaucoup plus complexe !

 Pam [1978], Blosum [1992], Gonnet [1992]…
 Basées sur: nombres de mutation nécessaires pour changer d’acide aminé,
propriétés physico-chimiques, évolution…
 Page d'Emmanuel Jaspard sur les matrices de substitution 33
Formulation
■ Définition : Alignement par paire
– Soit un alphabet Σ
– Soit S = {S1, S2} 2 séquences de caractères de Σ
– Un alignement de S, noté A(S1, S2) est une matrice 2*q
• Chaque élément au,v de la matrice a est défini dans Σ
• q est plus grand que la plus grande des séquences et plus petit
que la somme des tailles des séquences
• Les séquences {a1,1, a1,2,..., a1,q} et {a2,1, a2,2,..., a2,q} dans
laquelle on supprime les gaps correspondent à S1 et S2
■ Formulation : Problème d'alignement par paire
– Soient deux séquences S1 et S2 et une matrice de score w, le
problème d'alignement par paires consiste à déterminer un
alignement de coût optimal selon w

34
Résolution exacte
 Alignement de deux séquences de longueur n :

NbAlign   C nk Cn (Énumération exhaustive rapidement impossible)

n
k k

k 0

Longueur des 1 2 3 4 5 6
séquences

# alignements 3 13 63 321 1683 8527

 Algorithme de Needleman-Wunsch
 1970 : A general method applicable to the search for similarities in the amino
acid sequence of two proteins, J Mol Biol. 48(3):443-453
 effectue un alignement global de deux séquences, de manière optimale
 première application de la programmation dynamique pour la comparaison de
séquences biologiques

35
Programmation dynamique - exemple
 Suite de Fibonacci :
– La suite de Fibonacci est donnée par la formule récurrente :
• Fib(0) = 0
• Fib(1) = 1
• Fib(n) = Fib(n-1) + Fib(n-2)
– Pour calculer Fib(n) on peut définir naturellement un algorithme
récursif :

fonction Fib(n : entier) : entier

debut
si n <= 1 alors retour n;
retour Fib1(n-1) + Fib1(n-2);
fin

36
Programmation dynamique - exemple
 24 appels récursifs pour Fib(6) – 40 pour 7, 66 pour 8…
 Calculs redondants (exponentiels en fonction de n)
 Il faut stocker les résultats intermédiaires

5 4

4 3 3 2

3 2 2 1 2 1 1 0

2 1 1 0 1 0 1 0
1 0
37
Programmation dynamique - exemple
 On enregistre les valeurs de Fib(n) une fois calculées
– il suffit d'évaluer les Fib(n) dans l'ordre croissant des n

fonction Fib(n : entier) : entier

debut
tab[0] = 0;
tab[1] = 1;
pour i = 2 à n faire
tab[i] = tab[i-1] + tab[i-2];
fpour
retour tab[n];
fin

→ Calcul de Fib(n) en temps linéaire !

38
Algorithme de Needleman-Wunsch
 Méthode : Programmation dynamique
 Un algorithme de programmation dynamique procède en
réduisant le problème en plusieurs instances plus petites,
elles-mêmes résolues par décomposition
 Les résultats des calculs intermédiaires sont stockés dans
une table
 La solution est ensuite construite à partir de la table, en
remontant celle-ci
 Ici :
 calculs intermédiaires = scores d'alignements entre préfixes
des séquences

39
Algorithme de Needleman-Wunsch
 Recherche de Sim(i,j), alignement de score optimal entre les
séquences U(1..i) et V(1..j)
 Formule de récurrence :
Sim(0,0)  0
Sim(0, j)  Sim(0, j-1)  Ins(V(j))
Sim(i,0)  Sim(i -1,0)  Del(U(i))
Sim(i -1, j-1)  Sub(U(i), V(j))
Sim(i, j)  max Sim(i -1, j)  Del(U(i))
 Sim(i, j-1)  Ins(V(j))


 Exemple : aligner CAGCTTA avec CGCCTAA

CAGC? CAGCT CAGCT CAGC-
ou ou
C-GC? C-GCC C-GC- C-GCC

40
Programmation dynamique: Un exemple étapes par étapes
Programmation dynamique: Un exemple étapes par étapes
Programmation dynamique: Un exemple étapes par étapes
Programmation dynamique: Un exemple étapes par étapes
Programmation dynamique: Un exemple étapes par étapes
Programmation dynamique: Un exemple étapes par étapes
Programmation dynamique: Un exemple étapes par étapes
Programmation dynamique: Un exemple étapes par étapes
Programmation dynamique: Un exemple étapes par étapes
Programmation dynamique: Un exemple étapes par étapes
Alignement global
Alignement semi-global
 Algorithme de Needleman-Wunsch
- A C G T Pour remplir cette matrice d'alignement, on va utiliser
- 0 -2 -4 -6 -8 l'algorithme de Needleman-Wunsch (pour
l'alignement global).
A -2
Voici les paramètres donnés :
C -4 ✅ Match = +2
G -6 ✅ Mismatch = -1
T -8 ✅ Indel (gap) = -2

➡️ La première cellule en haut à gauche est

toujours 0.
➡️ La première ligne et la première colonne sont
remplies par l'introduction d'une pénalité de gap de
manière cumulative :
Première ligne :
•Première case = 0
•Ensuite : -2, -4, -6, -8...
Première colonne :
•Première case = 0
•Ensuite : -2, -4, -6, -8...
54
Étape 2 : Remplissage de la matrice

Pour chaque cellule M(i,j)M(i, j)M(i,j), le score est le maximum entre :

[Link]/Mismatch → Diagonale précédente + score de substitution (Match =

+2, Mismatch = -1)

[Link] dans la séquence horizontale → Valeur au-dessus + pénalité de gap (-

2)

[Link] dans la séquence verticale → Valeur à gauche + pénalité de gap (-2)

Exemple 2
Calcul détaillé cellule par cellule :
Cellule (A, A)
•Diagonale précédente = 0
•Match (car A = A) = +2
•Gap ligne = -4
•Gap colonne = -4
Max (0+2,−2+−2,−2+−2)= 2
Cellule (A, C)
•Diagonale précédente = -2
•Mismatch (car A ≠ C) = -1
•Gap ligne = -4
•Gap colonne = 0
max(−2+−1,−4,0+−2)=−1
Cellule (A, G)
•Diagonale précédente = -4
•Mismatch (car A ≠ G) = -1
•Gap ligne = -6
•Gap colonne = -1
max(−4+−1,−6,−1+−2)=−3
 - A C G T ✅ Match = +2
✅ Mismatch = -1
- 0 -2 -4 -6 -8 ✅ Indel (gap) = -2

A -2 2

C -4

G -6

T -8
Matrice finale
Étapes du backtracking :
[Link] de départ → dernière case (T, T) = 5
[Link] remonte dans la matrice en choisissant le score le plus élevé entre :
•Diagonale (match ou mismatch)
•Gauche (insertion)
•Haut (délétion)

Chemin détaillé :
➡️ (T, T) = 5 → correspond à un match ➡️ Remonte en diagonale vers (G, G) = 6
➡️ (G, G) = 6 → correspond à un match ➡️ Remonte en diagonale vers (C, C) = 4
➡️ (C, C) = 4 → correspond à un match ➡️ Remonte en diagonale vers (A, A) = 2
➡️ (A, A) = 2 → correspond à un match ➡️ Remonte en diagonale vers (-, -) = 0

Alignement optimal :
➡️ Séquence 1 : A C G T
➡️ Séquence 2 : A C G T
✅ Alignement parfait avec score +5 !
Alignement d’acides aminés
 Matrices de substitution des acides aminés
 Pam [1978], Blosum [1992]…
 Basées sur : nombres de mutation nécessaires pour changer d’acide
aminé, propriétés physico-chimiques, évolution…
 Exemple : BLOSUM62 (indel : -4)

60
Exercice
 Séquences ADN :
 Aligner les séquences ADN suivantes :
 ACGGATTACG
 CGCGTATTG
 Match 2, Mismatch -2, Indel -3
 Séquences protéiques :
 Aligner les séquences protéiques suivantes :
 STRLPTF
 SRAGDVPY
 Matrice BLOSUM62 (Indel -4)

61
Exercice : correction
- A C G G A T T A C G
- 0 -3 -6 -9 -12 -15 -18 -21 -24 -27 -30
C -3 -2 -1 -4 -7 -10 -13 -16 -19 -22 -25
G -6 -5 -4 1 -2 -5 -8 -11 -14 -17 -20
C -9 -8 -3 -2 -1 -4 -7 -10 -13 -12 -15
G -12 -11 -6 -1 0 -3 -6 -9 -12 -15 -10
T -15 -14 -9 -4 -3 -2 -1 -4 -7 -10 -13
A -18 -13 -12 -7 -6 -1 -4 -7 -2 -5 -8
T -21 -16 -15 -10 -9 -4 1 -2 -5 -8 -11
T -24 -19 -18 -13 -12 -7 -2 3 0 -3 -6
G -27 -22 -21 -16 -11 -10 -5 0 1 -2 -1

-ACGGATTACG A-CGGATTACG ACG-G-ATTACG

CGCGTATT--G CGCGTATT--G -CGCGTATT--G

62
Exercice : correction
- S T R L P T F
- 0 -4 -8 -12 -16 -20 -24 -28 Alignement
S -4 4 0 -4 -8 -12 -16 -20 optimal :

R -8 0 3 5 1 -3 -7 -11 S--TRLPTF
SRAGDVP-Y
A -12 -4 -1 2 4 0 -4 -8
G -16 -8 -3 -2 0 2 1 -3
D -20 -12 -7 -5 -4 -1 3 -1
V -24 -16 -11 -9 -4 -5 -1 2
P -28 -20 -15 -13 -8 3 -1 -2
Y -32 -24 -19 -17 -12 -1 1 2

63
Alignement global/local
 Les alignements globaux sont plus souvent utilisés quand les
séquences mises en jeu sont similaires et de taille égale

FTFTALILLAVAV
 Alignement global :
F--TAL-LLA-AV

 Les alignements locaux sont plus souvent utilisés quand deux

séquences dissemblables sont soupçonnées de posséder des
motifs semblables malgré l'environnement
FTFTALILLA-VAV
 Alignement local :
--FTAL-LLAAV--

 Remarque : Avec des séquences suffisamment identiques, il n'y

aucune différence dans les résultats

64
Algorithme de Smith et Waterman (1981)
 Cas particulier de l’alignement global : aligner un segment d’une séquence U
avec un segment d’une séquence
 Recherche de Sim(i,j), alignement de score optimal entre les séquences
U(a0..a1) et V(b0..b1)
 Algorithme presque inchangé ! (il suffit de remplacer les scores négatifs par 0)
 Formule de récurrence :
Sim(0,0)  Sim(0, j)  Sim(i,0)  0 i [1..a], j[1..b]
Sim(i -1, j-1)  Sub(U(i), V(j))

Sim(i -1, j)  Del(U(i))
Sim(i, j)  max
 Sim(i, j-1)  Ins(V(j))
 0
 Reconstruction d’un chemin optimal :
 Chercher la valeur maximale (d’indice minimal), puis remonter les chemins
possible jusqu’à aboutir à 0 !

65
Alignement local : exemple
 Matrice de substitution identité :
- T A T G C A C T A
- 0 0 0 0 0 0 0 0 0 0
T 0 1 1 1 1 1 1 1 1 1
G 0 1 1 1 2 2 2 2 2 2
A 0 1 2 2 2 2 3 3 3 3
- T A T G C A C T A
- X X X X X X X X X X
T X
G X
A X
TATGCACTA
TG-A
69
Alignement local : exemple
 Matrice de substitution : match=2, mismatch=-1, indel=-3
- A A T C C A C T G A
- 0 0 0 0 0 0 0 0 0 0 0
A 0 2 2 0 0 0 2 0 0 0 2
C 0 0 1 1 2 2 0 4 1 0 0
G 0 0 0 0 0 1 1 0 3 3 0
A 0 2 2 0 0 0 3 0 0 2 5
C 0 0 1 1 2 2 0 5 2 0 2
C 0 0 0 0 3 4 1 2 4 1 0
G 0 0 0 0 0 2 3 0 1 6 3
T 0 0 0 2 0 0 1 2 2 3 5
T 0 0 0 2 1 0 0 0 4 1 2
AAT CCACTG A
A CGACCG TT 70
Alignement local : variantes
 Beaucoup de variantes possibles :
 Alignement préfixes / Alignement suffixes
-ACGGATTACG GACCGGCTACCAGGATTACC
CGCGTATT--GATTCCTACC TACCAGTATTG-C

 Alignement préfixe+suffixe
ACCCTTCCAGGATTG
GTATTGAGCCTCATAA

 Alignement d’une sous séquence

ACCCTTCCAGGATTGAGCCTCATAA
GTATTG

 Algorithmes semblables mais différents pour chaque cas

68
Alignement par paires : Modèles de gap
 Définition : Un modèle de gap est une application de
ℕℝ qui attribue un score généralement négatif
(pénalité) à un ensemble de gaps consécutifs
 2 modèles traditionnels :
 Gap linéaire
 0 si n  0
g(n)   n: nombre de caractères
n  g o si n  1
consécutifs de gap
go<0 : pénalité pour l’insertion
 Gap affine d’un nouveau gap
 0 si n  0
g(n)  
g o  (n 1)  g e si n  1
go<0 : pénalité pour l’introduction
d’un nouveau gap
ge<0 : pénalité pour l’extension
d’un gap existant

69
Alignement par paires : Modèles de gap
 Remarques :
 Modèle linéaire : modèle de base, vu précédemment
 Modèle affine : plus proche de la réalité, mais plus complexe
à calculer
 Complexité de l’algorithme « naif » en O(n3)
 Complexité ramenée en O(n²) en utilisant des matrices stockant les
résultats intermédiaires
 Gap linéaire = cas particulier du gap affine (go=ge)
 Gap Affine : ouverture de gap fortement pénalisée
 ge  go

 Existence de modèles plus complexes

 g(n)     log(n) , algorithme en O(N²log(N))

70
Exemples de modèles de gap
Gap linéaire
pénalité

Gap affine
Gap logarithmique

|gap|
71
Alignement par paires avec gap affine
 En général, considérer que l'insertion d'un gap possède un coût
constant ne correspond pas à un modèle réaliste
 On préfère un modèle pour lequel un gap de longueur k est plus
probable que k gaps de longueur 1
 On utilise le modèle de gap affine car il n'augmente pas la
complexité du problème d'alignement (O(N²))
 On utilise 4 matrices pour le calcul du meilleur alignement
 M la matrice des coûts des meilleurs alignements qui dépend des 3 autres
matrices suivantes
 D la matrice des coûts des meilleurs alignements entre xi et yj,
 V la matrice des coûts des meilleurs alignements entre xi et un gap
 H la matrice des coûts des meilleurs alignements entre yj et un gap

72
Alignement par paires avec gap affine
 Initialisation :
M [0,0]  D[0,0]  H[0,0]  V[0,0]  0
D[i,0]  H[i,0]  go  (i 1)  g e , i [1..N ]
D[0, j]  V[0, j]  go  ( j 1)  g e , j [1..P]

 Calcul de M[1,1] :

 D[1,1]  D[0,0]  sim(x1, y1 )

M [1,1]  maxV [1,1]  V[0,1] g o
H[1,1]  H[1,0]  g o


73
Alignement par paires avec gap affine
 Calcul de M[i,1] (pour tout i>1) :
 D[i,1]  D[i 1,0]  sim(xi , y1 )
 V [i 1,1] ge

M [i,1]  maxV [i,1]  max D[i 1,1] g o
 H[i 1,1] g
 o

H[i,1]  H[i,0]  go

 Calcul de M[1,j] (pour tout j>1) :

 D[1, j]  D[0, j 1]  sim(x1 , y j )

 V[1, j 1]  go

M [1, j]  maxH[1, j]  maxD[1, j 1]  go
 H[1, j 1]  g
  e
V[1, j]  V[0, j]  go
74
Alignement par paires avec gap affine
 Calcul de M[i,j] (pour tout i,j>1) :
 M [i 1][ j 1]  sim(xi , y j )

  D[i 1, j 1]  sim(xi , y j )

 H[i 1, j 1]  sim(x , y )
 D[i, j]  max  i j
 V[i 1, j 1]  sim(x , y )
  i j

 V[i, j 1]  go
 
M [i, j]  maxH[i, j]  maxD[i, j 1]  g o
 H[i, j 1]  g
  e

 V[i 1, j]  ge
V[i, j]  
max D[i 1, j]  g o

  H[i 1, j]  g
  o 78
Gap affine : exemple
Matrice D Matrice V
- C T G A C A T - C T G A C A T
- -
C C
T T
A A

Matrice H Matrice M
- C T G A C A T - C T G A C A T
- -
C C
T T
A A

76
Gap affine : exemple
Matrice D Matrice V
- C T G A C A T - C T G A C A T
- 0 - 0
C C
T T
A A

Matrice H Matrice M
- C T G A C A T - C T G A C A T
- 0 - 0
C C
T T
A A

77
Gap affine : exemple
Matrice D Matrice V
- C T G A C A T - C T G A C A T
- 0 X X X X X X X - 0 X X X X X X X
C X C -3
T X T -4
A X A -5

Matrice H Matrice M
- C T G A C A T - C T G A C A T
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 -3 -4 -5 -6 -7 -8 -9
C X C -3
T X T -4
A X A -5

78
Gap affine : exemple
Matrice D Matrice V
- C T G A C A T - C T G A C A T
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 X X X X X X X
C -3 4 C -3 -6
T -4 T -4
A -5 A -5

Matrice H Matrice M
- C T G A C A T - C T G A C A T
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 -3 -4 -5 -6 -7 -8 -9
C X -6 C -3 4
T X T -4
A X A -5

79
Gap affine : exemple
Matrice D Matrice V
- C T G A C A T - C T G A C A T
- 0 X X X X X X X - 0 X X X X X X X
C X 4 -4 -5 -6 -2 -8 -9 C -3 -6 -7 -8 -9 -10 -11 -12
T X T -4
A X A -5

Matrice H Matrice M
- C T G A C A T - C T G A C A T
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 -3 -4 -5 -6 -7 -8 -9
C X -6 1 0 -1 -2 -3 -4 C -3 4 1 0 -1 -2 -3 -4
T X T -4
A X A -5

80
Gap affine : exemple
Matrice D Matrice V
- C T G A C A T - C T G A C A T
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 X X X X X X X
C -3 4 -4 -5 -6 -2 -8 -9 C -3 -6 -7 -8 -9 -10 -11 -12
T -4 -4 8 0 -1 -2 -3 -4 T -4 1 -2 -3 -4 -5 -6 -7
A -5 -5 0 7 9 3 7 1 A -5 0 5 2 1 0 -1 -2

Matrice H Matrice M
- C T G A C A T - C T G A C A T
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 -3 -4 -5 -6 -7 -8 -9
C X -6 1 0 -1 -2 -3 -4 C -3 4 1 0 -1 -2 -3 -4
T X -7 -2 5 4 3 2 1 T -4 1 8 5 4 3 2 1
A X -8 -3 2 4 6 5 4 A -5 0 5 7 9 6 5 4

81
Gap affine : exemple
Matrice D Matrice V
- C T G A C A T - C T G A C A T
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 X X X X X X X
C -3 4 -4 -5 -6 -2 -8 -9 C -3 -6 -7 -8 -9 -10 -11 -12
T -4 -4 8 0 -1 -2 -3 -4 T -4 1 -2 -3 -4 -5 -6 -7
A -5 -5 0 7 9 3 7 1 A -5 0 5 2 1 0 -1 -2

Matrice H Matrice M
- C T G A C A T - C T G A C A T
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 -3 -4 -5 -6 -7 -8 -9
C X -6 1 0 -1 -2 -3 -4 C -3 4 1 0 -1 -2 -3 -4
T X -7 -2 5 4 3 2 1 T -4 1 8 5 4 3 2 1
A X -8 -3 2 4 6 5 4 A -5 0 5 7 9 6 7 4

82
Gap affine : exemple
Matrice D Matrice V
- C T G A C A T - C T G A C A T
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 X X X X X X X
C -3 4 -4 -5 -6 -2 -8 -9 C -3 -6 -7 -8 -9 -10 -11 -12
T -4 -4 8 0 -1 -2 -3 -4 T -4 1 -2 -3 -4 -5 -6 -7
A -5 -5 0 7 9 3 7 1 A -5 0 5 2 1 0 -1 -2

Matrice H Matrice M
- C T G A C A T - C T G A C A T
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 -3 -4 -5 -6 -7 -8 -9
C X -6 1 0 -1 -2 -3 -4 C -3 4 1 0 -1 -2 -3 -4
T X -7 -2 5 4 3 2 1 T -4 1 8 5 4 3 2 1
A X -8 -3 2 4 6 5 4 A -5 0 5 7 9 6 7 4

83
Gap affine : exemple
 Calculer l’alignement optimal pour les séquences
suivantes :
 AGCTCGA
 TACAGCTTG
 Modèle de gap affine :
 Ouverture de gap : -3
 Extension de gap : -1
 Match : 2
 Mismatch : -2

84
Gap affine : exemple
- A G C T C G A - A G C T C G A
- 0 X X X X X X X - 0 X X X X X X X
T X T -3
A X A -4
C X C -5
A X A -6
G X G -7
C X C -8
T X T -9
T X T -10
G X G -11
- A G C T C G A - A G C T C G A
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 -3 -4 -5 -6 -7 -8 -9
T X T -3
A X A -4
C X C -5
A X A -6
G X G -7
C X C -8
T X T -9
T X T -10
G X G -11 88
Gap affine : exemple
- A G C T C G A - A G C T C G A
- 0 X X X X X X X - 0 X X X X X X X
T X -2 -5 -6 -3 -8 -9 -10 T -3 -6 -7 -8 -9 -10 -11 -12
A X -1 -4 -7 -8 -5 -8 -5 A -4 -5 -8 -9 -6 -9 -10 -11
C X -6 -3 -2 -7 -4 -7 -10 C -5 -4 -7 -8 -7 -8 -11 -8
A X -3 -6 -5 -4 -7 -6 -5 A -6 -5 -6 -5 -8 -7 -10 -9
G X -8 -1 -8 -7 -6 -5 -8 G -7 -6 -7 -6 -7 -8 -9 -8
C X -9 -8 1 -6 -3 -8 -7 C -8 -7 -4 -7 -8 -9 -8 -9
T X -10 -9 -6 3 -4 -5 -6 T -9 -8 -5 -2 -5 -6 -7 -8
T X -11 -10 -7 0 1 -2 -3 T -10 -9 -6 -3 0 -3 -4 -5
G X -12 -7 -8 -5 -2 3 -4 G -11 -10 -7 -4 -1 -2 -5 -6
- A G C T C G A - A G C T C G A
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 -3 -4 -5 -6 -7 -8 -9
T X -6 -5 -6 -7 -6 -7 -8 T -3 -2 -5 -6 -3 -6 -7 -8
A X -7 -4 -5 -6 -7 -8 -9 A -4 -1 -4 -5 -6 -5 -8 -5
C X -8 -7 -6 -5 -6 -7 -8 C -5 -4 -3 -2 -5 -4 -7 -8
A X -9 -6 -7 -8 -7 -8 -9 A -6 -3 -6 -5 -4 -7 -6 -5
G X -10 -9 -4 -5 -6 -7 -8 G -7 -6 -1 -4 -5 -6 -5 -8
C X -11 -10 -7 -2 -3 -4 -5 C -8 -7 -4 1 -2 -3 -4 -5
T X -12 -11 -8 -5 0 -1 -2 T -9 -8 -5 -2 3 0 -1 -2
T X -13 -12 -9 -6 -3 -2 -3 T -10 -9 -6 -3 0 1 -2 -3
G X -14 -13 -10 -7 -4 -5 0 G -11 -10 -7 -4 -1 -2 3 0 89
Gap affine : exemple
- A G C T C G A - A G C T C G A
- 0 X X X X X X X - 0 X X X X X X X
T X -2 -5 -6 -3 -8 -9 -10 T -3 -6 -7 -8 -9 -10 -11 -12
A X -1 -4 -7 -8 -5 -8 -5 A -4 -5 -8 -9 -6 -9 -10 -11
C X -6 -3 -2 -7 -4 -7 -10 C -5 -4 -7 -8 -7 -8 -11 -8
A X -3 -6 -5 -4 -7 -6 -5 A -6 -5 -6 -5 -8 -7 -10 -9
G X -8 -1 -8 -7 -6 -5 -8 G -7 -6 -7 -6 -7 -8 -9 -8
C X -9 -8 1 -6 -3 -8 -7 C -8 -7 -4 -7 -8 -9 -8 -9
T X -10 -9 -6 3 -4 -5 -6 T -9 -8 -5 -2 -5 -6 -7 -8
T X -11 -10 -7 0 1 -2 -3 T -10 -9 -6 -3 0 -3 -4 -5
G X -12 -7 -8 -5 -2 3 -4 G -11 -10 -7 -4 -1 -2 -5 -6
- A G C T C G A - A G C T C G A
- 0 -3 -4 -5 -6 -7 -8 -9 - 0 -3 -4 -5 -6 -7 -8 -9
T X -6 -5 -6 -7 -6 -7 -8 T -3 -2 -5 -6 -3 -6 -7 -8
A X -7 -4 -5 -6 -7 -8 -9 A -4 -1 -4 -5 -6 -5 -8 -5
C X -8 -7 -6 -5 -6 -7 -8 C -5 -4 -3 -2 -5 -4 -7 -8
A X -9 -6 -7 -8 -7 -8 -9 A -6 -3 -6 -5 -4 -7 -6 -5
G X -10 -9 -4 -5 -6 -7 -8 G -7 -6 -1 -4 -5 -6 -5 -8
C X -11 -10 -7 -2 -3 -4 -5 C -8 -7 -4 1 -2 -3 -4 -5
T X -12 -11 -8 -5 0 -1 -2 T -9 -8 -5 -2 3 0 -1 -2
T X -13 -12 -9 -6 -3 -2 -3 T -10 -9 -6 -3 0 1 -2 -3
G X -14 -13 -10 -7 -4 -5 0 G -11 -10 -7 -4 -1 -2 3 0
87
Gap affine : exemple

Alignement optimal : ---AGCTCGA

(gap affine) TACAGCTTG-

- A G C T C G A
- 0 -3 -4 -5 -6 -7 -8 -9
T -3 -2 -5 -6 -3 -6 -7 -8
A -4 -1 -4 -5 -6 -5 -8 -5
C -5 -4 -3 -2 -5 -4 -7 -8
A -6 -3 -6 -5 -4 -7 -6 -5
G -7 -6 -1 -4 -5 -6 -5 -8
C -8 -7 -4 1 -2 -3 -4 -5
T -9 -8 -5 -2 3 0 -1 -2
T -10 -9 -6 -3 0 1 -2 -3
G -11 -10 -7 -4 -1 -2 3 0

88
Problème lié au gap affine
 Dans certains cas, le résultat trouvé ne semble pas
entièrement approprié
 Exemple :
 Ouverture de gap : -3
 Extension de gap : -1
 Match : 4
 Mismatch : -2
A - - - - - - T G T - - - - - A - T G T
A C C T G A T T G T A C C T G A T T G T
4-3-1-1-1-1-1+4+4+4=8 -3-1-1-1-1+4-3+4+4+4=6

 Solution : changer le modèle, en ne pénalisant pas les gaps en

début de séquence (alignement local affine !)

89
Conclusion
→ L'alignement de séquences par paires est généralement
solvable en un temps raisonnable (quadratique)
→ De nombreuses variantes selon le résultat recherché
• Matrices de substitution
• Modèles de gap
• Alignements local/global
• …

Remarque : dans certains cas, l'algorithme est trop coûteux

• Très grandes séquences (génome)
• Recherche de similarité entre une séquence et une banque de
séquences (ex : GenBank)
→ Utilisation d'heuristiques (ex : Basic Local Alignment Search Tool)

90
Conclusion
BLAST :
• Recherche heuristique permettant de trouver les régions similaires entre deux ou
plusieurs séquences de nucléotides ou d'acides aminés.

• Permet de retrouver rapidement dans des bases de données, les séquences ayant
des zones de similitude avec une séquence donnée (introduite par l'utilisateur).

• Utilisé pour trouver des relations fonctionnelles ou évolutives entre les séquences et
peut aider à identifier les membres d'une même famille de gènes.

• Le terme blast peut être modifié en fonction de la nature de la séquence d'entrée, et

de la base de donnée utilisée : blast de nucléotides (séquence nucléotidique vs. BD
de séquences nucléotidiques) ; blast de protéines (séq prot. Vs BD prot.) ; blastx (nuc.
vs BD prot) ; tblastn (prot. Vs BD nuc.) ; tblastx (nuc.prot. Vs nuc. prot.).

• Différentes versions de l'algorithme : BlastN (séquences nucléotidiques, lent donc pas

applicable à toute la BD) ; BlastP (protéines, lent) ; Megablast (rapide, séquences
similaires) ; PSI-Blast (position-specific iterated BLAST), Blast relancé plusieurs fois par
itération. PHI-BLAST (pattern hit initiated Blast), utilisant un motif utilisé comme point
de départ des recherches.
91
Sommaire
 Introduction à la bioinformatique
 Notions de base
 Alignement 2 à 2 de séquences
 Alignement multiple de séquences
 Alignement multiple optimal
 Heuristiques pour l’alignement multiple
 Phylogénie

92
Alignement multiple
 Alignement 2 à 2 :
 Deux séquences quelconques
 Recherche d’une certaine similarité syntaxique
 Fonction commune ?
 Alignement multiple :
 Famille de séquences partageant une même fonction
 Quelle est la conservation syntaxique ?

93
Alignement multiple : score
 Exemple :
 Identité : +2
 Substitution : -1
 Indel : -2

A A C G T A C G A T A
A - C G T A - A A T G
G T C G T A - - T T A

94
Alignement multiple : score
 Exemple :
 Identité : +2
 Substitution : -1
 Indel : -2

A A C G T A C G A T A
8
A - C G T A - A A T G
G T C G T A - - T T A

95
Alignement multiple : score
 Exemple :
 Identité : +2
 Substitution : -1
 Indel : -2

A A C G T A C G A T A
8
A - C G T A - A A T G 5
G T C G T A - - T T A
3

96
Alignement multiple : score
 Exemple :
 Identité : +2
 Substitution : -1
 Indel : -2

A A C G T A C G A T A
8
A - C G T A - A A T G 5
G T C G T A - - T T A
3

Score de l’alignement multiple : 8+5+3=16

97
Alignement multiple : score
 Exemple :
 Identité : +2
 Substitution : -1
 Indel : -2

A A C G T A C G A T A
A - C G T A - A A T G
G T C G T A - - T T A

98
Alignement multiple : score
 Exemple :
 Identité : +2
 Substitution : -1
 Indel : -2

A A C G T A C G A T A
A - C G T A - A A T G
G T C G T A - - T T A
2
-1
-1
=
0

99
Alignement multiple : score
 Exemple :
 Identité : +2
 Substitution : -1
 Indel : -2

A A C G T A C G A T A
A - C G T A - A A T G
G T C G T A - - T T A
2 -2 2 2 2 2 -2 -1 2 2 -1
-1 -1 2 2 2 2 -2 -2 -1 2 2
-1 -2 2 2 2 2 0 -2 -1 2 -1
= = = = = = = = = = =
0 -5 6 6 6 6 -4 -5 0 6 0

100
Alignement multiple : score
 Exemple :
 Identité : +2
 Substitution : -1
 Indel : -2

A A C G T A C G A T A
A - C G T A - A A T G
G T C G T A - - T T A
2 -2 2 2 2 2 -2 -1 2 2 -1
-1 -1 2 2 2 2 -2 -2 -1 2 2
-1 -2 2 2 2 2 0 -2 -1 2 -1
= = = = = = = = = = =
0 -5 6 6 6 6 -4 -5 0 6 0

Score de l’alignement multiple : 0-5+6+6+6+6-4-5+0+6+0=16

101
Alignement multiple
 Recours à des approches heuristiques
 Réduire le temps de calcul
 Maximiser le score du résultat
 Pas de garantie d’optimalité !
 Quelques exemples d’algorithmes
 En étoile (basique)
 Clustal (le plus populaire)
 Dialign2 (complémentaire à Clustal)
 T-coffee, Pima, Multalin, Plasma…
 + méthodes heuristiques, métaheuristiques
 Autant d'alignements que de programmes…

102
Alignement multiple progressif
 Les séquences homologues sont reliées d’un point de
vue évolutif
 Idée : construire progressivement un alignement, à partir de
séries de séquences (ou de groupes de séquences) alignées
deux à deux, suivant un ordre de branchement donné par
un arbre d’évolution
 Alignement des séquences les plus proches d’un point de vue
phylogénétique (évolution)
 Intégration progressive des séquences un peu plus éloignées
 Approche suffisamment rapide pour permettre la
construction d’alignements contenant un grand nombre de
séquences

103
Heuristique en étoile
 Heuristique en étoile
 Sélection d'une séquence centrale
 Construction de l'alignement multiple, en partant de la
séquence centrale, puis en incorporant une à une les autres
séquences
 Exemple :
S1 cgatgagtcattgtgactg
S2 cgagccattgtagctactg
S3 cgaccattgtagctacctg
S4 cgatgagtcactgtgactg

 indel : -2, substitution : -1, identite : 1

104
Heuristique en étoile
 Etape 1 : Alignements globaux de toutes les séquences deux par deux
S1 cgatgagtcattgt-g--actg S2 cgagccattgtagcta-ctg
||| | |||||| | |||| ||| |||||||||||| |||
S2 cga-g--ccattgtagctactg S3 cga-ccattgtagctacctg
S1 cgatgagtcattg-tgactg S2 cga-g--ccattgtagctactg
||| | | | | | ||| ||| | || ||| | ||||
S3 cgacca-ttgtagctacctg S4 cgatgagtcactgt-g--actg
S1 cgatgagtcattgtgactg S3 cgaccattgtagctacctg
|||||||||| |||||||| ||| | | | |||
S4 cgatgagtcactgtgactg S4 cgatgagtcactgtgactg
Tableau des scores
S1 S2 S3 S4

S1 2 0 17

S2 2 14 0
k séquences  k(k-1)/2 alignements

S3 0 14 -1

S4 17 0 -1

105
Heuristique en étoile
 Etape 2 : sélection de la séquence centrale à partir du
tableau des scores
 séquence qui maximise la somme des similarités avec l'ensemble
des autres séquences
S1 S2 S3 S4

S1 2 0 17  19
S2 2 14 0  16
S3 0 14 -1  13
S4 17 0 -1  16

 But : Aligner selon la séquence la plus représentative de

l’ensemble (centre de gravité)

106
Heuristique en étoile
 Etape 3 : construction de l'alignement multiple par juxtaposition
des alignements deux à deux avec la séquence centrale
S1 cgatgagtcattgt-g--actg
||| | |||||| | ||||
S2 cga-g--ccattgtagctactg
Alignement multiple
S1 cgatgagtcattg-tgactg
||| | | | | | ||| s1 cgatgagtcattgtgactg
S3 cgacca-ttgtagctacctg  s4 cgatgagtcactgtgactg
S1 cgatgagtcattgtgactg
|||||||||| ||||||||
S4 cgatgagtcactgtgactg

 L'intégration d'une nouvelle séquence se fait en prenant la

séquence centrale comme guide
Possible en étirant les gaps de l'alignement multiple courant.
Heuristique en étoile
 Etape 3 : construction de l'alignement multiple par juxtaposition
des alignements deux à deux avec la séquence centrale
S1 cgatgagtcattgt-g--actg
||| | |||||| | |||| Alignement multiple
S2 cga-g--ccattgtagctactg s1 cgatgagtcattgtgactg
s4 cgatgagtcactgtgactg
S1 cgatgagtcattg-tgactg
||| | | | | | ||| s1 cgatgagtcattg-tgactg

S3 cgacca-ttgtagctacctg s3 cgacca-ttgtagctacctg
S1 cgatgagtcattgtgactg s1 cgatgagtcattg-tgactg
|||||||||| |||||||| s3 cgacca-ttgtagctacctg
S4 cgatgagtcactgtgactg s4 cgatgagtcactg-tgactg

 L'intégration d'une nouvelle séquence se fait en prenant la

séquence centrale comme guide
Possible en étirant les gaps de l'alignement multiple courant.
Heuristique en étoile
 Etape 3 : construction de l'alignement multiple par juxtaposition
des alignements deux à deux avec la séquence centrale
S1 cgatgagtcattgt-g--actg Alignement multiple
||| | |||||| | |||| s1 cgatgagtcattg-tgactg
S2 cga-g--ccattgtagctactg s3 cgacca-ttgtagctacctg
S1 cgatgagtcattg-tgactg s4 cgatgagtcactg-tgactg
||| | | | | | ||| s1 cgatgagtcattgt-g--actg
S3 cgacca-ttgtagctacctg  s2 cga-g--ccattgtagctactg
S1 cgatgagtcattgtgactg s1 cgatgagtcattg-t-g--actg
|||||||||| |||||||| s2 cga-g--ccattg-tagctactg
S4 cgatgagtcactgtgactg s3 cgacca-ttgtagct-a--cctg
s4 cgatgagtcactg-t-g--actg
 L'intégration d'une nouvelle séquence se fait en prenant la
séquence centrale comme guide
Possible en étirant les gaps de l'alignement multiple courant.
Clustal
 Higgins et Sharp [1988]. CLUSTAL: a package for performing multiple sequence
alignment on a microcomputer. Gene, 73, 237-244.
 Clustal = CLUSTer + ALignment
 Inspiré par la classification hiérarchique ascendante
 Regroupement progressif des séquences
 Exemple :
S1 cgatgagtcattgtgactg
S2 cgagccattgtagctactg
S3 cgaccattgtagctacctg
S4 cgatgagtcactgtgactg

 indel : 2, substitution : 1, identité : 0

 Attention, on calcule une distance, d’où les scores utilisés
110
Clustal
 Etape 1 : Alignements globaux de toutes les séquences
deux par deux

Tableau des distances

S1 S2 S3 S4

S1 12 11 1

S2 12 4 14

S3 11 4 10

S4 1 14 10

111
Clustal
 Etape 1 : Alignements globaux de toutes les séquences
deux par deux
 Les séquences sont regroupées suivant leur similarité à
partir de la matrice des distances 2 à 2

Tableau des distances

S1 S2 S3 S4
S1 S2
S1 12 11 1

S2 12 4 14 S4 S3
S1 S4
S3 11 4 10

S4 1 14 10

112
Clustal
 Etape 1 : Alignements globaux de toutes les séquences
deux par deux
 Les séquences sont regroupées suivant leur similarité à
partir de la matrice des distances 2 à 2
 Nouveaux scores : Neighbour-Joigning (cf. phylogénie)
Tableau des scores
S1/S4 S2 S3
S1 S2
S1/
12.5 10
S4
S4 S3
S2 12.5 4
S1 S4
S3 10 4

113
Clustal
 Etape 1 : Alignements globaux de toutes les séquences
deux par deux
 Les séquences sont regroupées suivant leur similarité à
partir de la matrice des distances 2 à 2.
 Nouveaux scores : Neighbour-Joigning (cf. phylogénie)
Tableau des scores
S1/S4 S2 S3
S1 S2
S1/
12.5 10
S4
S4 S3
S2 12.5 4
S1 S4 S2 S3
S3 10 4

114
Clustal
 Etape 2 : construction de l'alignement à partir de
l'arbre guide
 Arbre guide : classication hiérarchique ascendante
 Alignement entre deux clusters de séquences : alignement
deux à deux avec le score SP pour le score d'une colonne
 L'alignement est obtenu par extensions successives.
 « Once a gap, always a gap »

115
Clustal
S1 cgatgagtcattgt-g--ac-tg
S4 cgatgagtcactgt-g--ac-tg
S2 cga---gccattgtagctac-tg
S3 cga----ccattgtagctacctg

S1 cgatgagtcattgtgactg S2 cgagccattgtagctac-tg
|||||||||| |||||||| ||| ||||||||||||| ||
S4 cgatgagtcactgtgactg S3 cga-ccattgtagctacctg

S4 cgagccattgtagctactg S2 cgatgagtcactgtgactg

S1 cgatgagtcattgtgactg S3 cgaccattgtagctacctg
116
Clustal-W
→ Variante de Clustal
Thompson JD, Higgins DG, Gibson TJ (1994) CLUSTAL W: improving the sensitivity
of progressive multiple sequence alignment through sequence weighting,
position specific gap penalties and weight matrix choice. Nucleic Acids Res.
22(22):4673-80.
 Modification principale au niveau de la mise à jour de la
matrice des distances après regroupement de 2 séquences
 Des poids sont associés selon le nombre de séquences
concernées (cf. phylogénie)

117
Autres algorithmes d’alignement multiple
 Beaucoup d’algorithme dans la littérature!
 Les plus classiques/performants :
 clustal omega : nouvelle variante de clustal
 multalin : variante de clustal
 T-coffee : variante de clustal
 muscle : fonction de création de profils
 probcons : modèle de Markov
 mafft : transformée de Fourier
 dialign : recherche de chemins
 saga : algorithme génétique
 hmmer : modèle de Markov
 Voir: « Multiple sequence alignment », Robert C. Edgar and
Serafim Batzoglou, dans « Current Opinion in Structural
Biology », 2006, volume 16, pages 368–373.
118
Sommaire
 Introduction à la bioinformatique
 Notions de base
 Alignement 2 à 2 de séquences
 Alignement multiple de séquences
 Phylogénie
 Généralités / Notions sur les arbres
 Méthodes de reconstruction phylogénétique
 WPGMA / UPGMA
 Neighbourg-joigning
 Parcimonie

119
Phylogénie
Arbre de Haeckel (1866)
 La phylogénie est l'étude de la formation et
de l'évolution des organismes vivants en vue
d'établir leur parenté
 On représente couramment une phylogénie
par un arbre phylogénétique. La proximité
des branches de cet arbre représente le
degré de parenté entre les taxons, les
nœuds les ancêtres communs des taxons
 Dans un arbre élaboré par phénétique, la
longueur des branches représente la
distance génétique entre taxons

120
Phylogénie
 Depuis Darwin, il est communément admis que les êtres vivants
descendent tous les uns des autres.
 Jusqu'aux années 1960, les seuls moyens disponibles pour
construire des classifications d'espèces étaient :
 comparaisons entre les morphologies,
 comparaisons des comportements
 répartition géographiques des espèces…
 La découverte que des protéines homologues (ou acides
nucléiques) avaient des séquences en acides aminés (ou en
bases) qui variaient d'une espèce à l'autre a fourni un nouveau
moyen d'étude : la phylogénie.

121
Phylogén
ie
 Evolution
 L’évolution selon Lamarck (1744-1829)
 l'évolution est due à une adaptation continue au
milieu ambiant : un environnement changeant altère
les besoins de l'organisme vivant qui s'adapte en
modifiant son comportement

122
Phylogénie
 Evolution
 L’évolution selon Darwin (1809-1882)
 évolution par sélection naturelle : au sein d'une
même lignée, tous les individus sont différents
et la nature favorise la multiplication de ceux
qui jouissent d'un quelconque avantage

123
Phylogénie
 Pour quoi faire ?
 Retracer l’histoire évolutive d’une famille de gènes
 Reconstruire les relations évolutives entre espèces
 ex : arbre du vivant
 Classer une nouvelle espèce
 ex : souche virale
 Comment ?
 Aligner correctement les séquences nucléiques ou
protéiques
 Appliquer une méthode de génération d’arbres
 Évaluer statistiquement la robustesse des arbres

124
Phylogénie
 Notions de bases (arbres)
 Un arbre phylogénétique est caractérisé par :
 sa topologie
 la longueur de ses branches (éventuellement)

Seq D
Seq C
Seq A racine Seq C
Seq B Seq D Seq A

nœud interne Seq B

nœud feuille

 Nœud : estimation de l’ancêtre commun des éléments

appartenant à ce nœud
 Racine (root) : ancêtre commun de tous les éléments de l’arbre
 Un arbre peut avoir ou non une racine

125
Terminologie essentielle
•Taxon : Unité taxonomique (espèce, genre, famille, etc.) représentée dans l'arbre

•Nœud : Point de branchement représentant un ancêtre commun

•Branche : Ligne connectant les nœuds, représentant la continuité évolutive

•Clade : Groupe monophylétique comprenant un ancêtre commun et tous ses

descendants

•Racine : Point de départ de l'arbre, représentant l'ancêtre commun le plus ancien

•Groupe frère : Deux clades issus d'un même nœud

 Types d'arbres phylogénétiques

A- Selon la forme

•Arbre cladogramme : Représente uniquement les relations de parenté sans tenir

compte du temps ou du degré de divergence.
•Arbre phylogramme : Les longueurs des branches reflètent le degré de divergence
évolutive.
•Arbre chronogramme : Les longueurs des branches sont proportionnelles au
temps écoulé.

B- Selon l'orientation
•Arbre enraciné : Possède une racine identifiant l'ancêtre commun le plus ancien.
•Arbre non enraciné : Montre les relations entre taxons sans spécifier d'ancêtre
commun.

C- Selon la structure
•Arbre dichotomique : Chaque nœud donne naissance à exactement deux
branches.
•Arbre polytomique : Certains nœuds peuvent donner naissance à plus de deux
branches.
 Notions de bases (arbres)
 Différent types d’arbres
 Arbres enracinés
 Cladogrammes (longueur des branches non significative)
 Phylogramme (longueur des branches proportionnelle au nombre de
substitutions)
Seq D Seq D
racine Seq C racine Seq C
Seq A
Seq A
Seq B
Seq B

 Arbres non enracinés

 longueur des branches proportionnelle au nombre de substitutions
 longueur des branches non significative

Seq A Seq C Seq C

Seq A
Seq B Seq D Seq B Seq D

145
Phylogénie
 Notions de bases (arbres)
 Racine
 Pour un arbre sans racine (unrooted), il existe plusieurs arbres avec racine 
Position de la racine ?

Seq A 2 4 Seq C

Seq B 1 Seq D
3 5

A A B C D
B B A D C
C C C A A
D D D B B
1 2 3 4 5

 La position de la racine est choisie généralement arbitrairement :

 « midpoint rooting » : Racine placée au milieu de la plus longue branche
 « outgroup rooting » : L’utilisateur peut définir la ou les séquences constituant
l’outgroup pour enraciner l’arbre. Ces séquences doivent être éloignées des autres
séquences tout en étant homologues
Exemples détaillés du calcul du nombre d'arbres phylogénétiques
Exemple 1: Arbres non-racinés avec 5 taxons
La formule pour calculer le nombre d'arbres non-racinés avec n taxons est:

Pour n = 5 taxons:
[Link] (2n-5)!
2n-5 = 2×5-5 = 5
5! = 5×4×3×2×1 = 120
[Link] 2(n−3)2^{(n-3)} 2(n−3)
n-3 = 5-3 = 2
22=42^2 = 4 22=4
[Link] (n-3)!
(5-3)! = 2! = 2×1 = 2
[Link] la formule complète:
120 ÷ (4×2) = 120 ÷ 8 = 15
→ Avec 5 taxons, il existe 15 arbres non-racinés possibles.
Exemple 2: Arbres enracinés avec 4 taxons
La formule pour calculer le nombre d'arbres enracinés avec n taxons est:

Pour n = 4 taxons:
[Link] (2n-3)!
1. 2n-3 = 2×4-3 = 5
2. 5! = 5×4×3×2×1 = 120
[Link] 2(n−2)2^{(n-2)} 2(n−2)
1. n-2 = 4-2 = 2
2. 22=42^2 = 4 22=4
[Link] (n-2)!
1. (4-2)! = 2! = 2×1 = 2
[Link] la formule complète:
1. 120 ÷ (4×2) = 120 ÷ 8 = 15
→ Avec 4 taxons, il existe 15 arbres enracinés possibles.
Principales méthodes de construction d'arbres phylogénétiques

Méthodes basées sur les distances

•UPGMA (Unweighted Pair Group Method with Arithmetic Mean)
• Méthode simple basée sur les similarités entre séquences
• Peu utilisée aujourd'hui pour la phylogénie moléculaire
•Neighbor-Joining (NJ)
• Méthode rapide, idéale pour analyser des milliers de séquences
• Algorithme itératif qui minimise la longueur totale de l'arbre

Méthodes basées sur les caractères

•Maximum de Vraisemblance (ML)

• Méthode probabiliste nécessitant un modèle d'évolution
• Très précise mais computationnellement intensive
• Recommandée quand le nombre de caractères > ½ nombre de séquences
• Temps de calcul : peut prendre des semaines pour des centaines de
séquences
•Maximum de Parcimonie (MP)
• Minimise le nombre de changements évolutifs
• Bon compromis entre rapidité et précision
• Moins précise que ML mais calculs beaucoup plus rapides
142
La méthode UPGMA (Unweighted Pair Group Method with Arithmetic Mean)

Principe

•Méthode agglomérative hiérarchique basée sur les distances entre taxons

•Construit l'arbre en regroupant d'abord les taxons les plus proches
•Suppose un taux d'évolution constant (horloge moléculaire)

Algorithme:
[Link] la matrice de distance entre tous les taxons
[Link] les deux taxons les plus proches en un cluster
[Link] les distances entre ce nouveau cluster et les autres taxons
4.Répéter jusqu'à ce que tous les taxons soient connectés
Calcul de la matrice de distance entre taxons

La matrice de distance est une étape fondamentale dans la construction d'arbres

phylogénétiques par des méthodes comme UPGMA.

Voici comment la calculer:

Données de départ
Pour calculer une matrice de distance, vous avez généralement:
•Des séquences d'ADN/ARN/protéines alignées
•Des caractères morphologiques codés
•D'autres données comparables entre taxons
Méthodes de calcul de distance

1. Pour des séquences moléculaires

Distance de Hamming (distance p)
•Principe: Compte simplement la proportion de sites différents
•Calcul: nombre de différences / longueur totale
•Exemple:
• Séquence 1: ATGGCTAGC
• Séquence 2: ACGGCAAGC
• Différences: 2 positions (T→C et T→A)
• Distance = 2/9 = 0,22 ou 22%
Distance de Jukes-Cantor
•Principe: Corrige les substitutions multiples
•Formule: d = -3/4 × ln(1 - 4p/3) où p est la distance observée
•Adaptée pour l'ADN avec probabilité égale de substitutions
Distance de Kimura à 2 paramètres
•Distingue les transitions (A↔G, C↔T) des transversions (autres substitutions)
•Plus précise car ces deux types n'ont pas la même probabilité
2. Pour des données morphologiques
•Distance = nombre de caractères différents / nombre total de caractères
 Transitions : A ↔ G et C ↔ T (changements entre
purines ou entre pyrimidines)
 Transversions : tous les autres changements
(purine ↔ pyrimidine)
 Exemple avec 4 séquences d'ADN

Taxon A: ATGCTATCGGTA
Taxon B: ATGCAATCGGTA
Taxon C: ACGATACCGGTA
Taxon D: ACGATACAAGTA

Calcul avec distance p (proportion de sites différents):

•d(A,B) = 1/12 = 0,08 (1 différence)
•d(A,C) = 3/12 = 0,25 (3 différences)
•...etc.

A B C D
A 0 0,08 0,25 0,33
B 0,08 0 0,25 0,33
C 0,25 0,25 0 0,17
D 0,33 0,33 0,17 0

Cette matrice servira ensuite d'entrée pour des algorithmes comme UPGMA ou
Neighbor-Joining pour construire l'arbre phylogénétique.
Exemple 2 avec 4 taxons - Matrice de distance:

A B C D
A 0 5 9 9
B 5 0 10 10
C 9 10 0 8
D 9 10 8 0
Solution:
[Link] petite distance: A-B (5) → Fusion en cluster (AB)
[Link] de (AB) aux autres: d(AB,C) = (9+10)/2 = 9.5, d(AB,D) = (9+10)/2 = 9.5
[Link] petite distance: C-D (8) → Fusion en cluster (CD)
[Link] finale: d(AB,CD) = 9.5 → Fusion des clusters

Résumé des étapes pour votre exemple

[Link] A et B (distance = 5).
[Link] d(AB, C) = Moyenne de (A-C et B-C) = (9+10)/2=9.5
[Link] d(AB, D) = Moyenne de (A-D et B-D) = (9+10)/2=9.5
[Link] C et D (distance = 8).
[Link] d(AB, CD) = Moyenne de (AB-C et AB-D) = (9.5+9.5)/2=9.5
Phylogénie
 Neighbor-Joining (NJ)

 Développé par Saitou et Nei (1987)

 Tente de corriger la méthode UPGMA afin d'autoriser un taux
de mutation différent sur les branches.
 Même principe que UPGMA :
 Point de départ : matrice des distances 2 à 2
 Une itération supprime une ligne et une colonne de la matrice (on lie
deux nœuds)
 On itère jusqu’à ce que tout les nœuds soient reliés (matrice vide)

Neighbor-Joining (NJ) est une méthode de reconstruction

phylogénétique plus précise qu'UPGMA car elle ne suppose pas un taux
d'évolution constant (pas d’horloge moléculaire)

174
Phylogénie

A B C D
A 0 5 9 9
B 5 0 10 10
C 9 10 0 8
D 9 10 8 0

Étape 1 : Calculer les sommes des distances (Sᵢ) pour chaque taxon
Pour chaque taxon ii, calculer Si=∑kd(i,k)Si​=∑kd(i,k) (somme de toutes ses
distances).
•SA=5+9+9=23
•SB=5+10+10=25
•SC=9+10+8=27
•SD=9+10+8=27

175
Phylogénie
 Neighbor-Joining (NJ)
 Etape 2 : calcul de la nouvelle matrice en utilisant la formule

M(i,j)= d(ij) -[r(i)+r(j)] / (N-2)

Où n=4n=4 (nombre de taxons).
•Paire A-B :
MAB=5−(23+25)/(4−2)=5−(48)/2=5−24=−19
•Paire A-C :
MAC=−16
•Paire A-D :
MAD=−16
•Paire B-C :
MBC=−16
•Paire B-D :
MBD=−16
•Paire C-D :
MCD=−19
Résultat :
Les paires A-B et C-D ont la valeur la plus faible (MAB=MCD−19) → on choisit
arbitrairement de fusionner A-B (comme en UPGMA).
165
Étape 3 : Créer un nouveau nœud (U) et calculer les distances branches
On crée un nœud interne U reliant A et B.
•Longueur de la branche A-U :

Étape 4 : Mettre à jour la matrice de distance

On calcule les distances du nouveau nœud U vers C et D :
Phylogénie
 Neighbor-Joining (NJ)
 Etape 3 : Choix des plus proches voisins, c'est à dire des deux
séquences ayant le M(i,j) le plus petit
 soit A et B soit D et E sur l’exemple.
 On forme un nouveau nœud U avec A et B, et on calcule la
longueur de la branche entre U et A ainsi qu'entre U et B :
 S (AU) = d (AB) / 2 + [r(A) - r(B)] / 2 (N-2)
= 5/2 + [30-42] /2(6-2) = 1
 S (BU) = d (AB) - S(AU) = 5 - 1 = 4 B

A 4
 On applique à l’arbre
en construction :
1 U C

D
E 166
Phylogénie
 Enraciner un arbre

Souvent, les méthodes de reconstruction phylogénétiques

aboutissent à des arbres non enracinés :
 Méthode de « l’outgroup » : on ajoute une séquence dont on sait qu'elle est
beaucoup plus ancienne que toutes les autres séquences
 Si trop éloignée des autres données : peut conduire à des erreurs dans la topologie
de l'arbre
 Si trop proche des séquences: cela n'est peut-être pas un vrai "outgroup"
 L'utilisation de plus d'un "outgroup" améliore en général l'évaluation de l'arbre
 En l'absence d'un bon "outgroup", la racine peut être positionnée
approximativement à égale distance de toutes les séquences : on parle alors de
mid-point rooting
 Si l’état de l’ancêtre commun est connu ou peut être calculé convenablement,
alors enraciner l’arbre en conséquence
179
Exercice Récapitulatif
 Calculer les alignements 2 à 2 des séquences suivantes :
 Homme : AGCCACCGGGTGCA
 Gibbon : AGCACCGGATGCA
 Gorille : ACCAACGCGGGTGCCA
 Chat : AGCATCGTCTGCCGA
 Appliquer UPGMA, NJ
 A partir de l’arbre obtenu par NJ, construire un alignement
multiple probable
 Appliquer la méthode de Parcimonie à l’alignement obtenu. En
déduire une séquence probable pour l’ancêtre commun

180
 Nouvelle matrice
U C D
U 0 7 7
C 7 0 8
D 7 8 0

Étape 5 : Répéter le processus avec la nouvelle matrice

 C A

•Longueurs des branches : V U

• A−U=2, B−U=3
• C−V=4, D−V=4 D B
• U−V=3
Critère UPGMA Neighbor-Joining
Hypothèse d'horloge Oui (arbre ultramétrique) Non (taux variables permis)
Ajustement par divergence
Calcul des distances Moyennes simples
globale
Précision Moins précise si taux inégaux Plus robuste
Bootstrap
 Comment évaluer la confiance que l'on peut avoir dans un arbre
 Bootstrap
 Méthode proposée par Bradley Efron (1979) et introduite en phylogénie par Felsenstein en
1985.

 Méthode divisée en 3 étapes réalisées chacune au moins 100 fois :

 Réalisation d'un pseudo-alignement A' à partir des séquences d'origine en prenant arbitrairement
n colonnes (avec remplacements) de l'alignement d'origine

 Estimation de l'arbre obtenu : T'

 Comparaison des arbres T et T' : pour chaque nœud de T, on regarde s'il est présent dans T'

 On compte ensuite pour chaque nœud le nombre de fois où il est présent dans les T'. Cette
fréquence avec laquelle on retrouve un nœud est la valeur de bootstrap (plus elle est
élevée plus la fiabilité de la branche est importante)

 On supprime alors éventuellement les nœuds à faible fiabilité

184
Bootstrap

A A
75
99 B 99 B

95 C 95 C
D D
100 100
E E
F F

185
Bioinformatique des méthodes de
séquençage à haut débit
1- Les méthodes de séquençage : Première, deuxième et troisième
génération

- Qu’est-ce que le séquençage ?

déterminer la succession linéaire des bases A, C,G, T de l’ADN, la lecture de cette séquence
permet d’étudierl’information biologique contenue par celle-ci
- A quoi sert le séquençage?
 RNA-seq : transcriptome [Link] sur les ARN via le séquençage del’ADN
complémentaire (cDNA)

 Re-séquencage : séquençage d’un fragmentd’ADN et comparaison du résultat obtenu

avecune séquence de référence connue - détection deSNP, haplotyping

 Séquencage de novo : séquençage d’un génome pour lequel il n’existe pas de séquence
deréférence, détermination d’une sequence inconnue

 Epigénétique : étude des changements d'activitédes gènes qui sont transmis au fil des
divisionscellulaires ou des générations sans faire appel àdes mutations de l'ADN.

 Génotypage par séquençage : découverte etgénotypage de plusieurs milliers

depolymorphismes de type SNP/INDEL chez denombreux individus

 Metagénomique : analyse du matériel génétiqueprovenant directement des échantillons

biologiques – étude de la diversité génétique d’un échantillon
Comment fonctionne le séquençage de Sanger?
[Link] et dénaturation
1. Extraction : Un fragment d’ADN est isolé de l’échantillon.
2. Chauffage : L'ADN se déroule et les deux brins se séparent.
[Link] d’une amorce d’ADN
1. La température est abaissée.
2. Une amorce d’ADN s’attache au brin cible pour indiquer le début du
séquençage.
[Link] de la chaîne d’ADN
1. Température légèrement augmentée.
2. Ajout :
[Link]éotides libres (A, T, G, C).
[Link] polymérase pour construire un brin complémentaire.
[Link] contrôlée
1. Introduction de nucléotides chimiquement modifiés (terminateurs).
2. Ces nucléotides arrêtent l’élongation et sont marqués par des
colorants différents.
5.Séparation des fragments
1. Électrophorèse sur gel :
[Link] fragments sont triés par taille sous courant électrique.
[Link] plus courts migrent le plus loin.
[Link] de la séquence
1. Observation des bandes sous lumière UV ou radiographie.
2. Alignement des bandes permet de déduire la séquence d’ADN.
Évolution de la Méthode de Sanger : Séquençage Automatisé

Modifications Principales :
[Link] des fluorochromes
1. Petits composés chimiques émettant une
lumière colorée.
2. Chaque nucléotide (A, T, G, C) est marqué
par une couleur spécifique.
[Link] de la réaction
1. Séquençage réalisé dans un seul tube
capillaire.
2. Mélange unique contenant tous les
nucléotides marqués.
[Link] automatisée
1. Laser éclaire le tube.
2. Chaque bande colorée émet une lumière
détectée par un capteur.
4.Résultats
1. Le détecteur génère un graphique de pics.
2. Chaque pic représente une base
nucléotidique.
 évolution des modèles (1990-
1987 - 1er séquenceur 2000)
automatique
Deuxième génération (NGS - Next Generation Sequencing)
2005- Next Genration Sequencing
ou « high-throughput sequencing »
Nouvelles technologies de séquencage à Haut Débit
Récentes:
1ere commercialisé en 2005 (actuellement Roche 454),
Depuis x autres ont suivi (Illumina Solexa, Applied Biosystems, SOLiD [moribond], Ion
torrent, Pacbio, …)

Rapides:
~ 3 jours au lieu de 3 mois
Coût initial + production en baisse régulière
ex: 1000 génomes humains à « 1000$ »

Reads (Lectures) plus courts (pour le moment) :

taux d'erreur actuellement plus élevé => reads plus courts
 Haut Débit :
séquençage de milliers millions de « reads » en parallèle

Read = « lecture» de l'ordre de ~100 à ~400 bases.

Reads = comment sont-ils obtenus ??

principe général simplifié :

chaque lecture d'une lettre génère un point de couleur à une
position donnée sur une « image »
une suite d'images
Exemple lue donne une suite de couleurs, et (selon un code) une suite de
sur Illumina-Solexa
nucléotides …
1. Préparation de la bibliothèque
C'est la première étape clé pour préparer l'ADN ou l'ARN avant le séquençage.
•Fragmentation de l'ADN :
• L'ADN ou l'ARN est découpé en petits fragments (100 à 500 pb) ( mécaniquement ou enzymatiquement.
•Ajout des adaptateurs :
• Des adaptateurs (séquences d’ADN connues) sont fixés aux extrémités des fragments d’ADN.
• Ces adaptateurs permettent la liaison à la surface du séquenceur et la reconnaissance des fragments pendant le
séquençage.
•Amplification :
• Une amplification par PCR est souvent réalisée pour augmenter la quantité de fragments.
2. Fixation sur une surface solide (Flow Cell)
•Les fragments d’ADN préparés sont fixés à une surface solide (exemple : une cellule de flux dans les systèmes Illumina).
•Les adaptateurs fixés permettent l'ancrage des fragments à cette surface.

3. Amplification clonale
L’amplification clonale garantit que chaque fragment produit suffisamment de signal pour être détecté.
•PCR en pont (Bridge Amplification) :
• Les fragments d’ADN s’étendent en créant des clusters d’ADN identiques sur la surface de la flow cell.
• Chaque cluster représente plusieurs copies d’un fragment unique.
4. Séquençage par synthèse
Cette étape est propre à la technologie utilisée, mais la méthode la plus courante est le séquençage
par synthèse (Illumina).
•Principe général :
• Les nucléotides marqués par des fluorophores (A, T, C, G) sont ajoutés un par un.
• Un laser détecte la fluorescence émise lorsque chaque nucléotide est incorporé.
• La machine enregistre la couleur correspondant à chaque nucléotide incorporé.
•Résultat :
• Une image est générée pour chaque cycle, correspondant à l'ajout d'un nucléotide.

5. Lecture et assemblage
•Les données brutes générées sont des millions
de courtes lectures (short reads).
•Ces lectures sont alignées sur une séquence de
référence ou assemblées pour reconstruire le
génome.
Les 5 étapes du NGS
1. Préparation
Librairie

2. Amplification
clonale

3. Séquençage

4. Analyse bio-
informatique

5. Interprétation
biologique
La librairie
1. Préparation
Librairie

2. Amplification
clonale

3. Séquençage
Multiplexage
d’échantillons

4. Analyse bio-
informatique
Code-barre

5. Interprétation
biologique
L’enrichissement par capture
Génome
1. Préparation
Librairie

2. Amplification
clonale

3. Séquençage Panel de gènes,

Exome

4. Analyse bio-
informatique

5. Interprétation
biologique
Le séquençage
1. Préparation
Librairie

2. Amplification
clonale

3. Séquençage

4. Analyse bio-
informatique

5. Interprétation Ion torrent Solexa

biologique
ThermoFisher Illumina
 Troisième génération (NGS - Next Generation Sequencing)

Les technologies de troisième génération permettent un séquençage en temps réel de longues

molécules d'ADN ou d'ARN, sans amplification préalable. Cela élimine certains biais et erreurs
introduits par l'amplification.

Étapes principales
1. Extraction de l'ADN ou de l'ARN 2. Préparation de la bibliothèque
•Extraction de molécules d'ADN/ARN de haute •Les adaptateurs spécifiques sont fixés à l’ADN ou à l’ARN.
qualité et non fragmentées (préservation des •Contrairement à la deuxième génération, il n'y a
longues chaînes). généralement pas d’amplification, ce qui préserve la structure
•Préparation adaptée à la technologie utilisée. originale des fragments.

3. Séquençage en temps réel

•Longues lectures :
• Les technologies comme PacBio ou Oxford Nanopore permettent de lire des fragments d’ADN de
plusieurs dizaines à centaines de kilobases.
• Le séquençage se fait directement, sans amplification.
•Détection du signal :
• Les bases d'ADN sont identifiées en temps réel selon leur interaction avec une enzyme ou un capteur.
Par exemple :
• PacBio SMRT (Single Molecule Real-Time sequencing) :
• L’ADN passe dans une cavité nanométrique (ZMW - Zero-Mode Waveguide).
• Les bases incorporées par une polymérase émettent un signal fluorescent unique détecté par
des lasers.
• Oxford Nanopore :
• L’ADN ou l’ARN passe à travers un nanopore.
• Les bases sont détectées par les changements de courant électrique lorsqu'elles traversent le
pore.
2. La spécificité des données NGS

1. Volume important de données

•Massivité : Les plateformes NGS génèrent des milliards de lectures (reads),
produisant des quantités énormes de données, souvent en téraoctets.
•Conséquences : Ces données nécessitent des outils bioinformatiques
performants et une infrastructure informatique adaptée pour leur stockage et
analyse.
Introduction aux Formats de Fichiers NGS
La séquence de nouvelle génération (NGS) génère de grandes quantités de données. Ces
données sont stockées dans différents formats de fichiers, chacun ayant une utilité spécifique pour
les données biologiques, telles que les séquences de nucléotides, les scores de qualité, les
alignements, et les annotations génomiques.

3. SAM/BAM/CRAM
1. FASTA (FAST-All) Objectif : Stocke les alignements des lectures avec un
Objectif : Stocke des séquences biologiques (ADN, ARN, génome de référence.
protéines). Formats :
Format : •SAM : Format texte lisible.
•Une ligne de description (précédée de ">"), suivie de la •BAM : Version binaire de SAM, plus efficace pour le
séquence. stockage.
>Sequence_1 Exemple SAM :
ATCGTGCATGCA @SQ SN:ref LN:45
read1 99 ref 7 30 8M2I4M1D3M = 37 39
TTAGATAAAGGATACTG *
2. FASTQ (FAST-QuaLity)
Objectif : Extension du format FASTA avec les scores de qualité pour
chaque base.
4. BED/GTF
Format :
Objectif : Représente les annotations génomiques (gènes,
•Quatre lignes : identifiant de la séquence, séquence, un "+" et les scores
exons, etc.).
de qualité.
Format :
Exemple :
•BED : Format simple, tabulé
@SEQ_ID
EX: chr1 100 200 gene1 0 +
GATTTGGGGTTCAAAGCAGTATCGATCAAATAGTAAATCCATTTGTTC
•GTF : Format plus détaillé.
AACTCACAGTTT
EX: chr1 . gene 100 200 . + . gene_id "gene1";
+
!''*((((***+))%%%++)(%%%%).1***-+*''))**55CCF>>>>>>CCCCCCC65
L’analyse bio-informatique des données
1. Préparation
Librairie
1. Détermination de la séquence « Base calling »
2. Amplification
(Fastq)
clonale 2. Alignement de la séquence sur le génome de
référence
• « Mapping » (BAM/SAM)
3.
Séquençage 3. Détection des variants « Variant calling » (VCF)
4. Annotation des variants (VCF)
4. Analyse bio-
informatique 5. Filtrage des variants

5. Interprétation
biologique
L’analyse bio-informatique des données
1. Préparation • Scores de qualité « QC Metrics »
Librairie Séq. Brutes Séquences utiles globalement
➣ Eliminer duplicats de PCR, off target
• Attribuer index (dé-multiplexage)
2. Amplification
clonale
1. Détermination de la séquence « Base calling » (Fastq)
2. Alignement de la séquence sur le génome de référence
3. • « Mapping » (BAM/SAM)
Séquençage 3. Détection des variants « Variant calling » (VCF)
4. Analyse bio- 4. Annotation des variants (VCF)
informatique
5. Filtrage des variants
5. Interprétation
biologique
L’analyse bio-informatique des données
• Scores de qualité « QC Metrics »
Séq. Brutes Séquences utiles globalement
➣ Eliminer duplicats de PCR, off target
1. Préparation • Attribuer index (dé-multiplexage)
Librairie
1. Détermination de la séquence «
Base calling » (FASTQ)
2. Amplification
clonale
2. Alignement de la séquence sur le
génome de référence
« Mapping » (BAM/SAM)
3. Séquençage 3. Détection des variants « Variant
calling » (VCF)
4. Analyse bio- 4. Annotation des variants (VCF)
informatique
5. Filtrage des variants
Deux paramètres
essentiels
5. Interprétation
biologique ➣ Profondeur de
lecture
➣ Couverture de
séquence
L’analyse des données
1. Préparation
Librairie
1. Détermination de la séquence « Base calling »
(FASTQ)
2. Amplification
clonale 2. Alignement de la séquence sur le génome de
référence
« Mapping » (BAM/SAM)
3. Séquençage 3. Détection des variants « Variant calling » (VCF)
4. Annotation des variants (VCF)
4. Analyse bio- 5. Filtrage des variants
informatique

5. Interprétation ➣ Associer à chaque variant des

biologique •données
gène /sur
transcrit (s)
• Fréquence du variant dans les bases de
données
• Effet sur la protéine, sur l’épissage
• Prédictions de scores de pathogénicité
 L’analyse des données
1. Préparation
Librairie

1. Détermination de la séquence «
2. Amplification Base calling » (FASTQ)
clonale
2. Alignement de la séquence sur le
génome de référence
3. Séquençage « Mapping » (BAM/SAM)
3. Détection des variants « Variant
calling » (VCF)
4. Analyse bio-
informatique 4. Annotation des variants (VCF)
5. Filtrage / « priorisation » des
5. Interprétation variants
biologique