ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE. Klasifikace s apriorní znalostí

ZADÁNÍ

1

ZADÁNÍ

2

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE

Fakulta elektrotechnická Katedra počítačů

Bakalářská práce

Klasifikace s apriorní znalostí

červen 2007 

3

Vypracoval: 

Michal Trna

Vedoucí práce: 

Ing. Jiří Kléma, PhD.

BLANKPAGE BLANKPAGE BLANKPAGE BLANKPAGE BLANKPAGE 4

Poděkování

Chtěl bych na tomto místě poděkovat všem, kteří mi jakýkoli způsobem pomáhali při  vzniku této práce. Zvláště děkuji vedoucímu mé bakalářské práce Ing. Jiřímu Klémovi,  PhD. za odbornou pomoc a svému počítači za stovky hodin procesorového času.

5

BLANKPAGE BLANKPAGE BLANKPAGE BLANKPAGE BLANKPAGE 6

Čestné prohlášení

Prohlašuji,   že   jsem   zadanou   bakalářskou   práci   vypracoval   samostatně   s   přispěním  vedoucího   práce   a   použil   jsem   pouze   podklady   uvedené   v   přiloženém   seznamu.   Dále  prohlašuji,   že   nemám   závažný   důvod   proti   užití   tohoto   díla   ve   smyslu   §60   Zákona  č. 121/2000   Sb.,   o   právu   autorském,   o   právech   souvisejících   s   právem   autorským   a   o  změně některých zákonů (autorský zákon).

V Praze dne 15. 6. 2007 ............................................................ podpis

7

BLANKPAGE BLANKPAGE BLANKPAGE BLANKPAGE BLANKPAGE 8

ABSTRAKT

Oblast   analýzy   biomedicínských   dat   je   poměrně   mladá   disciplína   a   v  současnosti se velmi rychle rozvíjí. Problémy zpracování těchto specifických dat vybízí  k vyvinutí nových efektivních metod, k čemuž má přispět i tato práce; zabýváme se v  ní implementací a vyhodnocením výsledků   modifikovaného klasifikátoru CN2. Nově  dodaným   prvkem   v   něm   je   zvažování   použití   apriorní   znalosti   získané   z   popisů  atributů,   v   našem   případě   genů.   Různé   přístupy   použití   této   znalosti   při   stavbě  klasifikačních pravidel zde pak rozebíráme a vyhodnocujeme.

ABSTRACT

The analysis of biomedical data is quite young and rapidly developing discipline  at   present.   Problems   of   processing   such   specific   data   provokes   us   to   develop   new  effective   methods,   whereto   this   work   should   contribute.   It   inquires   into   the  implementation and evaluation of results of the modified algorithm CN2. The newly  added aspect to this algorithm is consideration of usage of the knowledge extracted  from annotations of attributes, in our case genes. Various approaches of usage of this  knowledge in the building process of classification rules are analysed and interpreted.

9

BLANKPAGE BLANKPAGE BLANKPAGE BLANKPAGE BLANKPAGE 10

Obsah Obsah

11

Seznam obrázků

13

Seznam grafů

14

Seznam tabulek

15

 1  Úvod

17

 1.1 Úvod do genetiky

17

 1.1.1 DNA

18

 1.1.2 Geny

21

 1.1.3 Chromozomy

23

 1.2 Genomická data

24

 1.2.1 Sekvenování DNA

24

 1.2.2 Genové čipy

26

 1.2.3 Genomická data

28

 1.2.3.1 SAGE data

29

 1.2.3.2 AML ALL data

29

 1.2.4 Genové ontologie

31

 1.3 Klasifikace

33

 1.3.1 CN2

33

 1.3.2 Křížová validace

37

 2  Injekce apriorní znalosti

39

 2.1 Získání termínů z genových popisů

40

 2.2 Získání matice podobnosti

40

 2.3 Úpravy v CN2

41

11

 3  Experimenty

45

 4  Závěr

53

 A. Seznam zkratek

54

 B. Reference

55

 C. Příloha

57

 I. Obsah přiloženého média

57

 II. Popis částí zdrojového kódu

58

 III.Popis instalace a spouštění CN2

61

 IV.Popisy přiložených skriptů

62

12

Seznam obrázků Obr. 1.

Struktura DNA

20

Obr. 2.  Proces přepisu genetické informace do proteinů 

23

Obr. 3.

Proces hybridizace na genovém čipu

27

Obr. 4 

Paprskové procházení stavovým prostorem algoritmu CN2

34

13

Seznam grafů Graf 1.

Kl. přesnost CN2 s bg. knowledge z GO BP injektovanou do primusu

45

Graf 2.  Kl. přesnost CN2 s bg. knowledge z GO MF injektovanou do primusu

46

Graf 3.  Kl. přesnost CN2 s bg. knowledge z GO BP injektovanou do primusu

47

Graf 4.  Kl. přesnost CN2 s bg. knowledge z GO MF injektovanou do primusu

47

Graf 5.  Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do primusu

48

Graf 6.  Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do primusu

48

Graf 7.  Kl. přesnost CN2 s bg. knowledge z GO BP/MF injektovanou do secundusu

49

Graf 8.  Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do secundusu

50

Graf 9.  Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do secundusu

50

Graf 10. Kl. přesnost CN2 s feature selection

51

14

Seznam tabulek Tab. 0.

Významy kodónů –  krátká označení aminokyselin a příslušné kodóny

20

Tab. 1.

Kl. přesnost CN2 s bg. knowledge z GO BP injektovanou do primusu

45

Tab. 2.

Kl. přesnost CN2 s bg. knowledge z GO MF injektovanou do primusu

46

Tab. 3.

Kl. přesnost CN2 s bg. knowledge z GO BP injektovanou do primusu

47

Graf 4.  Kl. přesnost CN2 s bg. knowledge z GO MF injektovanou do primusu

47

Tab. 5.

Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do primusu

48

Tab. 6.

Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do primusu

48

Tab. 7.

Kl. přesnost CN2 s bg. knowledge z GO BP/MF injektovanou do secundusu

49

Tab. 8.

Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do secundusu

50

Tab. 9.  Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do secundusu

50

15

BLANKPAGE BLANKPAGE BLANKPAGE BLANKPAGE

16

1. Úvod

Informační společnost generuje a kumuluje ohromná množství dat, která ve své  surové   podobě   nezřídka   nesou   jenom   malou   pragmatickou   informaci.   K   jejich  zpracování do zužitkovatelné podoby byly v průběhu let vyvinuty netriviální přístupy,  které   byly   souhrnně   začleněny   pod   hlavičku   dolování   dat   (data   mining,   DM)   popř.  objevování dat v databázích (knowledge discovery in databases, KDD). Mezi základní  úlohy disciplíny patří vyhledávání netriviálních vzorů, souvislostí či pravidel v datech  a jejich přehledné, člověkem pochopitelné prezentování. Tato   bakalářská   práce   se   zabývá   úpravou   klasifikačního   algoritmu   CN2   pro  účely   vylepšení   jeho   predikční   přesnosti   pro   data,   u   kterých   máme   tzv.   apriorní  znalost (background knowledge), tj. předem danou znalost vztahující se k jednotlivým  atributům. Touto znalostí může být – jako v našem případě – například textový popis  genu,   na   jehož   základu   se   dá   usuzovat   na   souvztažnost   některých   atributů,   a   na  základě   této   doplňkové   znalosti     můžeme    výběry   příslušných   atributů   do  generovaných   pravidel   motivovat.   Od   tohoto   přístupu   si   slibujeme   vylepšené  klasifikační schopnosti nového algoritmu.

1.1. Úvod do genetiky

V   této   části   se   stručně   zmíním   o   původu   dat,   nad   kterými   byly   prováděny  experimenty. Nejprve bychom si měli vytvořit představu o tom, co to genetická data  vlastně jsou: jsou to data týkající se obecně genomu; v našem kontextu jde vždy o data  týkající   se   genomu   lidského,   takže   všechna   následující   tvrzení   o   genomu   budiž  17

chápana v kontextu lidského genomu. Nejjednodušší   ještě   výstižná   představa   o   genomu   by   mohla   vypadat   takto:  genom   je   úplný   sada   instrukcí   kódujících   elementární   procesy   uvnitř   lidského   těla  (včetně jeho vzniku a také regulace procesu vzniku). Obsahuje “plány” (návrh, design)  základního   tělesného   uspořádání,   všech   buněčných   struktur   a   nitro­buněčných  procesů včetně  životního cyklu. Lidský genom je zakódovaný v molekulách deoxyribonukleové kyseliny (DNA),  které   se   standardně   nacházejí   v   jádře   prakticky   všech   buněk   (kromě   bezjaderných  červených   krvinek),   kde   spočívají   těsně   stočené   ve   šroubovici;  spolu   s   připojenými  proteinovými molekulami tvoří organizační jednotku zvanou chromozom. Chromozomů  má člověk v každé běžné buňce 46. V následujících odstavcích se stručně zmíním o základním popise a funkci DNA.

1.1.1. DNA

Po   chemické   stránce   je   DNA   dlouhý   polymer   skládající   se   z   jednoduchých  informaci nesoucích jednotek zvaných nukleotidy navázaných na informaci nenesoucí  kostře   z   cukrů   a   fosfátů   (zbytky   po   kyselině   fosforečné).   Ke   každému   cukru   je  připojena   jedna   ze   čtyř   druhů   molekul   zvaných   báze;   těmito   bázemi   mohou   být  adenin (A), cytosin (C), guanin (G) a thymin (T). Sekvence těchto bází podél fosfátové  kostry molekuly kóduje informaci podobně jako ji kódují dipóly na magnetické pásce.  Molekula DNA obsahuje dvě taková vlákna, která jsou k sobě připojena bázemi. Báze  se na sebe vážou pomocí vodíkových můstků; vždy adenin s thyminem a   cytosin s  guaninem;   říká   se,   že   jsou   tyto   báze   navzájem   komplementární.   Tyto   báze   spolu   s  cukr­fosfátovou   kostrou   tvoří   dvojitou   šroubovici   (double   helix).   Přesné   pořadí   bází 

18

podél kostry se nazývá DNA sekvence. Tato sekvence přesně obsahuje instrukce pro  vznik organizmu se specifickými rysy a též pro všechny jeho vnitřní pochody. Velikost  genomu se obvykle vyjadřuje jako počet bázových dvojic. Pro lidský genom se toto číslo  pohybuje přibližně na 2,9.109 dvojicích, pro srovnání pro genom domácí myši je to asi  2,5.109 dvojic, pro rýži asi 0,5.109 dvojic. Trojce po sobě následujících bází tvoří tzv. kodón. Vzhledem k tomu, že máme 4  možné báze, máme 43  = 64 možných kodónů, označují se postupným zápisem písmen  označujících jednotlivé báze (např. AAC, AUG). Tyto kodóny jsou úzce spjaty s tzv.  aminokyselinami, do kterých se při procesu předávání informace z DNA (translace)  přepisují;   těchto   aminokyselin   máme   20.   Některé   kodóny   mají   speciální  synchronizační funkci, např. start a stop kodóny vymezující oblast translace (viz dále).

Ala

A

GCU, GCC, GCA, GCG

Leu

L

UUA, UUG, CUU, CUC,  CUA, CUG

Arg

R

CGU, CGC, CGA, CGG, AGA,  Lys

K

AAA, AAG

AGG Asn

N

AAU, AAC

Met

M

AUG

Asp

D

GAU, GAC

Phe

F

UUU, UUC

Cys

C

UGU, UGC

Pro

P

CCU, CCC, CCA, CCG

Gln

Q

CAA, CAG

Ser

S

UCU, UCC, UCA, UCG,  AGU, AGC

Glu

E

GAA, GAG

Thr

T

ACU, ACC, ACA, ACG

Gly

G

GGU, GGC, GGA, GGG

Trp

W

UGG

His

H

CAU, CAC

Tyr

Y

UAU, UAC

Ile

I

AUU, AUC, AUA

Val

V

GUU, GUC, GUA, GUG

AUG, GUG

Stop

Start

UAG, UGA, UAA

Tab. 0 – Významy kodónů –  krátká označení aminokyselin a příslušné kodóny 19

Z předchozí tabulky (tab. 0) je vidět, že genetický kód je tzv. redundantní či  degenerovaný   –   tj.   že   jedna   aminokyselina   odpovídá   většímu   množství   kodónů.     Z  tohoto   důvodu   není   možné   z   vyrobeného   aminokyselinového   řetězce   zjistit   původní  podobu genu. Jak   již   bylo   řečeno,   DNA   je   nukleová   kyselina,   vyskytující   se   s   výjimkou  bezjaderných    červených   krvinek   v   jádře,   která   obsahuje   genetické   instrukce  používané při vývoji organismu a při řízení jeho vnitřních procesů. Hlavním úkolem  DNA je dlouhodobé uložení této informace. Segmenty DNA, které nesou smysluplnou  genetickou   informaci   se   nazývají   geny;   sem   patří   i   části   DNA   nesoucí   informaci   o  struktuře   nebo   mají   regulační   účel.   Na   DNA   jsou   taktéž   “hluché”   úseky   bez  jakéhokoliv známého významu, tzv. junk DNA, která tvoří až 97% lidské DNA.

Obr. 1 Struktura DNA

20

Obrázek   na   předchozí   straně   (obr.   1)   jasně   zachycuje   strukturu   DNA:   po  stranách se ve vertikálním smyslu vine cukr­fosfátové vlákno; vprostřed jsou na sebe  navázané A­T a C­G báze. Všimněte si, že báze adenin a thymin jsou navázány pomocí  dvou   můstků,   zatímco   cytosin   s   thyminem   váží   tři   můstky   a   tedy   jsou   bezpečně  nezaměnitelné. V RNA se místo thyminu používá trojvazný uracil (U). Jak již bylo zmíněno, základní jednotkou genetické informace je gen, který je  schopný   (resp.   podstupuje;   podle   úhlu   pohledu)   množení   (reprodukce)   a   změny  (mutace).   Funkcí   je   realizace   nějakého   znaku   či   vlastnosti,   kterou   kóduje.   V  makroskopickém pohledu je sám o sobě  víceméně pouze kus informace, která podléhá  výběrovým (selektivním; či vývojovým ­ evolučním) tlakům. Není bez zajímavosti, že  tzv. emergentní jevy nad pooly různých genů nacházejí uplatnění v jiných části umělé  inteligence   než   kterou   se   zde   zabýváme   –   v   genetickém   programování,   návrhu  genetických algoritmů a výzkumu kolektivní inteligence. Dnes víme, že lidský genom obsahuje ne více než 21000 genů [1], v době psaná  této   práce   známe   20488   s   tím,   že   ještě   asi   100   čeká   na   objevení   [2].   Z   tohoto   lze  vypozorovat, že genová hustota, která udává počet genů na bázi (b; popř. mega­bázi ­  Mb),   je   poměrně   nízká.   Hustota   lidského   genomu   je   asi   12­15   genů   na   Mb   [3].  Prokaryota mají tuto hustotu vyšší než vyšší organizmy. 

1.1.2. Geny

Jak   si   lze   odvodit   z   výše   napsaného,   každá   DNA   obsahuje   řádově   stovky   až  tisíce genů – základních fyzikálních a funkčních jednotek informace. Tato informace je  použita při konstrukci proteinů, které se následně zapojují do konstrukce a procesů a  reakčních cyklů uvnitř buňky – katalyzující proteiny se nazývají enzymy. Geny se velmi liší ve své délce; často se rozprostírají přes tisíce bází. Prostor 

21

mezi geny, který nenese žádnou informaci a nemá žádnou kódovací funkci zaplňují  tzv. introny. Jejich délka se liší a typicky to bývají úseky tisíce bází dlouhé, některé  však mohou mít i stovky tisíc bází na délku. Organismy   jsou   sestaveny   prakticky   zcela   z   proteinů.   Jsou   to   velké   složité  molekuly   tvořené   z   dlouhých   řetězců   podjednotek   –   aminokyselin.   Lidé   jich   mohou  syntetizovat   přinejmenším   100000   druhů.   Proteiny   se   skládají   z   20   druhů  aminokyselin   o   jejichž   kódování   kodóny   jsme   se   zmiňovali   výše.   Protein   průměrné  velikosti   (3000bp   –   base   pairs   –   párů   bází)   se   tedy   bude   skládat   přibližně   z   1000  aminokyselin.   Největší   proteiny   –   titiny,   složky   svalové   sarkomery   –   se   skládají   z  téměř 27000 aminokyselin a mají molekulovou hmotnost téměř 3MDa (megadalton)  [4]. Na této úrovni je genetický kód série kodónů určujících, které aminokyseliny na  kterém   místě   budou   použity   pro   vybudování   konkrétního   proteinu.   Toto   kódování  ovšem neprobíhá přímo. Instrukce   kódující   protein   jsou   nejprve   přeneseny   na   tzv.   mRNA   (messenger  RNA).   RNA   (ribonucleic   acid;   ribonukleová   kyselina)   je   nukleová   kyselina   velmi  podobná DNA ve stavebních kamenech s tím rozdílem, že místo thyminu (T) používá  uracil (U) jak jsme již zmínili; důležitější však je, že RNA je jednovláknová. MRNA je  tedy   speciální   druh   RNA,   který   má   jediný   účel   a   to   nechat   do   sebe   otisknout  (trascribe) genetickou informaci a poté ji po přesunu z jádra do cytoplasmy použít na  stavbu   proteinu   (translation).   Ta   probíhá   tak,   že   se   na   otištěné   kodóny   naváží  příslušné aminokyseliny, které se zřetězí a vytvoří tak molekulu proteinu. Na obrázku  2 je celý proces názorně zachycen.

22

Obr. 2 Proces přepisu genetické informace do proteinů 

1.1.3. Chromozomy Tři  miliardy   párů   bází   jsou   organizovány   do   23   fyzikálně   odlišných   jednotek  zvaných chromozomové páry. Všechny somatické lidské  buňky (všechny s výjimkou  pohlavních) obsahují dvě množiny chromozomů (říkáme že jsou diploidní) – každá je  od   jednoho   z   rodičů,   proto   páry.   Z   těchto   párů   je   22   tzv.   autosomů   (nesexuálních  chromozomů   společných   pro   obě   pohlaví)   a   dále   jeden   pár   pohlavně   specifický  (chromozomy X a Y). Normální žena má pár chromozomů XX a normální muž má XY. Chromozomy   jsou   pozorovatelné   mikroskopem   (po   obarvení   speciálním  barvivem)   a   lze   je   rozeznat   jasně   podle   velikosti   (největší   chromozom   č.   1   má  cca. 245Mbp, nejmenší č. 21 má oproti tomu jen asi 47Mbp). Jevy a případné změny na  úrovní DNA jsou ovšem příliš jemné a vyžadují molekulární analýzu. Tyto jemné DNA  abnormality jsou odpovědné za různé dědičné choroby jako je anemie nebo cystická  fibrióza nebo mohou mýt predispozicí pro vznik rakoviny popřípadě jiných složitých  chorob.  Je   dobré   zmínit,   že   podle   počtu   chromozomů   nelze   usuzovat   například   na 

23

vyspělost druhu. Octomilka má 8 chromozomů, morče 16, člověk jak byl řečeno 46,  drůbež 78 a motýli v závislosti na druhu až 380. Některé druhy rostlin pak 10, jiné i  přes 1200. Velká většina genů v těchto organizmech je však soustředěna v několika  málo velkých chromozomech; zbytek chromozomů je pak malý nebo vysloveně drobný  (rozpadlé chromozomy).

1.2. Genetická data

1.2.1. Sekvenování DNA

Sekvenování   DNA   je   prosté   určení   sekvence   nukleotidů   uvnitř   jednoho   DNA  řetězce   –   druhý   řetězec   je   jak   jsem   se   již   zmínil   komplementární   a   jednoznačně  odvoditelný. Sekvenování je tedy proces, kterým se převádí DNA sekvence do podoby  dat, se kterými se pak dá pracovat pomocí prostředků na hromadné zpracování dat. Pro   princip   sekvenování   existuje   několik   základní   metody.   Jednou   z   nich   je  například metoda chemické degradace, další je metoda terminace řetězců, která dnes  jednoznačně   převládá.   Tato   metoda   používá   jednovláknovou   DNA   jako   vzor   pro  syntézu   druhého   komplementárního   řetězce.   Tato   syntéza   je   zprostředkována  enzymem polymerázou. Reakce je upravena tak, že v určitých místech (na určitých  nukleotidech)   dochází   v   závislosti   na   sekvenci   vzorového   vlákna   k   ukončení  (terminaci)   syntézy.   Vznikají   tak   nedokončené   řetězce   komplementárního   vlákna  různých   délek;   a   tyto   délky   je   možné   zjistit   pomocí   elektroforézy   v   gelu.   Jelikož   k  ukončení   reakce   dochází   ve   chvíli,   kdy   se   ve   vzorovém   vlákně   vyskytne   určitý  nukleotid, tak délka odpovídá vzdálenosti od začátku vlákna, ve které se objevil tento  nukleotid.  Získáme  tedy  dílčí  informaci  o  sekvenci  –  známe  pozici  prvního výskytu 

24

daného nukleotidu ve vzorovém vlákně. Syntéza se provádí tak, že se vždy hledají řetězce pro jeden konkrétní nukleotid.  Trik   této   metody   spočívá   v   tom,   že   se   do   reakce   nepřidává   pouze   terminační  dideoxynukleotid,   ale   také   i   normální   partnerský   deoxynukleotid   v   poměru   100:1.  Další důležitým aspektem je, že reakce nikdy neobsahuje pouze jedno vzorové vlákno,  ale velké množství těchto vláken se stejnou sekvencí. Při sekvenování tedy probíhá  současně   více syntéz nových komplementárních vláken. Vzorová vlákna budou vždy  na stejných místech obsahovat např. guaniny, proti kterým bude DNA­polymeráza do  nového vlákna zařazovat cytosiny, které se budou náhodně vybírat z roztoku. Pokud  tedy bude jeden ze sta cytosinů mít podobu terminačního dideoxynukleotidu, dojde k  zastavení   (terminaci)   reakce   jen   u   jednoho   ze   sta   nově   syntetizovaných   vláken.   U  ostatních bude zařazen normální cytosin a syntéza tohoto vlákna bude pokračovat dále  k dalšímu místu, kde kam bude potřeba na guanin navázat nějaký cytosin. V tomto  momentu se opět zastaví 1% z dosud syntetizujících vláken. Na konci tohoto procesu  tedy bude výsledkem reakce směs nových vláken, která budou dlouhá v závislosti na  tom, kde se u nich syntéza zastavila. Po rozdělení v gelu a zjištění jejich délky v počtu  párů tedy zjistíme pozice, na kterých se ve vzoru objevil guanin. Současné metody jsou schopné přímo sekvenovat jenom relativně krátké úseky  DNA, 300­1000 nukleotidů; hlavním problémem je, že při dosažení této hranice chybí  rozlišovací schopnost od sebe rozeznat dva úseky lišící se v délce o jeden nukleotid.  Používaným   řešením   je,   že   se   DNA   (nejdelší   chromozom   =   250   milionů   bází)  mechanicky nebo pomocí speciálních enzymů rozstřihne na menší části, které se pak  za pomocí vhodné bakterie namnoží (což ovšem nelze úplně vždy mj. kvůli vlivu této  DNA   na   fungování   hostitelské   bakterie)   a   potom   sekvenují   s   tím,   že   se   s   výhodou  využije   faktu,   že   se   nová   sekvence   překrývá   se   nějakou   vhodnou   známou   částí   k  přesné identifikaci jejího umístění (shotgun sekvenování).

25

Jak jsme již zmínili, lidský genom obsahuje zhruba 3.109  bází. Při průměrné  velikosti sekvenovaného fragmentu 500bp a zanedbání překryvů, je potřeba nejméně  6.000.000 běhů k jeho úplnému osekvenování. I přes tuto zjevnou pomalost již v roce  1999   resp.   2000   byly   zveřejněny   sekvence   chromozomu   22   resp.   21.   V   současnosti  uváděné   sekvenční   technologie   jsou   nadto   schopny   pracovat   řádově   rychleji   než  dřívější elektroforézní systémy.

1.2.2. Genové čipy

Jiný přístup jak získat data z DNA je použít tzv. genové čipů, tzv. microarrays.  Tato   metoda   se   často   se   používá   pro   měření   aktivity   (exprese)   genů   v   organismu.  Vzhledem k tomu, že data zkoumaná v této práci mají původ právě v genových čipech,  tuto problematiku zde trochu rozvedeme. Tato metoda je založena na technologii DNA  prob;   probu   si   lze   představit   jako   jakousi   sondu,   sekvenci   několika   bází,   která  identifikuje určitý úsek DNA. Postup je následující. Vezmeme jedno vlákno DNA, toto  vlákno budiž komplementární doplněk sekvence, kterou chceme hledat. Vložíme ho do  ro roztoku, který obsahuje zkoumaný genetický materiál. V případě, že proba nalezne  v   roztoku   svůj   komplement,   dojde   ke   spojení   proby   a   tohoto   komplementu   ze  zkoumaného genetického materiálu (tzv. hybridizaci).  Trik této metody tkví v tom, že  dříve než se zkoumaný genetický materiál (což bývá RNA získaná ze zkoumané DNA)  vloží do roztoku, je opatřen fluorescentem. V   technologii   genetických   čipů  se   tohoto   využívá  tak,   že   se   proby  ve   velkém  množství zafixují na konkrétní přesně dané pozice na čipu (což je většinou sklíčko nebo  jiný speciální povrch), takže podle intenzity zbarvení lze v principu jednoduše určit  kam se obarvená RNA uchytává, tj. jaké sekvence obsahuje. Často se toto pak provádí  s různě zbarveným materiálem různého původu, takže lze okamžitě srovnat rozdíly ve 

26

výskytu   sekvencí   ve   vzorcích.   Různý   původ   může   například   znamenat,   že   jeden  materiál má původ ve zdravých buňkách a druhý v buňkách napadených rakovinou,  buňkách na které byly aplikovány léky apod. Jak bylo řečeno, prob může být velké  množství a hybridizace probíhá na všech současně, takže technologie dává poměrně  rozsáhlé výsledky – například pro bakterii E. coli, která je pro jednoduchý genom často  vyhledávaným objektem experimentů, se na čip  vejde dost  prob  pro nalezení všech  jejích 4000 genů. Dále pak na každý čip je umístěno velké množství prob, které jsou stejné; jelikož  ne každý proba je následně hybridizovaná v plné míře (dochází k částečné hybridizaci),  je   pro   přesnější   určení   přítomnosti   dané   sondy   ve   zkoumaném   vzorku   (samplu)  výhodné   získané   hodnoty   tímto   způsobem   zprůměrovat.   Tato   data   pak   naskýtají  vhodnou příležitost pro použití strojového učení. Následující obrázek č. 3 ukazuje, jak  může genový čip a hybridizační procesy na něm vypadat.

Obr. 3 Proces hybridizace na genovém čipu [5]

Z   obrázku   je   patrné,   že   délka   RNA   řetězců   je   výrazně   větší   než   délka   pro;  typická   délka   v   praxi   používaných   prob   je   asi   25   bází,   oproti   tomu   typická   délka  27

zkoumaného   samplu   je   v   tisících   bází.   Tato   délka   je   dostatečná   k   identifikaci  zkoumaných genů a na druhou stranu jsou proby dost krátké na to, aby nedocházelo k  nežádoucím   hybridizacím,   například   částečným   hybridizacím   nebo   vzájemným  hybridizacím dvou sond popřípadě jakési “sebehybridizaci” jedné sondy. Dále   po   ukončení   fáze   hybridizace   je   čip   opláchnut,   aby   se   smyla   všechna  nehybridizovaná (obarvená) DNA a pomocí optického mikroskopu se přečte hodnota  intenzity fluorescence každého konkrétního vzorku na čipu.

1.2.3. Genomická data Ve  stručnosti  o tom, jak  jsou  nasbíraná data  reprezentována a  jak je s nimi  manipulováno:   existuje   několik   pohledů   na   to   jak   organizovat   genomická   data   pro  další   využití lišící   se  v tom,  co  tvoří příklady   (examples)  a  co  vlastnosti  (features).  První   možností   je,   že   gen   tvoří   příklad   a   jeho   exprese   v   různých   podmínkách   je  množina vlastnosti. Druhý – asi přirozenější – přístup, který také používáme v této  práci,   je   ten,   že   příklad   je   tvořený   experimentem   a   jednotlivé   rysy   odpovídají  jednotlivým genům. V této práci k těmto datům přistupujeme pomocí tzv. metody učení s učitelem;  tj.   vytvoříme   model   na   trénovacích   datech,   kde   pro   každý   příklad   je   přiřazena  kategorie (rakovina ano­ne, leukémie  typ 1­typ 2). Na  základě vytvořeného modelu  pak   jsme   schopní   rozhodnout   pro   do   příkladů   nezahrnuté   případy   o   zařazení   do  kategorie.  Pro experimenty byly použity dva zdroje dat: “SAGE” data a “ALLAML”. data.

28

1.2.3.1. SAGE data Serial Analysis of Gene Expression data alias SAGE data jsou microarray data s  extrémně vysokou dimenzí a díky metodě měření jsou zde přítomny chyby ve velkém  množství.   Původním   problémem   nad   těmito   daty   je   správně   oklasifikovat   typ  rakoviny, v našem případě však hledáme pravidla pouze pro třídy rakovina ano/ne.  Tento data set má záměrně velmi diverzifikovaný původ (různé tkáně), aby bylo možné  provést mezitkáňová srovnání. Pro velkou šíři záběru tyto data asi nemá smysl více  rozebírat. Originální dataset obsahuje 35000 atributů a počet chyb dosahuje asi 10%[9]. V  našem   případě   jsme   však   až   s   takto   vysokodimenzionálními   daty   nepracovali   a   po  redukci atributů na takové, které se projevily alespoň v několika situacích zůstalo asi  11000 atributů. Klasifikační přesnost CN2 bez injektové apriorní znalosti se na těchto datech  pochybuje kolem 66%.

1.2.3.2. ALLAML data ALL  vs. AML   problém  spočívá   ve správném   klasifikování  vzorku   s  leukémií.  Leukémie je jak asi všichni víme, nádorové onemocnění bílých krvinek. Abnormální  bílé krvinky se množí na úkor červených krvinek i krevních destiček, čímž vyvolají  anémii, krvácení a krevní výrony. V těžkých případech mohou v kostní dřeni úplně  potlačit krvetvorbu.  Leukémie lze rozdělit podle dvou atributů do čtyř skupin: jednak  na akutní a chronické, dále pak na lymfocytické a myeloidní. Akutní   leukémie   je   charakterizovaná   rapidním   šířením   nezralých   krevních  buněk. Toto zahlcení způsobí, že kostní dřeň je následně neschopná tvořit zralé buňky,  29

kterých je pak logicky nedostatek. Tato nemoc je vyskytuje u dětí a dospívajících (v  USA v této kategorii je to nejčastější příčina úmrtí mezi zhoubnými onemocněními). Chronická   leukémie   se   liší   tím,   že   kostní   dřeň   produkuje   velké   množství  relativně vyspělých, ale stále nějak abnormálních buněk. Typicky trvá měsíce až roky  než se vyvinou a jsou produkovány v daleko větším počtu než je běžné. Výsledkem je  pak velké množství abnormálních bílých krvinek v krvi. Toto onemocnění je naopak  časté u starších lidí. Rozdíl   mezi   lymfocytickou   a   myeloidní   leukémií   je   v   tom,   který   typ   buněk  zasahuje – zda bílé krvinky (lymphocyty) nebo buňky kostní dřeně (myelocyty). Naučit  strojově   rozpoznávat   a   predikovat   tento   rozdíl   je   mj.   naším   úkolem   v   této   práci.  Příklady   jsou   rozděleny   do   dvou   tříd:   ALL   (Acute   Lymphocytic   Leukemia)   a   AML  (Acute   Myelogenous   Leukemia),   k   dispozici   jich   máme   celkem   72.   Každý   má   7129  atributů/feature, což jsou numericky vyjádřené exprese genů. Vzhledem k tomu, že data mají poměrně kompaktní původ (jedna série měření  zaměřená   na   jeden   problém),   jejich   klasifikace   je   při   použití   např.   CN2   poměrně  daleko   snazší   resp.   predikční   síla   větší   než   klasifikace   SAGE   dat,   i   když   metoda  získání (microarray) je u obou sad dat shodná.  Originální neupravená data lze získat na této adrese: 

http://www.broad.mit.edu/cgi­bin/cancer/publications/pub_paper.cgi?mode=view&paper_id=43

, kde je také jejich popis a popis jejich získání. Klasifikační přesnost CN2 bez injektované apriorní znalosti se na těchto datech  pochybuje kolem 87%.

30

1.2.4. Genové ontologie V této práci dále používáme genové ontologie, zde si je tedy stručně uvedeme. Gene   ontology   project     (GO)   poskytuje   slovník   vhodně   volených   termínů   pro  popis atributů genů a procesů týkajících se genů. GO popisuje tři základní struktury: –

molekulární funkce (molecular function; MF)

–

biologické procesy (biological processes; BP)

–

buněčné komponenty (cellular components) Molekulární funkce popisují různé aktivity genových produktů na molekulární 

úrovni;   nepopisují   ovšem   kdy   nebo   kde   se   dějí.   Biologické   procesy   popisují   sérii  prováděných akcí skládající se z více molekulárních funkcí. Buněčná komponenta je  součást buňky (organela) nebo skupina genových produktů. V oblasti GO se hlavní úsilí soustředí na vytvoření a udržování GO, dále jejich  propojení   se   spolupracujícími   databázemi   (DB   obsahující   data   týkající   se   genomu  člověka, zvířat, rostlin, bakterií apod.) a vytvoření nástrojů, které jsou schopné s GO  efektivně   pracovat   nebo   vytvářet   je.   Takováto   sjednocená   platforma   pak   umožňuje  jednotné dotazování napříč spolupracujícími databázemi. GO   výrazy   jsou   strukturovány   tak,   že   je   možné   pomocí   nich   uplatnit   různé  pohledy  na data.  Každý  genový produkt má alespoň  jednu  molekulární funkci  a  je  použitý alespoň v jednom biologickém procesu v alespoň jedné buněčné komponentě.  GO výrazy jsou organizované v orientovaném acyklickém grafu (directed acyclic  graph;   DAG).   Pro   první   představu   si   lze   DAGy   znázornit   jako   větvemi   propletené  orientované stromy – rozdíl oproti jednoduchému stromu je ten, že potomek může mít  více předků; teorií grafů se zde ovšem nebudeme zabývat, pro případ potřeby či zájmu  odkazuji na [10]. V GO platí pravidlo které říká, že pokud nějaký uzel grafu popisuje  nějaký genový produkt, pak tento genový produkt musí popisovat i jeho předchůdce.

31

GO výrazy v každém případě nejsou úplným popisem celé složité struktury a  všech jevů týkajících  se genových  produktů, umožňují nám přiřadit  genům a jejich  produktům   pouze   omezenou   množinu   atributů.   Pomocí   GO   například   není   možné  popsat   v   kterých   buňkách,   jejich   vývojových   stádiích   nebo   jakém   širším   kontextu  (například chorob) se projevují – tyto popisy jsou součástí jiných ontologií určených pro  jiné účely.

32

1.3. Klasifikace  1.3.1. CN2 Algoritmus   CN2   byl   uveden   v   roce   1988   [6],   jeho   princip   je   následující:   při  startu algoritmu máme prázdnou množinu pravidel a dokud existuje prvek v (nějak  neurčitě   definovanou   funkcí   určené)     množině   pravidel   s   výhodnou   hodnotou  výběrového kritéria (tj. jsou vhodná pro tvorbu pravidel), pak odstraníme z množiny  examplů   examply   pokryté   nejlépe   vypadajícím   pravidlem,   a   do   množiny   pravidel  přiřadíme toto pravidlo implikující majoritní třídu těchto examplů. V pseudokódu toto  vypadá přibližně následovně (pro uspořádanou variantu):

def CN2 ( Examples ): # seznam examplů (n-tic s třídou) je vstupem, tj. schematicky: # Examples = [ [ [ att1 ... attn ], class ], ... , ... ] # seznam pravidel je prázdný ListOfRules = empty # získáme nejlepší vhodné pravidlo nebo empty množinu BestRule = GetBestRule(Examples) # dokud není množina examplů prázdná # nebo nejsou žádná vhodná pravidla while ( not Examples.empty() and not BestRule.empty() ): # odstraníme pravidlem pokryté examply E.remove( BestRule.coveredExamples() ) # do seznamu pravidel přidáme na konec pravidlo # indukující majoritní třídů pokrytých examplů ListOfRules.addRuleWithClass( BestRule, BestRule.coveredExamples().getMajorityClass() ) # získáme nejlepší vhodné pravidlo pro další cyklus BestRule = GetBestRule(Examples)

33

Je zjevné, že naprosto rozhodující roli na efektivitu algoritmu bude mít kvalita  volby   funkce   GetBestRule.   CN2   algoritmus   tuto   funkci   implementuje   pomocí  paprskového   prohledávání   tak,   že   si   udržuje   množinu   (paprsek)   nejnadějnějších  pravidel a tyto specializuje dokud to je možné a výhodné. Následující obrázek proces  názorně ilustruje: TRUE

ATT1 op C1

ATT2 op C2 and  ATT1 op C1

ATT2 op C2

ATTn op Cn

ATT2 op C2 and  ATT3 op C3

ATTn op Cn and  ATT2 op C2

Obr. 4 Paprskové procházení stavovým prostorem algoritmu CN2

V   každém   momentu   si   algoritmus   pamatuje   jenom   určité   množství  nejnadějnějších pravidel (podle nějaké hodnotící funkce), které odpovídá šířce paprsku.  Původní implementace CN2 toto realizuje poměrně zbytečně složitým způsobem tak,  že   skladuje   seznam   nadějných   pravidel   na   velikostí   omezené   haldě   a   přebývající  pravidla tedy přepadnou “přes okraj” (první myšlenka jak to realizovat, která se sama  nabízí a může vás taktéž napadnout, ovšem není zrovna správná). Při defaultně malé  šířce paprsku (<10) se ale jinak žádoucí asymptotická výhodnost této metody bezpečně  nijak neprojevuje a realizace pomocí pole by mohla být dokonce výrazně výhodnější.  Pokud   jde   o   to   jak   vypadá   toto   paprskové   prohledávání   v   kódu,   pak   následuje 

34

pseudokód funkce GetBestRule:

def GetBestRule ( Examples, BeamSize ): # seznam examplů (n-tic s třídou) je vstupem, tj. schematicky: # Examples = [ [ [ att1 ... attn ], class ], ... , ... ] # na haldě / v paprsku a ve favoritovi máme triviální selektor Star = { Selector(TRUE) } Star.setBeamSize( BeamSize ) BestComplex = Selector(TRUE) # dokud máme něco na haldě / ve hvězdě while ( not Star.empty() ): # než začneme další turn, poznačujeme si pravidlně # nejlepší komplex na haldě... BestComplex = Star.top() # dále pak vytvoříme novou hvězdu StarNext = {} # přidáme do ní všechny specializace té staré for each Complex in Star: StarNext.add( Complex.getAllSpecializations() ) # provedeme cleanup duplicit a selektorů vybírajících { } StarNext.cleanup() # tím jsme hvězdu updatovali, takže jí dáme původní jméno Star = StarNext # pokud je nějaké pravidlo lepší než náš současný favorit # tak favorita nahradíme for each Complex in Star: if ( Complex.isStatisticallySignificant() and \ Complex.getRankOn(Examples)>BestComplex.getRankOn(Examples) ): BestComplex = Complex # a vyházíme všechno co se nevejde do paprsku Star.shakeOffScrap() # vrátíme to nejlepší, co jsme našli return BestComplex

35

Vidíme,   že   nejdůležitějším   prvkem   zde   bude   funkce   getRankOn(Examples),  která   určí,   která   pravidla   budou   vybrána   a   která   jsou   považovaná   za   zbytečná.  Původní verze algoritmu CN2 se k tomu stavěla tak, že spočítala informační entropii  pro pokryté třídy (1) a signifikanci tohoto pravidla ověřila testem (2):

Entropy=∑C ∈Classes − pC . log pC 

Significance=2 . ∑C∈Classes pC . log

(1)

pC eC

(2)



kde pc značí četnost třídy mezi pokrytými pravidly a ec defaultní četnost odhadnutá z  celé   trénovací   množiny.   Test   signifikance   je   tu   kvůli   tomu,   aby   z   množiny   vylovil  pravidla pro nízce zastupené třídy, jejichž odchylka zastoupení od očekávaného může  být náhodná. Dnes používaný přístup je pomocí laplacovského odhadu chyby, který vypadá  následujícím způsobem (3):

Laplacian=

N examples covered 1

(3)

N examples all Classes

čili počet pokrytých příkladů z predikované třídy (Nexamples   covered) pokrytých pravidlem  plus jedna dělený počtem všech příkladů  patřících do predikované třídy (Nexamples   all)  plus celkový počet tříd (Classes). Ačkoliv   to   v   Clakově   a   Nibbletově   práci[6]   není   zmíněno,   původní   CN2  algoritmus   používá   pro   ohodnocení   pravidla   místo   skaláru   dvojsložkový   vektor  označený     (primus,   secundus),   kde   kvalita   pravidel   se   nejprve   porovnává   podle 

36

primusu, a při shodě ještě podle secundusu. Třebaže secundus byl pravděpodobně při  vývoji zavržen a obsahuje vždy stejnou hodnotu, je jinak zcela úplně implementován a  my   tuto   skutečnost   s   výhodou   využijeme   při   našich   úpravách.   Úpravou   této   části  algoritmu  jsme v této práci vlastně zabývali ponejvíce.

1.3.2. Křížová validace

Křížová   validace   (cross   validation;   CV)   je   metoda   jak   pro   účely   testování  klasifikátoru   využít   soubor   příkladů   na   maximum.   Princip   spočívá   v   tom,   že   si  rozdělíme   soubor   příkladů   na   N   náhodně   vybraných   přibližně   stejně   velkých   částí.  Postupně pak každou z nich vezmeme jako testovací množinu a zbylých N­1 sdružíme  do   množiny   trénovacích   příkladů.   Postupně   se   tak   každý   example   dostane   jak   do  trénovací množiny (N­1­krát) a pak do testovací množiny (jednou). Je to jednoduchý a  efektivní způsob,  jak  zajistit,  aby  výsledky klasifikátoru  nabyly  na důvěryhodnosti.  Experimenty ukázaly, že nejlepší výsledky se dosahují pro N kolem 10 (10­fold CV). Jelikož jde o náhodný proces, tak abychom získali přesnou hodnotu klasifikační  přesnosti   testovaného   klasifikátoru,   je   potřeba   tento   přístup   několikrát   (~100­krát)  zopakovat a výsledky zprůměrovat. Jak je vidět, důsledné uplatnění této metody může  být velmi časově náročné. Jestliže prostá klasifikace examplů na plném rozsahu dat  trvá   v   řádu   minut,   stokrát   opakovaná   10­fold   CV   může   způsobit,   že   výpočet   se  protáhne na desítky hodin.

37

38

2. Metody injekce apriorní znalosti Tématem této práce je klasifikace s apriorní znalostí. Konkrétně pro účely naší  práce jsme vybrali výše popsaný klasifikátor CN2 jako základ, se kterým budeme dále  pracovat a bude obohacen o aspekt zvažování background knowledge při konstrukci  klasifikačních pravidel. V   kapitole   1.3.2.   jsme   si   tento   algoritmus   zevrubně   popsali,   zde   si   tedy  rozebereme, jaké možnosti úpravy se naskýtají. Základ algoritmu jak je zřejmé nemá  smysl příliš upravovat, stejně tak hvězdicové prohledávání; naopak výhodné místo pro  uplatnění dalšího vlivu se jeví vzorec ve funkci getRankOn(Examples) (3), který by  bylo lze obohatit o nějaké další členy; touto cestou jsme se také v této práci vydali. Cílem našich experimentů pak je ověřit klasifikační přesnost na daných datech,  která je slabá díky poměrně malému vzorku dat s velkým počtem atributů (SAGE data  matice řádově 200x11000 ~ 1:55, ALLAML 70x7000 ~ 1:100); takto postavená vzorky  má   klasická   CN2   tendenci   oklasifikovat   sérií   poměrně   krátkých   nepříliš   dobrých  pravidel   (max.   2   atributy;   ale   většinou   pouze   1   atribut);   při   takto   velkém   poměru  atributů   k   situacím   je   totiž   velmi   pravděpodobné,   že   se   náhodně   naleznou  jednoatributová   pravidla   s   velmi   dobrými   výsledky   na   trénovací   množině   (ale   pak  pochopitelně poměrně špatnými výsledky na testovací sadě). Cestou   z   této   situace   se   jeví   použít   background   knowledge   k   tomu,   aby  motivovala  vznik  delších  klasifikačních  komplexů,  které  se pak   –  jak  očekáváme  –  budou chovat na testovací množině lépe. Tímto motivem by mohla být například námi  zvolená metoda, kdy pravidla, která obsahují nějak spřízněné atributy, dostanou nějak  určené   benefity;   vliv   volby   těchto   strategií   na   klasifikační   přesnost   pak   budeme  zkoumat. Pro dokreslení představy, realizace by měla vypadat následovně:

39

–

Algoritmus   CN2   obohatíme   o   další   vstup,   vedle   seznamu   examplů   (a   seznamu  atributů, které se v CN2 zadávají odděleně) přidáme matici podobnosti (similarity  matrix),   která   bude   pro   každé   dva   atributy   obsahovat   číslo   udávající   jejich  příbuznost. Matici podobnosti generujeme právě z background knowledge tak, že  srovnáváme   textové   popisy   jednotlivých   genů   a   na   základě   jejich   podobnosti  určujeme číselnou míru podobnosti těchto dvou genů použitou v CN2 algoritmu.  Podrobněji tento proces v kapitole 2.1. a 2.2.

–

Na   základě   hodnot   v   této   matici   pak   upravíme   hodnotu   funkce  getRankOn(Examples); jednotlivé metody úpravy diskutujeme níže v kapitole 2.3.

2.1. Získání termínů z genových popisů

Genové popisy získáváme z databáze Entrez (viz http://www.ncbi.nlm.nih.gov/).  Pythonovské   skripty   na   stahování   genových   anotací   jsou   umístěné   v   adresáři  scripts/entrez; tyto skripty byly dodány vedoucím práce. Jejich hlubší principy nejsou  pro   naši   práci   příliš   podstatné   a   proto   pro   bližší   informace   odkazuji   na   jejich  příslušnou dokumentaci.

2.2. Získání matice podobnosti

Anotace stažené z Entrezu obsahují klíčová slova, jejichž četnosti zaneseme do  vektoru. Slova, jejichž četnosti ve všech anotacích dohromady nedosahují alespoň pěti  výskytů, jsou vyloučeny. Seznam použitých slov s jejich četnostmi naleznete v souboru  bow_frequency_approved_corrected. Zbude vektor o přibližně 19400 položkách. Těchto 

40

vektorů   máme   podle   použité   sady   dat   cca.   7000   nebo   11000   a   pro   každou   dvojici  spočítáme jejich Czekanowského­Diceovu vzdálenost[8]:

Distance gene1 , gene2=

Card Terms gene1 Terms gene2  Card Terms gene1∪Terms gene2 Card Termsgene1 ∩Termsgene2 

(4)

V   této   formuli   (4)   pak   značí   gene1   a   gene2   geny,   pro   které   se   počítá   vzájemná  vzdálenost,   Terms   jsou   množiny   slov   odpovídající   daným   genům,   Card   je   funkce  určující   kardinalitu   množiny,   Δ   je   symetrická   množinová   diference,   zbylé   dvě  množinové operace myslím není potřeba vysvětlovat. Když   máme   určenou   Czekanowského­Diceovu   vzdálenost,   není   těžké   odvodit  Czekanowského­Diceovu podobnost:

Similarity  gene1 , gene2=1−Distance gene1 , gene2

(5)

Výsledné   hodnoty   jsou   pak   uložené   v   matici   go­functions.bg.txt,     go­ processes.bg.txt   a   allaml.bg.txt.   Z   důvodu   úspory   místa   je   uložena   jenom   horní  trojúhelníková část – tj. jenom hodnoty nad diagonálou, která je logicky nulová; a dále  jsou všechny nulové hodnoty vynechány. Každá hodnota je ukončená čárkou. S touto  formou pak také pracuje upravený algoritmus CN2.

2.3. Úpravy v CN2 S hotovou maticí podobnosti máme několik možností jak podobnostní koeficient  uplatnit ve funkci getRankOf(Examples): 1. Můžeme   ovlivnit   přímo   primus   CN2,   tj.   upravit   rank   (tj.   dvojci   primus­ sekundus) z tvaru (6) na tvar (7)

41

Rank= Laplacian ; 0

(6)

Rank=. Laplacian . Similarity ; 0

(7)

kde Laplacian je nám známý laplacián z kapitoly 1.3.1 o CN2 a Similarity je  funkce   hodnot   vyzískaných   z   matice   podobností   pro   atributy   účastnící   se  komplexu na levé straně pravidla.  Hodnota   Similarity   může   být   též   otázkou   volby   strategie.   Komplex   může  obsahovat větší množství atributů a tak můžeme z jejich vzájemných podobností  vzít například průměr nebo maximum. 1. Průměr je poměrně konzervativní funkce; jakmile je Similarity jednou nízká,  budou ji nové atraktivní atributy poměrně pomalu zvedat: Rank=. Laplacian . Avg Similarity g1 , g2; g1 , g2∈GenesInComplex  ; 0 (8) 2. Maximum je naopak poměrně agresivní; jakmile najde v komplexu dokonale  sehranou   dvojici   atributů,   bude   funkce   jejich   podobnost   vydávat   pro   celý  komplex: Rank=. Laplacian . Max Similarity g1 , g2 ; g1 , g2∈GenesInComplex ; 0 (9) Nastavení   parametrů   α   a   β   pro   obě   varianty   je   dále   předmětem   našich   experimentů. Ještě lze dodat, že při řádově rozsáhlejší úpravě CN2 dále lze (pravděpodobně i  s lepšími výsledky) do Similarity počítat jenom podobnosti nového atributu s  těmi stávajícími; tím se ale v této práci nezabýváme. 2. Můžeme   využít   sekundusu;   v   tomto   případě   se   jako   velmi   výhodné   jeví  kvantizace   primusu,   abychom   zabránili   ideálně   špatnému   případu,   kdy   se   z  pravidel   s   výrazně   rozdílnými   sekundárními   ranky   ale   velmi   podobnými  primárními   vybral   ten   s   jen   málo   lepším   primusem,   zato   výrazně   špatným 

42

sekundusem. Kvantizace byla zvolená ekvidistantní, což sice přirozeně limituje  efektivitu metody, protože mohou nastat obě špatné varianty (v nejvyšší třídě je  kde   co,   a   v   nejvyšší   třídě   je   jenom   velmi   malá   množina   prvků),   na   druhou  stranu     výhodnější   ekvifrekvenční   rozložení   by   znamenalo   další   zvýšení  výpočetní složitosti celého problému, což už je jen těžko únosné. V experimentální části této práce jsme opět vyzkoušeli různě hrubou kvantizaci  a její efekt na kvalitu klasifikace.

Ještě poznámka k samotnému procesu úpravy: Pokud jde o provedení úprav na  CN2, celý kód je napsaný v K&R verzi C, byl většinou sepsán v roce 1989 a jeho vývoj  byl ukončen v roce 1991. Je nutné zmínit, že  velkou slabinou projektu bylo, že kromě  v dnešní době už poměrně silně zastaralého kódovacího stylu a naprosto chaotického  objektového   modelu   (tím   myslím   poněkud   divoké   sdružování   funkcí   do  modulů/objektů, kdy nakonec stejně všechny části všechno vyexportují, což – ne nutně,  ale   v   tomto   případě   se   tak   stalo   –,   vede   k   tomu,   že   se   všechno   nepřehledně   volá  odevšad),   prakticky   jediné   komentáře,   které   zdrojový   kód   obsahuje   jsou  zakomentované části kódu. Tento autorský nešvar se stal chronickou zátěží vývoje a  pokud jde o případné další práce s CN2, velmi silně doporučuji napsat algoritmus od  začátku moderním způsobem například v C++ pomocí templatů (a s dokumentací!), jak  jsme u této práce po zkušenostech s úpravami také zvažovali.

43

44

3. Experimenty Zde se budeme zabývat výsledky jednotlivých běhů experimentů. Jak již bylo  řečeno, k dispozici  jsme používali  SAGE data  s genomickou background  knowledge  získanou z GO  biological processes a cellular components (molecular function nebyla  shledána příliš nadějnou, tak jsme ji vynechali) a ALLAML data. Abychom   se   vyhnuli   velkým   časovým   nákladům,   optimalizovali   jsme   úsilí   s  jakým jsme jednotlivé hodnoty získali. Každý bod byl získán desetkrát opakovanou 5­ CV, což by ovšem mělo postačovat pro poměrně velmi přesný odhad accuracy. I tak  trval výpočet jedné tabulky/grafu na 3GHz & 2GB RAM stroji cca. 15­20 hodin. Pro   grafy   je   použité   následujícího   značení:   Primus/Secundus   podle   místa  injekce, Avg/Max podle funkce nad množinou podobnostních hodnot a následně zdroj  background knowledge.

Primus ­ Avg @ GO Biological Processes 70 60 50 40

Default accuracy Current accuracy

30 20 10 0 0

0,2

0,4

0,6

0,8

1

Graf 1. Kl. přesnost CN2 s bg. knowledge z GO BP injektovanou do primusu

Alfa

0

0,2

0,4

0,6

0,8

1

Beta

1

0,8

0,6

0,4

0,2

0

69,66

69,66

69,46

67,86

63,38

66,63

Accuracy

Tab 1. Kl. přesnost CN2 s bg. knowledge z GO BP injektovanou do primusu 45

Znovu   připomínám,   že   parametr   α   platí   pro   laplacián   a   β   pro   injektovaný  koeficient   odvozený   z   podobnosti.   Z   těchto   prvních   výsledků   je   vidět,   že   nejlepších  výsledků   CN2   dosahuje   při   naprosté   resp.   téměř   naprosté   akceptaci   background  knowledge a úplném resp. téměř úplném pominutí laplaciánu. Totéž je vidět i z druhého grafu výsledku experimentu lišícího se komponentou  GO, ze které byla získána background knowledge.

Primus ­ Avg @ GO Molecular function 70 60 50 40

Default accuracy Current accuracy

30 20 10 0 0

0,2

0,4

0,6

0,8

1

Graf 2. Klasifikační přesnost CN2 s bg. knowledge z GO MF injektovanou do primusu Alfa

0

0,2

0,4

0,6

0,8

1

Beta

1

0,8

0,6

0,4

0,2

0

67,8

66,8

64,9

64,9

63,9

66,8

Accuracy

Tab 2. Klasifikační přesnost CN2 s bg. knowledge z GO MF injektovanou do primusu

Z následujících   výsledků (graf 3­4,  tab.  3­4)  je patrné,  že  funkce  i maximum  dává   poměrně   dobré   výsledky,   tentokráte   ovšem   naopak   spíše   na   background  knowledge z molecular function.

46

Primus ­ Max @ GO Biological Processes 70 60 50 40

Default accuracy Current accuracy

30 20 10 0 1

0,8

0,6

0,4

0,2

0

Graf 3. Klasifikační přesnost CN2 s bg. knowledge z GO BP injektovanou do primusu Alfa

0

0,2

0,4

0,6

0,8

1

Beta

1

0,8

0,6

0,4

0,2

0

67,8

67,8

67,8

67,8

62

66,8

Accuracy

Tab 3. Klasifikační přesnost CN2 s bg. knowledge z GO BP injektovanou do primusu

Primus ­ Max @ GO Molecular function 70 60 50 40

Default accuracy Current accuracy

30 20 10 0 1

0,8

0,6

0,4

0,2

0

Graf 4. Klasifikační přesnost CN2 s bg. knowledge z GO MF injektovanou do primusu Alfa

0

0,2

0,4

0,6

0,8

1

Beta

1

0,8

0,6

0,4

0,2

0

69,8

69,8

69,6

65,5

66,7

66

Accuracy

Tab 4. Klasifikační přesnost CN2 s bg. knowledge z GO MF injektovanou do primusu

47

Primus ­ Avg @ ALLAML 90 80 70 60 Default accuracy

50

Current accuracy

40 30 20 10 0 1

0,8

0,6

0,4

0,2

0

Graf 5. Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do primusu Alfa

0

0,2

0,4

0,6

0,8

1

Beta

1

0,8

0,6

0,4

0,2

0

88,9

88,9

88,9

88,9

87,92

87,64

Accuracy

Tab 5. Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do primusu

Primus ­ Max @ ALLAML 90 80 70 60 Default accuracy

50

Current accuracy

40 30 20 10 0 1

0,8

0,6

0,4

0,2

0

Graf 6. Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do primusu Alfa

0

0,2

0,4

0,6

0,8

1

Beta

1

0,8

0,6

0,4

0,2

0

89,46

89,46

89,46

89,46

89,18

86,66

Accuracy

Tab 6. Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do primusu

48

Tabulky 5,6 a grafy 5,6 ukazují, jak se klasifikační přesnost zlepšuje při použití  vyššího β­koeficientu; na všech použitých datech se tedy ukázalo, že použití  background knowledge má své opodstatnění při vylepšování klasifikační přesnosti. Naopak injekce background knowledge do secundusu se ukázala jako poměrně  kontroverzní čin. Výsledky jsou sice ještě relativně dobré, ale nevykazují žádnou  tendenci ke zlepšení. S malou odchylkou pro “nula tříd” (= žádná kvantizace primusu),  dokonce pro GO data přinesly všechny experimenty stejné hodnoty (tab., graf 7) – toto  si vysvětlujeme jako důsledek poměrně hrubé metody kvantizace, kdy z většího  množství pravidel bylo pravidelně vybráno několik s nejlepším sekundusem (např.  vzájemně spřízněné) a tyto pravidla pak při každém běhu experiementu vedla na  specifický výsledek. Přesto je výsledek lepší než výsledek originální CN2 (~66%).

Secundus ­ Avg/Max @ GO BP/MF 70 60 50 40

Current accuracy Default accuracy

30 20 10 0 0

1

2

3

5

10

20

Graf 7. Kl. přesnost CN2 s bg. knowledge z GO BP/MF injektovanou do secundusu Počet tříd

0

1

2

3

5

10

20

Accuracy

68,8

68,3

68,3

68,3

68,3

68,3

68,3

Tab 7. Kl. přesnost CN2 s bg. knowledge z GO BP/MF injektovanou do secundusu

Ani na ALLAML datech se injekce do secundusu příliš dobré výsledky nepřináší  (tab., grafy 8­9) , zejména pak v případě injekce bez kvantizace primusu (ale i tento 

49

výsledek je však lepší než výsledek základní CN2).

Secundus ­ Avg @ ALLAML 90 80 70 60 Current accuracy

50

Default accuracy

40 30 20 10 0 0

1

2

3

5

10

20

Graf 8. Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do secundusu Počet tříd Current accuracy

0

1

2

3

5

10

20

87,36

87,78

87,78

87,78

87,78

87,78

87,78

Tab 8. Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do secundusu

Secundus ­ Max @ ALLAML 90 80 70 60 Current accuracy

50

Default accuracy

40 30 20 10 0 0

1

2

3

5

10

20

Graf 9. Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do secundusu Počet tříd Current accuracy

0

1

2

3

5

10

20

88,06

88,76

88,76

88,76

88,76

88,76

88,76

Tab 9. Kl. přesnost CN2 s bg. knowledge z ALLAML injektovanou do secundusu

50

Tato   metoda   však   může   být   silně   poznamenaná   způsobem   kvantizace.   Proto  zůstává otázkou, zda nějaká šetrnější kvantizace (např. volba rozdělení do podobně  velkých   tříd   ~   ekvifrekvenční   intervaly;   nebo   jemnější   kvantizační   intervaly)   by  nepřineslo   lepší   výsledky.   V   použité   metodě   (ekvidistantní   intervaly)   se   nejvyšší  interval  může   jak   zahltit   velkým  množstvím   pravidel,  která   nejsou   až  tak   kvalitní  (“dobrá” varianta; pak se vybírá na základě secundusu s background knowledge), ale  také může nastat situace, kdy je v něm jen několik nebo v ideálně špatném případě  jenom jeden člen, který je pak vždy vybrán.

Graf 10. Kl. přesnost CN2 s feature selection

51

Pro srovnání klasifikační přesnosti s CN2 s feature selection (výběr atributů z  původní   množiny   na   základě   GainRatio)   na   SAGE   datech   viz   graf   10.   Maximální  přesnost je dosažena kolem 100 atributů/features, kdy accuracy dosahuje cca 75%. Na  těchto datech je CN2 s injekcí do primusu  schopná dosáhnout maximální accuracy jen  kolem 70%.

52

4. Závěr Bakalářská   práce   zkoumá   vliv   injekce   apriorní   znalosti   do   algoritmu   CN2.  Nejprve čtenáře uvede obecně do problematiky genetiky a genomických dat, následně  představí použitý klasifikátor, algoritmus CN2. Dále rozebírá jeho úpravy, přípravu a  výsledky experimentů. Z   výsledků   experimentů   je   patrné,   že   použití   apriorní   znalosti   zlepšuje  klasifikační přesnost algoritmu CN2: pro první z navržených metod (injekce do tzv.  primusu – primárního kritéria řazení navržených pravidel) jsou výsledky nadějné a  zdá se, že má smysl je rozpracovávat s adekvátně upravenou CN2 (nejlépe pro tento  účel napsanou) podle návrhů představených v experimentální části této práce. Druhá  metoda (kvantizace + injekce do secundusu – sekundárního kritéria řazení navržených  pravidel) se naopak jeví jako problematická a nezdá se, že by stála za další pozornost.

53

A. Seznam zkratek Zkratka

Anglická verze

Česká verze*

A

Adenine

Adenin

ALL

Acute Lymphocytic Leukemia

Akutní lymfocytická leukémie

AML

Acute Myelogenous Leukemia

Akutní myeloidní leukémie

BP

Biological processes

Biologické procesy

C

Cytosine

Cytosin

CV

Cross­validation

Křížová validace

DAG

Directed acyclic graph

Orientovaný acyklický graf

DB

Database

Databáze

DM

Data mining

Dolování dat

DNA

Deoxyribonucleic Acid

Deoxyribonukleová kyselina

G

Guanine

Guanin

GO

Gene ontology (project)

KDD

Knowledge discovery in databases

Objevování dat v databázích

MF

Molecular function

Molekulární funkce

MRNA

Messenger ribonucleic acid

Messangerová ribonukleová kyselina

RNA

Ribonucleic acid

Ribonukleová kyselina

SAGE

Serial Analysis of Gene Expression

T

Thymine

Thymin

U

Uracile

Uracil

* pokud to má smysl

54

B. Reference 1. International Human Genome Sequencing Consortium (2004); "Finishing the  euchromatic sequence of the human genome."; Nature 431:  str. 931­45 2. Michele Clamp (2007); "Working the (Gene Count) Numbers: Finally, a Firm  Answer"; Science 316:  str. 1113 3. Watson J.D., Baker T.A., Bell S.P., Gann A., Levine M., Losick R. (2004);  “Molecular Biology of the Gene, 5th. edition”; Cold Spring Harbor Laboratory  Press 4. Fulton A., Isaacs W. (1991); "Titin, a huge, elastic sarcomeric protein with a  probable role in morphogenesis"; Bioessays 13: 157­61 5. Kaisner D.; “Dolování biomedicínských dat”; diplomová práce; ČVUT FEL 6. Clark P., Niblett T. (1989); “The CN2 Induction Algorithm”; Machine Learning  Journal 261­283 7. Clark P., Niblett T. (1991); “Rule Induction with CN2: Some Recent  Improvements”; Machine Learning ­ Proceedings of the Fifth European  Conference; 151­163; Springer­Verlag 8. Martin et al (2004); “GOToolBox: functional analysis of gene datasets based on  Gene Ontology”; Genome Biol. 2004 http://www.pubmedcentral.nih.gov/articlerender.fcgi?tool=pubmed&pubmedid= 15575967 9. Ng R. T., Sander J., Sleumer M.C.; “Hierarchical cluster analysis of SAGE data  fro cancer profiling”;  ahttp://www.cs.rpi.edu/~zaki/BIOKDD01/ng.ps.gz 10. Demel J.; 2002; “Grafy a jejich aplikace”; Academia

55

56

C. Příloha I. Obsah přiloženého média ./bin

# adresář s cn2; jelikož neumí pracovat s cestami, je potřeba # ji mít i v adresáři s daty ./bin/cn # cn2 ./bgk # adresář s maticemi similarit ./bgk/addcommas.sh # skript na přidávání koncových čárek – v cn2 vyžadujeme, aby # hodnoty v matici čárkou končily, nikoliv aby byly jenom # odděleny ./bgk/go-processes.bg.txt ./bgk/go-functions.bg.txt ./bgk/allaml.bg.txt ./cncom # dávkové příkazy pro CN2 ./data # adresář se soubory atributů a příkladů; cn2 a py-skripty # kvůli chybě v cn2 je potřeba to mít takto nahuštěné ./docs ./docs/bakalarka # adresář s touto prací ./docs/vysledky # výsledky měření... ./intro # původní materiál od vedoucího práce ./log # adresář kam se ukládají temporary log fily ./src # zdrojové ksoubory CN2 ./src/cn_header.h # hlavičkový soubor s nadeklarovanými metodami ./src/peccles.c # soubor s částí ködu, kam byla do CN2 injektovaná bg. kn-dge ./src/Makefile # Makefile: make; make clean ./src/main.c # hlavní zdrojový kód CN2; úpravy interfacu

57

II. Popis částí zdrojového kódu Skripty   jsou   popsány   samostatně,   pokud   jde   o   samotnou   CN2,   dvě   hlavní   ohniska  úprav,   v   main.c   a   peccles.c   jsou   v   místě   myslím   pochopitelně   okomentované.  Nejzajímavější částí nového kódu je asi místo, kam se umístila background knowledge.  Kód   je   dokomentován   včetně   původních   nekomentovaných   úseků,   pro   kompaktnost  většinou anglicky; debug reporty jsou vynechané.

void BGK_RANK (Node *node, Rank *potential, int lapA, int lapB, int lapC) { /////////////////////// // BGK injection... // - 1. define vars int i,j; int DBG=0; // what value will be used double BGK_COEF = 0.0; // various methods for obtaining bgk_coef double SUMOFSIM = 0.0; int NUMOFSIM = 0; double AVGOFSIM = 0.0; double MAXOFSIM = 0.0; // - 2. get list of attributes involved in current rule int *ATTRLIST = malloc(sizeof(int)*number_of_attributes); int ATTRLIST_SZ = 0; // vyber atributu, kterych se tyka pravidlo do listu (z masky) for (i=0;iselector[i].setp!=0) ATTRLIST[ATTRLIST_SZ++]=i; } // ATTRLIST ted obsahuje seznam atributu v pravidlu (velikost ATTRLIST_SZ) // - 3. get distances of these attributes and count candidates for // bgk_coef for (i=0;iBGK_MATRIX_SZ||y>BGK_MATRIX_SZ) { // ignore it ! //fprintf(stddebug,"index too high..."),exit(-1);

58

} else if (i<j) { // debug SUMOFSIM+=BGK_MATRIX[x][y]; NUMOFSIM++; if (BGK_MATRIX[x][y]>MAXOFSIM) MAXOFSIM = BGK_MATRIX[x][y]; } }

}

free(ATTRLIST);

// we don't need it anymore; it is good just // for decreasing complexity of (3.) from // o(n^2) to ~o(n)

// - 4. - choose method for counting BGK coef. (bgk_coef) // from distance matrix (ME_COUNTING_BGK_COEF) switch (ME_COUNTING_BGK_COEF) { case AVG_OF_SIM: // bgk_coef is average of similarities if (NUMOFSIM) BGK_COEF = SUMOFSIM / NUMOFSIM; else BGK_COEF = 0.0; break; case MAX_OF_SIM: // bgk_coef is minimum of similarities default: BGK_COEF = MAXOFSIM; break; } // - 5. - inject BGK into primus (laplacian) or secundus if (ATTRLIST_SZ==0) { // we are choosing first attribute // get laplacian... potential->primus = (lapA + 1.0) / (lapB + lapC); // and secundus isn't used potential->secundus = -1.0; } else { // methods for injecting BGK coef. (bgk_coef) into // CN2 (ME_INJECTING_BGK_COEF) switch (ME_INJECTING_BGK_COEF) { case BGK_IS_IN_LAPLACIAN: // get laplacian... potential->primus = (lapA + 1.0) / (lapB + lapC); // potential->primus = (maximum_count + 1.0) / // (maximum_count + number_of_classes); // change it to alpha * laplacian + beta * // bgknowledge potential->primus = BGK_IS_IN_LAPLACIAN_ALPHA * potential->primus + BGK_IS_IN_LAPLACIAN_BETA * BGK_COEF; // secundus isn't used potential->secundus = -1.0; break; case BGK_IS_IN_SECUNDUS: default:

59

}

// get laplacian... potential->primus = (lapA + 1.0) / (lapB + lapC); // potential->primus = (maximum_count + 1.0) / // (maximum_count + number_of_classes); if (BGK_IS_IN_SECUNDUS_NCLASSES) { // quantize it to // BGK_IS_IN_SECUNDUS_NCLASSES classes ; // -0.001 ~ we don't want N+1 classes potential->primus = ( (int)(BGK_IS_IN_SECUNDUS_NCLASSES * potential->primus 0.001) )/BGK_IS_IN_SECUNDUS_NCLASSES;; } // bgknowledge write to the secondus potential->secundus = BGK_COEF; break;

} // BGK injection... /////////////////////// }

60

III. Popis instalace a spouštění CN2 V   adresáři   sources   je   přítomný   upravený   Makefile,   takže   pro   zkompilování  zdrojového kódu stačí zadat příkaz make a pro vyčistění nepořádku po kompilaci make clean.  Základní   verze   CN2   bez   injektované   background   knowledge   se   spouští   z  hlavního adresáře jednoduše cn. Rozšířená verze má tyto argumenty:

-bg filename # jméno souboru s matici podobnosti -sz size

# velikost matice

-cnt avg|max # způsob výpočtu koeficientu -inj pri|sec # způsob injekce – do primus-u nebo secundus-u -a alpha

# alfa koeficient (pri)

-b beta

# beta koeficient (pri)

-cl nclasses # počet tříd do kterých proběhne kvantizace (sec) -r 0|1

# tištění indukovaných pravidel (default=ano=1)

Spouštění pak může vypadat například takto:

cn -bg go-fs.bg.txt -sz 5051 -inj pri -cnt avg -a 0.2 -b 0.8 -r 1

61

IV. Popisy přiložených skriptů Opět   se   zde   nebudeme   zabývat   všemi   skripty,   které   byly   při   práci   použity.  Klíčové   jsou   zejména   dva   skripty   cv_pri.py   a   cv_sec.py,   pomocí   kterých   byla  shromážděna data z experimentů. Oba jsou to forky jednoho z původních skriptů z  intra (cross_validate_cn2.py) upravené tak, aby mohly pohodlně fungovat vedle sebe  (třebaže  uznávám není to příliš  ideální  stav [drátování  parametrů v kódu], ale mj.  počet   parametrů   skriptu   je   takový,   že   jejich   management   v   řádce   je   poměrně  neefektivní). Následuje popis jedno z nich:

Nastavíme sílu CV: ## the number of folds - the key parameter FOLDS=5

10x provedeme CV nad souborem s examply: for I in range(0,10): NCV('../data/SAGE.exs',FOLDS)

V   NCV   nejdříve   rozdělíme   soubor   s   examply   na   FOLDS   částí   a   následně   z   nich  zbudujeme train_pri_$.exs a test_pri_$.exs soubory pro CV (kde $ značí číslo sady): def NCV(filename,trials): rows=len(my_data) ## get random indeces indeces=get_indeces(rows,trials) ## generate and run for trial in range(1,trials+1): ## generate new training and testing files generate_data_4BATCH(my_data,indeces,'./',trial)

62

Následně nastavíme počet měření a spustíme jejich výpočty: N=6 for I in range(0,N): print('EXP'+str(I)+':') K=I/float(N-1) # run test cmd= 'cn -bg ../bgk/go-functions.bg.txt -sz 5051 -inj pri ' + '-cnt max -a '+str(K)+' -b '+str(1-K)+' -r 1' + ' <../cncom/cn.cv-commands-5cv-pri' + ' >../log/cn_pri_'+str(I)+'.log' print(cmd) status = os.system(cmd) parse_log('../log/cn_pri_'+str(I)+'.log',I,0)

Funkce   parse   log   vyhodí   výstup,   který   se   nejlépe   při   spuštění   skriptu   někam  přesměruje/uloží. Při hromadném zpracování do ní pak byl přidán řádek s tiskem na  hvězdičkou vyznačený řádek, který se dal snadno vygrepovat a efektivně zpracovat v  navazujícím řetězci ad­hoc shell skriptů.

Další skripty, které byly použity jsou skripty pro shromažďování apriorní znalosti a  skripty generující matici podobnosti: generate_bag_matrix.py  ;   který   generuje   pickle   soubor   (serializovanou   python  strukturu)  TFIDF_distance_effective_pickle.py trojúhelníkovou matici podobnosti

63

;   který   z   pickle   formy   vygeneruje