From Optflux
Jump to: navigation, search

For calculating the shortest path values for reasons of efficiency TNA4OptFlux normally uses the implementation of the breath-first search (BFS) algorithm present in the Jung library, however optionally the Set Based Breath-first Search (SBBFS) algorithm which was developed during the project which produced TNA4OptFlux can be used.

The SBFS algorithm is a variation of BFS which was developed to solve a problem which was initially observed when analyzing metabolic networks, the identification of shortest paths which were biological impossible, this problem arose from the fact that reversible reaction in TNA4OptFlux are connected to their metabolites by paralleled directed edges which lead to situation where the shortest path between two metabolites involved passing though a reaction in which they booth a participated as subtracts or products simultaneous.

A) Using BFS the shortest path between A and B is {A, R1, B} an impossible path since A and B are in the same side of the reaction R1 so they will always be consumed or produced together. B) with SBBFS on the other hand the shortest path between A and B will be {A, R2, E, R3, B} a longer but biologically valid path.

The SBBFS is adds to the normal BFS the notion of edge sets, in this algorithm edges have an associated attribute called the set and the process of path finding must obey to the condition that if a path enters a vertex though an edge of one set it must exit that node though an edge of that either belongs to the same set or as no set associated.

With the SBBFS algorithm if a metabolic network is correctly constructed it is possible to indentify all valid shortest paths from a selected vertex to all the vertices it is connected. It should be noted that since SBBFS must store the paths and edge information it is more memory expansive than the normal BFS.