(New page: 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, how...) |
(No difference)
|
Latest revision as of 19:44, 19 July 2012
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.
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.