Upload
juste-garin
View
111
Download
0
Embed Size (px)
Citation preview
Alignement de séquences biologiquesAlignement de séquences biologiques
Objectifs poursuivis Alignement de séquences: généralités Alignement de deux séquences Recherche rapide de similarités dans les banques de
séquences Alignement de n séquences (alignement multiple) Recherche de motifs dans les séquences
Objectifs poursuivisObjectifs poursuivis
Les alignements permettent de comparer des séquences biologiques. Cette comparaison est nécessaire dans différents types d’études :
Identification de gènes homologues Recherche de contraintes fonctionnelles communes à un ensemble de gènes
ou de protéines. Prédiction de structure (ARN, protéine) Prédiction de fonction Étude des processus créateurs de variabilité entre les séquences. Reconstitution des relations évolutives entre séquences. Choix d'amorces PCR Construction de contigs (séquençage) ...
Analyse comparative des gènes de Analyse comparative des gènes de -actine de l'homme et de la carpe-actine de l'homme et de la carpe
CarpeHomme5’UTR 3’UTR site polyA échelle de similarité: pas de similarité significative70 - 80% identité80 - 90% identitérégions codantes: éléments régulateurs:introns:ATGcodon stop
Prédiction de structure d'ARNPrédiction de structure d'ARN
C A G U G G C A U G C A C U GC A G C G G C G U G C G C U GC A G C G G T A U G C G C U GC A A U G G T A U G C A U U GC A G U G G C A U G C A C U G* * * * * * * * *
GUGACCACUGGCATG
Phylogénie moléculairePhylogénie moléculaire
Alignement: représentationAlignement: représentation
Les résidus (nucléotides, acides-aminés) sont superposés de façon à maximiser la similarité entre les séquences.
G T T A A G G C G – G G A A A
G T T – – – G C G A G G A C A
* * * * * * * * * * Mutations :
Substitution (mismatch) Insertion Délétion
Insertions ou délétions : indels (gap).
Quel est le bon alignement ?Quel est le bon alignement ?G T T A C G A G T T A C G AG T T - G G A G T T G - G A* * * * * * * * * *
OU
G T T A C - G AG T T - - G G A* * * * *
Pour le biologiste, généralement, le bon alignement est celui qui représente le scénario évolutif le plus probable
Autres choix possibles (exemple: erreurs de séquençage pour la construction de contigs)
Fonction de score de similaritéFonction de score de similarité
G T T A A G G C G – G G A A AG T T – – – G C G A G G A C A* * * * * * * * * *
Score =
Exemple: identité = 1 mismatch = 0 gap = -1
Score = 10 - 4 = 6
pondération_ substitution− pénalité_gapdébut
fin
∑début
fin
∑
Modèle d'évolution (ADN) Modèle d'évolution (ADN)
Transition: A <-> G T <-> C Transversions : autres substitutions p(transition) > p(transversion)
G T T A C G A G T T A C G A
G T T - G G A G T T G - G A
* * * * * * * * . * *
ACGT
Matrice de substitution (ADN)Matrice de substitution (ADN)
Gap = -1G T T A C G A G T T A C G AG T T - G G A G T T G - G A1 1 1 -1 0 1 1 1 1 1 .5 -1 1 1
score = 4 score = 4.5
ACGTACGT100.50100.50.5000.501010Exemples:δA,A()=1δA,C()=0δ,T()=0.5
Modèle d'évolution (protéines) Modèle d'évolution (protéines) Code génétique
Asp (GAC, GAU) Tyr (UAC, UAU) : 1 mutation Asp (GAC, GAU) Cys (UGC, UGU) : 2 mutations Asp (GAC, GAU) Trp (UGG) : 3 mutations
Propriétés physico-chimiques des acides-aminés (acidité, hydrophobicité, encombrement stérique, etc.)
Matrices de Dayhoff (PAM), BLOSUM: mesures des fréquences de substitutions dans des alignements de protéines homologues
PAM 60, PAM 120, PAM 250 (extrapolations à partir de PAM 15) BLOSUM 80, BLOSUM 62, BLOSUM 40 (basé sur des alignements de blocs)
ValIleHCCOOHHCCH3CH3NH2HCCOOHHCCH3CH2NH2CH3
Substitutions Substitutions conservatricesconservatrices
Matrice de substitution (protéines)Matrice de substitution (protéines)
D (Asp) E(Glu) F(Phe) G(Gly) W(Trp)
M R D W - G F M R - D W G F M R - W D G F M R W D - G F * * * * * * * * * *
Substitutions multiples (exemple: D E D)
DEFGDEFGWW44-61-204-61-20-10-20-20-10-201-64-61-205-613-6Exemples:δD,E()=4δF,D()=−6δW,G()=−2020
Pondération des gapsPondération des gaps
TGATATCGCCA TGATATCGCCA
TGAT---TCCA TGAT-T--CCA
**** *** **** * ***
Gap de longueur k: Pénalités linéaires: w = δo + δe k δo : pénalité pour l'ouverture d'un gap
δe : pénalité pour l'extension d'un gap
0
10
20
30
40
50
0 5 10 15 20k
Pondération des gaps (plus réaliste)Pondération des gaps (plus réaliste) Estimation des paramètres sur des alignements "vrais" (par exemple basés sur
l'alignement de structures connues) Gap de longueur k:
Pénalités logarithmiques: w = δo + δe log(k)
w = f(log(k), log(PAM), résidus, structure)– PAM: la probabilité d'un gap augmente avec la distance évolutive– Résidus, structure: la probabilité d'un gap est plus forte dans une boucle
(hydrophile) que dans le cœur hydrophobe des protéines
0
10
20
30
40
0 5 10 15 20k
Similarité globale, locale Similarité globale, locale
ARNmgènedomaineprotéine Aprotéine Bprotéine Aprotéine Bsimilarité globalesimilarité locale
Similarité, distance, homologie Similarité, distance, homologie Deux séquences sont homologues ssi elles ont un ancêtre commun
30% d'identité entre deux protéines => homologie, sauf si Fragment similaire court (< 100 aa) Biais compositionnel (régions de faible complexité, par exemple riche en Pro, Ala)
Le nombre d'alignementsLe nombre d'alignements Waterman (1984) a donné la formule récursive permettant de
calculer le nombre total d’alignements possibles entre deux séquences comportant m et n résidus :
D’autre part, Laquer (1978) a démontré que :
Le nombre total d’alignements possibles entre deux séquences de même longueur croît de façon exponentielle.
f m,n( ) = f m−1,n( ) + f m−1,n−1( ) + f m,n−1( )
Avec f 0, j( ) = f i,0( ) =1 ∀i, j
limn→ +∞
f (n,n) = n 1+ 2( )2n+1
Algorithmes d'alignement de deux Algorithmes d'alignement de deux séquencesséquences
Algorithme: description d'une suite d'opérations pour atteindre un objectif
Calculer l'ensemble de tous les alignements possibles et garder celui de meilleur score
Trop long (nombre d'alignements = f(exp(L)) Pas efficace (on recalcule souvent les mêmes valeurs)
G T T A C G A G T T A C G A
G T T - G G A G T T G - G A
* * * * * *
Algorithme de programmation dynamique Calcul de proche en proche de l'alignement optimal
Définition de la matrice de cheminsDéfinition de la matrice de chemins Les alignements peuvent être représentés sous la forme d’une
trajectoire dans une matrice de chemins. Pour chaque trajectoire on peut calculer un score et il faut donc
trouver celle qui optimise ce score. Soit deux séquences A et B de longueurs respectives m et n définissant
une matrice de chemin S. Dans chaque case de cette matrice on va stocker S(i, j), le score optimum de la trajectoire permettant d’arriver à cette case.
Exemple de matrice de cheminExemple de matrice de chemin
Construction récursive de la matriceConstruction récursive de la matrice Soit la case de coordonnées (i, j). Quelle que soit la trajectoire retenue, elle passera
forcément par l’une des trois cases la précédant, de coordonnées (i–1, j), (i–1, j–1), (i, j–1).
Supposons que l’on connaisse les scores optimums des trois cases précédentes, dans ce cas la valeur optimum du score dans la case (i, j) sera égale à :
Needleman et Wunsh, 1970
iS(i, j)i–1j–1j
S i, j( ) =max
S(i−1, j)+δ(gap),
S(i−1, j−1)+δ(ai,bj ),
S(i, j−1)+δ(gap)
⎡
⎣
⎢ ⎢ ⎢
⎤
⎦
⎥ ⎥ ⎥
Bords de la matriceBords de la matrice
Les cases situées sur le bord du haut ou le bord gauche de la matrice ne possèdent plus le total requis de trois cases précédentes.
Pour pallier ce problème on ajoute une ligne (0, j) et une colonne (i, 0) supplémentaires. Le balayage de la matrice ne se faisant plus qu’avec des indices ≥ 1 on ne rencontre plus de cases nécessitant un traitement particulier.
S(i, j)Bord gaucheS(i, j)Bord du haut
Bords de la matrice (suite)Bords de la matrice (suite)
La ligne et la colonne supplémentaires doivent être initialisées pour pouvoir construire la matrice.
Il existe plusieurs manières de faire selon la façon dont on veut comptabiliser les gains ou pertes d’éléments au niveau des extrémités.
En particulier, il faut savoir si on veut pénaliser ou non les éléments terminaux non appariés (ce que l’on appelle les extrémités flottantes).
- - - A T T C G T A T - - - T C G T
A T G A T T C G T A T G A T T C G T
* * * * * * * * * * * *
Bords de la matrice (fin)Bords de la matrice (fin)
Pénalisation des gaps terminaux
Pas de pénalisation des gaps terminaux
S(0,0) =0
i :1→ m S(i, 0) =0
j :1→ n S(0, j) =0
i:1→mS(i,0)=S(i−1,0)+δ(gap)j:1→nS(0,j)=S(0,j−1)+δ(gap)S(0,0)=0
Identité : +1Mismatch : +0Gap : –2
ATTGATG
Identité : +1Mismatch : +0Gap : –2
ATTGATGIdentité:Identité: +1+1Mismatch:Mismatch: +0+0Gap interne:Gap interne: -2-2Gap terminal:Gap terminal: +0+0
AGCTAATTAIdentité : +1Mismatch : 0Gap : -2
Identité : +1Mismatch : +0Gap : –2
CTACGTACTATA
Alignement local Alignement local (Smith-Waterman)(Smith-Waterman)
Initialisation des bords de la matrice de chemin à 0
S i, j( ) =max
S(i−1, j)+δ(gap),
S(i−1, j−1)+δ(ai,bj ),
S(i, j−1)+δ(gap)
0
⎡
⎣
⎢ ⎢ ⎢ ⎢ ⎢
⎤
⎦
⎥ ⎥ ⎥ ⎥ ⎥
Temps de calcul et occupation de la mémoire pour Temps de calcul et occupation de la mémoire pour l'alignement de deux séquences de longueur n et ml'alignement de deux séquences de longueur n et m
Needleman-Wunsh Temps: O(n m) Espace mémoire: O(n m) Amélioration: éliminer les chemins qui s'éloignent trop de la
diagonale Smith-Waterman
Temps: O(n m) Espace mémoire: O(n m)
Amélioration de Smith-Waterman Temps: O(n m) Espace mémoire: O(n)
Dot PlotDot Plot Représentation graphique de régions d'identité ou de similarité
entre deux séquences
Utilisation de fenêtres et de seuils pour réduire le bruit de fond Visualisation des inversion, duplications, palindromes
CTTGCACGTATCTGCACGTATTA
Recherche rapide de similarités dans les Recherche rapide de similarités dans les banques de séquencesbanques de séquences
Comparaison d'une séquence à toute une banque de données de séquences, comparaisons entre deux banques …
Algorithmes exhaustifs (Smith-Waterman) DAP, BLITZ, SSEARCH, …
Algorithmes basés sur des heuristiques FASTA
1 - recherche de ‘ k-tuplets ’ identiques
2 - alignement global, ancré sur la région similaire
BLAST
1 - recherche de ‘ mots ’ similaires
2 - extension des blocs similaires
BLASTBLASTSéquencebanqueSéquencerequêteLongueur du mot = WScore ≥ T (Threshold score)MotEtape 1: détection de “mots” similairesEtape 2 : extension du segment similaire ScoreExtension du segmentExtension est stoppée quand : - la fin d’une des deux séquences est atteinte - score ≤ 0 - score ≤ score_max - X
SéquencebanqueSéquencerequêteHSP: high score segment pair)TScore maxX
Alignement par bloc ou alignement global : comparaison BLAST / FASTA
protéine 1protéine 2A1B1C1A'1A2C2B2A2A1B1C1A'1A2C2B2A1B1C1A'1A2C2B2Recherche desimilitudeFASTABLAST
Stratégies de recherche de similarités: ADN ou protéine ?Stratégies de recherche de similarités: ADN ou protéine ? Limites des recherches de similarité au niveau ADN
Alphabet réduit (4 lettres) Dégénérescence du code génétique
Mais … tout n'est pas codant régions régulatrices, ARN structuraux, ...
Deux brins!Deux brins!
Différentes versions de BLAST adaptées à Différentes versions de BLAST adaptées à différents problèmesdifférents problèmes
blastp: protéine/protéine blastn: ADN/ADN (utile pour non-codant) blastx: ADN-traduit/protéine (utile pour séquences
codantes non-identifiées; plus sensible que blastn) tblastn: protéine/ADN-traduit (utile pour
rechercher des homologues de gènes protéiques dans un génome non-entièrement annoté; plus sensible que blastn)
Choix de la matrice de substitutionsChoix de la matrice de substitutions
Différentes matrices de substitutions, adaptées à différentes distances évolutives
BLOSUM 62: convient pour une large gamme de distances évolutives
Combiner plusieurs matrices
Évaluation statistique de la similaritéÉvaluation statistique de la similarité Parmi les similarités qui ont été détectées, quelles sont celles qui reflètent des
relations biologiquement importantes, quelles sont celles qui sont simplement dues au hasard ?
Distribution des scores d'alignements locaux optimaux entre séquences non homologues
Probabilité qu'une similarité de score S soit simplement due au hasardScoreScore
Nombre d'occurrencesNombre d'occurrences
Traitement du bruit de fond: filtres et masquesTraitement du bruit de fond: filtres et masques Similarités sans intérêt biologique
Séquences de faible complexité (protéines, ADN):40% des protéines ADN: microsatellites
15% du total des résidus exemple: CACACACACACACACACA
Ala, Gly, Pro, Ser, Glu, Gln
logiciels de filtrage: SEG, XNU, DUST
RSPPR--KPQGPPQQEGNNPQGPPPPAGGNPQQPQAPPAGQPQGPP . ::: : :: : : ::::: : :: :.: :: : :::::QGPPRPGNQQCPPPQGG--PQGPPRP--GNQQRP--PPQGGPQGPP
Séquences abondantes
3000 Immunoglobulines dans GenBank
106 Alu, 105 L1 dans le génome humain
logiciels de masquage: XBLAST, RepeatMasker
NNNNNNNNNNNNN
Bilan: quelle approche adopter ?Bilan: quelle approche adopter ?
algorithme matrices de substitution, pondération des gaps stratégie de recherche (nucléique, protéique) traitement du bruit de fond complétude des banques de données
1 - logiciel rapide, paramètres par défaut 2 - filtrage éventuel 3 - changement des paramètres (matrices, W, k, etc.) 4 - changement d'algorithme 5 - répéter la recherche régulièrement
Alignement multiple: programmation dynamiqueAlignement multiple: programmation dynamique
La généralisation de l’algorithme précédent au traitement simultané de plus de deux séquences est théoriquement possible mais inexploitable en pratique.
Pour un alignement de n séquences le nombre de chemins possibles pour chaque case est de 2n – 1.
On a une croissance exponentielle du temps de calcul et de l'espace mémoire requis en fonction du nombre de séquences.
Problème du choix d ’une fonction de score Utilisation de méthodes heuristiques.
Alignement de deuxséquences : trois choix
Alignement de troisséquences : sept choix
Alignement progressifAlignement progressif
Approche consistant à construire itérativement l’alignement multiple en groupant des alignements de paires de séquences.
Ce genre de méthodes comporte trois étapes : L’alignement des paires de séquences. Le groupement des séquences. Le groupement des alignements (alignement progressif).
CLUSTAL (Thompson et al., 1994), le programme d’alignements multiples le plus utilisé à l’heure actuelle utilise cette approche.
Pénalités initiales pour les gapsPénalités initiales pour les gaps CLUSTAL utilise une fonction de pénalité linéaire pour les gaps. De
plus, les valeurs initiales de δo et δe sont corrigées en fonction de nombreux facteurs :
Le degré de similarité entre les séquences : δo %identité(A, B)
La longueur des séquences :δo log[min(m, n)]
La différence de longueur entre les deux séquences :δe 1.0 + log[n/m]
Ces pondérations sont prises en compte au moment de l’alignement des paires de séquences.
Pénalités en fonction de la positionPénalités en fonction de la position CLUSTAL introduit également des pondérations qui sont dépendantes
de la position des gaps.
Diminution de la pénalité à l’emplacement de gaps préexistants. Augmentation de la pénalité au voisinage (8 résidus) de gaps préexistants. Réduction de la pénalité au niveau de régions contenant des suites
d’acides aminés hydrophiles (≥ 5 résidus). Modification spécifiques en fonction des acides aminés présents
(e.g., la pénalité est plus faible avec Gly, Asn, Pro).
Ces pondérations sont prises en compte au moment du groupement des alignements.
Alignement progressif: pas toujours Alignement progressif: pas toujours optimaloptimal
Un seul des ces trois alignements est optimal
Alignement de trois séquences
x ...ACTTA...y ...AGTA...z ...ACGTA...
Arbre guide
Etape 1: alignement xy
x ACTTA x ACTTA x ACTTAy A-GTA y AGT-A y AG-TA
Etape 2: alignement xyz
x ACTTA x ACTTA x ACTTAy A-GTA y AGT-A y AG-TAz ACGTA z ACGTA z ACGTA
xyz
Global Alignments, Global Alignments, Block alignmentsBlock alignments
1234 5123 51234 5134 5 123 123 123 123a) b)
DialignDialignMorgenstern et al. 1996 PNAS 93:12098Morgenstern et al. 1996 PNAS 93:12098
Search for similar blocks without gap
Select the best combination of consistent similar blocks (uniforms or not) : heuristic (Abdeddaim 1997)
Alignment anchored on blocks Slower than progressive alignment, but better when sequences contain
large indels Do not try to align non-conserved regions
A G A G T C A C T A G T C A
A G T G T C A C A T A A T C A A
T C A C A T A A T C A A
C G T A A C T G A A T C A G A G T
Exact blockUniform block
Local Multiple AlignmentsLocal Multiple Alignments
MEME MATCH-BOX PIMA
1341234122241234
OverviewOverview
ClustalW
Dialign T-coffee
MEME
1234 5123 51234 5134 5 123 123 123 1231341234122241234
Éditeur d ’alignement multipleÉditeur d ’alignement multiple
Special casesSpecial casesAlignment of coding DNA sequences
L F L F CTT TTC CTT TTC
CTC --- --- CTC L - - L
alignment of protein sequencesback-translation of the protein alignment into a DNA alignment
Alignment cDNA / genomic DNA: SIM4Alignment protein / genomic DNA : GeneWise
Limits of pairwise comparison (BLAST, FASTA, ...)Limits of pairwise comparison (BLAST, FASTA, ...)
Seq A CGRRLILFMLATCGECDTDSSE … HICCIKQCDVQDIIRVCC
:: : ::: :: : :
Insulin CGSHLVEALYLVCGERGFFYTP … EQCCTSICSLYQLENYCN
::: : : : :: : :
Seq B YQSHLLIVLLAITLECFFSDRK … KRQWISIFDLQTLRPMTA
Pairwise comparison:
Insulin / Seq A : 25% identity
Insulin / Seq B : 25% identity
Insulin gene family: sequence alignment Insulin gene family: sequence alignment
B-chain A-chain
INSL4 Q14641 ELRGCGPRFGKHLLSYCPMPEKTFTTTPGG...[x]58 ....SGRHRFDPFCCEVICDDGTSVKLCT
INSL3 P51460 REKLCGHHFVRALVRVCGGPRWSTEA.......[x]51 ....AAATNPARYCCLSGCTQQDLLTLCPY
RLN1 P04808 VIKLCGRELVRAQIAICGMSTWS..........[x]109 ....PYVALFEKCCLIGCTKRSLAKYC
BBXA P26732 VHTYCGRHLARTLADLCWEAGVD..........[x]25 ........GIVDECCLRPCSVDVLLSYC
BBXB P26733 ARTYCGRHLADTLADLCF--GVE..........[x]23 ........GVVDECCFRPCTLDVLLSYCG
BBXC P26735 SQFYCGDFLARTMSILCWPDMP...........[x]25 ........GIVDECCYRPCTTDVLKLYCDKQI
BBXD P26736 GHIYCGRYLAYKMADLCWRAGFE..........[x]25 ........GIADECCLQPCTNDVLLSYC
LIRP P15131 VARYCGEKLSNALKLVCRGNYNTMF........[x]58 ........GVFDECCRKSCSISELQTYCGRR
MIP I P07223 RRGVCGSALADLVDFACSSSNQPAMV.......[x]29 ....QGTTNIVCECCMKPCTLSELRQYCP
MIP II P25289 PRGICGSNLAGFRAFICSNQNSPSMV.......[x]44 ....QRTTNLVCECCFNYCTPDVVRKYCY
MIP III P80090 PRGLCGSTLANMVQWLCSTYTTSSKV.......[x]30 ....ESRPSIVCECCFNQCTVQELLAYC
MIP V P31241 PRGICGSDLADLRAFICSRRNQPAMV.......[x]44 ....QRTTNLVCECCYNVCTVDVFYEYCY
MIP VII P91797 PRGLCGNRLARAHANLCFLLRNTYPDIFPR...[x]86 ..EVMAEPSLVCDCCYNECSVRKLATYC
ILP P22334 AEYLCGSTLADVLSFVCGNRGYNSQP.......[x]31 ........GLVEECCYNVCDYSQLESYCNPYS
INS P01308 NQHLCGSHLVEALYLVCGERGFFYTPKT.....[x]35 ........GIVEQCCTSICSLYQLENYCN
IGF1 P01343 PETLCGAELVDALQFVCGDRGFYF.........[x]12 ........GIVDECCFRSCDLRRLEMYCAPLK
IGF2 P01344 SETLCGGELVDTLQFVCGDRGFYF.........[x]12 ........GIVEECCFRSCDLALLETYCATPA
*. .* ** * . *
Biomolecular Sequence Motif DescriptorsBiomolecular Sequence Motif Descriptors
Exact word: e.g. EcoRI restriction site GAATTC
Consensus: e.g. TATA box: TATAWAWR
Regular expression: e.g. insulins PROSITE pattern C-C-{P}-x(2-4)-C-[STDNEKPI]-x(3)-[LIVMFS]-x(3)-C
Weight matrix: position-specific weighting of substitutions
Generalised profiles (hidden markov models) : position-specific weighting of substitutions and indels
Example of weight matrixExample of weight matrix
Splice donnor sites of vertebrates: frequency (%) of the four bases at each position
log transformation weight matrix
Base Position-3 -2 -1 +1 +2 +3 +4 +5 +6
A 33 60 8 0 0 49 71 6 15C 37 13 4 0 0 3 7 5 19G 18 14 81 100 0 45 12 84 20T 12 13 7 0 100 3 9 5 46
Cons. M A G G T R A G T
Searching for distantly related Searching for distantly related homologues in sequence databaseshomologues in sequence databases
1- search for homologues (e.g. BLAST) 2- align homologues (e.g. CLUSTAL, MEME) 3- compute a profile from the multiple alignment 4- compare the profile to a sequence database (e.g. MAST,
pfsearch)
pfsearch: http://www.isrec.isb-sib.ch/profile/profile.html
MEME/MAST: http://meme.sdsc.edu/meme/website/
PSI-BLASTPSI-BLAST
Position-Specific Iterated BLAST 1- classical BLAST search 2- compute a profile with significant BLAST hits 3- BLAST search based on the profile 4 -repeat steps 2-3 up to convergence
More sensitive than Smith-Waterman 40 times faster
Comparison of a sequence to Comparison of a sequence to a database of protein motifsa database of protein motifs
Databases: PROSITE, PFAM, PRODOM, …, INTERPRO
Search tools: ProfileScan : http://hits.isb-sib.ch/cgi-bin/PFSCAN