Crimson: A Data Management System to Support Evaluating Phylogenetic Tree Reconstruction Algorithms ∗

Evolutionary and systems biology increasingly rely on the con-struction of large phylogenetic trees which represent the relation-ships between species of interest. As the number and size of such trees increases, so does the need for efficient data storage and query capabilities. Although much attention has been focused on XML as a tree data model, phylogenetic trees differ from document-oriented applications in their size and depth, and their need for structure-based queries rather than path-based queries. This paper focuses on Crimson, a tree storage system for phyloge-netic trees used to evaluate phylogenetic tree reconstruction algo-rithms within the context of the NSF CIPRes project. A goal of the modeling component of the CIPRes project is to construct a huge simulation tree representing a “gold standard ” of evolutionary his-tory against which phylogenetic tree reconstruction algorithms can be tested. In this demonstration, we highlight our storage and indexing strate-gies and show how Crimson is used for benchmarking phylogenetic tree reconstruction algorithms. We also show how our design can be used to support more general queries over phylogenetic trees. 1