Cytoscape.js extension for querying large networks

[ugurdogrusoz]

Background

Traversal-based graph algorithms are especially useful in figuring out "sub-graphs of interest" in a large graph. Examples include simple queries such as k-neighborhood (e.g. neighbors of a gene) as well as more advanced ones such as common targets (genes in downstream of all specified genes) using no more than k links and shortest plus k distance paths [1].

Goal

The goal of this project is to implement such graph algorithms as an extension to Cytoscape.js, a graph visualization and analysis library implemented in pure JavaScript.

Description

Among the queries to be supported are:

• k-neighborhood
• common targets (downstream) / regulators (upstream)
• shortest plus k distance paths
• paths between specified nodes with length no more than k

Notice that these algorithms are variations of the classical ones. For instance, Dijkstra’s algorithm won't work if we want to have all shortest plus a constant distance (paths that are shortest or up to a specified distance longer) paths between two genes.

An implementation of above algorithms are available in Java as part of the paxtools library [2]. They need to be converted to JavaScript and adapted to Cytoscape.js graph model. Cytoscape.js core already provides traversal mechanisms and certain graph algorithms. These would be additional algorithms. Another idea is to make this a generic JavaScript graph algorithms library and write an adapter for Cytsocape.js as an extension.

Difficulty level: 3

This project requires good programming skills. Experience in web technologies (JavaScript , html, css) is a plus.

Potential mentors

Ugur Dogrusoz, Ozgun Babur, Max Franz

[1] U. Dogrusoz, A. Cetintas, E. Demir, and O. Babur, "Algorithms for Effective Querying of Compound Graph-Based Pathway Databases", BMC Bioinformatics, 10:376, 2009.

[2] https://biopax.github.io/Paxtools/

[Anishka0107]

Hi, I am interested in working on this project. I am proficient in graphs algorithms and web technologies (HTML, CSS and JavaScript). Can I be a part of it? @ugurdogrusoz @maxkfranz

[ugurdogrusoz]

@Anishka0107 please read how GSoC works. If you have any specific questions regarding this particular idea, you may email me.

[AlexanderPico]

@Anishka0107 Here's a link to our GSoC page, which includes a timeline and resource links. I particularly recommend the GSoC Student Guide. Thanks for your interest in our projects!

http://nrnb.org/gsoc.html

[ugurdogrusoz]

@Anishka0107 You may refer to the paper (reference [1]) for the actual algorithms we'd like to port to JavaScript. A Java implementation of these algorithms in the context of pathways can be found here: https://github.com/BioPAX/Paxtools/tree/master/paxtools-query/src/main/java/org/biopax/paxtools/query/algorithm

[Anishka0107]

Thank you for the reply @ugurdogrusoz and @AlexanderPico. I have seen the Student Guide and timeline.

[Anishka0107]

Hi, I have mailed you the proposal regarding the implementation ideas. Could you please see it? @ugurdogrusoz

[ugurdogrusoz]

@Anishka0107 Thanks for being so enthusiastic and preparing a proposal. However, it's too early for a proposal. This is a good time to get to know the associated tools. Please take a look at GSoC student guide for details.

[Anishka0107]

Sir, I have shared the draft at the GSoC website regarding this project. Could you please review it and suggest me the edits required? @ugurdogrusoz @ozgunbabur

[Blackglade]

Hi @ugurdogrusoz, I'm actually really interested in submitting a proposal for this project as well. Could I email you with a couple of questions I had regarding traversal algorithms? Also... Cytoscape.JS is pretty cool!

[ugurdogrusoz]

@Anishka0107 your proposal looks good, thanks! @Blackglade sure you can email me with questions you have

[khanspers]

GSoC 2017 selected project