Optimal leaf ordering of phylogenetic trees

master's thesis

Gojko Hajduković (Author), Tomaž Curk (Mentor), Igor Ruiz de los Mozos (Co-mentor)

Abstract

Phylogeny is the study of evolutionary relationships within any taxonomic group of any rank (taxa), such as species, family or class. These relationships are represented with a phylogenetic tree. The leaves of these trees represent species or other taxa, while the internal nodes refer to (hypothetical) ancestors. Branches connecting the leaves represent evolutionary distances between taxa. The common misinterpretation of phylogenetic trees is due to the fact that the leaves are initially arranged in a pseudo-random order, thus not allowing the observers to correctly perceive evolutionary similarities between leaf nodes based on the proximity in the linear leaf ordering. Our work addresses two main shortcomings of visualizing optimally ordered phylogenetic trees in 2-dimensional space using Radial Layout algorithm. We present an evaluation metric to measure the quality of the 2-dimensional layout, also capable of conveying and measuring the quality of the linear leaf ordering. We present two node-correction algorithms ANBC and FFAC applied as a post-processing step to the Radial Layout that aim to improve the quality of a 2-dimensional visualization. The main contribution of this thesis is presenting an effective post-processing algorithm ANBC that improves the visualization quality of the Radial Layout and eliminates the visualization anomalies.

Keywords

phylogenetic trees;leaf ordering;radial layout;computer science;computer and information science;master's thesis;

Data

Language:	English
Year of publishing:	2021
Typology:	2.09 - Master's Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[G. Hajduković]
UDC:	004:575.8(043.2)
COBISS:	87446275
Views:	153
Downloads:	58
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Optimalno razvrščanje listov filogenetskih dreves
Secondary abstract:	Filogenija je preučevanje evolucijskih odnosov znotraj taksonomske skupine nekega ranga, kot so vrsta, družina ali razred. Odnose predstavimo s filogenetskim drevesom. Listi dreves predstavljajo vrste ali druge taksone, notranja vozlišča pa (hipotetične) prednike. Veje, ki povezujejo liste, predstavljajo evolucijske razdalje med taksoni. Pogosta napačna razlaga filogenetskih dreves je posledica dejstva, da so listi prvotno razporejeni v psevdonaključnem vrstnem redu. Opazovalcem to ne omogoča, da bi pravilno zaznali evolucijske podobnosti med listi na podlagi bližine v linearnem vrstnem redu listov. Naše delo obravnava dve glavni pomanjkljivosti vizualizacije optimalno urejenih filogenetskih dreves v dvodimenzionalnem prostoru z uporabo algoritma Radial Layout. Predstavimo mero kakovosti dvodimenzionalne postavitve, s katero merimo kakovost zaporedja postavitve listov. Predstavimo dva algoritma za popravek vozlišč, ANBC in FFAC. Oba algoritma naknadno spremenita radialno postavitve z namenom izboljšati kakovost dvodimenzionalne vizualizacije. Glavni prispevek dela je učinkoviti algoritem ANBC, ki izboljša kakovost vizualizacije Radialne postavitve in odpravlja vizualne anomalije.
Secondary keywords:	filogenetska drevesa;razvršanje listov;radialna vizualizacija;računalništvo in informatika;magisteriji;Filogenija;Računalništvo;Univerzitetna in visokošolska dela;
Type (COBISS):	Master's thesis/paper
Study programme:	1000471
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	VIII, 61 str.
ID:	14047820