Visualizing Phylogenetic Trees : Algorithms And Visual Comparison Techniques
Loading...
Date
2011-12
Authors
Wan Zainon, Wan Mohd Nazmee
Journal Title
Journal ISSN
Volume Title
Publisher
Universiti Sains Malaysia
Abstract
This thesis is about visualizing tree structured data. In particular, the emphasis is on visualizing the similarities and differences between pairs of trees. There are many research areas (such as biology, linguistics, chemistry and computer science) that use the tree as a basic data structure. The impetus for the work comes from the field of bioinformatics, where biologists construct complex phylogenetic trees to represent the evolution of species or genes. Once phylogenetic trees reveal potential interrelationships between examined species, the next step would be to validate the derived data. At this point, the comparison between the trees derived from various experimental data is necessary in order to find the best model for a given set of species. The two main issues that arise when comparing these data is to know how to efficiently and effectively compare phylogenetic trees, and how to visually present the results of the comparison
This thesis examines current tree visualization and comparison techniques and proposes algorithms that display fully resolved binary trees in a way that facilitates their visual comparison. The primary approach is to present a new framework for tree structure visualization techniques that will display pairs of trees “face to face” with leaf nodes aligned. In general, it will not be possible to fully align leaf nodes of different trees. This thesis presents several algorithms that arrange and align the nodes in various ways: the minimum triplet difference algorithm, the maximum branch similarity algorithm, and all-but-n algorithm. In addition, a variety of visual comparison techniques are proposed to visualize the similarities and differences between pairs of trees. Finally a prototype interactive tool named VCPT (Visual Comparison of Phylogenetic trees) is developed to explore and evaluate the proposed concepts and issues in regard to visual comparison and manipulation of phylogenetic trees.
Description
Keywords
Visualizing phylogenetic trees , algorithms and visual comparison techniques