Naprogramujte bioinformaticky skript, ktery na vstupu dostane geneticke informace o sade organismu a na jejich zaklade do vystupniho souboru vyrenderuje fylogeneticky strom, tedy strom korespondujici s evolucnim vyvojem organismu. Pracujme na zaklade hypotezy, ze cim podobnejsi jsou geneticke informace dvou genetickych organismu, tim blize by organismy mely byt ve fylogenetickem stromu. Ten vypada tak, ze listy jsou nase organismy, zatimco vnitrni uzly jsou hypoteticke, jiz davno vymrele "vyvojove clanky". Jako geneticke informace nebudeme pouzivat cele genomy, ale pouze vybrane geny, o kterych biologove zjistili, ze dobre reflektuji vyvoj druhu; budeme se soustredit na obratlovce a gen HOX-A1 (http://kam.mff.cuni.cz/~pasky/autophylo-ex.tar.gz, ex_hoxa1/), ktery ridi ranny embryonalni vyvoj ("clankovani" organismu atd.). "Gen" je pak proste posloupnost bazi, tedy /^[ACTG]*$/i. Uzivatelske rozhrani vaseho skriptu by mohlo byt treba: phylo.sh [-h] [-o OUTPUT] DNAFILE... Kdyz skript uvidi parametr -h, vypise pouze help; -o zmeni jmeno vystupniho obrazku z defaultniho tree.png; zbyle parametry jsou soubory s genetickymi informacemi jednotlivych zviratek. Neco vice o algoritmu. Prvni legitimni otazka je, jak merit podobnost dvou genu; musime si uvedomit, jak se vlastne geny mohou menit, tzn. mutovat. Bud se muze nejaka baze zmenit, nejaka navic objevit, nebo naopak nejaka zmizet. Zajimava mira je tedy editacni vzdalenost, kterou snando ziskame prikazem diff (nejdrive si baze rozdelime na zvlast radky, treba pomoci `sed s/./&\n/g`). Ovsem mutace mohou vypadat i jinak, napriklad se muze cely jeden segment genu nekolikrat cely rozkopirovat. Abychom pochytili i takove zmeny, jako zajimava mira vychazi |gzip(A + B)| / (|gzip(A)| + |gzip(B)|) kde A + B je zretezeni genu A a B. Na cviceni jsme zkouseli vzorecek interpretovat a zminovali souvislost s kolmogorovskou nahodnosti. Dle nasi hypotezy by v nasem strome mely byt primarne hrany odpovidajici vysoce podobnym genum. Pokud si spocteme vzdalenosti kazdych dvou paru organismu a vyslednou matici interpretujeme jako uplny graf, zajimavou zacne byt moznost takovy strom interpretovat jako minimalni kostru tohoto uplneho grafu. Jen si musime rozmyslet, jak nakladat s vnitrnimi uzly (uznal bych vsak i pekne reseni bez "virtualnich" vnitrnich uzlu). Mame-li strom, jak jej vyrenderovat do pekneho obrazku? Soucasti popularniho baliku nastroju GraphViz je nastroj dot, ktery snadno umi renderovat hierarchicke grafy: cat ex_hoxa1/realtree.dot | dot -Tpng >tree.png Poznamky: (i) Uloha je pomerne rozsahla; nepanikarte, rozdelte si ji na jednotlive podulohy a nad kazdou zkuste zapremyslet a naimplementovat ji zvlast. (ii) Potrebujete-li merit velikost souboru, misto parsovani vystupu ls nebo findu muzete pouzit `stat -c +%s`. (iii) Pro snadnou praci s UNIXovymi nastroji je nejlepe vybrat si nebo vhodne zkombinovat dve moznosti ukladani datovych struktur - posloupnost strukturovanych radek a mnozina malych souboru v nejakem podadresari. Prve se hodi na davkove zpracovani (trideni, iterace), druhe na primy pristup (ve stylu pole, nechceme-li pouzivat bashova rozsireni nebo awk). (iv) Tedy konkretneji, chceme-li implementovat treba Kruskaluv algoritmus na minimalni kostru, setridime si seznam hran a pak postupne zkousime kazdou hranu pridat - to selze, pouze pokud vede v ramci stejne komponenty. Informaci o komponentach si muzeme ukladat v malych souborech zvlast pro jednotlive uzly, v pripade slouceni dvou komponent pak muzete shellovym globem snadno proiterovat vsechny soubory a informaci o komponente upravit. A nebo to cele muzete udelat nejak jinak! (v) Samozrejme muzeme diskutovat o tom, jestli ze spoctenych dat nedokazeme nakreslit vernejsi strom jinym postupem, nez nasim naivnim stavenim minimalni kostry. Mnoho algoritmu, ktere se snazi aproximovat a modelovat realitu (at uz ditherujeme obrazek nebo ucime neuronovou sit), je zalozeno na principu minimalizace celkove chyby vytvoreneho modelu oproti skutecnosti. Zlepsovani algoritmu je samozrejme zcela nad ramec nasi pisemky, zajimaji-li Vas vsak algoritmy a datove struktury, bioinformatika nebo umela inteligence, zkuste se nad problemem zamyslet treba z tohoto uhlu.