Optimal leaf ordering of phylogenetic trees

Hajduković, Gojko (author), Curk, Tomaž (mentor), Ruiz de los Mozos, Igor (co-mentor)

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.

• Language: English
• Keywords: phylogenetic tree, optimal leaf ordering, radial visualization
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2021
• PID: 20.500.12556/RUL-133567
• COBISS.SI-ID: 87446275
• Publication date in RUL: 01.12.2021

Secondary language

• Language: Slovenian
• Title: Optimalno razvrščanje listov filogenetskih dreves

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.

• Keywords: filogenetska drevesa, razvrščanje listov, radijalna vizualizacija