A Heuristic Algorithm for Finding the Longest Pathways in a Biochemical Network

Finding the longest cycle is a novel concept in biochemical feedback loop analysis in systems biology. Biochemical networks are often represented as directed graphs in which vertices represent chemical compounds and edges represent chemical reactions between compounds. Therefore, a biochemical longest feedback loop can be formulated as the longest cycle in a directed graph. Because finding the longest cycle in a directed graph is NP-hard, in this paper, we proposed an intelligent heuristic algorithm to find the longest cycle in a directed graph. We tested the algorithm on both randomly generated complex networks and real biochemical networks extracted from the KEGG database. The results showed that our algorithm is able to find more than 70% of the real longest cycles in the 200 randomly generated complex networks and also can find the feedback loop in the longest pathway. Compared with the traditional breadth first search pathway finding algorithm, the search efficiency of the proposed algorithm has been improved dramatically. Among the feedbacks found from the KEGG database using the proposed algorithm, the longest feedback includes 8 compounds, 9 reactions, and 6 pathways across different modules.