{"action":"opened","issue":{"url":"https://api.github.com/repos/dondi/GRNsight/issues/298","repository_url":"https://api.github.com/repos/dondi/GRNsight","labels_url":"https://api.github.com/repos/dondi/GRNsight/issues/298/labels{/name}","comments_url":"https://api.github.com/repos/dondi/GRNsight/issues/298/comments","events_url":"https://api.github.com/repos/dondi/GRNsight/issues/298/events","html_url":"https://github.com/dondi/GRNsight/issues/298","id":168190993,"number":298,"title":"How to deal with autoregulatory nodes in shortest path computation","user":{"login":"kdahlquist","id":6463867,"avatar_url":"https://avatars.githubusercontent.com/u/6463867?v=3","gravatar_id":"","url":"https://api.github.com/users/kdahlquist","html_url":"https://github.com/kdahlquist","followers_url":"https://api.github.com/users/kdahlquist/followers","following_url":"https://api.github.com/users/kdahlquist/following{/other_user}","gists_url":"https://api.github.com/users/kdahlquist/gists{/gist_id}","starred_url":"https://api.github.com/users/kdahlquist/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kdahlquist/subscriptions","organizations_url":"https://api.github.com/users/kdahlquist/orgs","repos_url":"https://api.github.com/users/kdahlquist/repos","events_url":"https://api.github.com/users/kdahlquist/events{/privacy}","received_events_url":"https://api.github.com/users/kdahlquist/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/dondi/GRNsight/labels/functionality","name":"functionality","color":"0052cc"},{"url":"https://api.github.com/repos/dondi/GRNsight/labels/priority%200.5","name":"priority 0.5","color":"fad8c7"}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2016-07-28T20:39:04Z","updated_at":"2016-07-28T20:39:04Z","closed_at":null,"body":"Copying over an e-mail thread between @dondi, @acrans, and @kdahlquist\r\n\r\nMy original e-mail to @acrans:\r\n\r\nFor the GRNsight graph visualization software that Dondi and I are working on, we have implemented an open source library that computes the shortest path between nodes using the Dijkstra algorithm.  The software checks out with a manual inspection of the graph.  However, we have self-referential nodes in the graph, which the algorithm has returned a \"0\" for the shortest path between its own node, but it seems to me that it should be a \"1\" because there is actually a path there and that \"0\" suggests to me that no path is possible.  Nodes for which there really is no path are returned as blank right now (which is returned for many pairs of nodes because it is a sparse network).\r\n\r\nI'm not easily finding a reference that tells me what is the proper answer for what the shortest path is for a node referring to itself according to graph theory, so I was hoping that you could answer that for me or point me to a canonical reference.\r\n\r\nResponse from @acrans:\r\n\r\nI think you probably want to take out the loops to use the Algorithm.  If my memory serves me, the algorithm only works with \"simple\" graphs (i.e. ones without loops).  Besides, they're not contributing anything. =)  \r\n\r\nHere's something from Sage online.  Sorry, I gotta run now, but I'll try to help more later.\r\n\r\nhttp://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph.html\r\n\r\nResponse from @dondi:\r\n\r\nI think what we are dealing with here is a situation where a modeling approach (directed graphs) may have some caveats with respect to the real-world system that it is modeling. When Kam and I discussed this a few weeks ago, I mentioned how algorithmically, it makes sense that a node with an edge to itself is given a distance of zero, because in the graph theoretical sense, you are \"already there.\" The self-directed edge is itself a longer path than the \"zero\" path of already being at the node. My suggestion was to tweak this a bit for GRNs because with GRNs, it _is_ significant that there is a self-directed edge, because it indicates self-regulation/-suppression vs. having no effect.\r\n\r\nThe Wikipedia description of Dijkstra's algorithm may help explain why the algorithm computes zero:\r\n\r\n    https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm\r\n\r\nEssentially, the distance of a node to itself is initialized as zero, and no further evaluation is performed because a node's neighbors do not include itself. In the version above, the absence of a path also is indicating by a distance of positive infinity, not zero. The cytoscapejs implementation appears to replace this with empty values.\r\n\r\nBut of course this is the algorithm's assumption, and the key here I think is that the real-world entity that we are modeling has a distinct property which does not line up with the algorithmic result. Perhaps we can modify/augment the implementation so that GRNsight makes a special-case calculation for nodes with self-referring edges so that we consider their shortest paths to be 1 and not 0.\r\n\r\n@kdahlquist response:\r\n\r\n@dondi, I remember us talking about replacing the 0's with 1's.  I guess what I was trying to suss out was, is that a valid thing to do.  In terms of the biology, it make sense to me, but I don't want to be violating what is accepted  theory/practice either.\r\n\r\nThe other layer of the biology is that our nodes are simulataneously representing both the DNA (gene) and protein.  So, a self-referential node really means that the protein encoded by that gene binds to the DNA of its own gene, but that there are, in fact, two entities, the DNA and the protein.\r\n\r\nHaving decided to replace the 0's with 1's for self-referential edges, should the rest of the 0's be replaced with an empty value?"}}
{"actor":{"display_login":"kdahlquist"}}