Error in graph.prototype.walker

[manulera]

Hello,

I think there is a bug function graph.prototype.walker. As it is, it only works if for a given node X, the function walking_fun returns an edge in which node X is the object, but not if node X is the subject. This gave a problem with get_descendent_subgraph or get_ancestor_subgraph, I don't remember which one of the two.

[manulera]

I provide a fix in #7

[kltm]

@manulera It might be good to explore this with positive and negative test cases. Given how this needs to work on ontologies, which are inherently directional, from memory I don't think we want to create a situation where subject or object is taken.

[manulera]

But then the function could not accept get_child_edges, and therefore not be used for get_descendent_subgraph, I think.

When you are requested to provide the function to "walk" the ontology, it would be already implicit in the function whether you walk downstream or upstream the interactions.

I am fairly new with using ontologies, tagging @cmungall in case he can say something about this.

[manulera]

This is the commit, changing only two lines:

828c03f

[kltm]

Chris is out for a couple of weeks, so it unlikely to be responsive for a bit.

"Walking", for the purpose of this function is directional, with the covered use cases originating in how we use GO-CAMs for the Noctua JS clients early on. Any changes would have to be compatible with how we currently do directional traversals, so we'd need positive and negative testing code in place. I think that your code would rather change how things are retrieved. I do not believe we have any current use cases that are omni-directional and that's wired pretty deep in the library. If one wanted to do omni-directional operations, I believe that you'd want to add links in both directions or explore up and down and aggregate.

That said, I think it might be good to step back here and look at your use cases. I'm honestly a little surprised that we have anybody not internal to the GO using this library. Most users would likely be directed towards tools like the Ontology Access Kit (OAK, https://github.com/INCATools/ontology-access-kit) and the Ontology Development Kit (ODK, https://github.com/INCATools/ontology-development-kit).

[kltm]

Direct context link: INCATools/obographviz#20

[manulera]

In this case, it would be for getting the descendants of a certain GO term. This would be supported in principle by this library in the function get_ancestor_subgraph.

https://berkeleybop.github.io/bbop-graph/doc/module-bbop-graph-graph.html#get_ancestor_subgraph

I don't think this should be the expected behaviour of the function (minimal example):

import { OboGraphViz } from "obographviz";

async function main() {
    const go_resp = await fetch(
        "http://current.geneontology.org/ontology/go.json"
    );
    const ogv = new OboGraphViz(await go_resp.json());
    const newGraph = ogv.createBbopGraph();
    const termUrl = `http://purl.obolibrary.org/obo/GO_0006366`;
    const descendentSubgraph = newGraph.get_descendent_subgraph(termUrl);
    const ancestorSubgraph = newGraph.get_ancestor_subgraph(termUrl);
    console.log(descendentSubgraph.all_nodes()) // Unexpected, returns a single node, GO_0006366
    console.log(ancestorSubgraph.all_nodes()) // Expected, returns ancestor nodes
}

window.onload = () => {
    main()
};

[kltm]

Ah, okay, I see what's happening now under the hood. Concretely:

var a = require('/tmp/go.json');
var model = new require('..');
var g = new model.graph();
g.load_base_json(a.graphs[0]);
g.all_nodes().length;
// 50999 :)
var anc = g.get_ancestor_subgraph('http://purl.obolibrary.org/obo/GO_0006366');
anc.all_nodes().length;
// 29 :)
g.get_child_nodes('http://purl.obolibrary.org/obo/GO_0006366').length
// 13. :)
var des = g.get_descendent_subgraph('http://purl.obolibrary.org/obo/GO_0006366');
des.all_nodes().length;
// 1 ?! :(

Your PR now makes complete sense to me. I think I need to meditate on it a little more--I kind of want to just get rid of the abstract walker there and just have two functions but I think what you do sniffing the node ID may be fine. (Honestly, my code there is getting a little too cute and gets hard to reason about.)

Either way, it would be good for you to add the positive/negative test to the PR with the test data we have and we can iterate from there.

[kltm]

At a meta-level, I believe this slipped through as we literally use get_descendant_subgraph nowhere in our local codebase and missed the test for it. A good argument for better code coverage tools here in this repo.

[kltm]

Okay, I think I have a fix in (thank you @manulera ) and I now need to figure out how to do a release again.

[manulera]

Hi @kltm thanks for having a look. I think a better choice would be to add an argument to the function to determine walking direction, rather than duplicating the code, and to be more specific about the direction (subject2object / object2subject rather than up/down to avoid confusion, see below).

I propose a solution in #9 which also handles errors in passed function, and prevents passing self-referencing functions. If you absolutely want to have the walker_up and walker_down, you could call walker with the true / false object2subject argument.

Also, I believe the docstrings are wrong in #8:

bbop-graph/lib/graph.js

Line 1221 in 4bc0975

* Walk up a graph. Object to subject.

But then

bbop-graph/lib/graph.js

Line 1264 in 4bc0975

var obj_id = edge.object_id();

And the same for the other function.

[kltm]

Good catch on the doc--I've updated that.

[kltm]

Fixed version should be published on npm with: [email protected]

[manulera]

Hi @kltm and @cmungall unless I am missing something, I think this error persists and get_descendent_subgraph has not the expected behaviour.

I would expect to get the full subgraph , e.g. what you see for GO:0030864 below. However, the code from npm or from this repository only returns the first degree relatives (7 children). The code from my repository that I proposed as a solution for this issue returns the full graph. I have made a small repository that gets all children of the term using the different library versions: npm, and the github versions from berkeleybop and mine, so you can reproduce:

https://github.com/manulera/bbop-graph-error

Happy to re-implement on the current version of the library as I think this library is pretty cool and would like to use it in several projects.

graph BT;
      http://purl.obolibrary.org/obo/GO_0110131["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0110131>GO:0110131</a><br>Aim21-Tda2 complex"]-->|part_of|http://purl.obolibrary.org/obo/GO_0030479["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0030479>GO:0030479</a><br>actin cortical patch<br>"];
      http://purl.obolibrary.org/obo/GO_0110086["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0110086>GO:0110086</a><br>meiotic actomyosin c<br>ontractile ring"]-->|is_a|http://purl.obolibrary.org/obo/GO_0005826["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0005826>GO:0005826</a><br>actomyosin contracti<br>le ring"];
      http://purl.obolibrary.org/obo/GO_0110085["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0110085>GO:0110085</a><br>mitotic actomyosin c<br>ontractile ring"]-->|is_a|http://purl.obolibrary.org/obo/GO_0005826["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0005826>GO:0005826</a><br>actomyosin contracti<br>le ring"];
      http://purl.obolibrary.org/obo/GO_1903144["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:1903144>GO:1903144</a><br>actomyosin contracti<br>le ring actin filame<br>nt"]-->|part_of|http://purl.obolibrary.org/obo/GO_0005826["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0005826>GO:0005826</a><br>actomyosin contracti<br>le ring"];
      http://purl.obolibrary.org/obo/GO_0032157["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0032157>GO:0032157</a><br>prospore contractile<br> ring"]-->|is_a|http://purl.obolibrary.org/obo/GO_0110086["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0110086>GO:0110086</a><br>meiotic actomyosin c<br>ontractile ring"];
      http://purl.obolibrary.org/obo/GO_0000142["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0000142>GO:0000142</a><br>cellular bud neck co<br>ntractile ring"]-->|is_a|http://purl.obolibrary.org/obo/GO_0110085["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0110085>GO:0110085</a><br>mitotic actomyosin c<br>ontractile ring"];
      http://purl.obolibrary.org/obo/GO_0120104["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0120104>GO:0120104</a><br>mitotic actomyosin c<br>ontractile ring, pro<br>ximal layer"]-->|part_of|http://purl.obolibrary.org/obo/GO_0110085["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0110085>GO:0110085</a><br>mitotic actomyosin c<br>ontractile ring"];
      http://purl.obolibrary.org/obo/GO_0120106["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0120106>GO:0120106</a><br>mitotic actomyosin c<br>ontractile ring, dis<br>tal actin filament l<br>ayer"]-->|part_of|http://purl.obolibrary.org/obo/GO_0110085["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0110085>GO:0110085</a><br>mitotic actomyosin c<br>ontractile ring"];
      http://purl.obolibrary.org/obo/GO_0120105["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0120105>GO:0120105</a><br>mitotic actomyosin c<br>ontractile ring, int<br>ermediate layer"]-->|part_of|http://purl.obolibrary.org/obo/GO_0110085["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0110085>GO:0110085</a><br>mitotic actomyosin c<br>ontractile ring"];
      http://purl.obolibrary.org/obo/GO_1990357["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:1990357>GO:1990357</a><br>terminal web"]-->|is_a|http://purl.obolibrary.org/obo/GO_0030864["<u><strong><a href=https://www.ebi.ac.uk/QuickGO/term/GO:0030864>GO:0030864</a><br>cortical actin cytos<br>keleton</strong></u>"];
      http://purl.obolibrary.org/obo/GO_0008091["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0008091>GO:0008091</a><br>spectrin"]-->|part_of|http://purl.obolibrary.org/obo/GO_0030864["<u><strong><a href=https://www.ebi.ac.uk/QuickGO/term/GO:0030864>GO:0030864</a><br>cortical actin cytos<br>keleton</strong></u>"];
      http://purl.obolibrary.org/obo/GO_0030479["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0030479>GO:0030479</a><br>actin cortical patch<br>"]-->|part_of|http://purl.obolibrary.org/obo/GO_0030864["<u><strong><a href=https://www.ebi.ac.uk/QuickGO/term/GO:0030864>GO:0030864</a><br>cortical actin cytos<br>keleton</strong></u>"];
      http://purl.obolibrary.org/obo/GO_0030478["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0030478>GO:0030478</a><br>actin cap"]-->|part_of|http://purl.obolibrary.org/obo/GO_0030864["<u><strong><a href=https://www.ebi.ac.uk/QuickGO/term/GO:0030864>GO:0030864</a><br>cortical actin cytos<br>keleton</strong></u>"];
      http://purl.obolibrary.org/obo/GO_0070687["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0070687>GO:0070687</a><br>macropinocytic cup c<br>ytoskeleton"]-->|part_of|http://purl.obolibrary.org/obo/GO_0030864["<u><strong><a href=https://www.ebi.ac.uk/QuickGO/term/GO:0030864>GO:0030864</a><br>cortical actin cytos<br>keleton</strong></u>"];
      http://purl.obolibrary.org/obo/GO_0032437["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0032437>GO:0032437</a><br>cuticular plate"]-->|part_of|http://purl.obolibrary.org/obo/GO_0030864["<u><strong><a href=https://www.ebi.ac.uk/QuickGO/term/GO:0030864>GO:0030864</a><br>cortical actin cytos<br>keleton</strong></u>"];
      http://purl.obolibrary.org/obo/GO_0005826["<a href=https://www.ebi.ac.uk/QuickGO/term/GO:0005826>GO:0005826</a><br>actomyosin contracti<br>le ring"]-->|part_of|http://purl.obolibrary.org/obo/GO_0030864["<u><strong><a href=https://www.ebi.ac.uk/QuickGO/term/GO:0030864>GO:0030864</a><br>cortical actin cytos<br>keleton</strong></u>"];

Loading

[kltm]

@manulera Hm. I haven't had a chance to try updating our tests in the repo to the most recent version of the GO, so I'm trying to feel my way through here; assuming http://current.geneontology.org/ontology/go.json is on /tmp/go.json:

var a = require('/tmp/go.json');
var model = new require('..');
var g = new model.graph();
g.load_base_json(a.graphs[0]);
g.all_nodes().length;
// 51156 :)
var des = g.get_descendent_subgraph('http://purl.obolibrary.org/obo/GO_0030864');
des.all_nodes().length;
// 17

Which seems to align with what you have in #6 (comment) .
Would you mind confirming? Unless I missed something--quite possible--I'm beginning to think that I may have biffed the release...

[manulera]

Hi @kltm thanks for having a look. Yes, 17 should be the length of des.all_nodes()

[kltm]

@manulera
Hm.

npm install bbop-graph
[...]
+ [email protected]
diff node_modules/bbop-graph/lib/graph.js ~/local/src/git/bbop-graph/lib/graph.js
[returns nothing]

Okay, so it looks like that 0.0.21 version of the code is the one released and it's working for me at my end. Can you confirm the library version at your end and try those commands to see if you get something different?

[manulera]

Hi @kltm I see what's going on now. The library indeed returns the right results if I call it like you did:

import { graph } from "bbop-graph";

const resp = await fetch("http://current.geneontology.org/ontology/go.json");
const goJson = await resp.json();

var g = new graph();
g.load_base_json(goJson.graphs[0]);
console.log(g.all_nodes().length);

var des = g.get_descendent_subgraph(
  "http://purl.obolibrary.org/obo/GO_0030864"
);
console.log(des.all_nodes().length);
// 17

However, obographviz is shipped with its own outdated version of the library (node_modules/obographviz/node_modules/bbop-graph/lib/), so it does not work like this:

import { OboGraphViz } from "obographviz";

const resp = await fetch("http://current.geneontology.org/ontology/go.json");
const goJson = await resp.json();

const goGraph = new OboGraphViz(goJson);
const bbopGraph = goGraph.createBbopGraph();

const subgraph = bbopGraph.get_descendent_subgraph(
  "http://purl.obolibrary.org/obo/GO_0030864"
);

subgraph
  .all_edges()
  .forEach((edge) =>
    console.log(
      edge
        .subject_id()
        .replace("http://purl.obolibrary.org/obo/", "")
        .replace("_", ":")
    )
  );

The weird thing though is that when I used my forked library from github, node was using that instead of using the internal bbop-graph shipped with obographviz, but this was not the case either when I installed bbop-graph@21 with npm nor this github repository.

Anyway, I guess this is then a dependency issue of obographviz rather than an issue of this library. I will make an issue there

[manulera]

Aaand here is the reason why I was getting the error:

WHen I was using my library:

  "dependencies": {
    "bbop-graph": "github:manulera/bbop-graph",
    "obographviz": "^0.4.2"
  },

When I was using this one

  "dependencies": {
    "obographviz": "^0.4.2",
    "bbop-graph": "github:berkeleybop/bbop-graph"
  },

I thought the order would not matter! Anyway something learnt today. I will close the issue, sorry for the confusion!