Graph Sorting

In order to be able to compute pathway signal flow propagation, one needs to perform sorting of the pathway in a way that all the nodes are put in levels of increasing order, such that nodes of lower level interact with the nodes of the next level, until reaching the output or sink nodes. For directed acyclic graphs (DAGs), i.e. graphs that do not contain cycles, topological sorting may be applied to order the nodes in such a way that for each directed edge uv, the node u comes before the node v. If the graph contains cycles, however, topological sorting is impossible. Biological pathways mostly contain cycles that represent positive or negative feedback loops. Thus, some assumptions should be made in order to classify the nodes into levels of signal propagation, and respective algorithms should be applied.

1. Breadth first search (BFS) algorithm. BFS algorithm will sort the nodes into levels of increasing order, where each level indicates the shortest path distance from nodes of that level to the input nodes (or nodes of the initial level). Signal flow propagation, in this case, will proceed with the assumption that the signal flow starts at input nodes, then flows to all the nodes that are directly reachable from input nodes, and so on, until reaching output or sink nodes. BFS algorithm has been applied by Isik et al in Pathway Scoring Application.

2. Depth first search (DFS) algorithm. DFS algorithm traverses the graph starting from an input node, then visits all the nodes on a branch starting from that nodes, then returns to the last branching point and continues its traversal to the end of the second branch, and so on. For sorting purposes, DFS will assign timestamps to each node it visits, to indicate the level of that node. The advantage of DFS is that it finds cycles in the graph and it should be applied in cases where finding cycles is essential for the signal propagation algorithm to work.

3. Sometimes, it is reasonable to treat edges which introduce cycles in the graph separately, before proceeding to sorting and signal propagation. In this case, one would try to minimize the number of such edges. For this, there exist approximate solutions to the feedback arc set problem, that is to find the minimal set of edges in a directed cyclic graph, which, if removed or reversed, will make the graph acyclic. These algorithms are not intended for initial implementation, but will be considered in further developments (see below).