We present several visualization systems for comparing and browsing evolutionary trees and genomic sequences. These systems use the Focus+Context navigational metaphor of allowing users to fluidly stretch and shrink parts of the view, as if manipulating a rubber sheet with the borders tacked down. We introduce cognitive scalability to this approach by guaranteeing the visibility of landmarks at all times, so that users can stay oriented as they explore complex datasets. In our systems, landmarks can be regions of difference between datasets, or the results of a search, or user-chosen regions. This technique, which we call "accordion drawing", supports smooth realtime transitions between a big-picture overview and a drilled-down views that show details in context.
TreeJuxtaposer is a system that allows users to compare large trees of several hundred thousand nodes. We propose a new methodology for detailed structural comparison between two trees and provide a new nearly-linear algorithm for computing the best corresponding node from one tree to another. SequenceJuxtaposer is a sequence visualization tool for the exploration and comparison of biomolecular sequences. SequenceJuxtaposer supports interaction at 20 frames per second when browsing a single sequence of over 1.2 million base pairs, or large collections of sequences up to 2 million total base pairs. In both systems, all runtime rendering algorithms are sublinear in the total number of tree nodes or base pairs in the dataset, and all preprocessing is subquadratic in those variables. Our rendering algorithms accomodate high-resolution displays as well as standard screen sizes. With these systems, we are able to quickly observe many features that had previously required significant analysis to discover.
We also present the TJC and TJC-Q systems, which allow users to browse extremely large trees using the accordion drawing technique. TJC is a system that supports browsing trees up to 15 million nodes by exploiting leading-edge graphics hardware while TJC-Q allows browsing trees up to 5 million node on commodity platforms. Both of these systems use a fast new algorithm for drawing and culling and benefit from a complete redesign of all data structures for more efficient memory usage and reduced preprocessing time. In addition to browsing evolutionary trees, these tools are also useful in many other application domains where there is a demand for large-scale tree browsing, including network management, software engineering, database integration, and genealogy.
About the speaker:
Tamara Munzner has been an assistant professor in the University of British Columbia Department of Computer Science since 2002. Her current research interests are information visualization, graph drawing, dimensionality reduction, and interactive computer graphics. She was a research scientist from 2000 to 2002 at the Compaq Systems Research Center in California, and earned her PhD from Stanford between 1995 and 2000. She was on the technical staff of The Geometry Center, a mathematical visualization research group at the University of Minnesota, from 1991 to 1995.
Contact information:
Tamara Munzner
University of British Columbia, Department of Computer Science
web: http://www.cs.ubc.ca/~tmm
email: