Comparaison de séquences - QCM - Polytech Clermont - Janvier 2019 PDF

Comparaison de séq d'acides nucléiques o - Alignements de séq Important - Pour information : « Examen » QCM (Zapettes) ~ 30 questions Temporisation automatique 30 – 40 s 1 réponse /question +1 / réponse juste -0.25 /...

Comparaison de séq d'acides nucléiques o - Alignements de séq Important - Pour information : « Examen » QCM (Zapettes) ~ 30 questions Temporisation automatique 30 – 40 s 1 réponse /question +1 / réponse juste -0.25 / réponse fausse Date(s) : 28 Nov. 2024– Amphi 1 – 10h15 Polytech Clermont | Evénement XYZ| Janvier 2019 2 Objectif Connaitre les concepts associés aux méthodes de comparaison de séquences nucléiques et d’acides aminés Pré-requis Génie Génétique / Terminologie Acquis ✓Banques de données Biologiques ✓Recherche dans les Banques de données ✓Méthodes de comparaison de séquences ✓ Principe des calculs de score ✓ Principaux algorithmes de comparaison et leur utilisation (limite et interprétation des résultats) ✓ Utilisation BLAST Polytech Clermont | Evénement XYZ| Janvier 2019 3 1 - Introduction Rappels et contexte Bases de données de séquences ? Comparaison de séquences ? Définitions / terminologie 2 – Comparaison de séquences 2 à 2 Première approche : le dot plot Comparaison avec alignement L’alignement et son évaluation : scores et Matrices de substitution Algorithmes d’alignement A la base de tous les algorithmes : programmation dynamique Alignement Global (Needelman et Wunsch, 1970) Alignement Local (Smith et Waterman, 1981) 3 - Comparaison d’une séquence avec les BD Principe et limitation de la recherche par similitude FASTA (Lipman, Pearson, 1985) BLAST (Altshul et al. , 1990) 4 – L’alignement Multiple CLUSTALW Polytech Clermont | Evénement XYZ| Janvier 2019 4  1 - Introduction Rappels et contexte Biologie Une science « molle » (par opposition aux sciences dures = physique / chimie) Biologie = étude des relations spatiales et dynamiques entre objets « vivants » Rien n’est totalement prévisible, reproductible ou constant Concepts et principes pour la pluparts empruntés à la physique ou la chimie Bio-informatique (terme vague et définitions variables) Champ de recherche multi-disciplinaire (biologistes, informaticiens, mathématiciens et physiciens) dont le but est de résoudre un problème scientifique posé par la biologie. Peut être considérée, suivant les situations, comme une science ou comme une technologie. Polytech Clermont | Evénement XYZ| Janvier 2019 5 6 La bioinformatique des séquences La bioinformatique structurale. La bioinformatique des réseaux (interactions entre gènes, protéines, cellules, organismes, flux génétiques ou métaboliques. La bioinformatique statistique et la bioinformatique des populations Comparaison Séquences -– Version 4-23  1 - Introduction Rappels et contexte Culture générale : Biologie (ADN) et Informatique … 19ième : Evolution et hérédité 1859 – théorie évolution (Darwin) 1866 – les lois de Mendel (à partir d’analyse statistique de données biologiques) 1913 – mise en évidence du chromosome comme support cellulaire de l’hérédité et de l’information génétique (Morgan) 1940 - 1970 1946 – ENIAC (ancêtre ordinateur) 1953 – double hélice de l’ADN (Watson & Crick) 1965 – régulation génétique (opéron lactose – Jacob, Monod & Lwoff) 1968 – 1ère calculatrice programmable (T.I. , 20kg) 1969 – arpanet (ancêtre internet) 1970 – 1ère méthode d’alignement de séquences (2 à 2) 1971 – microprocesseur Intel Polytech Clermont | Evénement XYZ| Janvier 2019 7  1 - Introduction Rappels et contexte 1970 - 1990 1977 – techniques de séquençage des acides nucléiques 1977 – 1ers ordinateurs « micro » (et consoles de jeux) 1978 – Tech. Comparaison Séqu. : matrices PAM 1984 – technique de séquençage par PCR 1985 – début du séquençage massif des génomes (1er séquenceur en 1987) / techniques haut débit 1986 – 1ers serveurs de séquences « mondiaux » (1980 EBI , 1986 Swiss-prot, DDBJ , 1988 NCBI) 1988 - Tech. Comparaison Séqu. : FASTA 1988 – HUGO : Human Genome Organisation 1989 – internet et WWW (premiers « vrais » navigateurs en 1993) 1990 – Tech. Comparaison Séqu. : BLAST 1992 - Tech. Comparaison Séqu. : matrices BLOSUM Polytech Clermont | Evénement XYZ| Janvier 2019 8  1 - Introduction Rappels et contexte Avant ~1990 Séquençage, analyse, annotation séquences de génomes au niveau du laboratoire Avantages : détail et précision des analyses Inconvénients : quantité / qualité des séquences Après ~1990 Séquençage massif Avantages : quantité (…qualité en augmentation…) des séquences / génomes Inconvénients : automatisation des annotations et risque de récursivité des erreurs Source : EMBL-EBI – methodology - 2024 Polytech Clermont | Evénement XYZ| Janvier 2019 9  1 - Introduction Rappels et contexte Gros volumes de données Outils de stockage (BDD) Outils d’analyse et d’interprétation Polytech Clermont | Evénement XYZ| Janvier 2019 10  1 - Introduction Bases de données de séquences ? Bases de Données en biologie moléculaire et plus spécifiquement BDD de séquences Trop nombreuses pour être présentées de manière exhaustive. Peuvent être : publiques / privées De Séquences primaires De Séquence assemblées / gènes ; Génomes De Structure Relationnelles et fonctionnelles Spécifiques à un ou plusieurs Organismes Cliniques …….. Un petit aperçu dans Nucleic Acids Research qui réalise une review tous les ans sur les bases de données de biology moléculaire https://www.oxfordjournals.org/nar/database/c/ Mise à jour Janvier 2023 : “we have updated 463 entries, 92 new resources have made it to the database and further 96 discontinued were removed, bringing the total collection to 1764 databases” Polytech Clermont | Evénement XYZ| Janvier 2019 11  1 - Introduction Bases de données de séquences ? BDD de séquences primaires issues de collaboration internationales et publiques (Les principales et celles avec lesquelles on pourra travailler en TP) Séquences Nucléiques ENA ( European Nucleotide Archive / EMBL-EBI - Europe) : submissions of raw data, assembled sequences and annotation from small-scale sequencing efforts, data provision from the major European sequencing centres and exchange with our partners in the International Nucleotide Sequence Database Collaboration Genbank (NCBI - USA) : publicy nucleotide sequences for 400 000 formally described species obtained primarily through submissions from individual laboratories and batch submissions from large-scale sequencing projects. Daily data exchange with the European Nucleotide Archive and the DNA Data Bank of Japan ensures worldwide coverage DDBJ (DNA Data Bank of Japan - GenomeNet Japon) : All known nucleotide and protein sequences Séquences Protéiques NCBI Protein Database (NCBI - USA) : sequences taken from a variety of sources, including SwissProt, PIR ( Protein Information Resource), PRF (Protein Research Foundation), PDB (Protein Data Bank), and translations from annotated coding regions in the GenBank and RefSeq databases. Uniprot (EMBL-EBI - Europe) : The UniProt databases are produced by the members of the UniProt Consortium who are based in the UK at the EMBL-EBI, in Switzerland at the SIB (Swissprot) and in the US at the PIR. Polytech Clermont | Evénement XYZ| Janvier 2019 12  1 - Introduction Bases de données de séquences ? Interconnexions (complexes) entre les bases de données : exemple DBGET databases (GenomeNet) Biblio/PubMed Métabolites/molécules Séq. Nucléiques Séq. proteiques Polytech Clermont | Evénement XYZ| Janvier 2019 13  1 - Introduction Bases de données de séquences ? 4 principaux portails de Base de Données de séquences (publiques) GenomeNet / KEGG With 28 member states, laboratories at six sites across Europe working together, the European Molecular Biology Laboratory (EMBL) is an intergovernmental organisation, headquartered in Heidelberg, and was founded in 1974 with the mission of promoting molecular biology research in Europe Expasy is the bioinformatics GenomeNet is a Japanese network of resource portal of the SIB database and computational services Swiss Institute of for genome research and related Bioinformatics research areas in biomedical sciences, operated by the Kyoto University Bioinformatics Center. Polytech Clermont | Evénement XYZ| Janvier 2019 14  1 - Introduction Bases de données de séquences ? Quelques infos statistiques : Base ENA (séquences nucléotidiques) Source : https://www.ebi.ac.uk/ena/browser/about/statistics (2023) 3.2 Milliards de Séquences 20 Mille Milliard de bases Doublement du nombre ~17 mois (bases) ~21 mois (Séquences) Targeted Locus Sequence (TLS) ~ Remarque : Si on regarde par rapport au similar to WGS & TSA nombre de bases (au lieu des séquences), High level Assembly information Sequence (CON) * ~ 90% des bases sont dans STD, WGS et Expressed Sequence Tag (EST) ** CON (peu de Séquences mais grandes en terme de taille) Whole Genome sequencing (WGS) * Genome Survey Sequence (GSS) High Troughoutput Transcriptomic (HTG) High Troughoutput Genomic (HTG) * Sequence associated to a PATENT (PAT) ** Standart Taggered Annotated/Assembled Sequence (STD) * Sequence Tagged Site (STS) ** Transcriptome Shotgun Assembly (TSA) * Génome Séquences assemblées(→ grande taille) ** Séquence TAG (qq bases) Polytech Clermont | Evénement XYZ| Janvier 2019 15  1 - Introduction Bases de données de séquences ? ~ 1 base annotée / 1000 bases lues... ne pas confondre quantité (lectures) et qualité (annotation/connaissance)… Polytech Clermont | Evénement XYZ| Janvier 2019 16  1 - Introduction Comparaisons de séquences ? L’objectif du « biologiste » avec les outils de comparaison de séquences Pourquoi comparer des Pour utiliser les outils.. Il faut les séquences? connaitre et les comprendre Une fois la séquence obtenue (le texte) il faut identifier les gènes (les mots) ❑ Trouver les séquences de comparaison : le choix des DB , la pertinence de leur contenu, puis trouver leur fonction (le sens) l’objectif de la comparaison, … fonctions biologiques similaires structures comparables ❑ Comprendre le principe des algorithmes de comparaison de séquences arbres phylogénétiques mutations des gènes transferts de gènes On ne peut pas interpréter un choisir des amorces PCR résultat sans connaitre l’outil … que l’on utilise Liens non permanents http://www.irisa.fr/SAMBA/COURS/ Polytech Clermont | Evénement XYZ| Janvier 2019 17  1 - Introduction Comparaisons de séquences ? Que compare-t-on ? Information biologique primaire (et donc partielle) Suite d’acides nucléiques (ADN brut et régions codantes, ARN) Suite d’acides aminés (protéine) des alphabets différents ▪ 4 ou 20 lettres des longueurs différentes ▪ ADN >> ARN >> protéine des natures différentes ▪ comparer 2 nucléotides  comparer 2 acides animés Polytech Clermont | Evénement XYZ| Janvier 2019 18  1 - Introduction Comparaisons de séquences ? Comment Compare-t-on ? → Comparaison Directe et simple sans alignement → Comparaison avec recherche d’alignement des séquences - Alignement global - Alignement local → Comparaison avec alignement et recherche de similitudes de séquences Postulats : Les séquences évoluent par mutation et sélection Les séquences de 2 protéines de fonctions apparentées vont présenter des ressemblances (réciproquement), 2 protéines dont les séquences présentent des ressemblances ont probablement des fonctions apparentées Comparaison de 2 séquences : 1ère étape d’analyse en bio-informatique Polytech Clermont | Evénement XYZ| Janvier 2019 19  1 - Introduction Définitions Importantes Identité Proportion de paires de résidus identiques entre 2 séquences. Généralement exprimée sous forme de pourcentage. Cette valeur dépend énormément de l'algorithme d'alignement. Similitude Proportion de paires de résidus similaires (identités et/ou substitutions conservatives) entre 2 séquences. Une matrice de substitution permet de décrire qui est similaire à qui. Le score de similarité dépend de l'algorithme d'alignement et de la matrice de similarité utilisée. Le résultat de recherche de similarité peut-être utilisé pour inférer l’homologie de séquences Homologie Deux séquences sont homologues seulement si elles ont un ancêtre commun. IL N'Y A PAS DE POURCENTAGE D'HOMOLOGIE : les séquences sont homologues ou elles ne le sont pas !!. Polytech Clermont | Evénement XYZ| Janvier 2019 20 Outils de stockage (BDD) → Utilisation / Navigation sur les portails TP → Lecture / Compréhension / Utilisation des « fiches » de TP séquences obtenues sur les BDD et différents portails Outils d’analyse et d’interprétation COURS → Quels outils pour comparaison de séquence ? → Méthodes et Algorithmes (derrière les outils) COURS → Utilisation pratique outils de comparaison de TP séquences Polytech Clermont | Evénement XYZ| Janvier 2019 21 1 - Introduction Rappels et contexte Bases de données de séquences ? Comparaison de séquences ? Définitions / terminologie 2 – Comparaison de séquences 2 à 2 Première approche : le dot plot Comparaison avec alignement L’alignement et son évaluation : scores et Matrices de substitution Algorithmes d’alignement A la base de tous les algorithmes : programmation dynamique Alignement Global (Needelman et Wunsch, 1970) Alignement Local (Smith et Waterman, 1981) 3 - Comparaison d’une séquence avec les BD Principe et limitation de la recherche par similitude FASTA (Lipman, Pearson, 1985) BLAST (Altshul et al. , 1990) 4 – L’alignement Multiple CLUSTALW Polytech Clermont | Evénement XYZ| Janvier 2019 22  2 – Comparaison séquences 2 à 2 DOT Plot Comparaison simple sans alignement : le dot plot (matrice point) ou graphique de ressemblance Les similitudes entre les séquences apparaissent sur un diagramme en 2D. Principe: Deux séquences à comparer sont représentées une horizontalement, l'autre verticalement. On dessine ensuite un point dans le tableau (la matrice) lorsque les deux positions correspondantes sont identiques. On peut comparer une séquence par rapport à elle-même ou par rapport à une autre. Lorsque des régions se ressemblent, on voit apparaître une diagonale (noire ou blanche selon le code couleur). Polytech Clermont | Evénement XYZ| Janvier 2019 23  2 – Comparaison séquences 2 à 2 DOT Plot Le mot en position 0 sur seq1 et 32 sur sequ2 Dot plot simple : comparaison des 2 séquences →point blanc quand l’élément i de la séquence 1 et l’élément j de la séquence 2 sont identiques. →La fenêtre de comparaison porte sur 1 seul élément http://www.code10.info/index.php?option=com_content&view=category&id=52&Itemid=76 Polytech Clermont | Evénement XYZ| Janvier 2019 24  2 – Comparaison séquences 2 à 2 DOT Plot Paramètres pour un dot plot : → La taille de la fenêtre de comparaison : ici 4 éléments → La couleur (niveaux de gris) : dans l’exemple 2 éléments / 4 identiques = 50%. Il existe de nombreuses variantes pour l’utilisation de la couleur : exemple blanc si > 75% de similarité, et noir sinon, etc… Polytech Clermont | Evénement XYZ| Janvier 2019 25  2 – Comparaison séquences 2 à 2 DOT Plot Séqu. B 1 3 2 Séqu. A Inversion de 1 : Délétion A Séquences Régions de faible séquence 2 : Mutation A/B répétées complexité (amas 3 : Insertion A autour diagonale) Hexosaminidase A Humaine vs. Hexosaminidase A Souris DNA sequence EU127468.1 comparée par rapport à elle même. (fenêtre =16 ; noir pour identité 10600 alignements possibles (en incluant, insertions/délétions) Polytech Clermont | Evénement XYZ| Janvier 2019 29  2 – Comparaison séquences 2 à 2 Comparaison avec alignement Problématique : Quel est le meilleur alignement ? 2 problèmes à résoudre : 1 - Evaluer la « qualité » d’un alignement ➔ score d’alignement 2 – Réaliser les alignements ➔ méthodes / algorithmes Polytech Clermont | Evénement XYZ| Janvier 2019 30  2 – Comparaison séquences 2 à 2 Comparaison avec alignement 1 : Notion de score -- critère d’évaluation de l’alignement Score =  score élémentair e -  score pénalité ins/del (gap) match / substitution Pénalité Ins/Del ? Un gap = même coût ou extension moins Matrices de substitution pénalisante ? Polytech Clermont | Evénement XYZ| Janvier 2019 31  2 – Comparaison séquences 2 à 2 Comparaison avec alignement 2 : Algorithmes d’optimisation d’alignement de séquences De nombreux algorithmes qui - possèdent chacun leur propre méthode de calcul - ne donnent pas tous les mêmes résultats - ne sont pas tous adaptés aux mêmes problèmes - sont plus au moins rapides (important pour comparer aux séquences de DB) Algorithmes « exacts » – programmation dynamique - algorithme de Needleman-Wunsch pour l'alignement global (1970) - algorithme de Smith-Waterman pour l'alignement local (1981) Algorithmes approchés – méthodes heuristiques / recherche de similitudes - FASTA (Pearson et Lipman 1988) - BLAST (Altschul et al 1990) Polytech Clermont | Evénement XYZ| Janvier 2019 32 1 - Introduction Rappels et contexte Bases de données de séquences ? Comparaison de séquences ? Définitions / terminologie 2 – Comparaison de séquences 2 à 2 Première approche : le dot plot Comparaison avec alignement L’alignement et son évaluation : Scores et Matrices de substitution Algorithmes d’alignement A la base de tous les algorithmes : programmation dynamique Alignement Global (Needelman et Wunsch, 1970) Alignement Local (Smith et Waterman, 1981) 3 - Comparaison d’une séquence avec les BD Principe et limitation de la recherche par similitude FASTA (Lipman, Pearson, 1985) BLAST (Altshul et al. , 1990) 4 – L’alignement Multiple CLUSTALW Polytech Clermont | Evénement XYZ| Janvier 2019 33  2 – Comparaison séquences 2 à 2 Scores et matrices de substitutions Matrices substitution : cas des Acides Nucléiques Matrice unitaire A C G T Matrice unitaire inverse A C G T Match = 1 A 1 0 0 0 Match = 0 A 0 1 1 1 Mismatch = 0 C 0 1 0 0 Mismatch = 1 C 1 0 1 1 G 1 1 0 1 G 0 0 1 0 T 1 1 1 0 T 0 0 0 1 Matrice évolutive A C A ➔G = Transition T ➔C A C G T A 3 0 1 0 Les autres = Transversion C 0 3 0 1 G 1 0 3 0 P(transition) >P( transversion) G T T 0 1 0 3 Match = 3 Transition = 1 Transversion = 0 Polytech Clermont | Evénement XYZ| Janvier 2019 34  2 – Comparaison séquences 2 à 2 Scores et matrices de substitutions Problématique : aligner 2 séquences … Séquence 1 : GTTACGA Séquence 2 : GTTGGA GTTACGA GTTACGA GTTAC-GA ||| :|| |||: || ||| || GTT-GGA GTTG-GA GTT--GGA Matrice unitaire 1+1+1-5+0+1+1 1+1+1+0-5+1+1 1+1+1-5-5-5+1+1 GAP = -5 0 0 -10 Matrice évolutive 3+3+3-5+0+3+3 3+3+3+1-5+3+3 3+3+3-5-5-5+3+3 GAP = -5 10 (C→G transver.) 11 (A→G transi.) 0 Matrice évolutive 3+3+3-5+0+3+3 3+3+3+1-5+3+3 3+3+3-5-1-1+3+3 GAP = -5 10 8 11 Extension = -1 Polytech Clermont | Evénement XYZ| Janvier 2019 35  2 – Comparaison séquences 2 à 2 Scores et matrices de substitutions Matrices substitution : cas des Acides Aminés (Protéines) Plus compliqué que pour les Ac. Nucléiques (alphabet et informations différentes) Fitch (1966) : matrice déduite de la dégénérescence du code génétique. Depuis, nombreuses matrices de substitution, classées en 2 grandes catégories : Matrices liées aux caractéristiques physico-chimiques Matrices liées à l’évolution : PAM et BLOSUM Choix d’une matrice de substitution ? Importance de connaître la théorie sous-jacente → influence les résultats Choix de la matrice peut aussi dépendre de l’algorithme utilisé pour les alignements Globalement plutôt les matrices basées sur les comparaisons de séquences (Gonnet et al., 1992 ; BLOSUM50 ; BLOSUM62) ou sur les structures 3D Polytech Clermont | Evénement XYZ| Janvier 2019 36  2 – Comparaison séquences 2 à 2 Scores et matrices de substitutions Matrices liées (uniquement) aux propriétés physico-chimiques Matrice « d’hydrophobicité » des A.A. (levitt, 1976) Matrice de « structures secondaires» (Levin et al., 1986) Matrices de « structure III / groupes séquences » (Risler et al., 1988 ; Johnson et Overington, 1993) → Peuvent être utilisées pour des protéines relativement éloignées adapted from Livingstone & Barton, CABIOS, 9, 745-756, 1993 (PubMed) Polytech Clermont | Evénement XYZ| Janvier 2019 37  2 – Comparaison séquences 2 à 2 Scores et matrices de substitutions Matrices liées à l’évolution : PAM (Point Accepted Mutation) Représentent les échanges possibles et acceptables (notion stat.) d’un A.A. par un autre lors de l’évolution des protéines (mutations..) – Dayhoff, 1978. Principe : les protéines évoluent via des successions de mutations ponctuelles indépendantes les unes des autres et acceptées Matrice de probabilité Etude de 71 familles de protéines (~1300 séquences) très semblables (< 15% différence) et faciles à aligner (alignement global) Probabilité d’observer une mutation A.A. i → A.A. j = Fij Fréquence observée AA i → AA j Pij = log (Fi * F j ) Fréquence théorique si la substitution était due au hasard (Fi = fréquence de AA i dans la famille protéique) PAM 1 : ~ score de similarités pour 1 mutation acceptée / 100 sites durant un temps d’évolution donné Polytech Clermont | Evénement XYZ| Janvier 2019 38  2 – Comparaison séquences 2 à 2 Scores et matrices de substitutions PAM2 = PAM1 x PAM 1. PAM xxx = Comparaisons sur des distances d’évolution (~ %similarité et %identité) plus grandes distance (%) PAM 1 1 25 30 Protéines avec 0 résidus similaires : Exemple: Alanine Proline ; Serine ; Théonine A.A. 0 → points d’ancrages (Aligner un tryptophane (w) n’est pas un hasard) Valeurs fortes et Ac.Am. aromatique RK = 2 RH = -1 KH = 0 Polytech Clermont | Evénement XYZ| Janvier 2019 43  2 – Comparaison séquences 2 à 2 Scores et matrices de substitutions Quelques autres matrices en bref …. GONNET : (Gonnet, Cohen et Benner. 1992) Sur la base de 16300 séquences de protéines correspondant à 2600 familles. Construction itérative : Chaque séquence a été comparée à l'ensemble des séquences de la banque et les alignements ont été obtenus en utilisant une matrice initiale choisie arbitrairement. A partir de ces alignements→ une nouvelle matrice est construite → les alignements sont recalculés → une nouvelle matrice est construite ….. etc. jusqu'à ce que la matrice reste inchangée. Sur le principe des PAM → Gonnet 40, Gonnet 120,..., Gonnet 250, Gonnet 350. RISLER (1988) : Superposition des structures tridimensionnelles de 32 protéines regroupées en 11 groupes de séquences très voisines Johnson et Overington (1993) : 235 structures de protéines protéiques regroupées en 65 familles pour lesquelles on connaissait au moins la structure tridimensionnelle de trois séquences Polytech Clermont | Evénement XYZ| Janvier 2019 44  2 – Comparaison séquences 2 à 2 Scores et matrices de substitutions PAM vs. BLOSUM …. Comment choisir ? PAM BLOSUM petites Pas de matrice idéale (parfois tester 30 90 plusieurs). Utiliser le taux de conservation 50 prévu entre les sequences que l’on veut aligner. Prendre aussi en compte la taille 62 des sequences, 100 50 120 →PAM: basées sur des distances évolutives entre espèces 30 250 →BLOSUM : basées sur le contenu en information des substitutions longues (mieux adaptées à la detection d’alignements locaux) % identité entre Taille des séquences séquences Dayhoff, Schwartz & Orcutt (1978) "A model of evolutionary change in proteins, matrixes for detecting distant relationships" dans "Atlas of protein sequence and structure", Dayhoff, M.O. (ed.), vol 5, 345 - 358 Henikoff & Henikoff (1992) "Amino acid substitution matrices from protein blocks" Proc. Nat. Acad. Sci. USA 89, 10915 - 10919 Gonnet et al. (1992) "Exhaustive matching of the entire protein sequence database" Science 256, 1443-1444 Johnson & Overington (1993) "A structural basis for sequence comparisons. An evaluation of scoring methodologies" J. Mol. Biol. 233, 716 - 738 Mark P Styczynski; Kyle L Jensen, Isidore Rigoutsos, Gregory Stephanopoulos (2008). "BLOSUM62 miscalculations improve search performance". Nat. Biotech. 26 (3): 274–275 Polytech Clermont | Evénement XYZ| Janvier 2019 45  2 – Comparaison séquences 2 à 2 Scores et matrices de substitutions Notion de score -- critère d’évaluation de l’alignement Score =  score élémentair e -  score pénalité ins/del (gap) match / substitution Pénalité Ins/Del ? Un gap = même coût ou extension moins Matrices de substitution pénalisante ? OK !! … Je peux maintenant quantifier la valeur d’un alignement …. Encore faut-il avoir réalisé cet l’alignement !!! Polytech Clermont | Evénement XYZ| Janvier 2019 46 1 - Introduction Rappels et contexte Bases de données de séquences ? Comparaison de séquences ? Définitions / terminologie 2 – Comparaison de séquences 2 à 2 Première approche : le dot plot Comparaison avec alignement L’alignement et son évaluation : Scores et Matrices de substitution Algorithmes d’alignement A la base de tous les algorithmes : la programmation dynamique Alignement Global (Needelman et Wunsch, 1970) Alignement Local (Smith et Waterman, 1981) 3 - Comparaison d’une séquence avec les BD Principe et limitation de la recherche par similitude FASTA (Lipman, Pearson, 1985) BLAST (Altshul et al. , 1990) 4 – L’alignement Multiple CLUSTALW Polytech Clermont | Evénement XYZ| Janvier 2019 47  Complexité de l’alignement de 2 séquences de longueur n ? →N alignements a évaluer → complexité = O(2n) ---- > proportionnelle à 2n → Pour 1 alignement/msec (calcul score, etc…) : séquence de 50 bp → 35 000 ans 17 min Polytech Clermont | Evénement XYZ| Janvier 2019 48  2 – Comparaison séquences 2 à 2 Needleman & Wunch : Programmation Dynamique Programmation dynamique et alignement de séquences Needleman-Wunch (1970) : La programmation dynamique est un moyen qui permet de reduire la compléxité pour conserver un temps de calcul de l'ordre de n*n (compléxité O(n2) au lieu de O(2n)). Exemple 202=400 220=1 million Le principe est de déduire la solution optimale d’un problème à partir de la solution optimale de sous-problèmes (récursivité) HYPOTHESE : (sous OBJECTIF : problème) A partir de ces 3 CALCULER LE meilleur Les meilleurs alignements alignements → aligner connus jusqu’aux résidus : résidus i et j? alignement suivant (pour les Seq A | Seq B résidus (i , j)) : i-1 | j i-1 | j-1 i | j-1 A chaque étape on ne conserve que le meilleur ➔ on ne regarde pas toutes les combinaisons car on élimine les possibilités au fur et à mesure au lieu de les conserver Polytech Clermont | Evénement XYZ| Janvier 2019 49  2 – Comparaison séquences 2 à 2 Needleman & Wunch : Programmation Dynamique Programmation dynamique et alignement de séquences i Séq. A : xxxxxxxxxxxxACxxxxxxxxxxxx Séq. B : xxxxxTGxxxxxxxxxxx j HYPOTHESE : Meilleurs alignements CALCUL : LE meilleur alignement connus jusqu’aux résidus : suivant pour les résidus (i,j) : (i-1 , j) ; (i-1 , j-1) ; (i , j-1) Score (i-1,j) i i-1 + Score délétion sur B Séq. A xxxxxA C (GAP sur séq. B) On garde le Séq. B xxxT-G - MEILLEUR Score j j (maximum) des 3 Score (i-1,j-1) i i i-1 Séq. A xxxxxA C + Score Séq. A xxxxxAC = ? Score Séq. B xxxxxT G substitution Séq. B xxxT-G- alignement (i,j) j-1 j (i,j) j Score (i,j-1) i i + Score insertion sur B Séq. A xxxxAC - Séq. B xxxxxT G (GAP sur séq. A) j-1 j Meilleurs alignements sont connus Polytech Clermont | Evénement XYZ| Janvier 2019 50  2 – Comparaison séquences 2 à 2 Needleman & Wunch : Programmation Dynamique Programmation dynamique et alignement de séquences (graphiquement) Délétion j (séqu. B) Insertion i (séqu. A) Délétion i (séqu. A) insertion j (séqu. B) Score(i-1,j-1) Score(i,j-1) +p +s (élem. i , élem. j) Score(i-1,j) (i,j) +p Tableau pour comparer les Calcul de la case i,j à partir des séquences A et B 2 à 2 cases adjacentes Déplacement vertical == insertion pour B → s = matrice de substitution (==délétion pour A) → p = pénalité (GAP) Déplacement horizontal == délétion pour B (==insertion pour A) Polytech Clermont | Evénement XYZ| Janvier 2019 51  2 – Comparaison séquences 2 à 2 Algorithmes d’alignement Alignement global (Needleman-Wunsch, 1970) A Alignement des séquences apparentées sur toute B leur longueur, même si des sous-régions de hautes similitudes peuvent exister et qui ne seront pas alignées au terme du processus Alignement local (Smith-Waterman, 1981) A Rechercher dans la séquence A des régions (ou segments) semblables / haute similitude à la des B régions de la séquence B Polytech Clermont | Evénement XYZ| Janvier 2019 52  2 – Comparaison séquences 2 à 2 Needleman & Wunch : Align. global Alignement global (Needleman-Wunsch, 1970) Application de la méthode présentée. Il existe un autre algorithme aussi basé sur le même principe de programmation dynamique Alignement global de 2 séquence protéiques VTEERDAF et LTSHEAL Matrice de substitution : PAM250 Pénalité de GAP = -8 Matrice initiale - - 0 -8 -16 -24 -32 -40 -48 -56 -64 -V -8 -- -16 -24 -VT -32 --- -40 -48 -VTEERDAF -56 --------- -------- -LTSHEAL On conserve également le pointeur indiquant la case à l’origine du score Polytech Clermont | Evénement XYZ| Janvier 2019 53  2 – Comparaison séquences 2 à 2 Needleman & Wunch : Align. global Développement…. 2 s(V, L) = 2 p = -8 0 -8 +2 -8 -8 -8 2  maximum -16 -16 Polytech Clermont | Evénement XYZ| Janvier 2019 54  2 – Comparaison séquences 2 à 2 Needleman & Wunch : Align. global … matrice finale …. Parfois le même optimum est issu de 2 possibilités … et recherche du (des) meilleur(s) alignement(s) VTEERDAF Backtracking → LTS-HEAL Polytech Clermont | Evénement XYZ| Janvier 2019 55  2 – Comparaison séquences 2 à 2 Needleman & Wunch : Align. global Alignement global de 2 séquence protéiques VTEERDAF et LTSHEAL Matrice de substitution : PAM250 Pénalité de GAP = 0 VT-EERDAF Influence des paramètres choisis sur le résultat → LTSHE--AL Polytech Clermont | Evénement XYZ| Janvier 2019 56  2 – Comparaison séquences 2 à 2 Algorithmes d’alignement Alignement global (Needleman-Wunsch, 1970) A Alignement des séquences apparentées sur toute B leur longueur, même si des sous-régions de hautes similitudes peuvent exister et qui ne seront pas alignées au terme du processus Alignement local (Smith-Waterman, 1981) A Rechercher dans la séquence A des régions (ou segments) semblables / haute similitude à la des B régions de la séquence B Polytech Clermont | Evénement XYZ| Janvier 2019 57  2 – Comparaison séquences 2 à 2 Smith & Waterman : Align. Local Alignement local (Smith et Waterman, 1981) Application de la méthode présentée. Il existe un autre algorithme aussi basé sur le même principe de programmation dynamique →N’importe quelle cellule de la matrice de comparaison peut-être prise comme point de départ pour le calcul des scores sommes →Tout score qui devient négatif stoppe la progression du calcul. Cette case peut être initialisée a 0 et être un nouveau point de départ Alignement local de 2 séquence protéiques VTEERDAF et LTSHEAL Matrice de substitution : PAM250 Pénalité de GAP = -8 -8 0 - 8 ? => 0 Si score 30% sur >100 résidus → forte probabilité de régions homologues Qualité de la similitude = statistique Un score est statistiquement « bon » = biologiquement significatif → Notions statistique : le score dépasse une valeur seuil de probabilité choisie en fonction du but recherché Ces méthodes peuvent être très problématiques. Les valeurs obtenues (score / stat.) sont à utiliser avec précaution Un examen détaillé et attentif de l’ensemble des résultats est impératif La seule conclusion que l’on peut avoir avec certitude est qu’un résultat n’est pas satisfaisant Recherche de similitude ou homologie  comparaison séquences Polytech Clermont | Evénement 2 à Janvier XYZ| 2 2019 66  3 – Comparaison séquence et BDD Méthodes heuristiques Outils de comparaison séquences/banques : les heuristiques* 2 contraintes : banques de données de grandes taille et algorithmes rapides ➔ Méthodes heuristiques*. Combinent des méthodes approchées (plus rapides) et des méthodes exactes (optimisation). Pour l’alignement de séquences ce sont des méthodes basées sur la recherche de « mots » (ou méthode de k-uples) Les plus connues et utilisées : FASTA (Pearson et Lipman 1988) BLAST (Altschul et al 1990) * Une heuristique est un algo. qui fournit rapidement une solution réalisable (approximative) mais pas nécessairement optimale (exacte) pour un problème complexe. Polytech Clermont | Evénement XYZ| Janvier 2019 67  3 – Comparaison séquence et BDD Méthodes heuristiques Outils de comparaison séquences/banques : les heuristiques* Principes une séquence est une suite de caractères découpage (hachage) de la séquence en mots de K caractères (=mots) recherche des mots dans l'autre séquence Inconvénients la sensibilité dépend de la taille du mot heuristique pas toujours applicable Sélectivité : capacité à détecter seulement la réalité biologique et rien de plus faux-positifs : solution qui ne correspond pas à une réalité biologique peu de faux-positifs => bonne sélectivité pour enlever les faux positifs : traitement statistique des résultats pour essayer de détecter les solutions dues au hasard Sensibilité : capacité à détecter tout ce qui est intéressant sur le plan biologique faux-négatifs : non détection d'une similarité importante peu de faux-négatifs => bonne sensibilité Pour éviter les faux négatifs : utilisation raisonnée des paramètres des heuristiques Polytech Clermont | Evénement XYZ| Janvier 2019 68 1 - Introduction Rappels et contexte Bases de données de séquences ? Comparaison de séquences ? Définitions / terminologie 2 – Comparaison de séquences 2 à 2 Première approche : le dot plot Comparaison avec alignement L’alignement et son évaluation : Scores et Matrices de substitution Algorithmes d’alignement A la base de tous les algorithmes : la programmation dynamique Alignement Global (Needelman et Wunsch, 1970) Alignement Local (Smith et Waterman, 1981) 3 - Comparaison d’une séquence avec les BD Principe et limitation de la recherche par similitude FASTA (Lipman, Pearson, 1985) BLAST (Altshul et al. , 1990) 4 – L’alignement Multiple CLUSTALW Polytech Clermont | Evénement XYZ| Janvier 2019 69  3 – Comparaison séquence et BDD FASTA FASTA (Lipman, Pearson 1985) Premier algorithme heuristique de comparaison de séquences Principe : → Identification rapide des zones d’identités entre séquence cible et séquences de la banque (régions de forte similitudes) → Puis application d’un algorithme d’alignement sur la meilleure zone de ressemblance. Il existe différentes versions du logiciel : FASTA : ADN/banque ADN ou Protéine/banque Protéines TFASTA : ADN/banque protéique LFASTA : version de FASTA avec algorithme d’alignement local FASTA : se déroule en 4 étapes successives et distinctes Polytech Clermont | Evénement XYZ| Janvier 2019 70  3 – Comparaison séquence et BDD FASTA Etape 1: recherche des régions d’identité (Hot Spot) Utilisation d’une table de hachage pré-calculée (hash table, lookup table), contenant les k-uples possibles, et identifie leur position → même principe que le dot-plot avec une fenêtre de lecture de taille k. Requête 1 séq. parmi les séquences de la banque 1--------9-------13 1---------------15--------------------33 MYSEQUENCEQUERY DATABASESEQUENCEWITHLOTOFSEQUENCES 1 MY position 7 : Diff = 7-3 = 4 position position 2 YS position 9 : Diff = 9-3 = 6 position 26 : Diff = 26-3 = 23 9 15 3 SE 7 9 26 10 4 EQ 10 27 11 5 QU 11 28 12 6 UE 12 29 position 12 : Diff = 12-12 = 0 7 EN 13 30 position 12 : Diff = 12-6 = 6 position 29 : Diff = 29-12 = 17 8 NC 14 31 position 29 : Diff = 29-6 = 23 9 CE 15 32 12 ER Table hachage des k-uples (ici k=2) 13 RY 20k « mots » pour les proteines 4k « mots » pour les Ac. Nuc. Calcul rapide des différences de positions., pour une position de mot connue Polytech Clermont | Evénement XYZ| Janvier 2019 71  3 – Comparaison séquence et BDD FASTA Etape 1: recherche des régions d’identité (Hot Spot) pour quelle différences Nombre de « Graphiquement », cette pluspetite ==> motif de position ? fois méthode est ~ Dot Plot position 4 1 7 SE (avec fenêtre de lecture k-uples) 6 7 9 SEQUENCE 0 3 10 EQUE 23 7 26 SEQUENCE 17 3 27 EQUE (Débute en position 9) (Débute en position 26) → La différence de position =6 ou =23 est retrouvée 7 fois Les 2 Hot Spot = SEQUENCE → 2 Hot Spot de 8 résidus (=7+k-1) commençant en positions 9 et 26 → Le motif des 2 Hotspot lu est le même = « SEQUENCE » A cette étape on élimine également les séquences de la banque peu probables (avec peu de hot spot et de faible occurrence ): → ON ELIMINE AINSI DES SEQUENCES DE LA BASE DE DONNEE AVANT MEME D’AVOIR ESSAYE d’ALIGNER AVEC LA REQUETE Polytech Clermont | Evénement XYZ| Janvier 2019 72  3 – Comparaison séquence et BDD FASTA Etape 2: Pour les quelques séquences conservées sélection des 10 meilleurs « hot spot » et calcul d’un score requête 1 Séq. Conservée de la BDD Evaluation des matching de hot-spots sur les diagonales (illustration dans le diagramme dot-plot) Les matching diagonales (sans GAP) sont évalués (scorés) en utilisant une matrice de substitution (exemple : PAM 250). Score : init1 Polytech Clermont | Evénement XYZ| Janvier 2019 73  3 – Comparaison séquence et BDD FASTA Etape 3: Combinaison et score des matching diagonale avec les GAP Etape de « joining threshold » 1 local alignment GAP On recherche les combinaisons des différentes régions sous forme d’un alignement avec GAP → plusieurs segments (combinaisons possibles) FASTA recherche le chemin de poids maximal parmi tous les segments possibles 1 segment de score initn A cette étape on élimine également les segments peu probables : - Score région < seuil - initn < init1 Polytech Clermont | Evénement XYZ| Janvier 2019 74  3 – Comparaison séquence et BDD FASTA Etape 4: Calcul d’un alignement local alternatif L’épaisseur de la bande autour de l’alignement considéré est peut être un 1 local alignment paramètre du FASTA GAP Un alignement Global est calculé en considérant une fine bande autour de la diagonale sélectionnée à l’étape 3. On calcule l’alignement local dans cette bande, en utilisant l’algorithme de programmation dynamique mais contrainte à cette bande. L’algorithme d’alignement fusionne les diagonales trouvées aux étapes précédentes pour donner un alignement qui contient des GAP. → Meilleur score d’alignement : opt Polytech Clermont | Evénement XYZ| Janvier 2019 75  3 – Comparaison séquence et BDD FASTA FASTA : … résultat Version actuelle améliorée de FASTA : utilise alignement local plutôt que alignement global Estimation statistique du résultat (E-Value) (remarque : E-value Non inclus dans les anciennes versions ) → Les séquences de la banque de donnée sont ordonnées par rapport aux meilleurs alignements, → Estimation statistique des résultats Histogramme des scores obtenus pour chaque séquence de la banque + moyenne + Ec. Type de la distribution des scores Z-score : calculé à partir d’un ajustement de la distribution des scores par une loi statistique (Monte Carlo) Versions Actuelles → E-Value Polytech Clermont | Evénement XYZ| Janvier 2019 76  3 – Comparaison séquence et BDD FASTA FASTA : paramètres importants k-uple (par défaut) : ADN : 6 k-uple faible ==> bonne sensibilité et temps de calcul long Protéine : 2 k-uple élevé ==> rapide mais peu sensible Substitution (par défaut) : ADN : +5 / -4 Protéine : matrice Blosum50 ou 62 Coûts des gaps (par défaut) : ADN : -16 / -4 Protéine : -12 / -2 FASTA : les limites Courts segments très similaires → réduit le poids des autres régions Les grandes insertions ne sont pas considérées Méthode heuristique moins rapide que BLAST Polytech Clermont | Evénement XYZ| Janvier 2019 77 1 - Introduction Rappels et contexte Bases de données de séquences ? Comparaison de séquences ? Définitions / terminologie 2 – Comparaison de séquences 2 à 2 Première approche : le dot plot Comparaison avec alignement L’alignement et son évaluation : Scores et Matrices de substitution Algorithmes d’alignement A la base de tous les algorithmes : la programmation dynamique Alignement Global (Needelman et Wunsch, 1970) Alignement Local (Smith et Waterman, 1981) 3 - Comparaison d’une séquence avec les BD Principe et limitation de la recherche par similitude FASTA (Lipman, Pearson, 1985) BLAST (Altshul et al. , 1990) 4 – L’alignement Multiple CLUSTALW Polytech Clermont | Evénement XYZ| Janvier 2019 78  3 – Comparaison séquence et BDD BLAST BLAST (Altshul et al., 1985) Basic Local Alignement Search Tool → Comparaison d'une séquence contre une banque Hypothèse sous-jacente : les bon alignements contiennent (quelque part) de petits segments strictement identiques. Prétraitement possible par des filtres (programme XNU) pour éliminer/masquer les régions répétitives et les segment de faible complexité (programme SEG et comparaison avec une banque de données contenant des séquences représentatives de faible complexité) Rapide mais sensibilité (=capacité à tout détecter) parfois insuffisante Traitement statistique des résultats inclus dans la méthode C’est l’outil de référence (on ne trouve plus vraiment de FASTA) Polytech Clermont | Evénement XYZ| Janvier 2019 79  3 – Comparaison séquence et BDD BLAST Version de l’algorithme BLAST (original) : sans GAP BLAST2 : avec GAP (version à utiliser) Version de logiciel Séquence Banque Nucléique Nucléique BLASTN Direct Protéique Protéique BLASTP Nucléique Protéique BLASTX Protéique Traduction Protéique Nucléique TBLASTN Proteique Nucléique Nucléique TBLASTX Protéique Protéique Polytech Clermont | Evénement XYZ| Janvier 2019 80  3 – Comparaison séquence et BDD BLAST BLAST Etape 1 : Identification de « mots » de longueur fixe = W (~ idem hachage FASTA) Ac. Nucléique : Recherche segments identiques W = 11 (défaut) Protéines : Recherche de tous les mots de taille W avec un score > t (Hit Blast) W =3 (défaut) t = score seuil (ajustable?) au delà duquel la ressemblance entre 2 mots n’est plus due au hasard : « neighborhood word score threshold » PQG = 18 Liste des mots PEG = 15 PQG PRG = 14 pour la séquence p …………………… requête PQ PQG PKG = 14 QG PNG = 13 taille W , PMG = 13 score > t PGA = 12 Exemple Seuil à t = 13 Hachage en « mots » de W=3 PQN = 12 …………… Score des mots voisins de PQG (BLOSUM 62) Exemple: Séquence 250 résidus ---------------> ~50 mots voisins / mot haché Polytech ----------> liste de 125 000 mots Clermont | Evénement XYZ| Janvier 2019 81  3 – Comparaison séquence et BDD BLAST BLAST Etape 2 : alignement et extension 1 séquence de la banque 2.1 : Match exact entre mots de la liste et chaque séquence de la banque = Hit (remarque : un hit = tous les mots adjacents qui ont matché) 2.2 : Extension sans GAP* de l’alignement local dans les deux directions et calcul du Score Cumulé (Sc) de la région étendue (ou paire de segments) Arrêt de l’extension si : → Diminution de Sc par rapport la valeur maximale obtenue (Sc < Sc_max – X) → Sc S ( score seuil) ➔ Segments de score >S = HSP : High-scoring Segment Pair ➔ 1 Segment de score maximum = MSP : Maximum Segment Pair Calcul des scores : HSP =  Si,j – GAP (calcul classique d’un score) Bit Score : score normalisé - comparable entre différents alignements obtenus à l’aide de la même matrice : → utilisable pour comparer les résultats de différentes recherches - Indépendant de la banque interrogée , mais dépendant du serveur utilisé ! S’ = (.S –ln K) / ln 2  et K , constantes statistiques du système de score S = score brut du MSP Polytech Clermont | Evénement XYZ| Janvier 2019 83  3 – Comparaison séquence et BDD BLAST BLAST : … Analyse statistique des HSP … L'intérêt de l'algorithme est que sa conception est basée sur un modèle statistique. Celui-ci a été établi d'après les méthodes statistiques de Karlin et Altschul (1990 ; 1993) qui s'appliquent aux comparaisons de séquences sans insertion-délétion P-value : probability P(x) = probabilité d’obtenir un score HSP > x Plus P est faible, plus le HSP est significatif P dépend de la matrice de score utilisée et de la longueur des séquences Polytech Clermont | Evénement XYZ| Janvier 2019 84  3 – Comparaison séquence et BDD BLAST BLAST : … Analyse statistique des HSP … E-value : « expect Value » Nombre d’alignements attendus (expected) par hasard et ayant un score > score obtenu dans la banque considérée E = 1 →→→ 1 chance dans la banque de trouver une séquence avec un score donné Plus la valeur est faible, plus l’alignement est fiable Attention cependant !! Pour des séquences requêtes très courtes, la "E-Value" est élevée, même pour les séquences dont l'alignement obtenu est significatif. La valeur limite (E-Threshold) de la E-value est un paramètre ajustable. Il ne sert qu’à limiter le nombre de résultats retenus Polytech Clermont | Evénement XYZ| Janvier 2019 85  3 – Comparaison séquence et BDD BLAST La E-Value est fonction de la P-Value et du nombre de séquences L de la banque : E = 1 – Exp(P.L) →E~ P.L (si P