tool for calculating the path length between to GO terms (in the MF aspect)?

Question

[halmubaid]

Hi, Is there any software (or online tool) that calculates the path length between two GO terms?

[halmubaid]

I mean 'two GO terms' sorry...

Answer 1

[LLTommy]

I don't know about a public tool (=easy way) at the moment, however, I think it is not that easy. There might be not ONE path, there might be multiple. Also, there might be circles, which makes it more difficult or impossible to answer this question - if you do not specify your question further.

Also, why are you interested in this, I would like to know.

[halmubaid]

thanks for your reply. I believe there are no cycles (circles) as GO is DAG (edges are directed). And yes there can be more than one path between two GO terms but usually we go for the shortest path. I am looking for such tool before we invest time to program it.

[LLTommy]

There most definitely are circles in GO as in pretty much every other ontology. If you don't believe me, follow this link. That is why I said you most likely need to specify your question a bit more, for example if you say that you only want to follow 'is a' relationships, the situation might be different. Still you did not explain why you want this information, what do you think this shortest path would be good for?

[halmubaid]

Ok, I am only considering 'is-a' relationship and looking for the shortest path length between two GO terms before we go ahead and implement it. I need it to implement some similarity measures between GO terms (and so between genes). So it is needed to deduce semantic similarity between genes. --thanks

[LLTommy]

Well. Let's wait for a couple of days and see if somebody else knows about a existing solution. If not, I might be able to help you a bit with this.

Answer 2

[Jean-Karim Heriche]

The Gene Ontology is a directed acyclic graph, provided you only consider is_a (parent/child) relations (see @LLTommy's comments). If so you can apply graph paths algorithm to it. It seems that what you're looking for is the Floyd-Warshall algorithm. You'll find an implementation in the perl Graph module. Alternatively, you can also use the distances() function in the R igraph package which implements several algorithms.

Edit: clarified when GO is a DAG as per @LLTommy's comments

[LLTommy]

Again, the ontology is ONLY acyclic if you look at parent/child relationships and ignore the rest!

[Jean-Karim Heriche]

Yes but this is most of the time what we're interested in or put another way, for most practical purposes, it can be treated as a DAG.

[LLTommy]

Well, who is we? :D I can ensure you that a lot of people are interested in the other relationships as well .... and yes, like I said, your statement is true for parent/child but there is a lot more to these ontologies and that is what I point out because many people seem to miss this/over simplify it.

[Jean-Karim Heriche]

Yes I sometimes forget there's a world outside my office :) I'll edit my answer for people who don't read the comments.