TreeJuxtaposer

TreeJuxtaposer compares large phylogenetic trees, taxonomies, gene trees, and other Newick-formatted tree structures to identify and visualize structural differences in datasets of up to 500,000 nodes.

Key Features:

• Guaranteed Visibility: Ensures highlighted differences between compared trees remain visually prominent as persistent landmarks.
• Nearly-linear Node Correspondence Algorithm: Computes the optimal corresponding node between two trees using a nearly-linear time algorithm for efficient structural alignment.
• Rectilinear Focus+Context Navigation: Provides rectilinear Focus+Context navigation for dynamic, side-by-side exploration while preserving landmark visibility.
• Newick and Large-scale Support: Supports trees in Newick format and scales to datasets containing up to 500,000 nodes.

Scientific Applications:

• Phylogenetics: Comparing evolutionary trees to assess species relationships and evolutionary history.
• Taxonomy: Comparing classification hierarchies to evaluate taxonomic structure and differences.
• Genealogy: Comparing genealogical trees for genetic research and ancestry studies.
• Network Management: Analyzing and comparing network topologies for management and optimization tasks.
• Call Graph Optimization: Comparing software call graphs to support optimization and structural analysis of codebases.

Methodology:

Implements a guaranteed-visibility mechanism to keep highlighted differences prominent; computes optimal node correspondences between two trees using a nearly-linear algorithm; and employs rectilinear Focus+Context navigation for side-by-side views while maintaining constant frame rates.