CDAOStore: A Phylogenetic Repository Using Logic Programming and Web Services

Brandon Chisham, Enrico Pontelli, Tran Cao Son, Ben WrightICLP (Technical Communications) 2011 · OpenReview

TL;DR

This paper introduces CDAOStore, a novel repository for phylogenetic data that leverages semantic web technologies and logic programming. It addresses the challenge of data format heterogeneity and complex querying in evolutionary biology by providing a domain-specific query interface and enabling better interoperability between different bioinformatics tools.

What Problem Does This Paper Address?

The field of evolutionary biology relies heavily on phylogenetic trees to understand the relationships and evolutionary history of life. However, a major bottleneck for large-scale and integrative analyses is the lack of interoperability among existing phylogenetic data repositories and tools. Data is often stored in various, sometimes proprietary, formats, making it difficult to combine and query information effectively. Existing repositories like TreeBase, while valuable, have limitations in handling diverse data formats and supporting complex, domain-specific queries. This paper aims to bridge this gap by creating a more flexible and powerful system for storing, retrieving, and querying phylogenetic data.

Methods

CDAOStore is built upon the EvoIO Stack, a set of interoperability standards for evolutionary biology. This stack includes:

  • Comparative Data Analysis Ontology (CDAO): A formal ontology that defines the semantics of phylogenetic data, including taxa, characters, states, and trees.
  • NeXML: An XML-based exchange format for phylogenetic data and metadata, designed for better interoperability.
  • PhyloWS: A web services API that provides a standardized way to access phylogenetic data.

CDAOStore itself is implemented as an RDF triple store, meaning data is stored as subject-predicate-object statements. This semantic approach allows for richer data representation and querying. A key innovation is the integration of logic programming (Prolog) alongside standard web technologies and SPARQL. Prolog is used to handle complex format transformations and, crucially, to implement domain-specific queries that are difficult or impossible to express using standard query languages like SPARQL. These domain-specific queries are derived from studies of the actual needs of phylogenetic researchers.

Datasets

The paper mentions that CDAOStore was populated by importing data from TreeBase, the largest repository of phylogenetic trees. It also hosts data submitted by other domain scientists. At the time of writing, CDAOStore contained over 4,000 phylogenies and more than 90 million RDF triples. No new benchmarks were introduced; rather, the system was evaluated on sample queries drawn from scientific publications.

Key Insights and Ideas

  • Semantic Web for Biology: Applying semantic web technologies (ontologies, RDF) to biological data can overcome the limitations of traditional, format-specific approaches.
  • Logic Programming for Complex Queries: Integrating logic programming (Prolog) is essential for handling complex, domain-specific queries in fields like phylogenetics, where hierarchical structures and transitive relationships are common.
  • Domain-Driven Query Design: Designing query interfaces based on the actual needs and types of investigations performed by domain experts (life scientists) leads to more useful and powerful tools.
  • Interoperability as a Core Goal: The EvoIO Stack and CDAOStore emphasize interoperability, aiming to make data more accessible and reusable across different bioinformatics applications.

Key Results

CDAOStore is operational and has been successfully populated with a significant amount of phylogenetic data. The system offers a web portal and a PhyloWS API for data access. Preliminary evaluations showed varying execution times for different query types, with some complex queries taking tens of seconds. The paper highlights that performance was not the primary design criterion, with flexibility and advanced querying capabilities being prioritized. The system successfully implements a range of domain-specific queries, including finding phylogenies with specific taxa, calculating minimum spanning clades, and identifying phylogenies based on inference methods.

Limitations and Future Work

The authors acknowledge that performance was not the main focus of the initial implementation, and some queries can be slow. They are working on addressing issues like query timeouts for complex queries (e.g., radius and diameter calculations). Future work includes:

  • Extending the set of domain-specific queries, particularly for taxa clustering and phylogeny clustering based on distance measures.
  • Improving query speed through better representations and pre-computation of metadata.
  • Evaluating the suitability of the current RDFlib platform for handling the growing size of the triple store and exploring alternative, potentially higher-performance triple stores.
  • Adapting the system to accommodate global naming standards for taxa.

Summary updated

Abstract

The CDAOStore is a portal aimed at facilitating the storage and retrieval of data and metadata associated to studies in the field of evolutionary biology and phylogenetic analysis. The novelty of CDAOStore lies in the use of a semantic-based approach to the storage and querying of data. This enables CDAOStore to overcome the data format restrictions and complexities of other repositories (e.g., TreeBase) and to provide a domain-specific query interface, derived from studies of querying requirements for phylogenetic databases. CDAOStore represents the first full implementation of the EvoIO stack, an inter-operation stack composed of a formal ontology (the Comparative Data Analysis Ontology), an XML exchange format (NeXML), and a web services API (PhyloWS). CDAOStore has been implemented on top of an RDF triple store, using a combination of standard web technologies and logic programming technology. In particular, we employed Prolog to support some of the format transformation tasks and, more importantly, in the implementation of several of the domain-specific queries, whose structure is beyond the reach of standard RDF query languages (e.g., SPARQL). CDAOStore is operational and it already hosts over 90 million RDF triples, imported from TreeBase or submitted by other domain scientists.
BibTeX
@inproceedings{chisham2011cdaostore,
  author = {Brandon Chisham and Enrico Pontelli and Tran Cao Son and Ben Wright},
  title = {{CDAOStore: A Phylogenetic Repository Using Logic Programming and Web Services}},
  booktitle = {ICLP (Technical Communications)},
  year = {2011},
  url = {https://openreview.net/forum?id=T39Hrf1l2xk6},
}
Figure