Apprentissage de modèles à base de règles pour laprédiction de la résistance aux antibiotiques
Alexandre DrouinDépartement d’informatique et de génie logiciel, Université Laval
Département de médecine moléculaire, Université Laval

Sainte-Foy, Québec
17 mars 2017

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 2017

1 / 38Plan
1IntroductionRésistance aux antibiotiques
Un problème d’apprentissage automatique2

Méthode
Représentation des génomes
L’algorithme Set Covering Machine3

Résultats

4

Nouveaux résultats

5

Conclusion

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 2017

2 / 38

Introduction

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 20173 / 38Qu’est-ce que la résistance aux antibiotiques ?
État dans lequel une bactérie est capable de survivre en présence d’unantibiotiqueGénéralement atteint via des modifications génomiques :I

ex. : mutations, transfert horizontal de gènes

Credits: Harvard Medical School (Kishony Lab) and Technion, 2016
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 20174 / 38Qu’est-ce que la résistance aux antibiotiques ?

Source : http://www.med.uottawa.ca/sim/data/AntibioticResistance_e.htm

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 2017

5 / 38

Pourquoi prédire la résistance aux antibiotiques ?

Profilage rapide des antibiotiques pouvant être utilisés pour traiter
une infection
Plan de traitement personnalisé pour chaque patient,
raccourcir/éviter la thérapie empirique (médecine personnalisée)
Extraire des nouvelles connaissances biologiques des modèles obtenus

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 2017

6 / 38

Pourquoi prédire la résistance aux antibiotiques ?

Profilage rapide des antibiotiques pouvant être utilisés pour traiter
une infection
Plan de traitement personnalisé pour chaque patient,
raccourcir/éviter la thérapie empirique (médecine personnalisée)
Extraire des nouvelles connaissances biologiques des modèles obtenus

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 2017

6 / 38

Pourquoi prédire la résistance aux antibiotiques ?

Profilage rapide des antibiotiques pouvant être utilisés pour traiter
une infection
Plan de traitement personnalisé pour chaque patient,
raccourcir/éviter la thérapie empirique (médecine personnalisée)
Extraire des nouvelles connaissances biologiques des modèles obtenus

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 2017

6 / 38

“Genome-wide association study” bactérien
Sensitive

ResistantvsLearning algorithm?

Alexandre Drouin (Université Laval)

ModelRésistance aux antibiotiques

Sensitive

17 mars 20177 / 38GénomiqueÉtude de l’ensemble de l’ADN d’un ou plusieurs individus
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 20178 / 38

Formalisation : un problème d’apprentissage superviséEnsemble de donnéesdef

S = {(x1 , y1 ), (x2 , y2 ), ..., (xm , ym ))} ⇠ D m
def

x 2 X = {A, C , G , T }⇤ est un génome
y 2 {0, 1} est une étiquette (résistant, sensible)
D est une distribution inconnue qui génère les données

Objectif1
2

Définir une représentation vectorielle des génomes: X ! Rd

Trouver un prédicteur h : Rd ! {0, 1} qui a une bonne performancede généralisation, c.-à-d. qui minimise :defR(h) =

Alexandre Drouin (Université Laval)

Pr [h( (x)) 6= y ](x,y )⇠DRésistance aux antibiotiques

17 mars 2017

9 / 38

Formalisation : un problème d’apprentissage superviséEnsemble de donnéesdef

S = {(x1 , y1 ), (x2 , y2 ), ..., (xm , ym ))} ⇠ D m
def

x 2 X = {A, C , G , T }⇤ est un génome
y 2 {0, 1} est une étiquette (résistant, sensible)
D est une distribution inconnue qui génère les données

Objectif1
2

Définir une représentation vectorielle des génomes: X ! Rd

Trouver un prédicteur h : Rd ! {0, 1} qui a une bonne performancede généralisation, c.-à-d. qui minimise :defR(h) =

Alexandre Drouin (Université Laval)

Pr [h( (x)) 6= y ](x,y )⇠DRésistance aux antibiotiques

17 mars 2017

9 / 38

Formalisation : un problème d’apprentissage superviséEnsemble de donnéesdef

S = {(x1 , y1 ), (x2 , y2 ), ..., (xm , ym ))} ⇠ D m
def

x 2 X = {A, C , G , T }⇤ est un génome
y 2 {0, 1} est une étiquette (résistant, sensible)
D est une distribution inconnue qui génère les données

Objectif1
2

Définir une représentation vectorielle des génomes: X ! Rd

Trouver un prédicteur h : Rd ! {0, 1} qui a une bonne performancede généralisation, c.-à-d. qui minimise :defR(h) =

Alexandre Drouin (Université Laval)

Pr [h( (x)) 6= y ](x,y )⇠DRésistance aux antibiotiques

17 mars 2017

9 / 38

Les modèles doivent être interprétables

Réseau de neurones

Support Vector Machine

r1
True

False

r2
True

False

-

+

Arbre de décision
r1
True
r2
True
-

Les modèles doivent être interprétables :False

Validation et acceptation

r3
True

False
+

+

Alexandre Drouin (Université Laval)

False
-

Permet de détecter les biais

Résistance aux antibiotiques

17 mars 201710 / 38

Les modèles doivent être parcimonieux

Source : https://blog.bigml.com/2013/05/07/a-sunburst-of-insight/

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201711 / 38

Attention au surapprentissage
Représentation de très haute dimensionnalité (x)+Peu d’exemples d’apprentissage (m ⌧ d)=
Risque de surapprentissage !

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201712 / 38

Méthode

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201713 / 38

Représentation des génomes : profils de k-mers
Definition
k-mer : une séquence de k nucléotides
Note : Il y a 4k séquences possibles

Definition
K : l’ensemble de tous les k-mers qui sont dans au moins 1 génome de S
Note : |K| peut QUAND MÊME être ÉNORME (dizaines de millions)
Nous représentons chaque génome x par un vecteur binaire (x) 2 B|K| ,tel que(
1, si kj 2 K est une sous-séquence de x(x)j =
0, sinon.
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201714 / 38

Représentation des génomes : profils de k-mers
Definition
k-mer : une séquence de k nucléotides
Note : Il y a 4k séquences possibles (k = 31, 431 ⇡ 4 · 1018 )Definition
K : l’ensemble de tous les k-mers qui sont dans au moins 1 génome de S
Note : |K| peut QUAND MÊME être ÉNORME (dizaines de millions)
Nous représentons chaque génome x par un vecteur binaire (x) 2 B|K| ,tel que(
1, si kj 2 K est une sous-séquence de x(x)j =
0, sinon.
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201714 / 38

Représentation des génomes : profils de k-mers
Definition
k-mer : une séquence de k nucléotides
Note : Il y a 4k séquences possibles (k = 31, 431 ⇡ 4 · 1018 )Definition
K : l’ensemble de tous les k-mers qui sont dans au moins 1 génome de S
Note : |K| peut QUAND MÊME être ÉNORME (dizaines de millions)
Nous représentons chaque génome x par un vecteur binaire (x) 2 B|K| ,tel que(
1, si kj 2 K est une sous-séquence de x(x)j =
0, sinon.
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201714 / 38

Représentation des génomes : profils de k-mers
Definition
k-mer : une séquence de k nucléotides
Note : Il y a 4k séquences possibles (k = 31, 431 ⇡ 4 · 1018 )Definition
K : l’ensemble de tous les k-mers qui sont dans au moins 1 génome de S
Note : |K| peut QUAND MÊME être ÉNORME (dizaines de millions)
Nous représentons chaque génome x par un vecteur binaire (x) 2 B|K| ,tel que(
1, si kj 2 K est une sous-séquence de x(x)j =
0, sinon.
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201714 / 38

Représentation des génomes (exemple)

Représenta&on*“bagXofXwords”*{

AGATAG* AGAACA* ATAGAA* CCGGCT*AACAGC* TAGAAC*

TTTCGG*AAATAC*

1*

0*

1*

1*

0*

1*

1*

0*

1*

1*

TTTCGG*

AGATAG*GATAGA*CGATGA*

AACAGC*ATAGAA*

CCGGCT*TAGAAC*GAACAG*(x) =CAGATA*x = CAGATAGAACAGC*

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

1*0*
AAATAC*{AGAACA*K=

CAGATA* GATAGA* GAACAG* CGATGA*

17 mars 201715 / 38

Exemple : taille des ensembles de données

a)

1e7

4.0

k-mersk-mers(10 millions)

3.5
3.0
2.5
2.0
1.5
1.0
0.5
0.0
0

1000

2000

3000

4000

5000

Genomes
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201716 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2002)
Entrée : Un ensemble de règles à valeur booléenne (présence/absencede k-mers) et un ensemble de données (exemples, étiquettes)(x)

Objective : Trouver la plus courte conjonction (ET-logique) ou
disjonction (OU-logique) de règles qui prédit le plus précisément
possible les étiquettes

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201717 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2002)
Entrée : Un ensemble de règles à valeur booléenne (présence/absencede k-mers) et un ensemble de données (exemples, étiquettes)(x)

Objective : Trouver la plus courte conjonction (ET-logique) ou
disjonction (OU-logique) de règles qui prédit le plus précisément
possible les étiquettes

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201717 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2002)
Entrée : Un ensemble de règles à valeur booléenne (présence/absencede k-mers) et un ensemble de données (exemples, étiquettes)(x)

Objective : Trouver la plus courte conjonction (ET-logique) ou
disjonction (OU-logique) de règles qui prédit le plus précisément
possible les étiquettes(x)Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201717 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2003)
ObjectifÉtant donné un ensemble de règles à valeur booléenne R, trouver leprédicteur qui minimise le risque empirique :
def

RS =

m
X
1
i=1

m

I [h( (xi )) 6= yi ],en utilisant le plus petit sous-ensemble de R.
Ce problème est NP-difficile (minimum set cover)
Solution : Utilisé un algorithme glouton inspiré de celui de Chvátal(1979)

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201718 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2003)
ObjectifÉtant donné un ensemble de règles à valeur booléenne R, trouver leprédicteur qui minimise le risque empirique :
def

RS =

m
X
1
i=1

m

I [h( (xi )) 6= yi ],en utilisant le plus petit sous-ensemble de R.
Ce problème est NP-difficile (minimum set cover)
Solution : Utilisé un algorithme glouton inspiré de celui de Chvátal(1979)

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201718 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2003)
Algorithme glouton (Conjonction)
1

Commencer avec une conjonction vide2

Calculer un score d’utilité pour chaque règle de R3
4
5Sélectionner la règle avec la plus grande utilité (r ? )Supprimer tous les exemples pour lesquels r ? ( (x)) = Faux
Aller à l’étape 2 jusqu’à ce que l’une de ces conditions soit satisfaite :I
I

Tous les exemples négatifs ont été retiréss itérations complétées (hyperparamètre)

Justification de l’étape 4
La conjonction prend la valeur Faux pour tout exemple pour qui au
moins une règle retourne Faux.
Inutile de considérer ces exemples dans les itérations futures
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201719 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2003)
Algorithme glouton (Conjonction)
1

Commencer avec une conjonction vide2

Calculer un score d’utilité pour chaque règle de R3
4
5Sélectionner la règle avec la plus grande utilité (r ? )Supprimer tous les exemples pour lesquels r ? ( (x)) = Faux
Aller à l’étape 2 jusqu’à ce que l’une de ces conditions soit satisfaite :I
I

Tous les exemples négatifs ont été retiréss itérations complétées (hyperparamètre)

Justification de l’étape 4
La conjonction prend la valeur Faux pour tout exemple pour qui au
moins une règle retourne Faux.
Inutile de considérer ces exemples dans les itérations futures
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201719 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2003)
Algorithme glouton (Conjonction)
1

Commencer avec une conjonction vide2

Calculer un score d’utilité pour chaque règle de R3
4
5Sélectionner la règle avec la plus grande utilité (r ? )Supprimer tous les exemples pour lesquels r ? ( (x)) = Faux
Aller à l’étape 2 jusqu’à ce que l’une de ces conditions soit satisfaite :I
I

Tous les exemples négatifs ont été retiréss itérations complétées (hyperparamètre)

Justification de l’étape 4
La conjonction prend la valeur Faux pour tout exemple pour qui au
moins une règle retourne Faux.
Inutile de considérer ces exemples dans les itérations futures
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201719 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2003)
Algorithme glouton (Conjonction)
1

Commencer avec une conjonction vide2

Calculer un score d’utilité pour chaque règle de R3
4
5Sélectionner la règle avec la plus grande utilité (r ? )Supprimer tous les exemples pour lesquels r ? ( (x)) = Faux
Aller à l’étape 2 jusqu’à ce que l’une de ces conditions soit satisfaite :I
I

Tous les exemples négatifs ont été retiréss itérations complétées (hyperparamètre)

Justification de l’étape 4
La conjonction prend la valeur Faux pour tout exemple pour qui au
moins une règle retourne Faux.
Inutile de considérer ces exemples dans les itérations futures
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201719 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2003)
Algorithme glouton (Conjonction)
1

Commencer avec une conjonction vide2

Calculer un score d’utilité pour chaque règle de R3
4
5Sélectionner la règle avec la plus grande utilité (r ? )Supprimer tous les exemples pour lesquels r ? ( (x)) = Faux
Aller à l’étape 2 jusqu’à ce que l’une de ces conditions soit satisfaite :I
I

Tous les exemples négatifs ont été retiréss itérations complétées (hyperparamètre)

Justification de l’étape 4
La conjonction prend la valeur Faux pour tout exemple pour qui au
moins une règle retourne Faux.
Inutile de considérer ces exemples dans les itérations futures
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201719 / 38

L’algorithme Set Covering Machine (Marchand and Shawe-Taylor, 2003)
Algorithme glouton (Conjonction)
1

Commencer avec une conjonction vide2

Calculer un score d’utilité pour chaque règle de R3
4
5Sélectionner la règle avec la plus grande utilité (r ? )Supprimer tous les exemples pour lesquels r ? ( (x)) = Faux
Aller à l’étape 2 jusqu’à ce que l’une de ces conditions soit satisfaite :I
I

Tous les exemples négatifs ont été retiréss itérations complétées (hyperparamètre)

Justification de l’étape 4
La conjonction prend la valeur Faux pour tout exemple pour qui au
moins une règle retourne Faux.
Inutile de considérer ces exemples dans les itérations futures
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201719 / 38

The Set Covering Machine (Marchand and Shawe-Taylor, 2003)
Score d’utilité
Pour toute règle ri , l’utilité est donnée par :def

Ui = Ni p · Pi ,où Ni est le nombre d’exemples négatifs correctement classifiés par ri ,Pi est le nombre d’exemples positifs mal classifiés par ri ,p est un hyperparamètre.

Gros volumes de données
La complexité de calcul de SCM est O(m · |R| · s), donc linéaire en
fonction du nombre d’exemples et de règles
Implémentation out-of-core : les données sont analysées par blocs

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201720 / 38

The Set Covering Machine (Marchand and Shawe-Taylor, 2003)
Score d’utilité
Pour toute règle ri , l’utilité est donnée par :def

Ui = Ni p · Pi ,où Ni est le nombre d’exemples négatifs correctement classifiés par ri ,Pi est le nombre d’exemples positifs mal classifiés par ri ,p est un hyperparamètre.

Gros volumes de données
La complexité de calcul de SCM est O(m · |R| · s), donc linéaire en
fonction du nombre d’exemples et de règles
Implémentation out-of-core : les données sont analysées par blocs

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201720 / 38

The Set Covering Machine (Marchand and Shawe-Taylor, 2003)
Score d’utilité
Pour toute règle ri , l’utilité est donnée par :def

Ui = Ni p · Pi ,où Ni est le nombre d’exemples négatifs correctement classifiés par ri ,Pi est le nombre d’exemples positifs mal classifiés par ri ,p est un hyperparamètre.

Gros volumes de données
La complexité de calcul de SCM est O(m · |R| · s), donc linéaire en
fonction du nombre d’exemples et de règles
Implémentation out-of-core : les données sont analysées par blocs

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201720 / 38

Kover : une implémentation out-of-core pour la génomique
1) Représentation compresséeFictive 3-bit integers

Positive example
Negative example

1

0

0

0

1

1

1

1

0

0

0

0

1

1

1

0

1

0

1

1

0

0

0

0

1

0

1

1

1

0

1

1

1

1

1

1

1

0

0

1

0

1

1

1

0

0

0

1

1

1

0

1

0

1

0

1

0

1

0

1

0
0
0

0
1
0

0
1
0

1
1
1

1
0
0

1
1
1

1
0
1

0
1
1

0
1
0

1
0
0

1
1
1

1
1
0

1
1
1

1
0
0

1
0
1

1
0
0

0
1
1

0
1
0

1
1
1

=

Genomes

Genomesk-mersGenomesk-mers100k-mers
4

0

2

2

7

4 7

5

3

2

4

7

6

7

5

5 4

3

2

7

+ stored in HDF5 with gzip compression

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201721 / 38

Kover : une implémentation out-of-core pour la génomique
1) Représentation compresséeFictive 3-bit integers

Positive example
Negative example

0

0

0

1

1

1

1

0

0

0

0

1

1

1

0

1

0

1

1

0

0

0

0

1

0

1

1

1

0

1

1

1

1

1

1

1

0

0

1

0

1

1

1

0

0

0

1

1

1

0

1

0

1

0

1

0

1

0

1

0
0
0

0
1
0

0
1
0

1
1
1

1
0
0

1
1
1

1
0
1

0
1
1

0
1
0

1
0
0

1
1
1

1
1
0

1
1
1

1
0
0

1
0
1

1
0
0

0
1
1

0
1
0

1
1
1

=

Genomes

Genomesk-mers1

Genomesk-mers100k-mers
4

0

2

2

7

4 7

5

3

2

4

7

6

7

5

5 4

3

2

7

+ stored in HDF5 with gzip compression2) Apprentissage à partir des données compresséesAlexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201721 / 38

Kover : une implémentation out-of-core pour la génomique
1) Représentation compresséeFictive 3-bit integers

Positive example
Negative example

0

0

0

1

1

1

1

0

0

0

0

1

1

1

0

1

0

1

1

0

0

0

0

1

0

1

1

1

0

1

1

1

1

1

1

1

0

0

1

0

1

1

1

0

0

0

1

1

1

0

1

0

1

0

1

0

1

0

1

0
0
0

0
1
0

0
1
0

1
1
1

1
0
0

1
1
1

1
0
1

0
1
1

0
1
0

1
0
0

1
1
1

1
1
0

1
1
1

1
0
0

1
0
1

1
0
0

0
1
1

0
1
0

1
1
1

=

Genomes

Genomesk-mers1

Genomesk-mers100k-mers
4

0

2

2

7

4 7

5

3

2

4

7

6

7

5

5 4

3

2

7

+ stored in HDF5 with gzip compression2) Apprentissage à partir des données compresséesAlexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201721 / 38

Pouvons nous espérer une bonne performance degénéralisation ?
Nous pouvons borner le risque d’un prédicteur en fonction de sa
performance sur les données d’entraı̂nement. Le terme suivant borne lerisque de toute conjonction h de règles dans R avec probabilité 1.

Borne du rasoir d’Occam
1

def

✏=

m

 ✓ ◆
✓
◆
m
2 · 4k
ln
+ ln
r
r
|h|

ln(⇣(r ) · ⇣(|h|) · ) ,où r est le nombre d’erreurs sur l’ensemble d’entraı̂nement,|h| est le nombre de règles dans le modèle,P⇣ est une fonction telle que b2N ⇣(b)  1

Le terme combinatoire domine cette borne, même pour les prédicteurs
faisant peu d’erreurs
La borne suggère une mauvaise performance de généralisation.
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201722 / 38

Pouvons nous espérer une bonne performance degénéralisation ?
Nous pouvons borner le risque d’un prédicteur en fonction de sa
performance sur les données d’entraı̂nement. Le terme suivant borne lerisque de toute conjonction h de règles dans R avec probabilité 1.

Borne du rasoir d’Occam
1

def

✏=

m

 ✓ ◆
✓
◆
m
2 · 4k
ln
+ ln
r
r
|h|

ln(⇣(r ) · ⇣(|h|) · ) ,où r est le nombre d’erreurs sur l’ensemble d’entraı̂nement,|h| est le nombre de règles dans le modèle,P⇣ est une fonction telle que b2N ⇣(b)  1

Le terme combinatoire domine cette borne, même pour les prédicteurs
faisant peu d’erreurs
La borne suggère une mauvaise performance de généralisation.
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201722 / 38

Pouvons nous espérer une bonne performance degénéralisation ?
Nous pouvons borner le risque d’un prédicteur en fonction de sa
performance sur les données d’entraı̂nement. Le terme suivant borne lerisque de toute conjonction h de règles dans R avec probabilité 1.

Borne du rasoir d’Occam
1

def

✏=

m

 ✓ ◆
✓
◆
m
2 · 4k
ln
+ ln
r
r
|h|

ln(⇣(r ) · ⇣(|h|) · ) ,où r est le nombre d’erreurs sur l’ensemble d’entraı̂nement,|h| est le nombre de règles dans le modèle,P⇣ est une fonction telle que b2N ⇣(b)  1

Le terme combinatoire domine cette borne, même pour les prédicteurs
faisant peu d’erreurs
La borne suggère une mauvaise performance de généralisation.
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201722 / 38

Pouvons nous espérer une bonne performance degénéralisation ?
Nous pouvons borner le risque d’un prédicteur en fonction de sa
performance sur les données d’entraı̂nement. Le terme suivant borne lerisque de toute conjonction h de règles dans R avec probabilité 1.

Borne du rasoir d’Occam
1

def

✏=

m

 ✓ ◆
✓
◆
m
2 · 4k
ln
+ ln
r
r
|h|

ln(⇣(r ) · ⇣(|h|) · ) ,où r est le nombre d’erreurs sur l’ensemble d’entraı̂nement,|h| est le nombre de règles dans le modèle,P⇣ est une fonction telle que b2N ⇣(b)  1

Le terme combinatoire domine cette borne, même pour les prédicteurs
faisant peu d’erreurs
La borne suggère une mauvaise performance de généralisation.
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201722 / 38

Pouvons nous espérer une bonne performance degénéralisation ?
Dans le contexte de la compression d’échantillons, le prédicteur h est
spécifié en utilisant un petit ensemble d’exemples d’entraı̂nement (Zi ) :Borne de compression d’échantillons
def

✏=

m

1
|h|

2

✓

◆
✓
◆
m
m
|h|
4ln
+ ln
r
|h|
r
+

X

x2Zi

ln(2 · |x|)où r est le nombre d’erreurs faites sur S \ Zi .

3ln(⇣(|h|) · ⇣(r ) · )5 ,La borne ne dépend plus de kConsidérer des représentations exponentiellement plus complexes,sans pénalité au niveau de la généralisation
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201723 / 38

Pouvons nous espérer une bonne performance degénéralisation ?
Dans le contexte de la compression d’échantillons, le prédicteur h est
spécifié en utilisant un petit ensemble d’exemples d’entraı̂nement (Zi ) :Borne de compression d’échantillons
def

✏=

m

1
|h|

2

✓

◆
✓
◆
m
m
|h|
4ln
+ ln
r
|h|
r
+

X

x2Zi

ln(2 · |x|)où r est le nombre d’erreurs faites sur S \ Zi .

3ln(⇣(|h|) · ⇣(r ) · )5 ,La borne ne dépend plus de kConsidérer des représentations exponentiellement plus complexes,sans pénalité au niveau de la généralisation
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201723 / 38

Pouvons nous espérer une bonne performance degénéralisation ?
Dans le contexte de la compression d’échantillons, le prédicteur h est
spécifié en utilisant un petit ensemble d’exemples d’entraı̂nement (Zi ) :Borne de compression d’échantillons
def

✏=

m

1
|h|

2

✓

◆
✓
◆
m
m
|h|
4ln
+ ln
r
|h|
r
+

X

x2Zi

ln(2 · |x|)où r est le nombre d’erreurs faites sur S \ Zi .

3ln(⇣(|h|) · ⇣(r ) · )5 ,La borne ne dépend plus de kConsidérer des représentations exponentiellement plus complexes,sans pénalité au niveau de la généralisation
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201723 / 38

Pouvons nous espérer une bonne performance degénéralisation ?
Dans le contexte de la compression d’échantillons, le prédicteur h est
spécifié en utilisant un petit ensemble d’exemples d’entraı̂nement (Zi ) :Borne de compression d’échantillons
def

✏=

m

1
|h|

2

✓

◆
✓
◆
m
m
|h|
4ln
+ ln
r
|h|
r
+

X

x2Zi

ln(2 · |x|)où r est le nombre d’erreurs faites sur S \ Zi .

3ln(⇣(|h|) · ⇣(r ) · )5 ,La borne ne dépend plus de kConsidérer des représentations exponentiellement plus complexes,sans pénalité au niveau de la généralisation
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201723 / 38Résultats

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201724 / 38

La base de données PATRIC (Wattam et al, 2013)
a)

1e7

4.0

k-mersk-mers(10 millions)

3.5
3.0
2.5
2.0
1.5
1.0
0.5
0.0
0

1000

2000

3000

4000

5000

Genomes

5 espèces bactériennes, 36 ensembles de données, ⇠ 12000 génomes
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201725 / 38

La base de données PATRIC (Wattam et al, 2013)

Accuracy
1.0

SCM
Accuracy

0.8

0.6

0.4

0.2

0.0
0.0

0.2

0.4

0.6

0.8

1.0

Baseline: most abundant classe)

Taux de bonnes prédictions
Alexandre Drouin (Université Laval)

90% pour 26/36 ensembles de donnéesRésistance aux antibiotiques

17 mars 201725 / 38

La base de données PATRIC (Wattam et al, 2013)

1.00
0.95

Accuracy

0.90
0.85
0.80
0.75
0.70
0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0
1e7
k-mersk-mers(10 millions)

Le taux de bonnes prédictions ne dépend pas du nombre de k-mers
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201725 / 38

La base de données PATRIC (Wattam et al, 2013)

1200

Learning time (s)

1000
800
600
400
200
0
0

1000

2000

3000

4000

5000

Genomes

Temps de calcul linéaire en fonction du nombre de génomes (8 sec. - 18 min.)Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201725 / 38

Comparaison à d’autres algorithmes
Nous avons comparé SCM à :Arbres de décision (CART)r1

SVM parcimonieux(L -SVM)
True False1
SVM denses (Lr 2 -SVM)2

Falsepolynomial (PolySVM)
SVM avec True
noyau
-

+

r1
True

False

r2
True
-

r3
True

False
+

Alexandre Drouin (Université Laval)

+

False
-

Résistance aux antibiotiques

17 mars 201726 / 38

Comparaison à d’autres algorithmes
Nous avons comparé SCM à :Arbres de décision (CART) +2

r1

SVM parcimonieux(L -SVM) +True False1
SVM denses (Lr 2 -SVM)- +2

2

sélection d’attributs
2sélection d’attributs

sélection d’attributs

Falsepolynomial (PolySVM)
SVM avec True
noyau
-

+

r1
True

False

r2
True
-

r3
True

False
+

Alexandre Drouin (Université Laval)

+

False
-

Résistance aux antibiotiques

17 mars 201726 / 38

Comparaison à d’autres algorithmes
DatasetC. difficile
Azithromycin
Ceftriaxone
Clarithromycin
Clindamycin
Moxifloxacin
M. tuberculosis
Ethambutol
Isoniazid
Pyrazinamide
Rifampicin
Streptomycin
P. aeruginosaAmikacin
Doripenem
Levofloxacin
Meropenem
S. pneumoniae
Benzylpenicillin
Erythromycin
Tetracycline

SCM

2+ CART

2+ L1SVM

2+ L2SVM
6

PolySVM

0.030 (3.3)
0.073 (2.6)
0.011 (3.0)
0.021 (1.4)
0.020 (1.0)

0.086 (7.2)
0.117 (6.8)
0.070 (8.0)
0.011 (2.0)
0.020 (1.3)

0.064 (20326.0)
0.087 (8114.1)
0.062 (36686.1)
0.009 (598.2)
0.020 (25.6)

0.056 (10 )0.102 (106 )0.059 (106 )0.021 (106 )0.048 (106 )0.048 (all)0.076 (all)0.053 (all)0.039 (all)0.048 (all)0.179 (1.4)
0.021 (1.0)
0.318 (3.1)
0.031 (1.4)
0.050 (1.0)

0.185 (1.9)
0.021 (1.1)
0.371 (4.4)
0.031 (1.5)
0.052 (1.6)

0.153 (201.3)
0.017 (104.7)
0.353 (481.2)
0.031 (130.0)
0.043 (98.8)

0.221 (106 )0.125 (106 )0.342 (106 )0.196 (106 )0.137 (106 )0.221 (all)0.119 (all)0.382 (all)0.204 (all)0.148 (all)0.175 (4.9)
0.270 (1.4)
0.072 (1.2)
0.267 (1.6)

0.206 (14.1)
0.261 (1.9)
0.076 (1.0)
0.261 (1.0)

0.187 (11514.6)
0.261 (950.0)
0.085 (148.9)
0.328 (5368.5)

0.164 (106 )0.275 (106 )0.212 (106 )0.327 (106 )0.179 (all)0.281 (all)0.225 (all)0.331 (all)0.013 (1.1)
0.037 (2.0)
0.031 (1.1)

0.012 (2.3)
0.047 (3.8)
0.029 (1.2)

0.011 (124.9)
0.041 (328.8)
0.032 (1108.5)

0.013 (106 )0.042 (106 )0.037 (106 )0.015 (all)0.047 (all)0.037 (all)

SCM apprend les modèles les plus parcimonieux
Pour la plupart des datasets, SCM généralise bien et surpasse le baseline
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201727 / 38

Comparaison à d’autres algorithmes
DatasetC. difficile
Azithromycin
Ceftriaxone
Clarithromycin
Clindamycin
Moxifloxacin
M. tuberculosis
Ethambutol
Isoniazid
Pyrazinamide
Rifampicin
Streptomycin
P. aeruginosaAmikacin
Doripenem
Levofloxacin
Meropenem
S. pneumoniae
Benzylpenicillin
Erythromycin
Tetracycline

SCM

2+ CART

2+ L1SVM

2+ L2SVM
6

PolySVM

0.030 (3.3)
0.073 (2.6)
0.011 (3.0)
0.021 (1.4)
0.020 (1.0)

0.086 (7.2)
0.117 (6.8)
0.070 (8.0)
0.011 (2.0)
0.020 (1.3)

0.064 (20326.0)
0.087 (8114.1)
0.062 (36686.1)
0.009 (598.2)
0.020 (25.6)

0.056 (10 )0.102 (106 )0.059 (106 )0.021 (106 )0.048 (106 )0.048 (all)0.076 (all)0.053 (all)0.039 (all)0.048 (all)0.179 (1.4)
0.021 (1.0)
0.318 (3.1)
0.031 (1.4)
0.050 (1.0)

0.185 (1.9)
0.021 (1.1)
0.371 (4.4)
0.031 (1.5)
0.052 (1.6)

0.153 (201.3)
0.017 (104.7)
0.353 (481.2)
0.031 (130.0)
0.043 (98.8)

0.221 (106 )0.125 (106 )0.342 (106 )0.196 (106 )0.137 (106 )0.221 (all)0.119 (all)0.382 (all)0.204 (all)0.148 (all)0.175 (4.9)
0.270 (1.4)
0.072 (1.2)
0.267 (1.6)

0.206 (14.1)
0.261 (1.9)
0.076 (1.0)
0.261 (1.0)

0.187 (11514.6)
0.261 (950.0)
0.085 (148.9)
0.328 (5368.5)

0.164 (106 )0.275 (106 )0.212 (106 )0.327 (106 )0.179 (all)0.281 (all)0.225 (all)0.331 (all)0.013 (1.1)
0.037 (2.0)
0.031 (1.1)

0.012 (2.3)
0.047 (3.8)
0.029 (1.2)

0.011 (124.9)
0.041 (328.8)
0.032 (1108.5)

0.013 (106 )0.042 (106 )0.037 (106 )0.015 (all)0.047 (all)0.037 (all)

SCM apprend les modèles les plus parcimonieux
Pour la plupart des datasets, SCM généralise bien et surpasse le baseline
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201727 / 38

Comparaison à d’autres algorithmes
DatasetC. difficile
Azithromycin
Ceftriaxone
Clarithromycin
Clindamycin
Moxifloxacin
M. tuberculosis
Ethambutol
Isoniazid
Pyrazinamide
Rifampicin
Streptomycin
P. aeruginosaAmikacin
Doripenem
Levofloxacin
Meropenem
S. pneumoniae
Benzylpenicillin
Erythromycin
Tetracycline

SCM

2+ CART

2+ L1SVM

2+ L2SVM
6

PolySVM

0.030 (3.3)
0.073 (2.6)
0.011 (3.0)
0.021 (1.4)
0.020 (1.0)

0.086 (7.2)
0.117 (6.8)
0.070 (8.0)
0.011 (2.0)
0.020 (1.3)

0.064 (20326.0)
0.087 (8114.1)
0.062 (36686.1)
0.009 (598.2)
0.020 (25.6)

0.056 (10 )0.102 (106 )0.059 (106 )0.021 (106 )0.048 (106 )0.048 (all)0.076 (all)0.053 (all)0.039 (all)0.048 (all)0.179 (1.4)
0.021 (1.0)
0.318 (3.1)
0.031 (1.4)
0.050 (1.0)

0.185 (1.9)
0.021 (1.1)
0.371 (4.4)
0.031 (1.5)
0.052 (1.6)

0.153 (201.3)
0.017 (104.7)
0.353 (481.2)
0.031 (130.0)
0.043 (98.8)

0.221 (106 )0.125 (106 )0.342 (106 )0.196 (106 )0.137 (106 )0.221 (all)0.119 (all)0.382 (all)0.204 (all)0.148 (all)0.175 (4.9)
0.270 (1.4)
0.072 (1.2)
0.267 (1.6)

0.206 (14.1)
0.261 (1.9)
0.076 (1.0)
0.261 (1.0)

0.187 (11514.6)
0.261 (950.0)
0.085 (148.9)
0.328 (5368.5)

0.164 (106 )0.275 (106 )0.212 (106 )0.327 (106 )0.179 (all)0.281 (all)0.225 (all)0.331 (all)0.013 (1.1)
0.037 (2.0)
0.031 (1.1)

0.012 (2.3)
0.047 (3.8)
0.029 (1.2)

0.011 (124.9)
0.041 (328.8)
0.032 (1108.5)

0.013 (106 )0.042 (106 )0.037 (106 )0.015 (all)0.047 (all)0.037 (all)

SCM apprend les modèles les plus parcimonieux
Pour la plupart des datasets, SCM généralise bien et surpasse le baseline
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201727 / 38

Les modèles obtenus sont interprétables

Isoniazid
1.00
15

C. difficile

S. pneumoniae

M. tuberculosis

Rifampicin

Erythromycin

0.95

0.85

0.07

6

1

31

Azithromycin

0.19

0.79
3

2
0.79

0.83

0.85

0.23

17

katG - Catalase-Peroxydase
rpoB - RNA Polymerase β-Subunit

0.83

Clindamycin
0.19

616

5

0.23

Clarithromycin

mel - ABC Transporter ATPase Subunit
metE - Methionine Synthase

Penicillin-Binding Protein

ermB - rRNA Adenine N-6-Methyltransferase

Tn6194-like Conjugative Transposon

Tn6110 Transposon

En quelques heures de calcul and sans connaissances a priori, nous avons
retrouvé des mécanismes de résistance aux antibiotiques connus.

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201728 / 38

Les modèles obtenus sont interprétables

Isoniazid
1.00
15

C. difficile

S. pneumoniae

M. tuberculosis

Rifampicin

Erythromycin

0.95

0.85

0.07

6

1

31

Azithromycin

0.19

0.79
3

2
0.79

0.83

0.85

0.23

17

katG - Catalase-Peroxydase
rpoB - RNA Polymerase β-Subunit

0.83

Clindamycin
0.19

616

5

0.23

Clarithromycin

mel - ABC Transporter ATPase Subunit
metE - Methionine Synthase

Penicillin-Binding Protein

ermB - rRNA Adenine N-6-Methyltransferase

Tn6194-like Conjugative Transposon

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

Tn6110 Transposon

17 mars 201728 / 38

Les modèles obtenus sont interprétables

Isoniazid
1.00
15

C. difficile

S. pneumoniae

M. tuberculosis

Rifampicin

Erythromycin

0.95

0.85

0.07

6

1

31

Azithromycin

0.19

0.79
3

2
0.79

0.83

0.85

0.23

17

katG - Catalase-Peroxydase
rpoB - RNA Polymerase β-Subunit

0.83

Clindamycin
0.19

616

5

0.23

Clarithromycin

mel - ABC Transporter ATPase Subunit
metE - Methionine Synthase

Penicillin-Binding Protein

ermB - rRNA Adenine N-6-Methyltransferase

Tn6194-like Conjugative Transposon

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

Tn6110 Transposon

17 mars 201728 / 38

Les modèles obtenus sont interprétables

Isoniazid
1.00
15

C. difficile

S. pneumoniae

M. tuberculosis

Rifampicin

Erythromycin

0.95

0.85

0.07

6

1

31

Azithromycin

0.19

0.79
3

2
0.79

0.83

0.85

0.23

17

katG - Catalase-Peroxydase
rpoB - RNA Polymerase β-Subunit

0.83

Clindamycin
0.19

616

5

0.23

Clarithromycin

mel - ABC Transporter ATPase Subunit
metE - Methionine Synthase

Penicillin-Binding Protein

ermB - rRNA Adenine N-6-Methyltransferase

Tn6194-like Conjugative Transposon

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

Tn6110 Transposon

17 mars 201728 / 38

Les modèles obtenus sont interprétables

Isoniazid
1.00
15

C. difficile

S. pneumoniae

M. tuberculosis

Rifampicin

Erythromycin

0.95

0.85

0.07

6

1

31

Azithromycin

0.19

0.79
3

2
0.79

0.83

0.85

0.23

17

katG - Catalase-Peroxydase
rpoB - RNA Polymerase β-Subunit

0.83

Clindamycin
0.19

616

5

0.23

Clarithromycin

mel - ABC Transporter ATPase Subunit
metE - Methionine Synthase

Penicillin-Binding Protein

ermB - rRNA Adenine N-6-Methyltransferase

Tn6194-like Conjugative Transposon

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

Tn6110 Transposon

17 mars 201728 / 38

Les modèles obtenus sont interprétables

Isoniazid
1.00
15

C. difficile

S. pneumoniae

M. tuberculosis

Rifampicin

Erythromycin

0.95

0.85

0.07

6

1

31

Azithromycin

0.19

0.79
3

2
0.79

0.83

0.85

0.23

17

katG - Catalase-Peroxydase
rpoB - RNA Polymerase β-Subunit

0.83

Clindamycin
0.19

616

5

0.23

Clarithromycin

mel - ABC Transporter ATPase Subunit
metE - Methionine Synthase

Penicillin-Binding Protein

ermB - rRNA Adenine N-6-Methyltransferase

Tn6194-like Conjugative Transposon

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

Tn6110 Transposon

17 mars 201728 / 38

Au delàM.desk-merstuberculosis

S. pneumoniae

Rifampicin

Erythromycin

0.95

0.85 WT0.19
S315G
S315I 3
31
S315N
S315T

Isoniazid
1.00
15

0.07

6

1

C. difficile

Azithromycin

AGC
GGC
ATC 2
AAC
ACC

0.79

0.79

0.83

0.85

0.23

17

katG - Catalase-Peroxydase
rpoB - RNA Polymerase β-Subunit

0.83

Clindamyc

0.1

616
0.23

Clarithromycin

mel - ABC Transporter ATPase Subunit
metE - Methionine Synthase

Penicillin-Binding Protein

ermB - rRNA Adenine N-6-Methyltransferase

Tn6194-like Conjugative Transposon

Tn6110 Tra

Des mutations connues pour causer la résistance ont été retrouvées(S315G, S315I, S315N et S315T)
Le modèle s’appuie sur l’absence de la séquence de type sauvage(WT), capturant efficacement la présence de ces quatres variantes
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201729 / 38

Au delàM.desk-merstuberculosis

S. pneumoniae

Rifampicin

Erythromycin

0.95

0.85 WT0.19
S315G
S315I 3
31
S315N
S315T

Isoniazid
1.00
15

0.07

6

1

C. difficile

Azithromycin

AGC
GGC
ATC 2
AAC
ACC

0.79

0.79

0.83

0.85

0.23

17

katG - Catalase-Peroxydase
rpoB - RNA Polymerase β-Subunit

0.83

Clindamyc

0.1

616
0.23

Clarithromycin

mel - ABC Transporter ATPase Subunit
metE - Methionine Synthase

Penicillin-Binding Protein

ermB - rRNA Adenine N-6-Methyltransferase

Tn6194-like Conjugative Transposon

Tn6110 Tra

Des mutations connues pour causer la résistance ont été retrouvées(S315G, S315I, S315N et S315T)
Le modèle s’appuie sur l’absence de la séquence de type sauvage(WT), capturant efficacement la présence de ces quatres variantes
Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201729 / 38

Nouveaux résultats

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201730 / 38

Apprentissage d’arbres de décision

Classification and regression trees (Breiman, 1984)
Nous avons réussi à obtenir une implémentation out-of-core de CART
Mêmes propriétés computationnelles que SCM

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201731 / 38

Arbre de décision vs conjonction

True

False

r2
True

False

-

Conjunction+

Decision tree

r1
True

r1
False

r2
True

False

True

r1

True
+

-

¬r2

(r1

r3
True

False
+

¬r2 )

+

(¬r1

False
-

r3 )

False

r2
True

False

r2

-

-

r1

True

r3
False

Alexandre Drouin (Université Laval)

True

False

Résistance aux antibiotiques

17 mars 201732 / 38CART surpasse SCM pour certains ensembles de données

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201733 / 38CART est meilleur où SCM est moins bon

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201734 / 38CART utilise plus de règles que SCM

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201735 / 38

Conclusion

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201736 / 38

Conclusion

Modèles exacts : modèles de la résistance aux antibiotiques faisanttrès peu d’erreurs de prédiction
Interprétables : les modèles soulignent l’importance d’un ensemble
concis de k-mers
Largement applicable : autres organismes et phénotypes
Gros volumes de données : implémentation basée sur le disque
Garanties mathématiques sur l’exactitude des modèles (à venir pour CART)

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201737 / 38

Conclusion

Modèles exacts : modèles de la résistance aux antibiotiques faisanttrès peu d’erreurs de prédiction
Interprétables : les modèles soulignent l’importance d’un ensemble
concis de k-mers
Largement applicable : autres organismes et phénotypes
Gros volumes de données : implémentation basée sur le disque
Garanties mathématiques sur l’exactitude des modèles (à venir pour CART)

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201737 / 38

Conclusion

Modèles exacts : modèles de la résistance aux antibiotiques faisanttrès peu d’erreurs de prédiction
Interprétables : les modèles soulignent l’importance d’un ensemble
concis de k-mers
Largement applicable : autres organismes et phénotypes
Gros volumes de données : implémentation basée sur le disque
Garanties mathématiques sur l’exactitude des modèles (à venir pour CART)

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201737 / 38

Conclusion

Modèles exacts : modèles de la résistance aux antibiotiques faisanttrès peu d’erreurs de prédiction
Interprétables : les modèles soulignent l’importance d’un ensemble
concis de k-mers
Largement applicable : autres organismes et phénotypes
Gros volumes de données : implémentation basée sur le disque
Garanties mathématiques sur l’exactitude des modèles (à venir pour CART)

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201737 / 38

Conclusion

Modèles exacts : modèles de la résistance aux antibiotiques faisanttrès peu d’erreurs de prédiction
Interprétables : les modèles soulignent l’importance d’un ensemble
concis de k-mers
Largement applicable : autres organismes et phénotypes
Gros volumes de données : implémentation basée sur le disque
Garanties mathématiques sur l’exactitude des modèles (à venir pour CART)

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201737 / 38

Travaux futurs

Abondance des k-mers au lieu de la présence/absence
Apprentissage semi-supervisé exploiter les données non-étiquetées(phylogénie)
Application au génome humain

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201738 / 38

Merci !
Frédéric Sébastien
Raymond GiguèreMaximeDéraspe

Mario
Gaël L. François
St-Pierre Laviolette Marchand

Jacques
Corbeil

KVVER
V

http://github.com/aldro61/kover
Drouin et al. (2016). Predictive computational phenotyping and biomarker
discovery using reference-free genome comparisons. BMC genomics,
17(1), 754.
Contact: alexandre.drouin.8@ulaval.ca

Alexandre Drouin (Université Laval)Résistance aux antibiotiques

17 mars 201738 / 38