Appren&ssage	  de	  modèles	  parcimonieux	  	  à	  par&r	  de	  génomes	  complets	  avec	  applica&on	  à	  la	  résistance	  aux	  an&bio&ques	  Alexandre	  Drouin	  Groupe	  de	  recherche	  en	  appren&ssage	  automa&que	  Département	  d’informa&que	  et	  de	  génie	  logiciel	  Université	  Laval	  Plan	  • Introduc&on	  – Génomique	  – Appren&ssage	  automa&que	  • Méthode	  – Représenta&on	  des	  données	  – Set	  Covering	  Machine	  • Implémenta&on	  • Résultats	  – Résistance	  aux	  an&bio&ques	  • Conclusion	  Introduc&on	  Génomique	  La	  génomique	  est	  un	  champ	  d’étude	  de	  la	  biologie	  portant	  sur	  l’étude	  de	  l’ensemble	  de	  l’ADN	  (génome).	  

A	  T	  G	  C	  Biologie	  moléculaire	  Séquençage	  de	  l’ADN	  TTCC	  ATTC	  AATT	  TCCG	  Le	  séquenceur	  produit	  un	  ensemble	  de	  courtes	  séquences	  	  représentant	  des	  fragments	  de	  la	  molécule	  d’ADN.	  Assemblage	  de	  l’ADN	  TTCC	  ATTC	  AATT	  TCCG	  ATTCCGAT	  L’assembleur	  assemble	  les	  fragments	  pour	  former	  de	  longues	  séquences	  con&gües.	  By	  Estevezj	  (Own	  work)	  [CC	  BY-­‐SA	  3.0	  (h[p://crea&vecommons.org/licenses/by-­‐sa/3.0)	  or	  GFDL	  (h[p://www.gnu.org/copyle_/fdl.html)],	  via	  Wikimedia	  Commons	  Études	  cas-­‐témoin	  Cancer	  Sain	  VS	  Les	  études	  cas-­‐témoin	  comparent	  l’ADN	  de	  plusieurs	  individus,	  	  en	  vue	  de	  déterminer	  ce	  qui	  les	  dis&ngue.	  Appren&ssage	  automa&que	  "Field	  of	  study	  that	  gives	  computers	  the	  ability	  to	  learn	  without	  being	  explicitly	  programmed"	  	  -­‐	  Arthur	  Samuel,	  1959	  Appren&ssage	  Supervisé	  Ensemble	  de	  données	  S = {(xi , yi )}m
i=1 ⇠ Davec	   (xi , yi ) 2 X ⇥ Y

Espace	  d’entrée	   XL’ensemble	  de	  tous	  les	  génomes	  Espace	  de	  sor&e	   Y	  Y	  	  	  	  	  	  	  =	  	  	  	  	  	  	  {0,	  	  	  	  	  	  	  	  	  1}	  	  Hypothèse	  (modèle)	  	  h	  	  	  	  	  	  =	  	  	  	  	  	  	  A(S)	  	  	  	  	  	  	  	  	  	  	  	  	  	  ,	  	  h : X ! YRisque	  E(x,y)⇠DI[h(x) 6= y]Interprétable	  • Les	  modèles	  doivent	  pouvoir	  être	  interprétés	  par	  des	  experts	  du	  domaine	  • Parcimonieux	  • Structure	  du	  modèle	  Support	  Vector	  Machine	  Supposons	  que	  les	  	  x	  	  	  	  sont	  des	  vecteurs.	  Le	  modèle	  appris	  par	  une	  SVM	  est	  dense	  et	  a	  la	  forme	  d’une	  combinaison	  linéaire.	  Arbre	  de	  décision	  Is	  it	  a	  good	  &me	  to	  play	  baseball?	  

h[p://www.cise.uﬂ.edu/~ddd/cap6635/Fall-­‐97/Short-­‐papers/Image3.gif	  La	  structure	  d’un	  arbre	  de	  décision	  est	  simple	  à	  interpréter.	  Arbre	  de	  décision	  Source:	  h[p://li[leml.ﬁles.wordpress.com/2013/04/decision_tree.png	  Quand	  il	  est	  parcimonieux…	  Méthode	  Représenta&on	  “bag-­‐of-­‐words”	  • k-­‐mer:	  séquence	  de	  k	  nucléo&des	  • Soit	  	  K	  	  	  ,	  l’ensemble	  de	  tous	  les	  k-­‐mers	  présents	  dans	  les	  génomes	  de	  l’ensemble	  	  S	  	  .	  
• On	  représente	  chaque	  génome	  	  x	  	  	  par	  un	  vecteur	  	  	  	  	  (x)	  	  	  	  	  	  	  2	  	  	  	  	  R	  	  	  |K|	  	  	  	  	  	  	  tel	  que	  	  	  	  j	  	  (x)	  	  	  	  	  	  	  	  =	  	  	  	  1	  	  	  si	  	  k	  	  j	  	  	  	  2	  	  	  	  K	  	  	  	  et	  0	  sinon.	  
• |K|	  	  	  	  	  	  	  	  peut	  être	  très	  grand!	  (Humain	  >	  3000000000	  /	  individu)	  	  Représenta&on	  “bag-­‐of-­‐words”	  K={{CAGATA	   GATAGA	   GAACAG	   CGATGA	  AGATAG	   AGAACA	   ATAGAA	   CCGGCT	  AACAGC	   TAGAAC	  TTTCGG	  AAATAC	  1	  0	  1	  1	  0	  1	  1	  0	  1	  1	  1	  0	  TTTCGG	  AGATAG	  GATAGA	  CGATGA	  AACAGC	  ATAGAA	  CCGGCT	  TAGAAC	  GAACAG	  AGAACA	  AAATAC	  (x) =CAGATA	  x = CAGATAGAACAGC	  A[en&on	  au	  surappren&ssage!	  Set	  Covering	  Machine	  • Proposé	  par	  Marchand	  et	  Shawe-­‐Taylor	  en	  2003	  • Modèles:	  « Parcimonieux	  « Conjonc&ons/disjonc&ons	  de	  règles	  à	  valeur	  boolénne:	  r : R|K| ! {0, 1}	  • Complexité	  algorithmique	  op&male	   O(m|K|)

Règles	  à	  valeur	  booléenne	  • Pour	  tout	  k-­‐mer	  	  k	  	  	  j	  	  	  2	  	  	  	  	  	  K	  	  	  	  :	  	  « 	  	  Règle	  de	  présence:	  pkj ( (x)) = I[ j (x) = 1]« 	  Règle	  d’absence:	  akj ( (x)) = I[ j (x) = 0]Set	  Covering	  Machine	  Appren&ssage	  de	  disjonc&ons	  1. Créer	  un	  nouvel	  ensemble	  de	  données:	  S 0 = (xi , ¬yi ) : (xi , yi ) 2 S	  2. U&liser	  SCM	  pour	  apprendre	  à	  par&r	  de	  S	   0	  h=^ri? ( (x))

ri? 2R?

3. Appliquer	  la	  loi	  de	  De	  Morgan:	  ¬^ri? 2R?

ri? ( (x)) =_ri? 2R?

¬ri? ( (x))

Implémenta&on	  Matrice	  de	  Kmers	  Nous	  u&lisons	  Ray	  Surveyor	  pour	  produire	  une	  matrice	  de	  	  “bag-­‐of-­‐words”	  à	  par&r	  des	  génomes.	  

|K|
1 1 0 0 1 0 1 0 0 1 0
1 1 0 1 1 1 0 0 0 1 0m

0 1 0 0 1 1 1 1 1 1 10 1 0 1 0 1 0 0 1 1 1
1 0 1 1 0 1 0 1 1 1 1
1 1 1 1 0 0 0 0 1 1 1

h[ps://github.com/zorino/ray	  Calcul	  de	  la	  fonc&on	  d’u&lité	  |K||K|

1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1 1 0 1
1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1m0 1 0 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 00 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 0 0
1 0 1 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0
1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0|Ai | 1 1 1 0 3 1 3 2 0 0 0 2 2 2 3 0 2 0 1 3 3 3|Bi | 1 0 3 2 0 1 1 2 2 0 2 2 3 0 1 3 2 2 1 1 3 1

Calcul	  de	  la	  fonc&on	  d’u&lité	  |K||K|

1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 1 1 0 1
1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1m

0 1 0 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 0 0
1 0 1 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0
1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0• Astuce:	  regrouper	  les	  bits	  de	  chaque	  colonne	  dans	  des	  int64	  – 8	  x	  moins	  de	  mémoire	  – Instruc&on	  popcount	  =>	  64	  x	  moins	  d’opéra&ons!	  Stockage	  et	  accès	  aux	  données	  SCM	  Chargement	  ligne	  par	  ligne	  Fichier	  HDF5	  Compression	  Résultats	  Résistance	  aux	  an&bio&ques	  “Le	  rapport	  2014	  de	  l’OMS	  sur	  la	  surveillance	  mondiale	  de	  la	  résistance	  aux	  an&microbiens	  révèle	  que	  la	  résistance	  aux	  an&bio&ques	  n’est	  plus	  un	  souci	  pour	  l’avenir;	  c’est	  une	  réalité	  partout	  dans	  le	  monde	  aujourd’hui,	  qui	  risque	  de	  comprome[re	  notre	  capacité	  à	  traiter	  des	  infec&ons	  courantes	  dans	  la	  communauté	  comme	  dans	  les	  hôpitaux.”	  –	  Organisa&on	  mondiale	  de	  la	  santé,	  2014	  Ensembles	  de	  données	  Clostridium	  Diﬃcile	  |K|	  	   = 32	  823	  803,	  m	  =	  470	  Pseudomonas	  Aeruginosa	  |K|
= 132	  487	  288,	  m	  =	  393	  	  	  Mycobacterium	  tuberculosis	  |K|
= 11	  255	  033,	  m	  =	  154	  	  	  Streptococcus	  pneumoniae	  |K|= 10	  542	  251,	  m	  =	  680	  	  	  Source:	  Jacques	  Corbeil	  +	  Vivian	  Loo	  Source:	  AstraZeneca	  Source:	  PMID25599400	  Source:	  PMID23644493	  Filtres	  univariés	  • Filtrer	  certains	  k-­‐mers	  avant	  l’appren&ssage	  selon	  le	  résultat	  d’un	  test	  sta&s&que	  univarié.	  
2• Le	  test	  du	  	  	  	  	  	  	  	  de	  Pearson	  pour	  l’indépendance	  mesure	  la	  dépendance	  entre	  chaque	  k-­‐mer	  et	  les	  é&que[es.	  	  2• p-­‐value:	  probabilité	  d’obtenir	  une	  certaine	  valeur	  du	  	  	  	  	  	  	  	  sachant	  qu’un	  k-­‐mer	  est	  indépendant	  des	  é&que[es	  • Correc&on	  de	  la	  FDR	  par	  la	  méthode	  de	  Benjamini-­‐Yeku&eli	  Valida&on	  croisée	  imbriquée	  1	  2	  3	  4	  5	  Es&ma&on	  du	  risque	  Entraînement	  1	  2	  3	  4	  Test	  5	  Sélec&on	  des	  	  hyperparamètres	  Entraînement	  Test	  Résultats	  de	  prédic&on	  Clostridium	  Diﬃcile	  SCM	  Best	  DT	  L1SVM	  L2SVM	  Azithromycine	  0.015	  	  (3.2)	  0.111	  (1.0)	  0.056	  	  (8.8)	  0.050	  	  (3620.2)	  0.041	  	  (2462244.2)	  Ce_riaxone	  0.070	  	  (2.0)	  0.877	  	  (1.0)	  0.126	  	  (7.8)	  0.067	  	  (623.8)	  0.088	  	  (2449563.8)	  Clarithromycine	  0.015	  (3.0)	  0.091	  	  (1.0)	  0.073	  	  (10.8)	  0.071	  	  (1288.6)	  0.074	  	  (2463616.8)	  Clindamycine	  0.025	  	  (2.0)	  0.019	  	  (1.0)	  0.008	  	  (2.4)	  0.008	  	  (971.4)	  0.027	  	  (2106950.2)	  Moxiﬂoxacin	  0.019	  	  (1.0)	  0.019	  	  (1.0)	  0.019	  	  (1.0)	  0.022	  	  (414.0)	  0.041	  	  (2487703.6)	  Moyenne	  0.029	  	  (2.24)	  0.223	  	  (1.0)	  0.056	  	  (6.16)	  0.044	  	  (1383.6)	  0.054	  (2394015.7)	  Résultats	  de	  prédic&on	  Streptococcus	  Pneumoniae	  SCM	  Best	  DT	  L1SVM	  L2SVM	  Benzylpenicillin	  0.012	  	  (1.0)	  0.009	  (1.0)	  0.010	  (1.6)	  	  0.014	  (214.8)	  0.014	  	  (675375.6)	  Erythromycine	  0.031	  	  (2.0)	  0.049	  	  (1.0)	  0.047	  	  (7.0)	  	  0.045	  (378.8)	  0.041	  	  (581550.6)	  Tetracycline	  0.025	  (1.2)	  0.025	  (1.0)	  	  0.025	  (1.0)	  	  0.025	  (445.5)	  0.025	  (616914.4)	  Moyenne	  	  0.023	  (1.4)	  0.028	  	  (1.0)	  0.027	  	  (3.2)	  0.028	  (346.3)	  0.027	  	  (624613.5)	  Résultats	  de	  prédic&on	  Pseudomonas	  Aeruginosa	  SCM	  Best	  DT	  L1SVM	  L2SVM	  Dummy	  Amikacin	  0.181	  (6.0)	  0.192	  (1.0)	  0.195	  (21.0)	  0.181	  	  0.195	  (710.0)	   (115537.6)	  0.230	  Doripenem	  0.234	  (1.4)	  0.264	  (1.0)	  0.253	  0.262	  	  0.25	  (11.4)	   (1532.8)	   (11882.2)	  0.378	  Meropenem	  0.280	  (1.8)	  0.291	  (1.0)	  0.253	  	  (4.4)	  0.250	  	  (174.4)	  0.261	  (2961.2)	  0.472	  Levoﬂoxacin	  0.067	  (1.4)	  0.073	  (1.0)	  0.067	  (1.4)	  0.067	  (15.6)	  0.092	  (100928.2)	  0.416	  Moyenne	  0.191	  	   0.205	  (2.65)	   (1.0)	  0.192	  (9.55)	  0.190	  (608.2)	  0.2	  (57827.3)	  0.347	  Résultats	  de	  prédic&on	  Mycobacterium	  Tuberculosis	  SCM	  Best	  DT	  L1SVM	  L2SVM	  Ethambutol	  0.209	  (1.6)	  0.297	  (1.0)	  0.230	  (4.2)	  0.202	  (208.8)	  0.202	  (3219.8)	  Isoniazid	  0.021	  (1.0)	  0.979	  (1.0)	  0.014	  (1.0)	  0.021	  (20.2)	  0.029	  (1550.2)	  Rifampicin	  0.035	  (1.4)	  0.035	  (1.0)	  0.035	  (1.4)	  0.028	  (40.2)	  0.029	  (180.2)	  Streptomycin	  0.037	  (1.0)	  0.963	  (1.0)	  0.030	  (1.4)	  0.037	  (49.4)	  0.037	  (1185.6)	  Moyenne	  0.076	  (1.72)	  0.569	  (1.0)	  0.078	  (2.0)	  0.072	  (79.7)	  0.074	  (1554.0)	  Valida&on	  biologique	  1	  2	  5	  3	  10	  4	  15	  Azithromycine	  Clarithromycin	  Ce=riaxone	  Clindamycin	  6	  11	  13	  Moxiﬂoxacin	  9	  8	  26	  	  	   DNA	  gyrase	  subunit	  A	  	  	  	   Tn6194-­‐like	  Transposon,	  other	  	  	  sensor	  his&dine	  	   Two-­‐component	  kinase	  Transposon	  Tn6110	  and	  Clostridium	  Saccharoly&cum	  23S	  rRNA	  m(2)A-­‐2503	  methyltransferase	  Penicillin-­‐binding	  protein	  	  	   Conjuga&ve	  transposon	  FtsK/SpoIIIE-­‐like	  	  	  14	  	  12	  	  	  	  ErmB	  rRNA	  adenine	  N-­‐6-­‐	  	   methyltransferase	  	  	   Other:	  hypothe&cal	  proteins	  and	  	   unmatched	  k-­‐mers	  	  	  	  	  	  	  	  Conclusion	  • Notre	  méthode	  permet	  d’apprendre	  des	  modèles	  parcimonieux	  à	  par&r	  de	  génomes	  complets.	  
• Ces	  modèles	  sont	  composés	  de	  règles	  facilement	  interprétables.	  
• Nos	  modèles	  ont	  une	  forme	  qui	  les	  rend	  par&culièrement	  faciles	  à	  transformer	  en	  tests	  cliniques.	  
• Travaux	  futurs:	  corréla&on	  entre	  certains	  k-­‐mers,	  robustesse	  aux	  muta&ons,	  modèles	  plus	  complexes	  (DNF-­‐SCM),	  cancer.	  Remerciements	  • Personnes	  impliquées	  dans	  le	  projet:	  Appren&ssage	  Automa&que	  Bioinforma&que	  • Sébas&en	  Giguère	  • Vladana	  Sagatovich	  • François	  Laviole[e	  • Mario	  Marchand	  • Maxime	  Déraspe	  • Frédéric	  Raymond	  • Jacques	  Corbeil	  • Paul	  H.	  Roy	  Lynda	  Robitaille	  Références	  •Drouin,	  A.,	  Giguère,	  S.,	  Sagatovich,	  V.,	  Déraspe,	  M.,	  Laviole[e,	  F.,	  Marchand,	  M.,	  &	  Corbeil,	  J.	  (2014).	  
Learning	  interpretable	  models	  of	  phenotypes	  from	  whole	  genome	  sequences	  with	  the	  Set	  Covering	  Machine.	  arXiv	  preprint	  arXiv:1412.1074.	  

•Marchand,	  M.,	  &	  Shawe-­‐Taylor,	  J.	  (2003).	  The	  set	  covering	  machine.	  The	  Journal	  of	  Machine	  Learning	  Research,	  3,	  723-­‐746.	  

•World	  Health	  Organiza&on.	  (2014).	  An&microbial	  resistance.	  Factsheet	  194,	  2013.