Grafia   Graph Information Processing and Analysis

Software Release



Released on 4/7/2013

Ontology-based Subgraph Querying

OntQ is a novel ontology based subgraph querying framework, which revises subgraph isomorphism by mapping a query to semantically related subgraphs in terms of a given ontology graph. The work establishs a metric to measure the similarity of the matches and accordingly an optimization problem to find top K best matches. A filtering-and-verification strategy is designed to identify (top-K) matches for ontology-based subgraph queries. The framework efficiently extracts a small subgraph of the data graph from an ontology index, and further computes the matches by only accessing the extracted subgraph.


Released in May, 2012

A Self Evolving Distributed Graph Management Environment

Sedge is a software framework that supports large scale graph processing. Essentially, Sedge is inspired by Google’s Pregel. The Pregel like model is simply blind of intensive inter-machine communication and unbalanced workload. Sedge adds functions to support overlapping partitions, with the goal to process local graph queries faster. Sedge is able to minimize inter-machine communication by dynamically adapting graph partitions to query workload change, as well as data change.



Released in June, 2012

Memory Efficient De Bruijn Graph Construction

MSP, Minimum Substring Partitioning, is a method to construct De Bruijn graphs in a memory efficient way. De Bruijn graph is a key step in many de novo genome assembly algorithms that are able to assemble billions of short reads generated by massively parallel DNA sequencing technologies. MSP uses less than 10 gigabytes memory vs. several hundreds of gigabytes memory needed in existing algorithms for large genomes, without runtime slow down.

Software List