{"id":3946,"date":"2018-03-28T22:22:32","date_gmt":"2018-03-29T02:22:32","guid":{"rendered":"http:\/\/bioinfo.iric.ca\/?p=3946"},"modified":"2018-03-29T07:03:44","modified_gmt":"2018-03-29T11:03:44","slug":"comprendre-comment-kallisto-fonctionne","status":"publish","type":"post","link":"https:\/\/bioinfo.iric.ca\/fr\/comprendre-comment-kallisto-fonctionne\/","title":{"rendered":"Comprendre comment fonctionne kallisto"},"content":{"rendered":"

En 2016,\u00a0\u00a0Bray et al.<\/em><\/a>\u00a0ont introduit une nouvelle m\u00e9thode bas\u00e9e sur les k-mers pour estimer l’abondance des isoformes dans les donn\u00e9es de RNA-Seq.\u00a0 La m\u00e9thode s’appelle kallisto.\u00a0 Compar\u00e9e aux m\u00e9thodes existantes, pour une pr\u00e9cision de r\u00e9sultat comparable, kallisto est plus rapide et plus efficace en m\u00e9moire ce qui constitue une am\u00e9lioration significative.\u00a0 En fait, kallisto est capable de quantifier l’expression d’un \u00e9chantillon en l’espace d’une vingtaine de minutes au lieu de prendre plusieurs heures.\u00a0 Comme cette m\u00e9thode est l\u00e9g\u00e8re et conviviale, elle est de plus en plus utilis\u00e9e pour quantifier l’expression sous forme de TPM.\u00a0 Mais comment fonctionne-t-elle?<\/p>\n

Les m\u00e9thodes standards (pr\u00e9c\u00e9dentes) utilis\u00e9es pour la quantification de l’expression reposent sur une \u00e9tape d’alignement, c’est-\u00e0-dire sur l’alignement des reads<\/em> s\u00e9quenc\u00e9s par RNA-Seq \u00e0 un g\u00e9nome de r\u00e9f\u00e9rence.\u00a0 Les reads<\/em>\u00a0sont assign\u00e9s \u00e0 une position sur le g\u00e9nome de r\u00e9f\u00e9rence et les valeurs d’expression pour les g\u00e8nes ou les isoformes sont d\u00e9riv\u00e9es en comptant le nombre de reads<\/em> chevauchant ces derniers.<\/p>\n

L’id\u00e9e derri\u00e8re kallisto est de se baser sur un pseudo-alignement qui ne n\u00e9cessite pas d’alignement (de conna\u00eetre la position exacte d’un read<\/em> dans un transcrit) \u00e0 une s\u00e9quence.\u00a0 L’id\u00e9e est de seulement r\u00e9cup\u00e9rer le transcript d’origine potentiel. Ainsi, kallisto \u00e9vite de faire l’alignement de chaque read<\/em> \u00e0 un g\u00e9nome de r\u00e9f\u00e9rence ce qui constitue une \u00e9tape tr\u00e8s co\u00fbteuse.\u00a0 En fait, il n’utilise m\u00eame pas le g\u00e9nome de r\u00e9f\u00e9rence, seulement une collection des s\u00e9quences du transcriptome.<\/p>\n

Avant de pouvoir analyser des \u00e9chantillons s\u00e9quenc\u00e9s, il faut construire l’index kallisto.\u00a0 Kallisto construit d’abord un graphe de Bruijn (T-DBG) \u00ab\u00a0colored\u00a0\u00bb \u00e0 partir de tous les k-mers trouv\u00e9s dans le transcriptome.<\/p>\n

Chaque noeud du graphe correspond \u00e0 un k-mer (une courte s\u00e9quence de k bases) et contient l’information de son origine (de quel transcrit il peut venir) sous forme de couleur.\u00a0 Les trac\u00e9s lin\u00e9aires de m\u00eame couleur dans le graphe correspondent aux transcrits ou aux contigs.\u00a0 Une fois le T-DBG construit, kallisto conserve le lien entre chaque k-mer et son ou ses transcrit(s) d’origine de m\u00eame que sa position dans le(s) transcrit(s).\u00a0 Cette \u00e9tape n’est ex\u00e9cut\u00e9e qu’une seule fois et est d\u00e9pendante d’un fichier d’annotation qui doit \u00eatre fourni.<\/p>\n

Ensuite, pour un \u00e9chantillon s\u00e9quenc\u00e9 donn\u00e9, kallisto d\u00e9compose chaque reads<\/em> en ses k-mers et utilise ces k-mers pour trouver un chemin couvrant (path covering<\/em>)\u00a0 dans le graphe T-DBG.\u00a0 Ce chemin dans le graphe du transcriptome, o\u00f9 un chemin correspond \u00e0 un transcrit, g\u00e9n\u00e8re des classes de k-compatibilit\u00e9 pour chaque k-mer, c’est-\u00e0-dire un ensemble de transcrits d’origine potentiel associ\u00e9 \u00e0 un noeud.\u00a0 Les transcrits d’origine potentiel pour un read<\/em> (pas un k-mer ici) peuvent \u00eatre obtenus en faisant l’intersection des classes de k-compatibilit\u00e9 de ses k-mers.\u00a0 Pour que le pseudoalignement soit plus rapide, kallisto ne regarde pas les k-mers redondants puisque les k-mers voisins appartiennent souvent au m\u00eame transcrit.\u00a0 La Figure1, qui provient de l’article, r\u00e9sume les diff\u00e9rentes \u00e9tapes (petite note, je n’ai pas traduit la l\u00e9gende de la figure).<\/p>\n

 <\/p>\n

\"\"<\/p>\n

Figure1.<\/strong> Overview of kallisto. The input consists of a reference transcriptome and reads from an RNA-seq experiment. (a) An example of a read (in black) and three overlapping transcripts with exonic regions as shown. (b) An index is constructed by creating the transcriptome de Bruijn Graph (T-DBG) where nodes (v1, v2, v3, … ) are k-mers, each transcript corresponds to a colored path as shown and the path cover of the transcriptome induces a k-compatibility class for each k-mer. (c) Conceptually, the k-mers of a read are hashed (black nodes) to find the k-compatibility class of a read. (d) Skipping (black dashed lines) uses the information stored in the T-DBG to skip k-mers that are redundant because they have the same k-compatibility class. (e) The k-compatibility class of the read is determined by taking the intersection of the k-compatibility classes of its constituent k-mers.\u00a0 [Figure tir\u00e9e de\u00a0 Bray et al. Near-optimal probalistic RNA-seq quantification<\/em>, Nature Biotechnology, 2016.]<\/p>\n

Ensuite, kallisto optimise la fonction de vraisemblance du RNA-Seq en utilisant l’agorithme \u00ab\u00a0expectation-maximization\u00a0\u00bb (EM).<\/p>\n

 <\/p>\n

\"\"<\/p>\n

Dans cette fonction,\u00a0F<\/em>\u00a0est l’ensemble des fragments (ou reads<\/em>), T<\/em> est l’ensemble des transcrits, lt<\/sub><\/em> est la longueur (effective) du transcrit t<\/em> et yf,t<\/sub><\/strong> est la matrice de compatibilit\u00e9 d\u00e9finie comme 1 si le fragment f<\/em> est compatible avec t<\/em> et 0 sinon.\u00a0 Les param\u00e8tres \u03b1t<\/sub><\/em> sont les probabilit\u00e9s de s\u00e9lectionner des reads<\/em> provenant du transcrit\u00a0t<\/em>. Ces\u00a0\u03b1t<\/sub><\/em> sont les param\u00e8tres d’int\u00e9r\u00eat puisqu’ils repr\u00e9sentent l’abondance des isoformes ou l’expression relative.<\/p>\n

Pour rendre l’algorithme plus rapide, la matrice de compatibilit\u00e9 est \u00ab\u00a0factoris\u00e9e\u00a0\u00bb\u00a0 en classes d’\u00e9quivalence.\u00a0 Une classe d’\u00e9quivalence consiste en tous les reads<\/em> compatibles ayant le m\u00eame sous-ensemble de transcrits.\u00a0 L’algorithme EM est appliqu\u00e9 sur les classes d’\u00e9quivalence et non sur les reads<\/em>.\u00a0 Chaque\u00a0\u03b1t<\/em> est optimis\u00e9 pour maximiser la vraisemblance.<\/p>\n

Nous pouvons illustrer les diff\u00e9rentes \u00e9tapes impliqu\u00e9es dans kallisto avec un petit exemple.\u00a0 En partant d’un minuscule g\u00e9nome de 3 transcrits, nous assumons que notre exp\u00e9rience de RNA-Seq a produit 4 reads<\/em> comme le montre l’image suivante.<\/p>\n

 <\/p>\n

\"\"<\/p>\n

Si vous vous rappelez bien, la premi\u00e8re \u00e9tape \u00e9tait la construction du graphe T-DBG et de l’index de kallisto.\u00a0 Toutes les s\u00e9quences des transcrits sont d\u00e9compos\u00e9es en k-mers (ici k=5) pour construire le graphe de Bruijn.\u00a0 Je n’ai pas repr\u00e9sent\u00e9 tous les noeuds\/k-mers dans mon dessin mais vous pouvez imaginez des noeuds align\u00e9s (sans branchement) et des noeuds qui branchent repr\u00e9sentant diff\u00e9rents transcrits.\u00a0 \u00a0L’id\u00e9e est que chaque transcrit diff\u00e9rent produira\u00a0 un chemin diff\u00e9rent dans le graphe.\u00a0 Le brin n’est pas consid\u00e9r\u00e9 ici.<\/p>\n

 <\/p>\n

 <\/p>\n

\"\"<\/p>\n

Une fois l’index b\u00e2ti, les 4 reads<\/em> de l’\u00e9chantillon s\u00e9quenc\u00e9 peuvent \u00eatre analys\u00e9s.\u00a0 Ils sont d\u00e9compos\u00e9s en k-mers (k=5 ici aussi) et l’index pr\u00e9-construit est utilis\u00e9 pour d\u00e9terminer les classes de k-compatibilit\u00e9 de chaque k-mer.\u00a0 Ensuite, la classe de k-compatibilit\u00e9 de chaque read<\/em> est d\u00e9termin\u00e9e en regardant l’intersection.\u00a0 Par exemple, pour le read 1,\u00a0 l’intersection de toutes les classes de\u00a0k-compatibilit\u00e9 de ses k-mers sugg\u00e8re qu’il pourrait provenir du transcrit 1 ou 2.<\/p>\n

\"\"<\/p>\n

Ceci est fait pour les quatre reads<\/em> ce qui nous permet de construire la matrice de compatibilit\u00e9\u00a0\u00a0y<\/b>f,t<\/b><\/sub>\u00a0qui se trouve dans l’\u00e9quation de la function de vraisemblance pour le RNA-Seq que nous voulons maximiser. J’ai r\u00e9\u00e9crit les diff\u00e9rentes parties de l’\u00e9quation\u00a0 avec quelques explications.\u00a0 Dans notre cas, appliquer l’algorithme EM \u00e0 4 reads<\/em> n’aurait pas \u00e9t\u00e9 trop long, mais en r\u00e9alit\u00e9, l’appliquer \u00e0 des millions de reads\u00a0<\/em>serait tr\u00e8s lent.<\/p>\n

\"\"<\/p>\n

 <\/p>\n

Pour raccourcir le temps d’ex\u00e9cution, la matrice de compatibilit\u00e9\u00a0\u00a0y<\/b>f,t <\/b><\/sub>\u00a0 est transform\u00e9e en ses classes \u00e9quivalentes et un compte est calcul\u00e9 pour chacune des classes (combien de reads<\/em>\u00a0sont repr\u00e9sent\u00e9s par cette classe).\u00a0 L’algorithme EM utilise cette information pour maximiser la nouvelle, mais \u00e9quivalente, fonction de vraisemblance pour le RNA-Seq afin d’optimiser les\u00a0\u03b1t<\/sub><\/em> , qui sont les valeurs que nous voulons d\u00e9terminer.<\/p>\n

\"\"<\/p>\n

 <\/p>\n

L’algorithme EM changera\u00a0\u00a0\u03b1t\u00a0 <\/sub><\/em>pour maximiser\u00a0L(\u03b1)<\/em>, i.e. il essaiera diff\u00e9rentes valeurs de probabilit\u00e9s pour chaque transcrit dans le but d’avoir la plus grande vraisemblance possible. Et il fait cela intelligemment, d’une fa\u00e7on qui lui permet de converger.\u00a0 Je n’ai pas roul\u00e9 l’algorithme EM, mais pour se donner une id\u00e9e intuitive, regardons un petit exemple.\u00a0 Dans cet exemple, j’ai initialis\u00e9 les trois probabilit\u00e9s\u00a0\u03b1t<\/sub><\/em>\u00a0(i.e. probabilit\u00e9 de s\u00e9lectionner des reads<\/em> provenant de chacun des transcrits) \u00e0 une valeur de to\u00a0 0.33 pour les 3, ce qui donne une vraisemblance,\u00a0L(\u03b1),<\/em> de 8.4e-05.<\/p>\n

Si je change les valeurs d’abondance pour\u00a0 [0.98, 0.01, 0.01]\u00a0 (plus de chance de venir du transcrit 1) au lieu de\u00a0 \u00a0[0.33, 0.33, 0.33], j’obtiens maintenant une\u00a0L(\u03b1)<\/em> de 4.2e-4, ce qui est sup\u00e9rieur \u00e0 8.4e-05.\u00a0 \u00a0[0.05, 0.05, 0.9] donne\u00a0 2.2e-06.\u00a0 Vous comprenez l’id\u00e9e….<\/p>\n

[0.33, 0.33, 0.33] ==>\u00a0 8.4e-05<\/span><\/p>\n

[0.45, 0.15, 0.4]\u00a0 \u00a0==> 0.00011<\/span><\/p>\n

[0.98, 0.01, 0.01] ==> 0.00042<\/span><\/p>\n

[0.9, 0.05, 0.05]\u00a0 ==> 0.00037<\/span><\/p>\n

[0.05, 0.9, 0.05]\u00a0 ==> 1.5e-05<\/span><\/p>\n

[0.05, 0.05, 0.9]\u00a0 ==> 2.2e-06<\/span><\/p>\n

[0.15, 0.45, 0.4]\u00a0 == >3.3e-05<\/span><\/p>\n

En consid\u00e9rant cet exemple de 4 reads, il est probable que les reads proviennent du transcript 1 qui serait le transcrit le plus abondant des trois transcrits.\u00a0 On pourrait donc dire que les transcrits 1,2 et 3 ont respectivement une abondance de 0.98, 0.01, et 0.01.\u00a0 Dans kallisto,\u00a0 l’algorithme EM s’arr\u00eate lorsque pour chaque transcrit\u00a0t<\/em>, \u03b1t<\/sub>N<\/em> > 0.01, o\u00f9\u00a0N<\/em> est le nombre total de reads<\/em>, change de moins de\u00a0 1%.<\/p>\n

Quoique ce soit un article tr\u00e8s int\u00e9ressant, l’article d\u00e9crivant kallisto n’est pas super facile \u00e0 comprendre. J’esp\u00e8re avoir un peu d\u00e9mystifi\u00e9 comment fonctionne cet outil de plus en plus utilis\u00e9.<\/p>\n","protected":false},"excerpt":{"rendered":"

En 2016,\u00a0\u00a0Bray et al.\u00a0ont introduit une nouvelle m\u00e9thode bas\u00e9e sur les k-mers pour estimer l’abondance des isoformes dans les donn\u00e9es de RNA-Seq.\u00a0 La m\u00e9thode s’appelle kallisto.\u00a0 Compar\u00e9e aux m\u00e9thodes existantes, pour une pr\u00e9cision de r\u00e9sultat comparable, kallisto est plus rapide et plus efficace en m\u00e9moire ce qui constitue une am\u00e9lioration significative.\u00a0 En fait, kallisto est capable de quantifier l’expression d’un \u00e9chantillon en l’espace d’une vingtaine de minutes au lieu de prendre plusieurs heures.\u00a0 Comme cette m\u00e9thode est l\u00e9g\u00e8re et conviviale, […]<\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"image","meta":{"jetpack_post_was_ever_published":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[161,69,41],"tags":[],"class_list":["post-3946","post","type-post","status-publish","format-image","hentry","category-analyse-de-donnees-fr","category-analyse-de-donnees","category-bioinformatique","post_format-post-format-image"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts\/3946","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/comments?post=3946"}],"version-history":[{"count":15,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts\/3946\/revisions"}],"predecessor-version":[{"id":3965,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/posts\/3946\/revisions\/3965"}],"wp:attachment":[{"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/media?parent=3946"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/categories?post=3946"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bioinfo.iric.ca\/fr\/wp-json\/wp\/v2\/tags?post=3946"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}