University of Maryland, College Park
Spring 2006
TreeJuxtaposer Nick Chen (nchen@cs.umd.edu) Maryam Farboodi (farboodi@cs.umd.edu)

Overview

TreeJuxtaposer is designed to facilitate the comparison and exploration of large tree structures. From a high level, the TreeJuxtaposer application can be divided into two parts that work together to accomplish the application’s design goals. First, TreeJuxtaposer introduced a framework for efficiently rendering multiple trees containing hundred of thousands to millions of nodes to enable large trees to be visualized in real-time. Second, alongside the rendering infrastructure, efficient tree comparison is made possible using novel algorithms that run in sub-linear time.

The primary domain for which TreeJuxtaposer is intended is the exploration of large phylogenetic trees by evolutionary biologists. Phylogenetic trees depict the points at which ancestors of different species of organisms diverged from each other. Given different sources of evidence, a number of different phylogenetic trees may be produced. Biologists compare multiple trees for similarities and differences to form a more complete picture of the evolutionary history of organisms.

The rendering and comparison features of TreeJuxtaposer demonstrated how the application could be used for the comparison of trees. However, biologists have been hesitant to embrace the application as several critical features were absent in the initial version. We extended the TreeJuxtaposer application with a number of additional capabilities to make it more suitable for use in examining phylogenetic trees. The key feature added to TreeJuxtaposer is the consideration of edge length when comparing trees as well as in rendering.

Prior to our additions, the comparison was purely topological (i.e. subtrees were scored purely on adjacencies of nodes). In terms of visualization, all nodes at a given height in the tree would be located at the same horizontal position. Additionally, users had reported difficulty interacting with the visualization as interactions were limited to modifying a single corner of a selected box. Interaction techniques built into the new system continue to use the Accordion Drawing framework utilized by TreeJuxtaposer but may be more familiar to users


Group members

Nick Chen (nchen@cs.umd.edu)
Maryam Farboodi (farboodi@cs.umd.edu)

This is our final project for Dr. Shneiderman's Spring 2006 Information Visualization class, CMSC 838S.