BACKGROUND: Parsimony methods are widely used in molecular evolution to estimate the most plausible phylogeny for a set of characters. Sankoff parsimony determines the minimum number of changes required in a given phylogeny when a cost is associated to transitions between character states. Although optimizations exist to reduce the computations in the number of taxa, the original algorithm takes time O(n(2)) in the number of states, making it impractical for large values of n. RESULTS: In this study we introduce an optimization of Sankoff parsimony for the reconstruction of ancestral states when ultrametric or additive cost matrices are used. We analyzed its performance for randomly generated matrices, Jukes-Cantor and Kimura's two-parameter models of DNA evolution, and in the reconstruction of elongation factor-1alpha and ancestral metabolic states of a group of eukaryotes, showing that in all cases the execution time is significantly less than with the original implementation. CONCLUSION: The algorithms here presented provide a fast computation of Sankoff parsimony for a given phylogeny. Problems where the number of states is large, such as reconstruction of ancestral metabolism, are particularly adequate for this optimization. Since we are reducing the computations required to calculate the parsimony cost of a single tree, our method can be combined with optimizations in the number of taxa that aim at finding the most parsimonious tree.

MOTIVATION: The DNA Data Bank of Japan (DDBJ) has developed a new DNA database system with a new schema design to accommodate rapid change and growth of requirements on the system. RESULTS: The new schema and systems were created using an object-oriented design approach. The design was accomplished in accordance with ANSI/SPARC three-level schema architecture. First, the conceptual schema was designed using a functional model named AIS (associative information structure) and was visualized in extended diagram format. The model is a natural extension of an ER (entity relationship) model and describes real-world objects in binary associations between entities with the concept of order. Second, the schema was mapped on a relational database as a physical schema. All details are concentrated in this schema and the layer lying above enjoys physical independence. Finally, as another layer, external modeling was introduced for the database applications interface. It provides set-at-a-time basis operations and was implemented as a C++ object-oriented library. On this common framework of a new schema, a new annotator's workbench named Yamato II and a World Wide Web (WWW) submission system named Sakura have been successfully developed to improve drastically daily transactions in the DDBJ. AVAILABILITY: Sakura is available at the following address: http://sakura.ddbj.nig.ac.jp. CONTACT: [email protected]