David Nohejl Vývojové stromy

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁSKÁ PRÁCE

David Nohejl Vývojové stromy

Katedra aplikované matematiky

Vedoucí bakalá°ské práce: RNDr. Ond°ej Pangrác, Ph.D.

Studijní program: Informatika

Studijní obor: Obecná informatika

Praha 2012

Cht¥l bych pod¥kovat svojí rodin¥ a p°átel·m za podporu b¥hem mých studií.

Dal²í díky pat°í vedoucímu práce RNDr. Ond°eji Pangrácovi, Ph.D. za jeho tr- p¥livost, poskytnutí literatury a cenných rad, které mi pomohly p°i psaní této práce.

Prohla²uji, ºe jsem tuto bakalá°skou práci vypracoval samostatn¥ a výhradn¥

s pouºitím citovaných pramen·, literatury a dal²ích odborných zdroj·.

Beru na v¥domí, ºe se na moji práci vztahují práva a povinnosti vyplývající ze zákona £. 121/2000 Sb., autorského zákona v platném zn¥ní, zejména skute£nost, ºe Univerzita Karlova v Praze má právo na uzav°ení licen£ní smlouvy o uºití této práce jako ²kolního díla podle Ÿ60 odst. 1 autorského zákona.

V Praze dne 2.8.2012 David Nohejl

Název práce: Vývojové stromy Autor: David Nohejl

Katedra: Katedra aplikované matematiky

Vedoucí bakalá°ské práce: RNDr. Ond°ej Pangrác, Ph.D., Informatický ústav Uni- verzity Karlovy

Abstrakt: Vývojové stromy jsou grafy znázor¬ující p°íbuzenské vztahy mezi enti- tamy. V této práci prezentuji vlastní program WPF Trees. Ten slouºí k práci se st°edn¥ velkými stromy (do 500 uzl·), a implementuje nejpouºívan¥j²í zobrazova- cí styly a edita£ní nástroje. Také se v¥nuji aplikaci metody simulovaného ºíhání na problém minimalizace p°ekrývaní popisk· list· stromu.

Klí£ová slova: vývojové stromy, vizualizace, software, simulované ºíhání

Title: Phylogenetic trees Author: David Nohejl

Department: Department of applied math

Supervisor: RNDr. Ond°ej Pangrác, Ph.D., Computer Science Institute of Charles University

Abstract: Phylogenetic trees are graphs representing relations between entities.

In this work, we present our program WPF Trees. This program works with medium sized trees (up to 500 nodes), and implements most common visualization styles and editing tools. We are also describing how to apply simulated annealing method to minimize overlapping of tree node labels.

Keywords: phylogenetic trees, visualization, software, simulated annealing

Obsah

1 Úvod 2

1.1 Známé výsledky . . . 2

1.2 Cíl práce . . . 2

1.3 Struktura práce . . . 3

2 P°ehled srovnatelných produkt· 4 2.1 Archaeopteryx . . . 4

2.2 Tree View . . . 6

2.3 Interactive Tree of Life . . . 6

2.4 HyperTree . . . 7

2.5 Drawgram/Drawtree . . . 8

2.6 Phylodendron . . . 9

3 Popis implementace 11 3.1 Implementa£ní technologie . . . 11

3.2 Základní struktura aplikace . . . 11

3.3 Parser . . . 14

3.4 Styly zobrazení strom· . . . 15

3.5 Stromové operace . . . 21

3.6 Uºivatelské rozhraní . . . 24

3.7 Optimalizace umíst¥ní popisk· . . . 25

3.8 Workspace . . . 28

4 Uºivatelská dokumentace 30 4.1 Instalace a spu²t¥ní programu . . . 30

4.2 Uºivatelské rozhraní . . . 30

4.3 Uºivatelská nastavení . . . 32

4.4 P°íklad . . . 32

5 Záv¥r 34 Seznam pouºité literatury 35 P°ílohy 37 5.1 Obsah p°iloºeného CD . . . 37

1. Úvod

Vývojové stromy jsou diagramy znázor¬ující p°íbuznost entit. íká se jim den- drogramy. V listech (a n¥kdy i ve vnit°ních uzlech) jsou Taxonomické Opera£ní Jednotky (OTU-Operational Taxonomical Unit) - to jsou typicky biologické dru- hy. Dendrogram je graf, který spojuje OTU prost°ednictvím v¥tví s uzly, které re- prezentují hypotetické spole£né p°edky propojených OTU a jsou navzájem dal²ími spojnicemi propojeny s p°edchozí 'generací' spole£ných p°edk·, reprezentovaných uzly hloub¥ji uvnit° stromu.- F. Cvr£ková v [8]

Znalost p°íbuznosti mezi ºivo£i²nými druhy je pro lidstvo d·leºitá z mnoha d·vod·. Na základ¥ p°íbuznosti vir· lze efektivn¥ji vyvíjet nové léky, genové in- ºenýrství vytvá°í odoln¥j²í a produktivn¥j²í plodiny. . . Podobných vyuºití t¥chto znalostí najdeme mnohem více.

P°íbuznost organism· se stanovuje na základ¥ podobnosti DNA. Poté se z mati- ce vzdáleností vývojové stromy konstruují typicky dynamickým programováním.

Celou problematiku dob°e shrnuje práce [9].

1.1 Známé výsledky

Pouºívá se n¥kolik styl· jak vývojové stromy zobrazovat, ve 2D i 3D. Existují programy zam¥°ené na vizualizaci vývojových strom·, z nichº nejznám¥j²í je Tre- eView, a dále se o nich pojednává v Kapitole 2. S nedostatkem plochy pro nakres- lení celého stromu se bojuje s vyuºitím t°etího rozm¥ru a technik focus+context (viz t°eba [11]).

Co chybí Jsem toho názoru, ºe chybí aplikace cílené na mén¥ `v¥decky` za- m¥°eného uºivatele (t°eba u£itele nebo studenty st°edních ²kol, paleontologické nad²ence bez formálního vzd¥lání, apod.). Samotnou vizualizací vývojového stro- mu práce nekon£í. Pro správnou interpretaci vztah· zobrazených dendrogramem záleºí na po°adí uzl· ve stromech, popiscích, dodate£né gracké úprav¥, apod.

Typicky se proto p°ed publikací výstupy z program· je²t¥ upravují v grackém editoru. Mnoho úprav by se ale lépe d¥lalo na úrovni aplikace která 'rozumí' zobrazovaným dat·m, a ne v obecném grackém editoru.

1.2 Cíl práce

V této práci popisuji aplikaci ur£enou k vizualizaci vývojových strom· do veli- kosti okolo 1000 OTU, s uºivatelsky p°ív¥tivým grackým rozhraním a ²irokými edita£ními moºnostmi pro publikaci. Zabývám se také automatickou optimalizací umíst¥ní popisk· vývojových strom· metodou simulovaného ºíhání.

1.3 Struktura práce

V textu této práce nejprve nabídnu p°ehled existujících program·, a porovnám je s mojí aplikací v Kapitole 2.

Následuje popis implementace v Kapitole 3, kde se zabývám celkovou struktu- rou aplikace, parserem vstupních dat, implementací jednotlivých styl· zobrazení, operacemi se stromy, komponentami uºivatelského rozhraní a optimalizací umís- t¥ní popisk·. Kapitola obsahuje také zd·vodn¥ní mých návrhových rozhodnutí a zku²enosti s danou technologií a algoritmy.

V Kapitole 4 následuje návod k instalaci, popis rozhraní mojí aplikace a p°í- klady pouºití.

V záv¥ru p°ijde shrnutí dosaºených výsledk· a nastín¥ní moºných sm¥r· dal²í práce.

Pokud není uvedeno jinak, jsou obrázky v práci screenshoty z mojí aplikace.

2. P°ehled srovnatelných produkt·

Pot°eba prezentovat vývojové stromy je stejn¥ stará jako evolu£ní teorie. Exis- tuje tedy mnoºství program·, které se tímto úkolem zabývají.

Obrázek 2.1: Ilustrace z Darwinovy On the Origin of Species by Natural Selection, 1859. [Zdroj:Wikipedie]

V této kapitole se v¥nuji n¥kolika program·m vizualizujícím vývojové stromy.

Snaºil jsem se vybrat ty nejd·leºit¥j²í £i n¥£ím zajímavé. Není to vý£et ani zdaleka úplný.

Mým hlavním zdrojem program· vizualizujících vývojové stromy je seznam List of phylogenetic tree visualization software [2] na Wikipedii. Krom¥ klasických aplikací uvádím i webové aplikace.

Poznámka Styly implementované v mojí aplikaci (Rectangular, Radial, Cla- dogram) jsou podrobn¥ popsány v sekci 3.4. V této kapitole je nepopisuji, jen uvádím, jak se odpovídající styly jmenují v r·zných programech.

2.1 Archaeopteryx

Jedná se jak o online applet, tak samostatnou aplikaci v Jav¥. Je to nástupce programu ATV [18]. Podporuje mnoºství styl·:

Circular Styl Circular, na obrázku 2.2 Rectangular Styl Rectangular

Rounded Jako styl Rectangular, ale se zaoblenými rohy Unrooted Styl Radial

Euro style Ukázka stylu je na obrázku 2.3 Curved Ukázka stylu je na obrázku 2.4

Convex Ukázka stylu je na obrázku 2.5

Obrázek 2.2: Styl Circular [Zdroj: screenshot z aplikace Archaeopteryx]

Obrázek 2.3: Styl Euro [Zdroj: screenshot z aplikace Archaeopteryx]

Obrázek 2.4: Styl Curved [Zdroj: screenshot z aplikace Archaeopteryx]

Obrázek 2.5: Styl Convex [Zdroj: screenshot z aplikace Archaeopteryx]

Archaeopteryx umí zobrazovat data z externích dataset· (nap°íklad obrázky).

Má také dob°e zpracované zoomování.

Jako výstupní formáty umí PDF, PNG, GIF, a JPG. Vstup jsou krom¥ soubor·

ve formátu Newick také phyloXML, Nexus a dal²í.

2.2 Tree View

Klasická aplikace, která byla vyvíjena v letech 1995-2000. Je zdarma ke sta- ºení na [19] a vy²el o ní £lánek [15]. Aplikace je ur£ená pro platformy Microsoft Windows a Apple Macintosh.

Produkuje obrázkový výstup ve fromátu WPF pro Windows a PICT pro Ma- cintosh.

Umí 4 zobrazovací styly:

Radial styl Classic Radial, vylep²ený algoritmem 'equal daylight'¹ Slanted cladogram Styl Cladogram

Rectangular cladogram Styl Rectangular

Phylogram Styl Rectangular, beroucí v potaz ohodnocení hran

TreeView umoºnuje základní formátování (bold/italic, fonty, velikosti písma), podporu pro copy & paste, drag & drop. Lze zobrazit popisky vnit°ních uzl·.

Sou£ástí programu je editor, který umí p°esouvat v¥tve strom·, °adit podstro- my podle hloubky (operace ladderize), zm¥nu ko°ene (reroot), a 'sbalení' pod- stromu (collapse). V²echno d¥lá se strukturou stromu, je ur£en k vytvo°ení nové topologie, a ne k dodate£ným úpravám p°ed tiskem (publikací).

shrnutí Moje aplikace má bohat²í edita£ní schopnosti, zatímco TreeView má (p°edev²ím díky 'equal daylight' algoritmu) kvalitn¥j²í výstup pro v¥t²í stromy.

2.3 Interactive Tree of Life

Tento projekt sídlí na webové adrese http://itol.embl.de/. Vy²ly o n¥m studie [12] a [13].

Interactive Tree of Life (ITOL) poskytuje 3 zobrazovací styly:

Circular Styl Circular Unrooted Styl Radial Normal Styl Rectangular

1Page uvádí na stránce programu Treeview algoritmus 'maximum daylight' od J. Felsenstei- na, a jeho implementaci od D. Swoorda. Po neúsp¥²ných pokusech najít jakékoliv informace o algoritmu 'maximum daylight' jsem na²el v dokumentaci k Drawtree algoritmus 'equal day- light' a zmínku o tom, ºe ho se svolením J. Felsensteina pouºívá PAUP (balí£ek od Swoorda) a Treeview.

a stromové operace

Collapse/Expand Sbalení/rozbalení podstrom·.

Reroot Zm¥na ko°ene stromu.

Grupování Barevné odli²ení podstrom·.

Obrázek 2.6: Interactive Tree of Life - strom ºivota zobrazený stylem Circular.

[Zdroj:Wikipedie]

Aplikace ITOL umoº¬uje propojení OTU zobrazených ve stromu s externími datasety. Lze nap°íklad u jednotlivých list· (biologických druh·) zobrazit obráz- ky, jak daný organizmus vypadá, data ze kterých se p°i tvorb¥ stromu vycházelo, atd.

2.4 HyperTree

Tento program [6] napsaný v Jav¥ poskytuje 3 zobrazovací styly:

Linear tree Styl Rectangular Radial tree Styl Classic Radial

Hyperbolic tree Zobrazení ve stylu 'sh eye'

Obrázek 2.7: Strom ºivota v hyperbolickém zobrazení [Zdroj: screenshot z pro- gramu HyperTree]

Hyperbolické zobrazení je zástupcem technik focus+context. Hlavní my²lenkou tohoto p°ístupu je dát objektu zájmu v centru zobrazovací oblasti hodn¥ prostoru, zatímco zbytek stromu je v men²ím detailu stále vid¥t na zbytku plochy.

Program disponuje pom¥rn¥ slu²nými edita£ními vlastnostmi. Lze obarvovat podstromy, collapse/expand, °adit podstromy podle velikosti (operace ladderize) a schovat popisky. Lze m¥nit strukturu stromu pomocí kopírování, p°idávání a mazání uzl· nebo celých podstrom·.

2.5 Drawgram/Drawtree

Tyto dva programy jsou sou£ásti balí£ku PHYLIP [3] od J. Felsensteina.

Drawgram umí 6 zobrazovacích styl·:

Cladogram Styl Cladogram Phenogram Styl Rectangular

Curvogram Styl Curvogram, jako v 2.5.

Eurogram Styl Eurogram, jako v 2.3.

Swoopogram Styl Swoopogram, jako v 2.10 Circular Tree Styl Circular

Drawtree je ur£en ke kreslení nezako°en¥ných strom· (styl Radial). Obsahuje 3 iterativní metody:

Equal Arc Metoda od Christophera Meachama pro program PLOTREE. Pod- strom·m se alokuje výse£ podle po£tu list·.

Equal Daylight Vychází z první metody, prochází vnit°ní uzly stromu a otá£í podstromy tak, aby mezi nimi byly stejné mezery 'sv¥tla'.

N-Body Metoda simuluje odpuzovaní elektrických náboj· umíst¥ných na kon- cích v¥tví stromu. Je pomalej²í a m·ºe dokonce zp·sobit p°ek°íºení v¥tví stromu.

Stojí za zmínku, ºe Drawtree má p°epína£ D (avoiD overlap of labels), kterým se snaºí zabránit p°ekrývání popisk·. V základním nastavení je tato vlastnost vypnutá, protoºe podle autora je 'pom¥rn¥ chabá a £asto neúsp¥²ná, a £asto stromy vypadají divn¥'.

2.6 Phylodendron

Existuje online i jako samostatná aplikace.

Podporované styly:

Tree diagram Styl Radial Cladogram Styl Cladogram Phenogram Styl Rectangular Eurogram Styl Eurogram

Curvogram Ukázka stylu je na obrázku 2.9 Swoopogram Ukázka stylu je na obrázku 2.10

Obrázek 2.8: Styl Cladogram v podání programu Phylodendron [Zdroj: screenshot z aplikace Phylodendron

Obrázek 2.9: Styl Curvogram v podání programu Phylodendron[Zdroj: screenshot z aplikace Phylodendron]

Obrázek 2.10: Styl Swoopogram [Zdroj: screenshot z aplikace Phylodendron]

3. Popis implementace

V této kapitole popisuji nejd·leºit¥j²í pouºité datové struktury, algoritmy, cel- kov¥ nástin implementace vlastností programu WPF Trees, a návrhová rozhodnutí která implementaci p°edcházela. Odkazuji se také na t°ídu £i soubor ve kterém je daná struktura, algoritmus nebo vlastnost programu naimplementovaná.

3.1 Implementa£ní technologie

Aplikace je napsaná v C# a postavená nad .NET Frameworkem od Microsoftu.

Jako knihovnu na tvorbu uºivatelského rozhraní pouºívá WPF (Window Presen- tation Foundation). Hlavním kritériem p°i rozhodování jaké techonologie zvolit byly moje zku²enosti s technologiemi a jejich vhodnost pro danou úlohu.

Od poºadavku na p°enositelnost jsem £áste£n¥ upustil. WPF aplikace totiº, narozdíl od £istého C# a .NET Frameworku p°enositelné nejsou, protoºe nikdo nenapsal vlastní WPF implementaci pro jiné opera£ní systémy. Nicmén¥ kód ne- související p°ímo s UI p°enositelný je.

3.2 Základní struktura aplikace

Kaºdá význam¥j²í funkcionalita aplikace má svojí sloºku (a zárove¬ jmenný prostor), ve které jsou umíst¥né zdrojové kódy t°íd:

DataStructures Datové reprezentace stromu.

FontChooser Komponenta na výb¥r font·.

images Sloºka obrázk·.

LabelOptimization T°ídy pro optimalizaci umíst¥ní popisk·.

Layouts Zobrazovací styly.

Lib Knihovna komponenty na výb¥r barev.

Parser Parser vstupních soubor·.

PropertyDialogs Dialogy vlastností objekt· a nastavení.

ResizingAdorner Komponenta.

Tools Operace se stromem.

Workspace T°ídy k ukládaná pracovní plochy do souboru.

3.2.1 Vykreslování strom·

Základní postup p°i vykreslení stromu je následující:

1. Parser v pam¥ti vytvo°í reprezentaci stromu

2. metoda BuildTree() strom projde a vytvo°í gracké prvky reprezentující uzly, v¥tve a popisky stromu, a p°idá je na objekt Canvas (a naváºe na uzly stromu p°es vlastnosti VisualElement, BranchToParentElement).

3. zavolá se metoda ExecuteLayout() na aktivní implementaci zobrazovacího stylu. ExecuteLayout projde strom, a navázaným grackým prvk·m nastaví sou°adnice na kanvasu podle daného algoritmu.

Kroky 1. a 2. se vykonají jen p°i na£tení nového stromu, krok 3. vºdy kdyº je pot°eba strom p°ekreslit.

3.2.2 Reprezentace stromu

N-ární strom je reprezentovaný generickou t°ídou DataStructures.NTree. Im- plementace je roz²í°ením kódu z [1]. Strom je reprezentovaný seznamem násled- ník·. K implementaci jsem p°idal vlastnosti TreeInfo a SelectedNode. TreeInfo je struktura obsahující informace jako nap°íklad maximální hloubku stromu, cestu k souboru kde je strom uloºen, a seznam list·. Tyto informace se vypl¬ují p°i na£ítání stromu.

Uzly stromu jsou potomky generické t°ídy NTreeNode, která je také p°evzaná, a roz²í°ená o vlastnosti Leaves a Level. Leaves je po£et list· v podstromu uzlu, a Level °íká v jaké hloubce se uzel nachází.

p°enositelnost Tato reprezentace je nezávislá na prezentaci (WPF) a tudíº p°enositelná.

Obrázek 3.1: Diagram t°íd datových struktur NTree, NTreeNode a TreeInfo

3.2.3 Hierarchie ILayout

Kaºdá t°ída reprezentující styl nakreslení stromu implementuje rozhraní ILay- out. To denuje p°edev²ím metodu ExecuteLayout(canvas, tree) - na vykreslení stromu na kanvas. Dále vlastnost IsRooted, která °íká jestli se má strom vykreslit jako zako°en¥ný, a IBranchDrawer objekt na vykreslení v¥tví.

Rozhraní IBranchDrawer denuje metody na vytvo°ení gracké reprezentace spojnice dvou uzl· (=v¥tve stromu) a její umíst¥ní na dané sou°adnice.

Pokud styl nakreslení podporuje zobrazování skupin (viz 3.5.3), nebo ohodno- cení hran délkou, implementuje rozhraní ISupportGroups resp. ICanUseBranch- Lengths. Aplikace detekuje tyto rozhrani a podle toho zobrazuje nebo schovává p°íslu²né nabídky uºivatelského rozhraní.

roz²i°itelnost P°edpokládá se, ºe t°etí strany budou implementovat vlastní ILayout a p°ípadn¥ i IBranchDrawer.

3.3 Parser

V této sekci popisuji formát vstupních soubor· aplikace, a jejich parser.

3.3.1 Formát Newick

Formát Newick (anglicky Newick tree format,Newick notation nebo New Hampshire tree format) je ²iroce pouºívaný textový formát reprezentující stro- my. Formáln¥ je popsaný v [14].

Nap°íklad strom zapsaný ve formátu newick jako

((a:1,a2:1):0.5,b:0.5,(c:0.5,d:0.1):1.,e:0.5):0.4;

je vizualizovaný na obrázku 3.2.

Obrázek 3.2: Vizualizace ukázkového stromu

ƒísla, uvedená v zápisu stromu za názvy uzl·, zna£í ohodnocení hran. íká se jim 'délky hran'. Interpretují se jako vzdálenost mezi uzlem a jeho p°edkem (a´

uº vzdálenost m¥°íme £asem, nebo podobností DNA, nebo jinak). Na obrázku 3.3 je strom z p°edchozího p°íkladu zobrazen stylem, který délky hran podporuje.

Obrázek 3.3: Vizualizace ukázkového stromu stylem Rectangular, který zachovává

P°i implementaci aplikace jsem napsal vlastní parser formátu newick, bez po- uºití nástroj· na automatické generování parser· z gramatiky.

3.3.2 Implementace parseru

Parsování vstupu za°izují t°ídy z jmenného prostoru WPFTrees.Parser.

T°ída parser na£te vstup, provede tokenizaci, a pak z token· sestaví stromovou strukturu.

Tokeny jsou typ·:

OpeningBracket Otevírací závorka ClosingBracket Zavírací závorka Comma ƒárka

Label Popisek

BranchLenght Délka v¥tve Semicolon St°edník

Comment Komentá°

Tokenizaci provádí t°ída WPFTrees.Parser.Lexer v metod¥ Tokenize(string in- put). V metod¥ je implementovaný stavový automat, který £te vstup znak po znaku, p°echází mezi stavy ReadingToken, ReadingLabel, ReadingQuotedLabel, ReadingBranchLength, ReadingComment a buduje seznam token·.

Pokud p°i parsování narazí parser na neo£ekávaný vstup (nap°íklad o£ekává zavírací závorku a dostane se na konec souboru), vyvolá vyjímku ParserException, kterou zachytne hlavní okno aplikace a zobrazí uºivateli zprávu o chyb¥.

£asová a pam¥´ová sloºitost ƒasová sloºitost parsování je O(N), kde N je dél- ka vstupu. Tokenizace £te vstup lineárn¥, kaºdý znak jednou. Zpracování token·

je cyklus, který v kaºdé iteraci zpracuje 1-2 tokeny, £ili také lineární.

3.4 Styly zobrazení strom·

V této sekci popisuji zobrazovací styly, které jsem implementoval v mojí práci.

3.4.1 Styl Radial

Tento styl je známý také jako 'radial tree'. Uzly se v tomto stylu umístují na soust°edné kruºnice se st°edem v ko°eni. Kaºdému synovi ko°ene se ur£í kruhová výse£, do které se jeho podstrom nakreslí.

délky hran Tento styl nepodporuje délky hran.

Obrázek 3.4: Styl Radial

algoritmus Algoritmus si udrºuje dvojici úhl· angleLeft, angleRight,ur£ující výse£ do které se (pod)strom daný uzlem node nakreslí. Poté výse£ rozd¥lí podle po£tu syn· uzlu node, a do st°edu kaºdé nové výse£e umístí jednoho syna. Na v²echny syny se zavolá rekurze.

pseudokód

Algorithm 1. Algoritmus Stylu Radial

1: procedure RadialLayout(root, rootP os, angleLef t, angleRight)

2: root.x←rootP os.x

3: root.y←rootP os.y

4: if root is leaf then return

5: end if

6: α←(angleRight−angleLef t)/root.CountChildren

7: for i= 0, i < root.ChildrenCount;i+ + do

8: otoceni←angleLef t+i∗alpha+ (α/2)

9: tempP os←(rootP os.x, rootP os.y+def aultRadius)

10: itemP os←RotateP ointByAngle(otoceni, tempP os)

11: lef tN ew ←angleLef t+i∗α

12: rightN ew←lef tN ew+α

13: RadialLayout(item,itemPos,leftNew,RightNew)

14: end for

15: end procedure end

£asová a pam¥´ová sloºitost Algoritmus rekuzivn¥ prochází strom a kaºdý uzel nav²tíví jednou, £asová sloºitost je O(N).

3.4.2 Styl Classic Radial

Obrázek 3.5: Styl Classic Radial

Tento styl je popsaný v [4] jako Radial Layout. Nazývejme tento styl Classic Radial, aby se rozli²il od stylu, který je v této práci nazvaný Radial (viz. 3.4.1)

My²lenkou algoritmu je kaºdému podstromu p°i°adit kruhovou výse£ podle po£tu list· v podstromu relativn¥ k ostatním podstrom·m (Narozdíl oproti stylu Radial, který p°i°azuje kaºdému synovy stejn¥ velkou výse£.). P°íklad rozd¥lení výse£e podstrom·m je na obrázku 3.6.

délky hran Tento styl podporuje délky hran.

Obrázek 3.6: Schéma rozd¥lení kruhové výse£e mezi potomky uzlu [Zdroj: [4]]

pseudokód

Algorithm 2. Algoritmus Stylu Classic Radial

procedure ClassicRadialLayout(root, node, wedgeP arent, wedgeGrandP arent, tau, grandP arentT au)

xV ector←(root.x, root.y)

yV ector.x←cos(tau+wedgeP arent/2) yV ector.y ←sin(tau+wedgeP arent/2)

newP osition ←xV ector+branchLenght∗yV ector node.x←newP osition.x

node.y←newP osition.y n ←tau

for all child innode.Children do

childLeavesCount=max(child.children,1) w←childLeavesCount/root.ChildrenCount tauW ←n

ClassicRadialLayout(node, child, newP osition, w, tauW, wedgeP arent, tau) n←n+w

end for end procedure end

Popisek listu se nato£í ve sm¥ru daném vektorem mezi rodi£ovským uzlem a nov¥ umíst¥ným uzlem.

£asová a pam¥´ová sloºitost ƒasová sloºitost je O(N), algoritmus projde celý strom a v kaºdém uzlu provede triviální práci.

Ve zdrojových kódech algoritmus najdete ve t°íd¥ WPFTRees.Layouts.ClassicRadialLayout.

3.4.3 Styl Rectangular

Tento styl je vhodný pro vizualizaci malých strom·. Pro kaºdý podstrom se rezervuje obdélníková oblast, jejíº ²í°ka je daná po£tem list· v podstromu.

délky hran Tento styl podporuje délky hran.

algoritmus Stejn¥ jako ve stylu Cladogram se ur£í ²í°ka pásma pro jednoho syna. Udrºují se left a right oblasti. Vykreslí se ko°en do st°edu oblasti a pak se metoda rekurzivn¥ zavolá na syny.

Oproti stylu Cladogram se jinak po£ítá y-sou°adnice uzl·. Pokud se uvaºuje ohodnocení hran, k y-sou°adnici ko°ene podstromu se prost¥ p°i£te y-sou°adnice otce vynásobená jednotkou (jednotka = vý²ka oblasti/maximální hloubka stro-

Obrázek 3.7: Styl Rectangular

Spojnice mezi ko°enem (pod)stromu a jeho syny se nakreslí pomocí t°ídy Rectan- gularBranchDrawer.

pseudokód

Algorithm 3. Algoritmus Stylu Rectangular

1: procedure RectangularLayout(root, lef t, right)

2: x←lef t

3: for all child inroot.Children do

4: if child is leaf then

5: if useBranchLenghts then

6: childXY = (x,root.y+child.branchLength*unit)

7: else

8: childXY = (x,bottom)

9: end if

10: x←x+childW idth

11: else

12: lef tN ew ←x

13: rightN ew←lef tN ew+child.leaf Count∗childW idth

14: x←rightN ew+childW idth

15: if useBranchLenghts then

16: y←y+child.branchLength∗unit

17: else

18: y←bottom−child.Leaf Count∗childW idth

19: end if

20: childXY =(x,y)

21: RectangularLayout(child, lef tnew, rightnew)

22: end if

23: end for

24: end procedure end

£asová a pam¥´ová sloºitost ƒasová sloºitost je O(N), strom se rekurzivn¥

projde a v kaºdém uzlu se ud¥lá triviální práce.

3.4.4 Styl Cladogram

Stejn¥ jako styl popsaný v 3.4.3. je vhodný pro vizualizaci malých strom·.

TreeView [15] nazývá tento styl slanted cladogram.

délky hran Tento styl nepodporuje délky hran.

Obrázek 3.8: Styl Cladogram

algoritmus P°i návrhu algoritmu vycházíme z toho ºe v²echny listy jsou na stejné úrovni, a chceme aby podstromy byly tvo°eny pokud moºno podobný- mi trojúhleníky. Pro daný obdélník o rozm¥rech width,height se spo£ítá úhel α = arctan(width/2, height). Mezera mezi listy childWidth se spo£ítá jako gap

= width/po£et list·. Nech´ 0,0 jsou sou°adnice levého horního rohu obdélníku.

Algoritmus nejprve umístí ko°en do st°edu horní hrany obdélníku. Potom iteruje syny a podle po£tu list· v jejich podstromech p°id¥luje pásmo do kterého se listy vykreslí (parametry left a right). Na n¥j se rekurzivn¥ zavolá, a posune pásmo pro dal²ího syna. Pokud je ale syn listem, nakreslí se spojnice p°ímo do spodu obdélníku.

pseudokód

Algorithm 4. Algoritmus Stylu Cladogram

1: procedure CladogramLayout(root, lef t, right)

2: x←lef t

3: for all child inroot.Children do

4: if child is leaf then

5: childXY = (x,bottom)

6: x←x+childW idth

7: else

8: lef tN ew ←x

9: rightN ew←lef tN ew+child.leaf Count∗childW idth

10: x←rightN ew+childW idth

11: y←(bottom−newW idth/2)/tan(α)

12: childXY =(x,y)

13: CladogramLayout(child, lef tnew, rightnew)

16: end procedure end

£asová a pam¥´ová sloºitost ƒasová sloºitost je O(N), algoritmus rekurzivn¥

projde strom a v kaºdém uzlu ud¥lá triviální práci.

3.5 Stromové operace

3.5.1 Ladderize

Operace ladderize znamená rekurzivní set°íd¥ní podstrom· podle po£tu list·

v podstromech. Podle toho jestli je °azení vzestupné nebo sestupné se rozli²uje ladderize left a ladderize right. Implementace t¥chto metod je v t°íd¥ Tree- Tools. Pseudokód:

Algorithm 5. Algoritmus operace Ladderize

procedure Ladderize(root) . ladderizes subtree of root node Sort(root.Children)

for all child inroot.Children do .recurse all children Ladderize(child)

end for end procedure end

Sloºitost algoritmu je O(M*Log(M)*N), kde M je maximální stupe¬ uzl· stro- mu. O(M*Log(M)) je sloºitost set°íd¥ní syn· jednoho uzlu, a uzl· je O(N).

3.5.2 Rotate

rotate je operace p°esunu posledního syna p°ed prvního, nebo prvního za po- sledního. V

pseudokód

Algorithm 6. Algoritmus operace Rotate

procedure Rotate(root) . rotate children of root node count←root.CountChildren

f irst←root.Children[0]

for i←0, count do . move all children except the last one root.Children[i]←root.Children[i+ 1]

end for

root.Children[count−1]←f irst . last children becomes rst end procedure

end

£asová a pam¥´ová sloºitost Sloºitost algoritmu je O(N), kde N je stupe¬

vrcholu. Kdyby seznam syn· byl implementovaný jinak neº pole, nap°íklad jako spojový seznam s odkazem na poslední prvek, mohlo by to být O(1). Stupn¥

vrchol· stromu jsou ale typicky malé a kompaktní reprezentace v poli se mi proto zdá vhodná.

3.5.3 Grupování

Podstromu v dendrogramu se °íká klad (anglicky clade) ¹. Skupina organism·

v kladu má v¥t²inou sv·j název. Aplikace WPF Trees podporuje denování a vizualizaci skupin.

Vlastnost uzl· NewickNode.GroupInfo obsahuje objekt Parser.GroupInfo. Ten udrºuje informace o skupin¥, kterou podstrom daný tímto uzlem p°edstavuje.

Hlavní informace jsou název skupiny a barva, které skupin¥ uºivatel programu p°id¥lil.

Pokud pouºitý zobrazovací styl (implementace ILayout) podporuje skupiny, vytvo°í se gracká reprezentace skupiny. Podle toho, o jaký styl jde, je skupi- na reprezentovaná trojúhleníkem, obdélníkem nebo kruhovou výse£í. Skupiny se mohou p°ekrývat.

Obrázek 3.9: Dv¥ skupiny, styl Cladogram. Tvar skupiny tvo°í trojúhleník

1P°esn¥ji, klad p°edstavuje druh a v²echny jeho potomky - v£etn¥ t¥ch, které je²t¥ neznáme, a ve stromu se kterým pracujeme tudíº nejsou.

Obrázek 3.10: tatẠtopologie, styl Rectangular. Obdélník skupiny kopíruje oblast p°i°azenou podstromu.

Obrázek 3.11: tatẠtopologie, styl Radial. Tvar skupiny je kruhová výse£ ko- pírující výse£ p°i°azenou podstromu algoritmem, polom¥r výse£e se ur£í podle sou°adnic nejvzdálen¥j²ího listu v podstromu.

roz²i°itelnost Auto°i nových zobrazovacích styl·, které podporují skupiny, mu- sí naimplementovat interface ISupportGroups a dodat kód na tvorbu grackého prvku skupiny. V metod¥ ExecuteLayout pak musí napsat kód který aktualizuje velikost a sou°adnice prvku skupiny.

3.5.4 Collapse/Expand

Zobrazení/schování podstromu d¥lá funkce TreeTools.CollapseOrExpandSubtree, která prost¥ nastaví uzl·m podstromu p°íznak 'neviditelnosti' a strom se p°ekres- lí. Kolapsovaný podstrom se nevykresluje, ale algoritmy zobrazovacích styl· s nimi stále 'po£ítají' a alokují pro n¥ místo. Zvaºoval jsem implementaci, ve které by se strom p°ekreslil jako kdyby se zm¥nila topologie, ale p°i²lo to mi to matoucí pro uºivatele.

3.5.5 Vyhledávání

Pro snaº²í orientaci je moºné mezi listy stromu vyhledávat. Protoºe se udrºuje seznam list·, je £asová sloºitost vyhledávaní O(N), kde N je po£et list· stromu.

Ve vnit°ních uzlech vyhledávat neumí.

3.6 Uºivatelské rozhraní

P°i implementaci aplikace jsem pouºil n¥kolik komponent uºivatelského rozhra- ní od t°etích stran. V této sekci uvádím jejich p°ehled. Auto°i komponent jsou náleºit¥ kreditovnáni ve zdrojovém kódu.

ResizingAdorner Tento uºivatelský prvek je malý £tvere£ek u objekt·, za kte- rý lze táhnout a tak m¥nit jeich velikost. Komponentu jsem p°evzal.

FontChooser Komponentu na výb¥r font· jsem p°evzal.

WPFColorPicker Komponentu na výb¥r barev jsem p°evzal.

Panning

Se stromem je moºné po pracovní plo²e pohybovat.

3.6.1 Vkládané objekty

Krom¥ stromu m·ºe uºivatel na pracovní plochu p°es nabídku menu vloºit r·zné dop¬ující texty a obrázky. My²í je umístí na poºadované místo a nastaví velikost. P°es kontextovou nabídku je dostupný dialog, ve kterém se nastavuje text/obrázek objektu.

Funkcionalita vkládnaých objekt· je ve zdrojovém souboru InsertedItems.cs Poloha, rozm¥ry a vlastnosti vkládaných objekt· lze uloºit do souboru a pozd¥ji na£íst (viz 3.8).

3.6.2 Generování výstupu

Standardnímy prost°edky .Net Frameworku/WPF se exportuje celá pracovní plocha aplikace do souboru bitmapy.

Tisk je také °e²en standartní metodou, která vytiskne obsah pracovní plochy aplikace.

3.7 Optimalizace umíst¥ní popisk·

Se vzr·stající velikostí strom· se popisky (list· i skupin) za£ínají p°ekrývat.

Problém umíst¥ní popisk· ('automatic label placement') je problém jak je uspo-

°ádat, aby se co nejmén¥ p°ekrývaly, a zárove¬ byly co nejblíºe objekt·m které popisují.

3.7.1 Metoda

Simulované ºíhání (Simmulated annealing) je optimaliza£ní metoda popsaná v [5], která má dobré výsledky (viz [17]) p°i umis´ování popisk· na mapy. Zkusil jsem tedy metodu pouºít na optimalizaci umíst¥ní popisk· vývojových strom·.

Následující popis metody simulovaného ºíhání je p°eloºený z [5]:

[za£átek p°ekladu]

1. Kone£ná mnoºina S.

2. Hodnotící funkce J,J :S →R. Nech´S∗ ⊂S je mnoºina globálních minim fukce J.

3. Pro kaºdé i ∈ S, mnoºina S(i)⊂S− {i} se nazývá okolí i.

4. Pro kaºdé i, m¥jme koecienty q_ij, j ∈ S(i), tak ºe P

j∈S(i)

q_ij = 1 . P°edpo- kládá se, ºe j ∈S(i)⇔i∈S(j)

5. Nerostoucí funkce T, T : N → (0,∞), takzvaný chladící rozvrh. Hodnot¥

T(t) °íkejme teplota v £ase t.

6. Po£áte£ní 'stav' x(0)∈S

SA algoritmus je za takovýchto podmínek diskrétní nehomogenní markov·v

°etezec x(t), jehoº evoluci te¤ popí²eme. Pokud je aktuální stav x(t) = i, vybereme náhodn¥ souseda j. Pravd¥podobnost výb¥ru kaºdého souseda j je q_ij. Kdyº je j vybrán, následující stav x(t+1) se ur£í následovn¥:

1: if J(j)≤J(i) then

2: x(t+1) = j.

3: else

4: if J(j)≥J(i)then

5: x(t + 1) = j s pravd¥podobností exp(−J(j) − J(i))/T(t)), x(t+ 1) =ijinak.

6: end if

7: end if [konec p°ekladu]

3.7.2 Implementace

Jako odrazový m·stek pro implementaci metody simulovaného ºíhaní poslouºil

£lánek [10].

V [16] se jako jeden krok simulovaného ºíhání p°i umis´ování popisk· na mapy bere umíst¥ní jednoho popisku, takºe ve své implementaci jsem jako jeden krok zvolil náhodné vybrání a oto£ení jednoho popisku o úhel 0-180 stup¬·. Otá£í se kolem OTU kterou popisuje, takºe kritérium 'býti blízko popisovaného objektu' je triviáln¥ spln¥no. Na druhou stranu, n¥kdy by sta£ilo popisek trochu posunout aby se zabránilo k°íºení, a v tom p°ípad¥ tato implementace selºe. Proto je moºné popisky také otá£et a posouvat manuáln¥. Se stisknutým levým tla£ítkem lze popisky otá£et my²í, a p°i stisknutém Alt se posouvají.

Hodnotící funkce J je po£et k°íºení popisk· (tedy k°íºení popisk· s stromem neuvaºuji). Hodnotící funkci v kódu po£ítá metoda ValueFunction, která pro kaº- dý popisek p projde ostatní popisky a pokud se alespo¬ jeden k°íºí s p, zvý²í po£et k°íºení o 1 (a nezkou²í uº zbytek popisk·). Metoda tedy beºí v £ase O(N²), kde N je po£et list·.

Chladící rozvrh Teplota T v £ase t je daná vztahem T(t) = t₀∗alpha^t, kde t₀ je po£áte£ní teplota.

Samotná metoda SA je implementovaná velmi p°ímo£a°e:

1: temperature←1000

2: alpha←0.999

3: score←V alueF unction()

4: while temperature > epsilondo . skon£íme, kdyº je teplota dostate£n¥

blízko nule

5: RotateRandomLabel()

6: newscore←V alueF unction()

7: if newscore < score then .men²í skore je lep²í

8: score←newscore

9: else

10: U ndoRotateRandomLabel()

11: end if

12: temperature←temperature∗alpha . sníºení teploty

13: end while

V kódu je optimalizace popisk· k nalezení ve t°íd¥ LabelOptimizer jmenného prostoru WPFTrees.LabelOptimization..

Obrázek 3.12: Testovací strom s 50 listy, zobrazený stylem Radial.

Obrázek 3.13: Tentýº strom po optimalizaci umíst¥ní popisk·

První obrázek má 40 p°ek°íºení. Druhý má 19 p°ek°íºení. Optimalizace trvala na mém po£íta£i (Core2 Duo 2.2GB a 4GB pam¥ti, 32bit Windows 7) 101.5s a p°es 13800 iterací.

3.8 Workspace

Uºivatelovu práci s programem lze uloºit do souboru workspace. To je XML soubor s p°íponou .WTW (WPF Trees Workspace), obsahující pozice a rozm¥ry objekt·, cesty k dat·m, a r·zná nastavení barev.

Uºivatel m·ºe kdykoliv workspace uloºit a pozd¥ji se k rozd¥lané práci vrátit.

Ukládají se pouze cesty k objekt·m, takºe pokud se mezitím na disku zm¥ní, uºivatel nedostane p°esn¥ to co ukládal.

Zatím se neukládájí úpravy stromu jako ladderize, skupiny, rotace popisk·, apod.

Práci s workspace zaji²tují t°ídy Workspace a WorkspaceManager.

4. Uºivatelská dokumentace

4.1 Instalace a spu²t¥ní programu

Aplikaci lze nainstalovat kliknutím na odkaz na webové stránce http://davidnohejl.

com/wpftrees/.

Alternativn¥ lze aplikaci nainstalovat z p°iloºeného CD (viz 5.1).

Po nainstalování se aplikace p°idá do menu Start pod Programy → David Nohejl→WPFTrees. Odtud nebo otev°ením souboru WPFTrees.exe lze spustit.

4.2 Uºivatelské rozhraní

Aplikace má standardní uºivatelské rozhraní windows aplikace: menu, panel s nástroji, kontextové menu, dialogy a stavový °ádek.

Obrázek 4.1: Hlavní obrazovka aplikace

Strom nebo celý workspace se na£ítá p°es menu File→Open resp. File→Load Workspace. Po na£tení se strom vykreslí aktualním stylem na pracovní plochu aplikace. Výchozí styl je Cladogram. Ve stavovém °ádku se zobrazí informace o na£teném stromu: Kolik obsahuje uzl·, kolik z toho je list·, jestli je binární atd.

4.2.1 Panely nástroj·

Standardní nástroje P°es tento panel lze tisknout pracovní plochu a otevírat soubory se stromy.

Styly Styly se p°epínají v tomto panelu nástroj·.

Navigace Naviga£ní panel nástroj· obsahuje tla£ítka pro rotaci o 90 stup¬·

doleva, doprava a vycentrování stromu na pracovní plo²e.

Vkládané objekty Dal²í je vyhledávací panel a panel vkládání dopl¬kových obrázk· a text·.

4.2.2 Hlavní menu

Nabídka File

Open Zobrazí dialog pro otev°ení souboru se stromem.

Export as bmp Zobrazí dialog pro uloºení obsahu pracovní plochy jako obrázek Load Workspace Zobrazí dialog pro otev°ení souboru workspace.

Save Workspace Zobrazí dialog pro uloºení souboru workspace.

Exit Ukon£í aplikaci Nabídka Tree

Use branch lenghts Pokud je za²krtnuto, pouºijí se délky hran (pokud to ak- tuální styl podporuje).

Unroot Pokud je za²krnuto, zobrazí se aktuální strom jako nezako°en¥ný (pokud to aktuální styl podporuje).

Properties... Zobrazí dialog s vlastnostmi stromu.

Nabídka View

Toolbars P°es tuto nabídku lze schovávat a zobrazovat panely nástroj·.

Colors... Zobrazí dialog nastavení barev.

Labels P°es tuto nabídku lze m¥nit font, zobrazení popisk·, spustit optimalizaci umíst¥ní popisk· a povolit/zakázat rotování popisk· o 90 stup¬· spolu se stromem.

Nabídka Tools

Settings... Zobrazí dialog s dal²ími nastaveními.

Nabídka Help

Contents Zobrazí nápov¥du programu.

About Zobrazí dialog s verzí programu.

4.3 Uºivatelská nastavení

P°es menu View→Colors je p°ístupný dialog nastavení barev, ve kterém lze nastavit barvu list· (Leaf color), popisk· (Leaf label color) a pozadí (Background color).

Obrázek 4.2: Dialog nastavení barev

Menu Tools→Settings zp°ístupnuje dialog s dal²ím nastavením. Zatím lze na- stavit jen velikost uzl·.

4.4 P°íklad

Na p°iloºeném CD (viz 5.1) je v adresá°i Bin/Examples/Mammals ukázkový workspace mammals.wtw. Workspace obsahuje strom ze souboru mammals.txt, dva obrázky a dva texty (viz obrázek 4.3).

Obrázek 4.3: Ukázkový workspace mammals.wtw

5. Záv¥r

Poda°ilo se mi vyvinout aplikaci srovnatelnou s ostatním programy, podporující hlavní zobrazovací styly, s ²irokými moºnostmi úpravy grackého výstupu.

Modulární návrh aplikace umoºnuje jenodu²e roz²i°ovat aplikaci o dal²í zobra- zovací styly. Na b¥ºném PC umoº¬uje rozumn¥ pracovat se stromy do velikosti 500 uzl·.

dal²í práce Tak jako snad kaºdý program, ani WPF Trees není hotový a spous- ta v¥cí se nestihla podle mých p°edstav. Nestihlo se p°edev²ím dolad¥ní vizuální stránky UI, a ukládaní více nastavení do workspace.

Krom¥ dod¥lávek vidím n¥kolik sm¥r·, kterýmy by se mohl dal²í vývoj ubírat:

1. Bylo by dobré doprogramovat zbývající zobrazovací styly, které se b¥ºne pouºívají (Circular, Eurogram, atd.).

2. Zavést pluginy; dát moºnost cílovému uºivateli nové styly stáhnout a pouºít v uº zkompilované aplikaci.

3. Také bych rád naprogramovat iterativní vylep²ení vzhledu strom· nakres- lených stylem Classic Radial (Equal Daylight atd)

4. Napojení vizualizace na externí datasety podobn¥ jako u projektu Inter- active Tree Of Life by aplikaci velmi obohatilo.

5. Dále by bylo uºite£né pracovat na zoomování. Zvaºoval jsem i výrobu ani- mací. Práv¥ ve spojení se zoomováním, a napojením na n¥jaký gracký dataset by se daly vytvá°et vizuáln¥ velmi efektivní animované 'prohlídky' stromu ºivota.

6. Pro dal²í úpravy by bylo vhodné mít moºnost výstupu ve formátu, který umoº¬uje dal²í pokro£ilé úpravy v grackém editoru typu Adobe Illustrator (tzn. ne bitmapa, ale vektorové reprezentace objekt·).

Myslím si, ºe oblast optimalizace umíst¥ní popisk· stromu je nedostate£n¥

prozkoumaná. V²echny m¥ známé studie 'label placement' problému se zabývají obecn¥j²ím problémem umíst¥ní popisk· na mapy, který je NP t¥ºký [17].

Pro n¥které styly nakreslení je úloha triviální. Pro jiné by z°ejm¥ ²lo vyuºít vlastností zobrazovacích algoritm· a konkrétních strom· (úhly mezi v¥tvemi, re- lativní velikosti podstrom·, nejvy²²í stupe¬ vrcholu v podstomu, atd...).

Z mojí naivní implementace se zdá metoda simulovaného ºíhaní jako nevhodná pro reálné pouºití, resp. p°íli² pomalu sm¥°ující k uspokojivému cíli. Moºná by to bylo lep²í s chyt°ej²í implementací a lep²í hodnotící funkcí, t°eba beroucí v potaz

Seznam pouºité literatury

[1] Creating an n-ary tree http://codeidol.com/csharp/csharpckbk2/

Data-Structures-and-Algorithms/Creating-an-n-ary-Tree

[2] List of phylogenetic tree visualization software http://en.wikipedia.org/

wiki/List_of_phylogenetic_tree_visualization_software [3] http://evolution.gs.washington.edu/phylip.html

[4] Bachmaier, Christian, Brandes,Ulrich, Schlieper, Barbara. Drawing Phylogenetic Trees (Extended Abstract). 2005

[5] Bertsimas, D.J, Tsitsiklis, J, Simulated annealing Statistical Science, vol. 8 (page 10), 1993

[6] Bingham, J, Sudarsanam, S, Visualizing harge hierarchical clusters in hyperbolic space Bioinformatics (2000) 16(7): 660-1

[7] Carrizo, S.F. Carrizo, S.F. (2004). Phylogenetic Trees: An Information Visualisation Perspective. In Proc. Second Asia-Pacic Bioinformatics Con- ference (APBC2004), Dunedin, New Zealand. CRPIT, 29. Chen, Y.-P. P., Ed. ACS. 315-320.

[8] Cvr£ková, F Úvod do praktické bioinfomatiky Academia, Praha, 2006 ISBN 80-200-1360-1.

[9] Felsenstein, J Inferring Phylogenies Sinauer Associates Inc., Massa- chusetts. 2004; 664 pp. ISBN 0-87893-177-5.

[10] Chalhoub, Assaad Simulated Annealing Example in C# Pub- lished online at http://www.codeproject.com/Articles/13789/

Simulated-Annealing-Example-in-C in 2006

[11] Lamping, J., Rao, R. , Pirolli, P, A focus+context technique based on hyperbolic geometry for visualizing large hierarchies Proceedings of the SIGCHI conference on Human factors in computing systems, p.401-408, May 07-11, 1995, Denver, Colorado, United States

[12] Letunic, I,;Bork, P. Interactive tree of life (itol): an online tool for phy- logenetic tree display and annotation. Bioinformatics 2007;23:127-128 [13] Letunic, I, Bork, P. Interactive Tree Of Life v2: online annotation and

display of phylogenetic trees made easy. Nucleic Acids Res 2011, in press.

[14] Olsen,Gary Olsen, Gary (1990). Gary Olsen's Interpretation of the "Newick's 8:45"Tree Format Standard Published online, http://evolution.genetics.washington.edu/phylip/newick_doc.html

[15] Page, R.D.M. (1996) TreeView: An application to display phylogenetic trees on personal computers. Computer Applications in the Biosciences, 12 (4).

pp. 357-358. ISSN 0266-7061

[16] Shieber, S. M. , Christensen, J, a Marks, J. Placing text labels on maps and diagrams. Graphics Gems IV. Academic Press, pages 497-504.

[17] Shieber, S. M. , Christensen, J, a Marks, J. An empirical study of algorithms for point feature label placement. Transactions on Graphics, 14(3), July 1995.

[18] Zmasek, C., Eddy, S. 2001ATV: display and manipulation of annotated phylogenetic trees Bioinformatics 17383384

[19] TreeView Tree drawing software for Apple Macintosh and Windows http:

//taxonomy.zoology.gla.ac.uk/rod/treeview.html

P°ílohy

5.1 Obsah p°iloºeného CD

Adresá°ová struktura p°iloºeného nosi£e je následující:

\Doc\Src

\Bin\Examples

\Install

Doc je sloºka obsahující vygenerovanou programovou dokumentaci.

Src obsahuje zdrojové kódy aplikace.

Bin obsahuje nainstalovanou aplikaci.

Examples obsahuje p°íklady.

Install obsahuje instala£ní program.