FAQ Décrypthon

1) En quoi consiste le calcul?

Le calcul consiste a comparer entre elles, au moyen d'un algorithme exact d'alignement local, environ 550000 sequences de proteines.

2) Quel est l'algorithme utilise pour la comparaison de sequences?

Il s'agit de l'algorithme d'alignement local de Smith-Waterman (ref1), implementant une fonction de gap affine et les optimisations de Gotoh (ref2). Soient deux sequences A et B, l'algorithme de Smith-Waterman est un algorithme de programmation dynamique qui permet de calculer le meilleur score d'alignement de deux sous-sequences de A et de B. Le caractere significatif des alignements est evalue par la methode des Z-scores (ref3), en effectuant 100 replicats de l'experience aleatoire.

3) Qu'est-ce que la programmation dynamique?

C'est une methode de resolution de problemes qui procede en combinant les solutions de sous-problemes qui ne sont pas independants entre eux (i.e ils ont en commun des sous-sous problemes). Un algorithme de programmation dynamique memorise les solutions optimales de sous-sous problemes, evitant de les calculer a de multiples reprises.

Pour que la programmation dynamique soit applicable a un probleme d'optimisation, celui-ci doit presenter

1. une sous-structure optimale, i.e une solution optimale au probleme comporte des solutions optimales aux sous-problemes, et
2. des sous-problemes superposes, i.e l'algorithme recursif repasse sur les memes problemes plutot que d'en engendrer des nouveaux.

Les algorithmes de programmation dynamique comprennent typiquement les etapes suivantes:

• caracterisation de la structure d'une solution optimale
• definition recursive de la valeur d'une solution optimale
• calcul de la valeur d'une solution optimale en remontant progressivement jusqu'a l'enonce du probleme initial.

4) Pourquoi ne pas avoir choisi une approche heuristique telle que BLAST?

L'algorithme de Smith-Waterman est exact, dans le sens ou il garantit de trouver le score optimal pour une matrice de score donnee. L'algorithme de SW avec une fonction de gap affine est considere comme une des methodes les plus sensibles pour comparer des paires de sequences (ref 4). Le prix a payer pour cette sensibilite est un temps de calcul plus eleve (pour deux sequences de longueur n et m, la complexite en temps est de l'ordre de O(nm)) que celui associe a des methodes heuristiques telles que BLAST (ref 5). Etant donne la puissance de calcul disponible dans le "grid Decrypthon" (37 TFLOPS), cette consideration n'est pas prohibitive.

5) Qu'est-ce qu'un Z-score ?

La significativite d'un score calcule par l'algorithme de Smith-Waterman, ou la probabilite qu'un alignement soit du ou non au hasard, peut etre evaluee par la methode des Z-scores. Pour cela, on compare le score de deux sequences A et B avec les scores obtenus entre la sequence A et N sequences aleatoires de longueur et de composition en acides amines identiques a B. La methode Monte-Carlo est utilisee pour estimer la moyenne et l'ecart-type de cet echantillon, et le Z-score est defini comme Z(A,B)=(SW(A,B)-M)/S. La meme operation est ensuite realisee en comparant la sequence B avec N sequences A randomisees, et le Z-score finalement retenu est defini par Z-score=min(Z(A,B),Z(B,A)) (ref 6).

6) Quelle est la "taille" du calcul?

La complexite du calcul croit en O(N L^2), ou N est le nombre de repetitions de l'experience aleatoire, et L est la longueur de la banque de sequences.

7) Quelle est l'origine des sequences?

La banque de sequences utilisee pour le projet Decrypthon comporte environ 550000 sequences, et a ete compilee a partir des sources suivantes (ref 7): Swiss-Prot, TrEMBL, TrEMBL_new, RefSeq, certaines donnees d'EnsEMBL, ainsi qu'a partir des sequences d'environ 80 proteomes.

Environ 1,2 10^6 sequences ont ete rassemblees a partir de ces differentes sources. Apres elimination de la redondance exacte (414887 sequences (36%)), et des sequences partielles etiquetees en tant que "fragments" (167200 sequences (23% des sequences non identiques)), environ 550000 sequences ont ete conservees pour la comparaison "tout contre tout".

La librairie de 550000 sequences a ete decoupee en paquets d'environ 100 KBytes, qui ont ete combines de facon pairee et distribues sur les PCs participants au projet.

8) Comment ont ete traitees les sequences de proteines "hypothetiques" et les "fragments"?

Les sequences etiquetees "fragments" ont ete eliminees de toutes les banques de depart, a l'exception de Swiss-Prot. Il est en effet hautement probable que les sequences "fragment" de Swiss-Prot soient en fait les seules representantes des sequence completes correspondantes, et qu'elles apportent ainsi une information non redondante.

Les proteines hypothetiques non etiquetees "fragments" ont ete conservees pour le calcul pour deux raisons:

1. la plupart d'entre-elles provient de TrEMBL, qui est une base de donnees maintenue automatiquement (i.e les annotations n'y sont pas examinees par des humains comme dans Swiss-Prot) pour pouvoir faire face au volume croissant des donnees de sequences. Ignorer les proteines hypothetiques de TrEMBL reviendrait a ignorer les contributions des projets de sequencage massifs recents ou en cours.
2. le caractere non hypothetique de certaines de ces proteines peut etre mis en evidence par des relations de similarite avec d'autres proteines non hypothetiques.

9) En quoi consistent les resultats bruts?

Les resultats bruts du calcul consistent en un ensemble de coordonnees d'alignement et de scores (les scores Smith-Waterman et les z-scores), ainsi que le nombre et la longueur cumulee des gaps, pour chaque paire de sequences. Le resultat global du calcul est une matrice de similarite pour les 550000 proteines. Cette matrice est une ressource a partir de laquelle differents types d'analyse peuvent etre envisages, telles qu'un regroupement (clustering) des sequences "similaires", selon differentes procedures algorithmiques.

10) Tous les resultats sont-ils consideres?

Tous les resultats sont calcules, mais seuls ceux caracterises par une longueur d'alignement optimal de 30 lettres ou plus, et ayant un Z-score superieur ou egal a 5, sont rapportes.

11) Comment peut-on definir des ensembles de proteines similaires a partir de la matrice de resultats?

La matrice de similarite pourra etre clusterisee de differentes facons, p.ex:

1. par une approche traditionnelle de "single linkage" (ref 8),

   B) par un algorithme base sur la simulation de flux dans des graphes (ref 9).

2. La deuxieme approche pourrait permettre de palier a deux limitations associees au clustering par liaison simple: a) la presence de proteines multi-domaines, b) des variations dans le degre de similarite provoquees par des differences dans le taux d'evolution de differentes familles de proteines.

12) A quoi peuvent servir les clusters de sequences sans annotations?

Il est improbable que les similarites entre les sequences constitutives de clusters soient dues au seul hasard. En ce sens, ces clusters etablissent une realite biologique des sequences (ou de sous-sequences) qu'ils contiennent. En effet, certaines sequences comparees dans le calcul n'ont pas encore ete caracterisees biochimiquement, ni meme genetiquement; c'est le cas de nombreuses sequences de bacteries, et de tres nombreuses sequences de l'homme.

D'un autre cote, pour une classe d'annotation donnee, les clusters peuvent permettre de designer des "terra incognitae", e.g les clusters caracterises par une absence d'annotations structurales ou de liens vers des bases de donnees de structure (PDB, SCOP,...) peuvent servir a designer des cibles pour une determination de structure, optimisant de la sorte l'effort pour augmenter la couverture du "fold space" (ref 10).

13) Y aura-t-il d'autres types d'analyses sur les resultats bruts?

Dependant des moyens disponibles et de la mise en place de collaborations academiques, d'autres analyses pourront etre realisees. Par exemple, les clusters de proteines homologues pourront servir a definir des profils, ou PSSMs (ref 11), qui permettront a leur tour une classification de SNPs codants non synonymes et une prediction de leur pouvoir deletere (ref 12).

D'autres analyses pourront porter sur les domaines proteiques, p.ex la delimitation de ceux-ci sur base des donnees de similarites de sequence (ref 13), ou sur base d'une combinaison de donnees de sequence et de structure (ref 14), ou encore l'etude de la distribution de domaines adjacents dans le genome dans les clusters de proteines orthologues (ref 15), et la synthese de ces informations dans des reseaux "scale-free" (ref 16).

14) Comment les resultats seront-ils accessibles?

Les resultats seront mis dans le domaine public, et seront accessibles sur plusieurs sites destines a la communaute scientifique, dont INFOBIOGEN (www.infobiogen.fr) en France, et l'EBI (www.ebi.ac.uk) au Royaume-Uni. L'ensemble des resultats etant d'une taille assez importante (environ 35 GB), la possibilite de les diffuser sur des bandes est etudiee.

References:

1. Smith TF, Waterman MS.
   Identification of common molecular subsequences.
   J Mol Biol 1981 Mar 25;147(1):195-7.
   PMID: 7265238.
2. Gotoh O.
   An improved algorithm for matching biological sequences.
   J Mol Biol. 1982 Dec 15;162(3):705-8. No abstract available.
   PMID: 7166760.
3. Comet JP, Aude JC, Glemet E, Risler JL, Henaut A, Slonimski PP, Codani JJ. Significance of Z-value statistics of Smith-Waterman scores for protein alignments.
   Comput Chem. 1999 Jun 15;23(3-4):317-31.
   PMID: 10627144.
4. Durbin R, Eddy S, Krogh A, Mitchison G.
   Biological Sequence Analysis. Probabilistic models for proteins and nucleic acids.
   Cambridge University Press, 1998.
5. Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ.
   Basic local alignment search tool.
   J Mol Biol. 1990 Oct 5;215(3):403-10.
   PMID: 2231712.
6. Kriventseva EV, Fleischmann W, Zdobnov EM, Apweiler R.
   CluSTr: a database of clusters of SWISS-PROT+TrEMBL proteins.
   Nucleic Acids Res. 2001 Jan 1;29(1):33-6.
   PMID: 11125042.
7. ftp://ftp.ebi.ac.uk/pub/databases/sp_tr_nrdb/
   http://www.ebi.ac.uk/proteome/index.html
   http://www.ncbi.nlm.nih.gov/LocusLink/refseq.html
   liste des proteomes inclus dans le calcul.
8. voir p.ex
   Hartigan, John A.
   Clustering Algorithms, John Wiley & Sons, New York, NY, 1975.
9. Stijn Marinus van Dongen.
   Graph clustering by flow simulation.
   PhD thesis, University of Utrecht, May 2000.
   
10. Enright AJ, Van Dongen S, Ouzounis CA.
    An efficient algorithm for large-scale detection of protein families.
    Nucleic Acids Res. 2002 Apr 1;30(7):1575-84.
    PMID: 11917018.
11. Heger A, Holm L.
    Towards a covering set of protein family profiles.
    Prog Biophys Mol Biol 2000 Jan 1;73(5):321-337.
    
12. Gribskov M.
    Profile analysis.
    Methods Mol Biol. 1994;25:247-66.
    PMID: 8004170.
13. Ng PC, Henikoff S.
    Accounting for human polymorphisms predicted to affect protein function.
    Genome Res. 2002 Mar;12(3):436-46.
    PMID: 11875032.
14. Ng PC, Henikoff S.
    Predicting deleterious amino acid substitutions.
    Genome Res. 2002 Mar;12(3):436-46.
    PMID: 11875032.
15. Kuroda Y, Tani K, Matsuo Y, Yokoyama S.
    Automated search of natively folded protein fragments for high-throughput structure determination in structural genomics.
    Protein Sci. 2000 Dec;9(12):2313-21.
    PMID: 11206052.
16. Yona G, Levitt M.
    Towards a complete map of the protein space based on a unified sequence and structure analysis of all known proteins.
    Proc Int Conf Intell Syst Mol Biol. 2000;8:395-406.
    PMID: 10977100.
17. Apic, G., Gough, J. & Teichmann, S.A.
    An Insight into Domain Combinations.
    Bioinformatics, 17, S83-89. (2001).
    
18. Stefan Wuchty.
    Scale-Free Behavior in Protein Domain Networks.
    Molecular Biology and Evolution 18:1694-1702 (2001).