Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1109/ICMLA.2010.81 | ICMLA |
Keywords | Field | DocType |
search efficiency,vertex functions,np-hard,vertex,longest feedback,longest cycle,intelligent heuristic algorithm,kegg database,chemical reactions,chemical compound,biochemical network,biology,heuristic algorithm,longest pathways,search problems,computational complexity,complex network,directed graph,proposed algorithm,biochemical longest feedback loop,biochemical feedback loop analysis,directed graphs,systems biology,chemical reaction,longest pathway,real longest cycle,feedback loop,biological systems,algorithm design and analysis,breadth first search,system biology,complex networks,databases,np hard | Algorithm design,Vertex (geometry),Computer science,Heuristic (computer science),Breadth-first search,Directed graph,Theoretical computer science,Feedback loop,Complex network,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
978-1-4244-9211-4 | 0 | 0.34 |
References | Authors | |
12 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chun-Mei Liu | 1 | 245 | 41.30 |
Hui Li | 2 | 3 | 5.46 |
Alison Leonce | 3 | 0 | 0.34 |
Legand Burge | 4 | 29 | 9.60 |
John Trimble | 5 | 5 | 1.49 |
Peter A. Keiller | 6 | 0 | 1.01 |
Abdul-aziz Yakubu | 7 | 8 | 3.47 |