Recherche de gènes et régions codantes





télécharger 480.38 Kb.
titreRecherche de gènes et régions codantes
page7/15
date de publication13.02.2018
taille480.38 Kb.
typeRecherche
d.20-bal.com > droit > Recherche
1   2   3   4   5   6   7   8   9   10   ...   15
Format PIR-NBRF

Sur la 1ère ligne, l'identificateur de la séquence (code de 1 à 6 caractères ou chiffres) doit être précédé du caractère ">" suivi de deux caractères spécifiant la nature de la séquence et du caractère ";". Les deux caractères peuvent être :

P1 protein, complete

F1 protein, fragment

DL DNA, linear

DC DNA, circular

RL RNA, linear

RC RNA, circular

N1 functional RNA, other than tRNA

N3 tRNA

La 2e ligne doit contenir le nom de la séquence suivi de " - " et du nom de l'organisme ou de l'organelle.
La 3e ligne contient la séquence dans un format libre (les blancs et chiffres, s'ils sont présents, seront ignorés) mais terminée par le caractère "*".

LINE 1 :>P1;CBRT

LINE 2 :Cytochrome b - Rat mitochondrion (SGC1)

LINE 3 :M T N I R K S H P L F K I I N H S F I D L P A P S

LINE 4 : VTHICRDVN Y GWL IRY

LINE 5 :TWIGGQPVEHPFIIIGQLASISYFSIILILMPISGIVEDKMLKWN*

EX :

>P1;CCHU

cytochrome c - human

MGDVEKGKKIFIMKCSQCHTVEKGGKHKTGPNLHGLFGRKTGQAPGYSYTAANKNKGIIWGEDTLMEYLENPKKYIPGTKMIFVGIKKKEERADLIAYLKKATNE*

EX : Pir:VBRB [par SRS]

Les données complètes de la banque PIR se trouvent sous un format différent qui est le suivant (exemple d'une entrée) :

\\\

ENTRY A31391 #Type Protein

TITLE *Esterase-6 - Fruit fly (Drosophila melanogaster)

DATE 03-Aug-1992 #Sequence 03-Aug-1992 #Text 03-Aug-1992

PLACEMENT 0.0 0.0 0.0 0.0 0.0

COMMENT *This entry is not verified.

SOURCE Drosophila melanogaster

REFERENCE

#Authors Cooke P.H., Oakeshott J.G.

#Citation submitted to GenBank, April 1989

#Reference-number A31391

#Accession A31391

#Cross-reference GB:J04167

SUMMARY #Molecular-weight 61125 #Length 544 #Checksum 1679

SEQUENCE

5 10 15 20 25 30

1 M N Y V G L G L I I V L S C L W L G S N A S D T D D P L L V

31 Q L P Q G K L R G R D N G S Y Y S Y E S I P Y A E P P T G D

61 L R F E A P E P Y K Q K W S D I F D A T K T P V A C L Q W D

91 Q F T P G A N K L V G E E D C L T V S V Y K P K N S K R N S

121 F P V V A H I H G G A F M F G A A W Q N G H E N V M R E G K

151 F I L V K I S Y R L G P L G F V S T G D R D L P G N Y G L K

181 D Q R L A L K W I K Q N I A S F G G E P Q N V L L V G H S A

211 G G A S V H L Q M L R E D F G Q L A R A A F S F S G N A L D

241 P W V I Q K G A R G R A F E L G R N V G C E S A E D S T S L

271 K K C L K S K P A S E L V T A V R K F L I F S Y V P F A P F

301 S P V L E P S D A P D A I I T Q D P R D V I K S G K F G Q V

331 P W A V S Y V T E D G G Y N A A L L L K E R K S G I V I D D

361 L N E R W L E L A P Y L L F Y R D T K T K K D M D D Y S R K

391 I K Q E Y I G N Q R F D I E S Y S E L Q R L F T D I L F K N

421 S T Q E S L D L H R K Y G K S P A Y A Y V Y D N P A E K G I

451 A Q V L A N R T D Y D F G T V H G D D Y F L I F E N F V R D

481 V E M R P D E Q I I S R N F I N M L A D F A S S D N G S L K

511 Y G E C D F K D N V G S E K F Q L L A I Y I D G C Q N R Q H

541 V E F P

///

Format Swissprot

EX : Swissprot: P21170

Format PROSITE

La syntaxe d'un pattern PROSITE suit des règles.

o lettres A-Z correspondant aux acides aminés (minuscules ou majuscules)

o [] ambiguite inclusive EX: [ILVM]

o {} ambiguite exclusive EX: {FWY}

o X caractère positionnel indifférent

o (n) répétition n fixe d'un sous-motif EX: [RD](2)

o X(n,m) insertions min-max (insertion variable) EX: X(2,4)

o < au début du pattern : le pattern est cadré à gauche de la séquence

o > à la fin du pattern : le pattern est cadré à droite de la séquence

o le caractère '-' sépare chaque position

o le caractère '+' indique que la suite du pattern continue à la ligne suivante


Exemples de motifs :

C-{CPWHF}-X(2,4)-C-H-{CFYW}
AXGHXXX[QST]{DR}

[STANVF]-x(2)-F-x(4)-[DNS]-x(5,7)-[DENQTF]-Y-[HFY]-x(2)-[LIVMFY]-x(3)-+
[LIVM]-x(4)-[LIVM]-x(6,8)-Y-x(12,13)-[LIVM]-x(2)-N-[SACF]-x(2)-[FY]>
 

Les formats spécifiques de séquences multiples

Fichier FOSN (Files Of Sequence Names) de GCG

Le fichier FOSN est un fichier catalogue qui ne contient que des noms de séquences (un nom par ligne), c'est à dire des noms de fichiers personnels (contenant une ou plusieurs séquences) et/ou des noms de séquences de banque (nom_banque:mnémonique). Des commentaires peuvent être ajoutés : ils seront dans ce cas précédés du caractère !


EXEMPLE

!Nom du fichier : catalogue.list

.. ! Le fichier doit commencer par ..

em:*rna* ! Séquences de l'EMBL contenant rna dans leur nom

gamma.seq ! Fichier personnel au format GCG

gb:D01457 ! Séquence D01457 de Genbank

aligned.msf{*} ! Fichier de séquences alignées au format MSF

@em.strings ! Liste de noms de séquences

gb:Hum* ! Séquences humaines de Genbank

miu.seq begin:1 end:95 ! Séquence personnelle des positions 1 à 95

Pour traiter l'ensemble de ces séquences dans un programme de GCG, il suffit de désigner le nom de ce fichier précédé du caractère @ en paramètre d'entrée (EX: @catalogue.list). Le programme ira lui-même chercher les séquences correspondantes aux endroits adéquats (répertoire personnel ou banque).
Le fichier FOSN peut être généré par les commandes Names, StringSearch, Lookup de GCG ou (indirectement) par SRS (il faudra ajouter ..).
Il est possible d'indiquer pour chaque séquence des attributs :

o Début/fin : begin:m end:n (m etn : positions dans la séquence

o Topologie : Circ:T (séquence circulaire) Circ:F (linéaire)

o Brin : Strand:+ (sens directe) Strand:- (sens inverse)

o Poids de la séquence : Wgt:1

o Jointure : Join:nom_seq (concaténation de plusieurs fragments ayant la même étiquette)

Fichier RSF (Rich Sequence Format files) de GCG

Le fichier RSF contient une ou plusieurs séquences, enrichies en annotations : poids de la séquence, auteurs, features etc ... Ce fichier est créé sous l'éditeur multiple de SeqLab de GCG. Il est possible de convertir un fichier MSF en fichier RSF par la commande Reformat -MSF de GCG. Par défaut, le fichier RSF aura l'extension .rsf.
Si ce fichier contient plusieurs séquences, pour spécifier le traitement de l'une d'entre elle, il suffira de mentionner son nom entre {} (EX: opsin.rsf{opsf_human}).
Pour traiter toutes les séquences du fichier, on notera nom_fic.rsf{*} (EX: opsin.rsf{*}).
opsf.rsf{*human*} spécifiera toutes les séquences dont le nom contient human etc ...
EXEMPLE

!!RICH_SEQUENCE 1.0 ! En-tête obligatoire

.. ! Le fichier doit commencer par ..

{

name chkhba ! Attributs (noms, type, description ...)

type DNA

longname chkhba

checksum 980

creation-date 4/15/98 16:42:47

strand 1

sequence ! La séquence doit être précédé du mot-clé séquence

ACACAGAGGTGCAACCATGGTGCTGTCCGCTGCTGACAAGAACAACGTCAAGGGCATCTT

CACCAAAATCGCCGGCCATGCTGAGGAGTATGGCGCCGAGACCTTGGAAAGGATGTTCAC

CACCTACCCCCCAACCAAGACCTACTTCCCCCACTTCGATCTGTCACACGGCTCCGCTCA

...

}

{

name davagl

type DNA

longname davagl

checksum 7399

creation-date 4/15/98 16:42:47

strand 1

sequence

GTGCTCTCGGATGCTGACAAGACTCACGTGAAAGCCATCTGGGGTAAGGTGGGAGGCCAC

GCCGGTGCCTACGCAGCTGAAGCTCTTGCCAGAACCTTCCTCTCCTTCCCCACTACCAAA

...

}

 

Format MSF

Le fichier MSF (Multiple Sequence Format) contient plusieurs séquences dans un fichier. Il est issu d'un alignement multiple produit par les programmes PileUp, LineUp -MSF et reformat -MSF de GCG.


Pour spécifier les séquences du fichier MSF dans un programme de GCG, on utilise la syntaxe suivante :

aligned.msf{*} *: toutes les séquences du fichier MSF

ou aligned.msf{rna1,rna2} liste des noms de séquences du fichier MSF

EXEMPLE

cytc.seq MSF: 104 Type: N January 01, 1776 12:00 Check: 1595 ..

Name: ccho Len: 104 Check: 8847 Weight: 1.00

Name: cchu Len: 105 Check: 3247 Weight: 1.00

Name: cccz Len: 104 Check: 9501 Weight: 1.00

//

ccho GDVEKGKKIF VQKCAQCHTV EKGGKHKTGP NLHGLFGRKT GQAPGFTYTD

cchu MGDVEKGKKI FIMKCSQCHT VEKGGKHKTG PNLHGLFGRK TGQAPGYSYT

cccz GDVEKGKKIF IMKCSQCHTV EKGGKHKTGP NLHGLFGRKT GQAPGYSYTA

ccho ANKNKGITWK EETLMEYLEN PKKYIPGTKM IFAGIKKKTE REDLIAYLKK

cchu AANKNKGIIW GEDTLMEYLE NPKKYIPGTK MIFVGIKKKE ERADLIAYLK

cccz ANKNKGIIWG EDTLMEYLEN PKKYIPGTKM IFVGIKKKEE RADLIAYLKK

ccho ATNE

cchu KATNE

cccz ATNE

Format PHYLIP

Deux formats de base sont proposés. Dans les 2 cas, la 1ère ligne du fichier doit contenir le nombre de séquences suivi du nombre de sites (= nombre de positions) par séquence. Les séquences doivent être préalablement alignées : elles ont donc toutes la même taille. Le nom de chaque séquence doit figurer dans les 10ères colonnes de la ligne. Les séquences peuvent contenir ou non des espaces.

  1. Format intercalé (= "interleaved")
    EXEMPLE

5 42

Turkey AAGCTNGGGC ATTTCAGGGT

Salmo gairAAGCCTTGGC AGTGCAGGGT

H. SapiensACCGGTTGGC CGTTCAGGGT

Chimp AAACCCTTGC CGTTACGCTT

Gorilla AAACCCTTGC CGGTACGCTT

GAGCCCGGGC AATACAGGGT AT

GAGCCGTGGC CGGGCACGGT AT

ACAGGTTGGC CGTTCAGGGT AA

AAACCGAGGC CGGGACACTC AT

AAACCATTGC CGGTACGCTT AA

2- Format séquentiel
Les séquences se suivent (dans leur totalité) les unes après les autres.
EXEMPLE

5 42

Turkey AAGCTNGGGC ATTTCAGGGT

GAGCCCGGGC AATACAGGGT AT

Salmo gairAAGCCTTGGC AGTGCAGGGT

GAGCCGTGGC CGGGCACGGT AT

H. SapiensACCGGTTGGC CGTTCAGGGT

ACAGGTTGGC CGTTCAGGGT AA

Chimp AAACCCTTGC CGTTACGCTT

AAACCGAGGC CGGGACACTC AT

Gorilla AAACCCTTGC CGGTACGCTT

AAACCATTGC CGGTACGCTT AA

Les outils de conversion de formats

 ReadSeq

READSEQ est un programme de reformatage général des séquences (conversion) avec reconnaissance automatique du format du fichier d'entrée.

De nombreux formats de sortie sont autorisés par Readseq 

1. IG/Stanford used by Intelligenetics and others

2. GenBank/GB genbank flatfile format

3. NBRF format

4. EMB EMBL flatfile format

5. GCG single sequence format of GCG software

6. DNAStrider for common Mac program

7. Fitch format limited use

8. Pearson/Fasta a common format used by Fasta programs and others

9. Zuker format limited use. Input only.

10. Olsen format printed by Olsen VMS sequence editor.Input only.

11. Phylip3.2 sequential format for Phylip programs

12. Phylip interleaved format for Phylip programs (v3.3, v3.4, v3.5)

13. Plain/Raw sequence data only (no name, document, numbering)

14. PIR/CODATA format used by PIR

15. MSF multi sequence format used by GCG software

16. ASN.1 format used by NCBI

17. PAUP PAUP's multiple sequence (NEXUS) format

18. Pretty print with various options for nice looking output.

Readseq peut être utilisé de deux façons différentes :

Mode intéractif :

READSEQ peut être lancé en interactif (au prompt de la machine) :

Selon un dialogue interactif en saisissant :

readseq

fichier de sortie (en premier),

choix du format de sortie (18 choix)

et fichier d'entrée (plusieurs fois éventuellemnt)

terminez par un vide (validation de la liste)

Mode en ligne :

Selon une commande en ligne :

readseq [-options] in.seq > out.seq

ex : readseq fichier_entree - All -f8 >fichier_sortie

readseq files* -All -f5 -outfile=fichier_sortie

ConvSeq

Ce programme génère un fichier formaté de séquences à partir de séquences de banques désignées par leur identificateur ou leur numéro d'accession. Les formats de sortie possibles sont ceux autorisés par le programme Readseq.

Exemple de fichier d'entrée que l'on peut soumettre à CONVSEQ :

GENBANK:STRABP 15 328

GENBANK:SSALB r

GENBANK:A06977

EMBL:HSALBG

 

Programmes GCG de conversion de formats

GCG propose des commandes spécifiques de conversion selon les formats donnés en entrée et souhaité en sortie : :

Format GCG ---> Autre format

tostaden
tofasta
toig
topir

Format donné ---> format GCG

fromstaden
fromfasta
frompir
fromgenbank
fromembl
fromig

 

Les autres utilitaires de manipulation de séquences

Pour différentes raisons, il peut être utile de réaliser une inversion-complémentation d'une séquence nucléique. Plusieurs logiciels proposent ce type de manipulation :

Reverse Complement; INVCOMP ; Revseq

La comparaison de séquences

Sommaire

 Introduction

La notion de similarité, d’identité et d’homologie

Le choix du matériel à comparer : ADN ou protéine ?

Les principes de base pour identifier la ressemblance entre 2 séquences

Les principaux logiciels et programmes de comparaison avec les banques de séquences

Le logiciel FASTA

Le logiciel BLAST

L’alignement multiple
Introduction

La recherche de similitude entre séquences est un élément fondamental qui constitue souvent la première étape des analyses de séquences. Elémentaire, la question de la comparaison et de l'obtention d'un alignement optimal de 2 séquences biologiques, nécessite néanmoins la mise en œuvre de procédures de calcul et de modèles biologiques permettant de quantifier la notion de ressemblance entre ces séquences. L’objectif est de révéler des régions proches dans leur séquence primaire en se basant sur le principe de parcimonie, c'est-à-dire en considérant le minimum de changements en insertion, suppression, ou substitution qui séparent deux séquences. On peut apprendre ainsi, par association, des informations importantes sur la structure, la fonction ou l'évolution des biomolécules. Cette méthode est largement utilisée dans les recherches de motifs à travers une séquence, dans la caractérisation de régions communes ou similaires entre deux ou plusieurs séquences, dans la comparaison d'une séquence avec l'ensemble ou sous-ensemble des séquences d'une base de données, ou bien encore dans l'établissement d'un alignement multiple sur lequel sont basées les analyses d'évolution moléculaire. Nous décrirons dans ce chapitre les principes fondamentaux qui sont indispensables à la compréhension de ces outils en illustrant nos propos par un certain nombre de programmes couramment utilisés dans le domaine.
La notion de similarité, d’identité et d’homologie

Il existe plusieurs termes permettant de nommer la ressemblance entre deux séquences biologiques. La similarité est une quantité qui se mesure en % d’identité, identité elle même définie comme une ressemblance parfaite entre deux séquences. L’homologie quand à elle est une propriété de séquences qui a une connotation évolutive. Deux séquences sont dites homologues si elles possèdent un ancêtre commun. L’homologie présente la particularité d’être transitive. Si A est homologue à B et B homologue à C alors A est homologue à C même si A et C se ressemblent très peu. L’homologie se mesure par la similarité. On considère qu’une similarité significative est signe d’homologie sauf si les séquences présentent une faible complexité. L’inverse n’est par contre pas vrai. Une absence totale de similarité ne veut pas dire non-homologie.

Le choix du matériel à comparer : ADN ou protéine ?

Une des questions qui se posent au biologiste lorsqu’il compare des séquences est de savoir sur quel matériel il doit travailler : ADN ou protéine ?

Concernant les acides nucléiques, pour les parties non codantes, on peut identifier des séquences homologues jusqu’à 200 millions d’années, 600 millions pour les régions codantes. Pour les protéines, on trouve des séquences homologues après 1 milliard d’années d’évolution et des similarités significatives au delà de 2,5 millions d’années. En conclusion, dès que c’est possible, il est préférable de comparer les séquences au niveau protéique.
Les principes de base pour identifier la ressemblance entre 2 séquences

La détermination d'un score

Pour qualifier et quantifier la similitude entre séquences, un score est calculé. Celui-ci peut mesurer soit le rapprochement, soit l'éloignement des séquences pour refléter ce qui les sépare. Ce score repose sur un système qui permet d'attribuer un score élémentaire pour chaque position lorsque les séquences sont éditées l'une sous l'autre.


Le score élémentaire est un élément d'une matrice de scores qui rend compte de tous les états possibles en fonction de l'alphabet utilisé dans la description des séquences. Ainsi, pour les acides nucléiques, la matrice d'identité ou unitaire est principalement employée.



Elle rend compte de l'identité des résidus pour chacune des positions de la comparaison, on parle ainsi de bon ou de mauvais appariement ou bien de bonne ou mauvaise association. Ce critère qui permet déjà d'établir des ressemblances ne suffit pas toujours pour révéler au mieux les similitudes entre séquences. Très rapidement, on s'est aperçu qu'une insertion ou une délétion (on admettra ici le franglais) d'une ou plusieurs bases pouvait améliorer le score d'une comparaison et ainsi faire davantage ressortir les zones identiques ou très proches. Ces brèches (en anglais gap) que l'on impose aux séquences sont évidemment pénalisantes dans le calcul du score. Si l'on considère que le score donne le rapprochement entre deux séquences, on peut résumer celui-ci par l'équation suivante :
(
1)


se est un score élémentaire et sp une pénalité d'insertion ou de délétion.

Deux remarques s'imposent. La première est que le score est fonction de la longueur de la zone de similitude que l'on considère, c'est à dire que plus la longueur est grande, plus le score est élevé. La deuxième est que l'on peut nuancer le calcul en donnant plus ou moins d'importance aux pénalités et aux associations possibles entre résidus. Ainsi, le poids d'une insertion peut être plus ou moins fort par rapport à une mauvaise association. On voit déjà très bien ici que par le biais de ces deux éléments fondamentaux, on pourra privilégier une situation plutôt qu'une autre, c'est-à-dire avoir des comparaisons de séquences avec peu ou beaucoup d'insertions-délétions. On retrouvera bien sûr ce type d'éléments sous forme de paramètre dans les programmes de comparaison.
La recherche de segments et l'alignement

Les programmes de comparaison de séquences ont pour but de repérer les endroits où se trouvent des régions identiques ou très proches entre deux séquences et d'en déduire celles qui sont significatives et qui correspondent à un sens biologique de celles qui sont observées par hasard. En général les algorithmes fonctionnent sur des segments de séquences (on parle de fenêtres, de motifs ou de mots) sur lesquels on regarde s'il existe ou pas une similitude significative. Si on ne prend en compte que des analogies entre sous-séquences sans traiter la possibilité d'insertion ou de délétion, on parlera alors de segments similaires. Ainsi l'équation (1) se résume uniquement à l'expression de la somme des scores élémentaires. On distingue pour cette catégorie deux classes précises de similitude : la ressemblance parfaite ou identité et la ressemblance non parfaite que l'on qualifie de similitude.





Il existe bien évidemment plusieurs niveaux de similitude et les programmes s'attachent à repérer les régions où l'on trouve généralement des éléments identiques ou très similaires suffisamment nombreux pour que la ressemblance soit intéressante. En fait on considérera que la ressemblance est significative lorsque son score est supérieur ou égal à un score seuil que l'on s'est fixé (cf. l'évaluation des résultats). Bien entendu, pour l'identité, seules les matrices unitaires sont autorisées comme matrices de scores élémentaires alors que pour les autres ressemblances, toutes les matrices peuvent être employées. La notion d'alignement elle, suppose la recherche des positions auxquelles il est possible de faire des insertions ou des délétions afin d'optimiser le score d'une comparaison. On considère qu'un programme est un programme d'alignement s'il possède au moins cette étape.



La plupart des programmes de comparaisons de séquences s'appuient sur une de ces trois notions (la recherche de segments identiques, de segments similaires, ou d'alignements) pour faire ressortir des ressemblances entre séquences. Nous verrons que certains programmes, essentiellement pour les comparaisons avec les bases de données, peuvent utiliser une combinaison de ces principes fondamentaux. Il existe évidemment plusieurs méthodes pour mettre en œuvre ces principes, nous décrirons ici celles qui les illustrent le mieux et qui sont souvent les plus utilisées.
Les différents types d’alignements

Global/Local

Un alignement global considère l'ensemble des éléments de chacune des séquences. Si les longueurs des séquences sont différentes, alors des insertions devront être faites dans la séquence la plus petite pour arriver à aligner les deux séquences d'une extrémité à l'autre. Dans le cas où les longueurs sont très différentes, il est possible d'appliquer ce principe d'alignement global seulement en considérant chaque position d'une séquence longue comme étant un point de départ d'alignement avec une séquence courte. C'est l'algorithme de type II au sens Collins et Coulson (1987) que l'on appelle aussi couramment l'algorithme de meilleure localisation. Cependant dans un alignement global, si uniquement de courts segments sont très similaires entre deux séquences, les autres parties des séquences risquent de diminuer le poids de ces régions. C'est pourquoi d'autres algorithmes d'alignements, dits locaux, basés sur la localisation des similarités sont nés. Le but de ces alignements locaux est de trouver sans prédétermination de longueur les zones les plus similaires entre deux séquences. L'alignement local comporte donc une partie de chacune des séquences et non la totalité des séquences comme dans la plupart des alignement globaux.



Avec/sans gap

On a vu qu'il pouvait être nécessaire, pour optimiser la comparaison de deux séquences, d'introduire des insertions ou des délétions de longueur variable à certaines positions des séquences. En fait, pour conserver l'intégralité de l'information biologique, le traitement d'une délétion à l'intérieur d'une séquence est considéré comme une insertion dans la séquence lui faisant face. Dans certaines publications, on trouvera le terme d'indel (INsertion-DELetion) pour nommer ces événements. On a vu également que les indels sont considérées comme des pénalités dans le calcul du score. Il existe néanmoins plusieurs manières d'exprimer cette pénalité. voire Pondération des gaps
La recherche de segments similaires

L'algorithme élémentaire de ce type de recherche est basé sur la comparaison de fenêtres de longueur fixe que l'on déplace le long des séquences. Soit deux séquences A et B à comparer et l la longueur de la fenêtre. On détermine sur la séquence A une première fenêtre de longueur l que l'on va comparer avec toutes les fenêtres possibles de même longueur, obtenues à partir de la séquence B. Un incrément est alors appliqué pour déterminer une deuxième fenêtre sur la séquence A, puis l'on recommence le balayage des comparaisons sur la séquence B. Si l'on choisit un incrément de 1 et que les séquences ont respectivement une longueur de m et n éléments, on effectuera de l'ordre de nxm comparaisons de fenêtres différentes. Pour chaque comparaison entre deux fenêtres, un score est obtenu et l'on mémorisera uniquement les comparaisons dont les scores sont jugés significatifs, c'est-à-dire supérieurs ou égaux à un seuil que l'on s'est fixé. Par exemple lorsque le score correspond au minimum à 80% d'identité avec l'utilisation d'une matrice unitaire nucléique comme matrice de scores élémentaires. Les comparaisons sauvegardées qui correspondent à des positions chevauchantes des fenêtres peuvent éventuellement être concaténées pour faire ressortir, à l'édition des résultats, les meilleures zones de similitudes entre les deux séquences.

Application : le programme Diagon de Staden

Ce programme (Staden, 1982) utilise directement l'algorithme décrit ci-dessus en faisant une édition graphique des résultats. Sur le graphe, chacun des deux axes correspond à une séquence. On placera un point aux coordonnées i et j du graphe, i et j étant les positions centrées de chacune des fenêtres considérées, quand le score obtenu en comparant les deux fenêtres est supérieur au seuil fixé. On appelle un tel point, un point de similitude et un tel graphe, une matrice de points. Le tracé du graphe donne alors tous les points de similitude, c'est-à-dire la représentation de tous les segments similaires considérés comme significatifs. Quand deux séquences se ressemblent, une ligne diagonale se dessine sur le graphe par juxtaposition des points de similitude.



Le programme peut également être utilisé pour rechercher sur une séquence des répétitions directes ou des palindromes en comparant la séquence sur elle-même.



Cette représentation graphique permet aussi de visualiser les zones d'insertion-délétion présentes entre les deux séquences. Elles sont représentées par des déplacements verticaux ou horizontaux des régions diagonales similaires.
La recherche d'alignements optimaux

La méthode de programmation dynamique

Le temps de comparaison de deux séquences de longueur équivalente N est proportionnel à N². L'exploration de chaque position de chaque séquence pour la détermination éventuelle d'une insertion augmente d'un facteur 2N le temps de calcul. La programmation dynamique est un moyen qui permet de limiter cette augmentation pour conserver un temps de calcul de l'ordre de N². Elle est basée sur le fait que tous les événements sont possibles et calculables mais que la plupart sont rejetés en considérant certains critères. Needleman et Wunsch (1970) ont introduit les premiers ce type d'approche pour un problème biologique et leur algorithme reste une référence dans le domaine.

L'algorithme de Needleman et Wunsch

Cet algorithme a été développé initialement pour aligner deux séquences protéiques. Soit A et B deux séquences de longueur m et n. L'algorithme construit un tableau à deux dimensions (m,n) que l'on appelle matrice de comparaison.

L'équation suivante résume le principe de calcul d’une case de cette matrice :
S (i, j) = se (i, j) + MAX ((S (i+1,j+1)),(S (x, j+1) –P) ;(S (i+1, y) –P)) (2)


où S(i,j) est le score somme de la case d'indice i et j, se le score élémentaire de la case d'indice i et j de la matrice initiale et P la pénalité donnée pour une insertion.

 

Pour plus de détails sur les différentes étapes de l’algorithmes :

Dans une première étape, on attribue à cette matrice les valeurs appropriées selon la matrice de scores élémentaires choisie. On obtient ainsi une matrice initiale de comparaison. Puis dans une deuxième étape, la matrice est transformée par addition de scores. Cette opération est effectuée ligne par ligne en commençant par le coin droit inférieur et en terminant par le coin gauche supérieur. Pour chacune des cases de la matrice transformée, le score somme est calculé de la manière suivante:


où S(i,j) est le score somme de la case d'indice i et j et se le score élémentaire de la case d'indice i et j de la matrice initiale. Le score max S(x,y) correspond en fait au score somme maximum déjà présent dans la matrice de comparaison en cours de transformation. Une illustration de cette transformation est donnée dans la Figure suivante :


Le but est ensuite de trouver le meilleur alignement global, à partir de la matrice transformée. Pour cela, on établit dans la matrice un chemin qui correspond au passage des scores sommes les plus élevés, ceci en s'autorisant trois types de mouvements possibles et en prenant comme point de départ le score maximum présent dans la matrice transformée. Needleman et Wunsch nomment ce passage le chemin des scores maximum.



Les mouvements autorisés pour tracer le chemin sont :

a) le mouvement diagonal qui correspond au passage de la case (i,j) à la case (i+1,j+1). C'est le mouvement que l'on privilégie.
b) le mouvement vertical qui correspond au passage de la case (i,j) à la case (i,j+1), ce qui donne une insertion sur la séquence en i.
c) le mouvement horizontal qui correspond au passage de la case (i,j) à la case (i+1,j), ce qui donne une insertion dans la séquence en j.

Dans notre exemple, on ne considère pas de pénalités pour les insertions mais il est possible bien sûr d'incorporer celles-ci dans la méthode. Pour cela il suffit de soustraire dans le calcul de chaque score somme une pénalité en fonction de la position du score "max S(x,y)" considéré. Ainsi l'équation (3) prend la forme suivante:





où S(i,j) est le score somme de la case d'indice i et j, se le score élémentaire de la case d'indice i et j de la matrice initiale et P la pénalité donnée pour une insertion.

De nombreux programmes sont déduits de ce genre d'alignement, le programme ALIGN (Dayhoff et al., 1979) en est une application directe avec l'utilisation de pénalités à deux paramètres (dépendant et indépendant de la longueur). Cependant, surtout pour les séquences nucléiques, il peut exister plusieurs chemins possibles donnant un alignement optimal. On doit alors faire un choix arbitraire car l'algorithme ne conserve qu'un pointeur de chemin pour chaque position de la matrice de comparaison. Ceci est fait généralement en privilégiant les insertions les plus courtes. Le programme GAP du logiciel GCG (Devereux et al., 1984) permet de sauvegarder des pointeurs équivalents et ainsi peut palier à ce genre de problème.
L'algorithme de Smith et Waterman

Une des méthodes d'alignement local les plus utilisées fut introduite par Smith et Waterman (1981). La différence essentielle avec l'algorithme de Needleman et Wunsch que nous venons de décrire est que n'importe quelle case de la matrice de comparaison peut être considérée comme point de départ pour le calcul des scores sommes et que tout score somme qui devient inférieur à zéro stoppe la progression du calcul des scores sommes. La case pointée est alors réinitialisée à zéro et peut être considérée comme nouveau point de départ. Cela implique que le système de scores choisi possède des scores négatifs pour les mauvaises associations qui peuvent exister entre les éléments des séquences. L'équation utilisée pour le calcul de chaque score somme pendant la transformation de la matrice initiale prend alors l'expression suivante:


où S(i,j) est le score somme de la case d'indice i et j, se le score élémentaire de la case d'indice i et j de la matrice initiale et P la pénalité donnée pour une insertion. La Figure ci-dessous illustre un tel alignement.



Ce genre de méthode est souvent considéré comme plus sensible que celles directement inspirées de Needelman et Wunsch surtout lorsque les séquences à comparer sont inconnues ou de longueurs différentes. De plus, si les régions trouvées entre les deux séquences recouvrent la totalité de celles-ci, alors on peut considérer l'alignement local comme étant un alignement global.

Les principaux logiciels et programmes de comparaison avec les banques de séquences

Introduction

La taille sans cesse croissante des banques de séquences a nécessité l'élaboration d'algorithmes spécifiques pour effectuer la comparaison d'une séquence avec une banque de données car les algorithmes standards de comparaison entre deux séquences sont généralement trop longs sur des machines classiques (voire méthode de programmation dynamique). La plupart de ces programmes constituent des méthodes heuristiques. Leur but est de filtrer les données de la banque en étapes successives car peu de séquences vont avoir des similitudes avec la séquence comparée. Ces méthodes heuristiques utilisent donc certaines approximations pour éliminer rapidement les situations sans intérêt et ainsi repérer les séquences de la banque susceptibles d'avoir une relation avec la séquence recherchée. Ces programmes permettent ensuite de calculer un score pour mettre en évidence les meilleures similitudes qu'ils ont observées. Il existe de nombreux programmes qui répondent à cette fonction avec des approches qui peuvent être très différentes. Nous nous limiterons ici à la description détaillée des deux types de programme les plus utilisés par les biologistes qui sont les logiciels FASTA (Pearson et Lipman, 1988) et BLAST (Altschul et al., 1990). Ces programmes ont une approche différente mais complémentaire pour effectuer des recherches à travers une base de données, mais sont basés tous les deux sur des méthodes très heuristiques. C'est pourquoi ils doivent être utilisés essentiellement comme logiciels permettant de repérer les séquences de la banque susceptibles d'avoir des ressemblances biologiques avec la séquence recherchée. Ils ne constituent pas des programmes optimisés pour comparer deux séquences entre elles. Très souvent, les résultats qu'ils procurent devront être confirmés ou renforcés par d'autres programmes plus spécialisés en particulier dans la recherche de caractéristiques biologiques. Actuellement, seule, l'utilisation de machines parallèles ou massivement parallèles et de machines dites câblées donnent la possibilité d'utiliser des algorithmes plus rigoureux comme celui de Smith et Waterman (1981) pour la comparaison avec une banque de données.
Généralités sur la qualité des logiciels

La notion de sensibilité/sélectivité
1   2   3   4   5   6   7   8   9   10   ...   15

similaire:

Recherche de gènes et régions codantes iconRecherche année 2009/2010 Titre du stage
«Flux des (trans-)gènes et impact sur la biodiversité» ‘gmbioImpact’ (2007-2010)

Recherche de gènes et régions codantes icon«Titre de l’étude»
«indiquer la nature des prélèvements (sang, urine, moelle,adn, etc)» et notamment le fait qu’il s’agit d’étudier «les modifications...

Recherche de gènes et régions codantes iconLe transfert aux régions des biens immobiliers de l’Afpa appartenant...

Recherche de gènes et régions codantes iconRecherche L’alphabet français semble mieux convenir à la fonction...

Recherche de gènes et régions codantes iconRecherche L’alphabet français semble mieux convenir à la fonction...

Recherche de gènes et régions codantes iconRecherche L’alphabet français semble mieux convenir à la fonction...

Recherche de gènes et régions codantes iconLa Recherche Scientifique
...

Recherche de gènes et régions codantes iconRecherche à visée médicale: L'article 23 de l'actuel projet de loi,...
«autorisation implicite» et «favoriser les besoins de l'industrie de la procréation»

Recherche de gènes et régions codantes iconLa loi n° 2015-29 du 16 janvier 2015 relative à la délimitation des...

Recherche de gènes et régions codantes iconDecentralisation de l’action sociale et protection de l’enfance
«relative aux droits et libertés des communes, des départements et des régions»






Tous droits réservés. Copyright © 2016
contacts
d.20-bal.com