Biologie «in silicomthomas/M1/bio_in_silico/MTC... · 2013. 10. 14. · • Association de la biologie et de l'informatique • Objectifs : • Analyser, modéliser ou prédire les

Biologie «in silico»

Adapté de Pierre Vincens

Bioinformatique

•  Association de la biologie et de l'informatique •  Objectifs :

•  Analyser, modéliser ou prédire les informations issues de données biologiques expérimentales et développer les outils nécessaires.

•  Concevoir des méthodes de traitement de l'information

inspirées des systèmes biologiques permettant de résoudre des problèmes algorithmiques complexes. (algorithmes génétiques, réseaux de neurones formels,...)

Adapté de Pierre VINCENS – ENS - 2013

Biologie «in silico»

•  Traitement automatisé d'informations biologiques •  Analogie : «in vivo» (dans le vivant), «in vitro» (dans le

verre), «in silico» (dans la silice, composant des «puces» des ordinateurs)

•  Terme apparu dans «A. Danchin, C. Médigue, O. Gascuel, H Soldano, A Hénaut - From data banks to data bases - Research in Microbiology (1991) 142: 913-916»

•  Quelques approches •  Analyse de la séquence •  Analyse de l'expression •  Prédiction de structure •  Phylogénie

•  ...

●  Quelques objectifs ●  Comprendre les systèmes de régulation ●  Étudier les interactions moléculaires ●  Reconstituer l'histoire de la «vie» ●  ...


Autour du gène

GENE Séquence protéique

Métabolisme

Expression

Structure protéique

Dynamique moléculaire

Localisation chromosomique

homologie

phylogénie

Séquence nucléique

Cofacteurs


Autour d'un organisme

Organisme

Population

Génome

Protéome

Transcriptome

Taxonomie

Métabolome


De l'information...

•  Natures différentes •  Information = texte sous forme de collection de couple attribut/valeur •  Taxonomie = texte dont les relations entre les composants sont

organisées sous la forme d'un arbre. •  Séquences = texte dans un alphabet contraint •  Structure = suite de valeurs de positions •  Expression = suite de valeurs numériques •  ...

•  Une volumétrie conséquente •  Croissance exponentielle

=> Gérer cette information : → La collecter, l'organiser, la distribuer, l'exploiter,...


Gérer l'information

•  Banque de données •  Ensemble de données relatif à un domaine défini des connaissances,

généralement organisé et structuré en base de données pour être offert aux utilisateurs.

•  Base de données •  Ensemble structuré de données, généralement en champs, organisé en

vue de son utilisation par des programmes correspondant à des applications distinctes et afin de faciliter l’évolution indépendante des données et des programmes. Cela est réalisé à l'aide d'un système de gestion de base de données (SGBD)

(*) Définitions du Journal Officiel.


Historique des Banque de données

•  Premiers développements •  1965 : première compilation papier « Atlas of Protein Sequences »

•  Premiers supports informatiques •  1971 : première version de la PDB au Brookhaven National Laboratory •  1981-1982 : premières versions de EMBL et Genbank •  1986 : première version de Swissprot •  2002 : première version de Genbank WGS

•  État actuel •  2013 (oct) : Genbank rel 197 contient 167 295 840 entrées et 154 192 921 011 bases. •  2013 (oct) : PDB comporte 94 540 structures dont 87 516 de protéines


Banques de données

•  Consortium international •  Genbank (NCBI) : http://www.ncbi.nlm.nih.gov •  EMBL (EBI) : http://www.ebi.ac.uk •  DDBJ (Japon) : http://www.ddbj.nig.ac.jp

•  Autres sources •  UniProt (protéines associant Swiss-Prot (annotée), TrEMBL

et PIR) : http://www.uniprot.org •  PDB (structures macromoléculaires): http://www.pdb.org •  ENSEMBL (génomes annotées : http://www.ensembl.org •  Gene ontology: http://www.geneontology.org


Le site du NCBI (Genbank)

Pour télécharger la séquence

Pour spécifier le format


Une séquence au format Genbank

LOCUS HUMDGL1 1976 bp ds-DNA PRI 26-MAY-1991 DEFINITION Human gene for delta-globin. ACCESSION V00505 KEYWORDS delta-globin; germline; globin. SOURCE Homo sapiens DNA. ORGANISM Homo sapiens Eukaryota; Animalia; Metazoa; Chordata; Vertebrata; Mammalia; Theria; Eutheria; Primates; Haplorhini; Catarrhini; Hominidae. REFERENCE 1 (bases 1 to 1976) AUTHORS Spritz,R.A., DeRiel,J.K., Forget,B.G. and Weissman,S.M. TITLE Complete nucleotide sequence of the human delta-globin gene JOURNAL Cell 21, 639-646 (1980) STANDARD full automatic COMMENT EPD; 11105; Hs d’-globin. SWISS-PROT; P02042; HBD$HUMAN. KST HSA.DELGLOBIN From EMBL entry HSDGL1; dated 03-JAN-1991. FEATURES Location/Qualifiers .PE1 CDS join(173..265,394..615,1505..1630) /codon_start=1 precursor_RNA 123..1763 /note=”primary transcript” mRNA 123..265 /note=”mRNA (part 1)” intron 266..393 /note=”intron 1” ... BASE COUNT 541 a 397 c 411 g 627 t ORIGIN 1 AAT...


Le site de l'EBI (EMBL)


Une séquence au format EMBL

ID 13 standard; DNA; HTG; 84195 BP. XX AC chromosome:GRCh37:13:32889611:32973805:1 DT 12-NOV-2011 DE Homo sapiens chromosome 13 GRCh37 partial sequence 32889611..32973805 DE annotated by Ensembl OS Homo sapiens (human) OC Eukaryota; Metazoa; Eumetazoa; Bilateria; Coelomata; Deuterostomia; ... OC Hominoidea; Hominidae; Homininae; Homo. XX CC This sequence was annotated by the Ensembl system. Please visit the Ensembl CC web site, http://www.ensembl.org/ for more information. XX FH Key Location/Qualifiers FT gene 1..84195 FT /gene=ENSG00000139618 FT /locus_tag="BRCA2" FT /note="breast cancer 2, early onset [Source:HGNC FT Symbol;Acc:1101]" FT mRNA join(1..194,949..1054,3604..3852,9603..9711,10628..10677, FT 10769..10809,11026..11140,13970..14019,15446..15557, ... FT /gene="ENSG00000139618" FT /note="transcript_id=ENST00000380152" ... FT /translation="MPIGSKERPTFFEIFKTRCNKADLGPISLNWFEELSSEAPPYNSE FT PAEESEHKNNNYEPNLFKTPQRKPSYNQLASTPIIFKEQGLTLPLYQSPVKELDKFKLD ...


Séquences au format Fasta

>ENST00000530893 cdna:KNOWN_protein_coding GGCAGAGGCGGAGCCGCTGTGGCACTGCTGCGCCTCTGCTGCGCCTCGGGTGTCTTTTGC GGCGGTGGGTCGCCGCCGGGAGAAGCGTGAGGGGACAGATTTGTGACCGGCGCGGTTTTT GTCAGCTTACTCCGGCCAAAAAAGAACTGCACCTCTGGAGCGGACTTATTTACCAAGCAT TGGAGGAATATCGTAGGTAAAAATGCCTATTGGATCCAAAGAGAGGCCAACATTTTTTGA AATTTTTAAGACACGCTGCAACAAAGCAGGACCAATAAGTCTTAATTGGTTTGAAGAACT TTCTTCAGAAGCTCCACCCTATAATTCTGAACCTGCAGAAGAATCTGAACATAAAAACAA CAATTACGAACCAAACCTATTTAAAACTCCACAAAGGAAACCATCTTATAATCAGCTGGC TTCAACTCCAATAATATTCAAAGAGCAAGGGCTGACTCTGCCGCTGTACCAATCTCCTGT AAAAGAATTAGATAAATTCAAATTAGACTTAGGAAGGAATGTTCCCAATAGTAGACATAA AAGTCTTCGCACAGTGAAAACTAAAATGGATCAAGCAGATGATGTTTCCTGTCCACTTCT AAATTCTTGTCTTAGTGAAAGTCCTGTTGTTCTACAATGTACACATGTAACACCACAAAG AGATAAGTCAGTGGTATGTGGGAGTTTGTTTCATACACCAAAGTTTGTGAAGGGTCGTCA GACACCAAAACATATTTCTGAAAGTCTAGGAGCTGAGGTGGATCCTGATATGTCTTGGTC AAGTTCTTTAGCTACACCACCCACCCTTAGTTCTACTGTGCTCATAGTCAGAAATGAAGA AGCATCTGAAACTGTATTTCCTCATGATACTACTGCTAATGTGAAAAGCTATTTTTCCAA GTCTCAACTAACCCTTTCAGGTCTAAATGGAGCCCAGATGGAGAAAATACCCCTATTGCA TATTTCTTCATGTGACCAAAATATTTCAGAAAAAGACCTATTAGACACAGAGAACAAAAG ... TGATGAAACATCTTATAAAGGAAAAAAAA >ENST00000530893 cds:KNOWN_protein_coding ATGCCTATTGGATCCAAAGAGAGGCCAACATTTTTTGAAATTTTTAAGACACGCTGCAAC AAAGCAGGACCAATAAGTCTTAATTGGTTTGAAGAACTTTCTTCAGAAGCTCCACCCTAT AATTCTGAACCTGCAGAAGAATCTGAACATAAAAACAACAATTACGAACCAAACCTATTT AAAACTCCACAAAGGAAACCATCTTATAATCAGCTGGCTTCAACTCCAATAATATTCAAA GAGCAAGGGCTGACTCTGCCGCTGTACCAATCTCCTGTAAAAGAATTAGATAAATTCAAA TTAGACTTAGGAAGGAATGTTCCCAATAGTAGACATAAAAGTCTTCGCACAGTGAAAACT AAAATGGATCAAGCAGATGATGTTTCCTGTCCACTTCTAAATTCTTGTCTTAGTGAAAGT ...


A bioinformatics « world » for human users

http://tux.crystalxp.net/en.id.10838-brunocb-leonard-de-vinci----tux-de-vitruve.html


Les web services

•  Technologie permettant à des applications de dialoguer à distance via internet, indépendamment des plates-formes où elles reposent et des langages dans lesquelles elles sont écrites.

•  Utilise un ensemble de protocoles reposant sur XML et standardisant les modes d'invocations mutuels des composants des applications

•  WSDL : le contrat de service définit •  les types utilisés •  les appels de fonctions (=services fournis) •  La documentation •  UDDI : l'annuaire des services

•  Services disponibles à l'EBI •  Téléchargement de séquences •  Recherche de similitudes •  Alignement de séquences •  …


WSDL (contrat)


What are Web Services (WS) ? Defini&on:

A Web service is a so2ware system designed to support interoperable machine-‐to-‐machine interac&on over a network

Source: W3C: hBp://www.w3.org/TR/ws-‐gloss/

Service provider (server) client

network => internet

PERL script run_BLAST () blastall

call run_BLAST()

send back the results

#!/usr/bin/perl -w


Un exemple en PHP

... // Initialisation du client $urlEBI = "http://www.ebi.ac.uk/Tools/webservices/wsdl/"; $clientSOAP = new SoapClient( $urlEBI."WSDbfetch.wsdl", array("trace" => 1, "exceptions" => 0)); try { echo $clientSOAP->fetchData("embl:AA067310", "emblxml", "raw"); } catch (SoapFault $exception) { echo $exception; } ...

Spécifier le contrat

Réaliser l'action


Banques génomiques spécialisées

•  Quelques banques •  Flybase (drosophiles) : http://flybase.org/ •  SGD (Saccharomyces cerevisiae): http://www.yeastgenome.org •  WORMbase (nématodes) : http://www.wormbase.org •  TAIR (Arabidopsis thaliana) : http://www.arabidopsis.org •  Zebrafish (poisson zebre) : http://zfin.org •  …

•  Dédiées à un organisme •  Des outils adaptés...


Naviguer dans un génome

•  Visual iser les annotat ions associées aux régions du génome

•  Navigation le long du génome •  Associer une représentation graphique

adaptée à chaque propriété (glyph) •  Associer des l iens (URL) aux

annotations •  Recherche sur différents critères •  Enrichissement par l'utilisateur •  ...

=> Très populaire : gbrowse

- http://gmod.org/wiki/GBrowse


Gbrowse (ZFIN)

configurer les fontes se déplacer,

zoomer

la séquence


Contrôler l'affichage des pistes

Pour valider Pour changer

l'ordre des pistes


Propriétés d'affichage d'une piste


UCSC genome browser Custom track


Ensembl genome browser

•  Ensembl http://www.ensembl.org •  Vertébrés principalement

•  Ensembl genomes •  Metazoa => animaux •  Protists •  Bacteria •  Plants •  Fungi

⇒  Navigateur de génome ⇒  Accès par web service et API PERL


Annotation de régions génomiques


Les fichiers GFF

Col. Nom Description

1 Seqid Identifiant de la séquence

2 Source Texte décrivant l'algorithme ou la propriété associée à la caractéristique (si absent, mettre « . »)

3 Type Sous la forme d'un terme de la GO (ex : exon, mRNA,...)

4 Start Position de début de la région

5 End Position de fin de la région

6 Score Un nombre flottant (ex : E-value pour une similitude)

7 Strand Indique le brin « + » ou « - » (« . » si inconnu ou non pertinent)

8 Phase 0, 1 ou 2 pour indiquer la phase de lecture (« . » si non pertinent)

9 Attributes Une liste de caractéristiques sous la forme attribut=valeur

•  Fichiers textes (flat file) •  GFF3 : Neuf colonnes décrivant une propriété en une région

Description complète sur : http://www.sequenceontology.org/resources/gff3.html


Les attributs GFF

Attribut Description

ID Identifiant unique de la caractéristique (unicité au sein du GFF)

Name Nom de la caractéristique (pas d'unicité requise)

Alias Autre nom de la caractéristique

Parent Inclusion de la caractéristique (ex : exon dans un transcript)

Target Partenaire dans un alignement (forme : target_id start end [strand])

Gap Spécification d'une non-colinéarité dans un alignement

Derives_from Expression d'une relation autre que hiérarchique

Notes Texte libre

Dbxref Référence à une entrée d'une banque de données

Ontology_term Référence à un terme d'ontologie

•  Colonne 9 du fichier GFF3 sous la forme d'une liste dont les composants sont séparés par des « ; »


Composants de fichiers GFF3

ctg123 example match 26122 26126 . + . ID=match001 ctg123 example match 26497 26869 . + . ID=match001 ctg123 example match 27201 27325 . + . ID=match001 ctg123 example match 27372 27433 . + . ID=match001 ctg123 example match 27565 27565 . + . ID=match001

##gff-version 3 ctg123 . operon 1300 15000 . + . ID=operon001;Name=Op1 ctg123 . mRNA 1300 9000 . + . ID=mrna0001;Parent=Op1;Name=G1 ctg123 . exon 1300 1500 . + . Parent=mrna0001 ctg123 . exon 1050 1500 . + . Parent=mrna0001 ctg123 . exon 3000 3902 . + . Parent=mrna0001 ctg123 . exon 5000 5500 . + . Parent=mrna0001

•  Hiérachisation des caractéristiques •  Discontinuité (support partiel)


Composants de fichiers GFF3

##gff-version 3 ctg123 . exon 1300 1500 . + . ID=exon00001 ctg123 . exon 1050 1500 . + . ID=exon00002 ctg123 . exon 3000 3902 . + . ID=exon00003 ctg123 . exon 5000 5500 . + . ID=exon00004 ctg123 . exon 7000 9000 . + . ID=exon00005 ##FASTA >ctg123 cttctgggcgtacccgattctcggagaacttgccgcaccattccgccttg tgttcattgctgcctgcatgttcattgtctacctcggctacgtgtggcta tctttcctcggtgccctcgtgcacggagtcgagaaaccaaagaacaaaaa aagaaattaaaatatttattttgctgtggtttttgatgtgtgttttttat aatgatttttgatgtgaccaattgtacttttcctttaaatgaaatgtaat cttaaatgtatttccgacgaattcgaggcctgaaaagtgtgacgccattc ...

•  Inclusion d'une séquence au format fasta


Plusieurs niveaux de données

•  Niveau 1 : résultats expérimentaux •  Séquences nucléiques, protéiques,... •  Structure tridimensionnelle de protéines, de RNA,... •  Réaction chimique du métabolisme,... •  Electrophorèse 2D, puces à ADN, RNASeq...

•  Niveau 2 : analyse de données •  Similitude de séquences •  Prédiction de structure •  Chemin métabolique •  Groupe d’expression

•  Niveau 3 : interprétation de données •  Homologie •  Phylogénie •  Réseau de régulation


Plusieurs niveaux de données

•  Niveau 1 : résultats expérimentaux •  Séquences nucléiques, protéiques,... •  Structure tridimensionnelle de protéines, de RNA,... •  Réaction chimique du métabolisme,... •  Electrophorèse 2D, puces à ADN, RNASeq...

•  Niveau 2 : analyse de données •  Similitude de séquences •  Prédiction de structure •  Chemin métabolique •  Groupe d’expression

•  Niveau 3 : interprétation de données •  Homologie •  Phylogénie •  Réseau de régulation

14

pourquoi comparer les séquences ?

➢ une ressemblance entre séquences peut indiquer:

• une fonction biologique proche

• une structure 3D semblable

• une origine et/ou histoire évolutive commune

➢ la comparaison de séquence permet aussi

• d'assembler des fragments de séquences

• de mettre en évidence les différences de séquençage entre différents laboratoires

Adapté de Carl Hermann

Adapté de Carl Hermann 13

au début sont les alignements...

➢ alignements = outils de base de l'analyse bioinformatique

➢ permettent de comparer des séquences biologiques

• nucléiques (ADN,ARN)

• protéiques

➢ différents outils en fonction

• du type d'alignement (local/global)

• de la longueur des séquences, etc...

➢ alignement contre des banques de données de séquences(séquences nucléiques, protéiques, EST, ARNm,...)


W L T E K E G S - - Y P K L| | . . . . . . | . | W L S S S M N N Q V F P Q L

comparaison de 2 séquences

identité

substitution conservative

insertion/deletionexemple d'alignement

substitution non-conservative

séquence A

séquence B

W L T E K E G S Y P K L

W L S S S M N N Q V F P Q L


d'autres alignements sont possibles


W L T E - - K E G S Y P K L| | . . . . . | . |W L S S S M N N Q V F P Q L

comment décider ??


évolution des séquences protéiques

➢ mutations d'acides aminés

certaines mutations plus favorables

• propriétés physico-chimiques semblables

• structure 3D conservée

➢ insertion/délétion de fragments de séquences

• iso-formes issues de l'epissage alternatif

certains scénarios évolutifs

sont plus probables que d'autres


évaluation d'un alignement

➢ score qui dépend

• nombre et nature des identités

• nombre et nature des substitutions

• nombre d'insertion/délétion

➢ score global = ∑ scores des positions

➢ meilleur alignement: score maximum

score = s(W,W) +s(L,L) + s(T,S) + s(E,S) + ... + s(gap l=2) + ...



les paramètres

➢ insertion/délétion: 2 paramètres

• ouverture de gap

• extension de gap

➢ le caractère non linéaire est plus conforme à la réalité biologique

CGATGCAGCAGCAGCATCG|||||| |||||||CGATGC------AGCATCG

CGATGCAGCAGCAGCATCG|| || |||| || || |CG-TG-AGCA-CA--AT-G

ouverture de gap extension de gap

(13 x 1) - 10 - (6 x 1) = -3 (13 x 1) - (5 x 10) - (6 x 1) = -43


les paramètres

➢ identité/substitution: matrices de substitution

score pour chaque conservation/substitution

➢ obtenu empiriquement à partir des substitutions observées entre séquences

ex.: BLOSUM62


Matrice BLOSUM62

A R N D C Q E G H I L K M F P S T W Y V B Z X * A 4 -1 -2 -2 0 -1 -1 0 -2 -1 -1 -1 -1 -2 -1 1 0 -3 -2 0 -2 -1 0 -4 R -1 5 0 -2 -3 1 0 -2 0 -3 -2 2 -1 -3 -2 -1 -1 -3 -2 -3 -1 0 -1 -4 N -2 0 6 1 -3 0 0 0 1 -3 -3 0 -2 -3 -2 1 0 -4 -2 -3 3 0 -1 -4 D -2 -2 1 6 -3 0 2 -1 -1 -3 -4 -1 -3 -3 -1 0 -1 -4 -3 -3 4 1 -1 -4 C 0 -3 -3 -3 9 -3 -4 -3 -3 -1 -1 -3 -1 -2 -3 -1 -1 -2 -2 -1 -3 -3 -2 -4 Q -1 1 0 0 -3 5 2 -2 0 -3 -2 1 0 -3 -1 0 -1 -2 -1 -2 0 3 -1 -4 E -1 0 0 2 -4 2 5 -2 0 -3 -3 1 -2 -3 -1 0 -1 -3 -2 -2 1 4 -1 -4 G 0 -2 0 -1 -3 -2 -2 6 -2 -4 -4 -2 -3 -3 -2 0 -2 -2 -3 -3 -1 -2 -1 -4 H -2 0 1 -1 -3 0 0 -2 8 -3 -3 -1 -2 -1 -2 -1 -2 -2 2 -3 0 0 -1 -4 I -1 -3 -3 -3 -1 -3 -3 -4 -3 4 2 -3 1 0 -3 -2 -1 -3 -1 3 -3 -3 -1 -4 L -1 -2 -3 -4 -1 -2 -3 -4 -3 2 4 -2 2 0 -3 -2 -1 -2 -1 1 -4 -3 -1 -4 K -1 2 0 -1 -3 1 1 -2 -1 -3 -2 5 -1 -3 -1 0 -1 -3 -2 -2 0 1 -1 -4 M -1 -1 -2 -3 -1 0 -2 -3 -2 1 2 -1 5 0 -2 -1 -1 -1 -1 1 -3 -1 -1 -4 F -2 -3 -3 -3 -2 -3 -3 -3 -1 0 0 -3 0 6 -4 -2 -2 1 3 -1 -3 -3 -1 -4 P -1 -2 -2 -1 -3 -1 -1 -2 -2 -3 -3 -1 -2 -4 7 -1 -1 -4 -3 -2 -2 -1 -2 -4 S 1 -1 1 0 -1 0 0 0 -1 -2 -2 0 -1 -2 -1 4 1 -3 -2 -2 0 0 0 -4 T 0 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 1 5 -2 -2 0 -1 -1 0 -4 W -3 -3 -4 -4 -2 -2 -3 -2 -2 -3 -2 -3 -1 1 -4 -3 -2 11 2 -3 -4 -3 -2 -4 Y -2 -2 -2 -3 -2 -1 -2 -3 2 -1 -1 -2 -1 3 -3 -2 -2 2 7 -1 -3 -2 -1 -4


Alignement optimal

➢ comment trouver l'alignement optimal ?

➢ énumération de tous les alignements possibles et recherche du score max⇨ impossible! (complexité en (2n)!/n²)

➢ méthodes "heuristiques"

• pas de garantie que l'alignement soit optimal (il l'est cependant presque toujours...)

• énorme gain de rapidité (complexité en O(n²))


alignement global/local

A

B

Alignement global

Alignement local

A

B

Alignement forcédes extrémités

Pénalisation forte des délétions/insertions


alignement global

A

B

Alignement global


➢ utilisé pour aligner des séquences homologues (gènes, protéines, chromosomes) afin de déterminer les mutations

évolutives

➢ à la base des alignements multiples (ClustalW,...)


alignement local

Alignement local

A

B

Pénalisation forte des délétions/insertions

➢ utilisé pour identifier des séquences homologues, p.ex. dans les banques de données

➢ l'homologie peut être restreinte à une portion de séquence (domaine protéique)

➢ algo. le plus répandu: BLAST (blastp, blastn,...)


Recherche de similitudes

•  Identifier dans une banque de données des séquences ressemblantes à une séquence cible choisie.

•  Deux familles de programmes :

•  FASTA : algorithme proposé par Pearson basé sur l’identification rapide de fragments strictement identiques entre la séquence cible et les séquences de la banque.

•  BLAST : « Basic Local Alignment Search Tool » proposé par Altschul et al. (1990) dont l'algorithme est basé sur l'identification de fragments hautement similaires


•  Définitions : •  HSP (High-scoring Segment Pair) : segment commun le plus long possible

entre la séquence cible et une séquence de la banque. •  MSP (Maximal-scoring Segment Pair) : meilleur score obtenu parmi tous les

couples de fragments possibles que peuvent produire les deux séquences.

•  Deux étapes : → Repérer tous les HSP entre la séquence cible et les séquences de la base. Pour

cela, on recherche des mots similaires de longueur fixe W. •  Deux mots sont similaires s’ils ont un score supérieur à un seuil fixé pour

une matrice de substitution donnée. → Étendre la similitude à partir du mot commun dans les deux directions de la

séquence. L’extension s’arrête si : •  Le score cumulé diminue d’une valeur fixée par rapport au maximum atteint

précédemment. •  Le score cumulé devient inférieur ou égal à 0 •  La fin de l’une des deux séquences est atteinte.

BLAST


BLAST à l'usage

•  Paramètres : •  Taille des mots

•  ADN : W = 11 •  Protéines : W = 3 → Diminuer W permet d’obtenir

une meilleure sensibilité au prix d’une augmentation des temps de calcul.

•  Matrices de substitution •  DNA : +5 / -4 •  Protéines : Blosum62

•  Fichier de résultats •  N séquences trouvées comme étant les

plus proches de la séquence cible. •  Pour chaque séquence :

•  nom de la séquence •  score d’alignement (critère de tri) •  L'«Expect value» : c'est une estimation de

la probabilité d’avoir obtenu l’alignement par le seul jeu du hasard.

•  Pour les meilleures séquences : •  l’alignement entre la séquence cible et la

séquence de la base (*). (*) ATTENTION: par défaut, une partie des

séquences peut être masquée. Ces parties ne sont pas comptabilisées dans les résultats de l’alignement.


Les différentes versions de Blast

Programmes Séquence cible Banque

blastn séquences nucléiques séquences nucléiques

blastp séquences protéiques séquences protéiques

blastx séquences nucléiques traduites en séquences protéiques

séquences protéiques

tblastn séquences nucléiques séquences nucléiques traduites en séquences protéiques

tblastp séquences nucléiques traduites en séquences protéiques

séquences nucléiques traduites en séquences protéiques

Programmes Description

Megaplast rapide, permet de retrouver des séquences hautement similaires

PSI-Blast itératif. Une séquence consensus est déterminée à partir des résultats, et utilisée comme séquence source pour l'itération suivante ;

PHI-Blast (pattern hit initiated Blast)

programme utilisant comme source une séquence protéique et un motif, celui-ci étant utilisé comme point de départ des recherches de similitudes avec les séquences présentes dans les bases de données.


Alignement de séquences

•  Objectif : •  Trouver une solution mettant en correspondance les symboles de

deux séquences sous les contraintes: •  L'ordre des symboles des deux séquences S et T doit être

conservé •  Le score obtenu pour l'alignement doit être optimal.

•  Type d'alignement :Alignement global ou local •  Alignement global (ou semi-global) → l'alignement recherché inclut les séquences complètes. •  Alignement local → L'alignement recherché est restreint à la zone de plus forte

similitude entre les deux séquences


alignement global

A

B

Alignement global


➢ utilisé pour aligner des séquences homologues (gènes, protéines, chromosomes) afin de déterminer les mutations

évolutives

➢ à la base des alignements multiples (ClustalW,...)


Algorithme de Needleman et Wunsch

•  Fondée sur la programmation dynamique

•  Principe en deux étapes: •  Calculer une matrice M des meilleurs scores d'alignement entre les

deux séquences S et T •  La case M(i,j) donne le score d'alignement entre S[1..i] et T[1..j] •  Pour construire M : •  Supposons S[1..i-1] alignée avec T[1..j-1] •  Pour poursuivre l'alignement, trois possibilités : •  S[i] ~ T[j] avec M(i,j) ← M(i-1,j-1) + score(S[i] ~ T[j]) •  S[i] ~ 0 avec M(i,j) ← M(i-1,j) + score(indel) •  T[j] ~ 0 avec M(i,j) ← M(i,j-1) + score(indel) •  Donc pour calculer M(i,j), il suffit de choisir l'optimum entre les trois valeurs

précédents •  Reconstruire l'alignement en parcourant la matrice de la dernière case

à la première en choisissant à chaque pas le chemin conduisant au score intermédiaire optiomal.

Adapté de Carl Hermann - 32 -

A C T G

CTTG

Programmation dynamique

● Règle 1:

chaque case va contenir un score; le score de l'alignement sera celui de la case en bas à

droite

● Règle 2:

le score d'une case se déduit à partir de celui des cases au-dessus, à gauche ou en diagonale

● Règle 3:

un pas horizontal/vertical coûte 1 gap

un pas diagonal coûte 1 position alignée (match ou mismatch)



A C T G

0 -4 -8 -12 -16

C -4

T -8

T -12

G -16


Score:gap: -4

Etape 1:

on remplit la premièreligne et la première colonne



A C T G

0 -4 -8 -12 -16

C -4

T -8

T -12

G -16


Score:gap: -4 mismatch: -4

Etape 2:

on remplit toutes les cases en gardanten mémoire le mouvement qui donne lemeilleur score

alignement AC score = 0-4 = -4→

insertion de gap score = -4-4 = -8→




A C T G

0 -4 -8 -12 -16

C -4 -4

T -8

T -12

G -16



Etape 2:

on remplit toutes les cases en gardanten mémoire le mouvement qui donne lemeilleur score

alignement AC score = 0-4 = -4→




Adapté de Carl Hermann Adapté de Carl Hermann - 36 -

A C T G

0 -4 -8 -12 -16

C -4 -4

T -8

T -12

G -16


mismatch: -4match: +4

alignement CC score = -4+4 = 0→



Score:gap: -4


A C T G

0 -4 -8 -12 -16

C -4 -4 0

T -8

T -12

G -16


mismatch: -4match: +4

alignement CC score = -4+4 = 0→



Score:gap: -4



A C T G

0 -4 -8 -12 -16

C -4 -4 0

T -8

T -12

G -16



match: +4

alignement AT score = -4-4 = -8→





A C T G

0 -4 -8 -12 -16

C -4 -4 0

T -8 -8

T -12

G -16



match: +4

alignement AT score = -4-4 = -8→





Exemple : Alignement de Needleman et Wunsch

-GATTGACCTGTTTTACG TCATT-TCCAG--TTAGC

G-ATTGACCTGTTTTACG TCATT-TCCAG--TTAGC

G-ATTGACCTGTTTTACG TCATTT-CCAG--TTAGC

…

-GATTGACCTGTTTTACG TCATT-TCCAG-T-TAGC

92 solutions trouvées toutes équivalentes en terme de score


Limites de l'algorithme de Needleman et Wunsch

•  L'algorithme de Needleman et Wunsch nécessitent de construire une matrice de dimension (longueur de la première séquence, longueur de la seconde séquence)

•  Applicable seulement à des séquences de longueur maximale de quelques milliers de nucléotides.

•  Il existe plusieurs alignements strictement identiques du point de vue du score obtenu. •  Les programmes ne fournissent généralement qu'un seul résultat.

•  Le résultat proposé est dépendant de critère de choix dans le parcours du chemin lors de la construction de l'alignement

•  On peut privilégier le chemin haut, moyen ou bas. •  Ce peut être fait par tirage au sort •  On peut ajouter un critère tendant à ne retenir que l'alignement de

longueur minimale



Alignement local : algorithme de Smith et Waterman

•  Objectif : •  Ne conserver que les régions présentant le plus fort

alignement

•  Principe : •  Dérivé de l'algorithme de Needleman et Wunsch •  Ajout d'une quatrième possibilité pour déterminer le meilleur

score M(i,j) : ne pas aligner •  M(i,j) est choisi en prenant la valeur maximale de

•  M(i-1,j-1) + score(S[i] ~ T[j]) → mise en correspondance •  M(i-1,j) + score(indel) → ajout d'un indel sur S •  M(i,j-1) + score(indel) → ajout d'un indel sur T •  0 → pas d'alignement


Alignement multiple

•  Extension de l'alignement de deux séquences à n. •  Mettre en concordance les résidus de chacun des séquences en en

respectant l'ordre, ce qui revient à optimiser : •  Algorithmique

•  Les algorithmes de programmation dynamique ne peuvent être adaptés

•  Approches heuristiques tendant à obtenir une solution suboptimale •  Alignement des séquences deux à deux puis reconstruction de

l'alignement complet des n séquences •  Alignement par blocs •  ...


Programmes d'alignement multiple

•  ClustalW (et Clustal Omega) •  Proposé par Toby Gibson, Des Higgins et Julie Thompson •  Alignement des séquences deux à deux puis contruction d'un arbre pour déterminer

l'odre d'ajout des séquences dans la réalisation de l'alignement final. Clustal Omega ajoute une approche HMM.

•  T-Coffee •  Développé par Cédric Notredame •  Utilise des algorithmes génétiques •  Alignement par blocs

•  Muscle •  Proposé par Robert C. Edgard •  Stratégies avancées de remise en cause de l'ordre d'introduction des séquences de

l’alignement multiple

•  Mafft •  Proposé par Katoh, Kuma, Toh et Miyata •  Basé sur des transformée de Fourier (FFT)


Séquence consensus et profil

•  Séquence consensus •  Séquence résumé où en chaque position est retenu le symbole hors indel le plus

représentatif de toutes les séquences alignées.

•  Profil •  Matrice Position Specific Scoring Matrix (PSSM) quantifiant la représentativité de chaque

symbole en chaque position de la séquence. → Les probabilités brutes sont normalisées (matrice de substitution) → Le score représente la signification statistique de l’occurrence de chaque résidu.


Banque de domaines ou signatures

•  Domaine protéique : •  Unité structurale ou fonctionnelle, conservée lors de l'évolution

généralement décrit sous forme de profils (matrice PSSM)

•  Motifs protéiques: •  Fragment protéique généralement associé à une propriété et décrit

sous la forme d'une expression régulière : MS[VL](X)12C(X)5C

•  Quelques banques •  Prosite : http://prosite.expasy.org •  PFAM: http://pfam.sanger.ac.uk •  Prodom : http://prodom.prabi.fr •  SMART : http://smart.embl-heidelberg.de •  TIGRFam : http://www.jcvi.org/cgi-bin/tigrfams/index.cgi •  Interpro : http://www.ebi.ac.uk/interpro

Documents

Biologie «in silicomthomas/M1/bio_in_silico/MTC... · 2013. 10. 14. · • Association de la biologie et de l'informatique • Objectifs : • Analyser, modéliser ou prédire les