Motion Planning In Metabolic Pathways Using Probabilistic Roadmap and A* Algorithms
Motion planning and navigation strategies have found useful applications in many areas such as biological networks. This work applies motion planning algorithms to search for biochemically relevant pathways in metabolic pathways. The choice pathways are represented as graphs with its compounds as nodes (vertices), and the possible reactions between the compounds as the edges. The probabilistic roadmap (PRM) algorithm is then used to construct the roadmap (graph) using its local planner function while modelling a group of pool metabolites as obstacles. A* search algorithm queries the roadmap to get the most relevant (cost effective) path using the thermodynamic feasibility of the reactions as the weighting scheme. For ease of testing and evaluation, the system was implemented using python programming language. Choice pathways from KEGG database in KGML format (i.e. xml format for KEGG) were used to test the system, which revealed that the results were consistent with other pathway search tools with reasonable performance and can be adopted for pathfinding problems. Improvements in several areas can however better optimise the system, example include the aspect of weighting schemes utilized.
Keywords: Metabolic pathway, Metabolite, Organism, Graph, Nodes or Vertices, Edges.
Download Full-Text
ABOUT THE AUTHORS
Angela Makolo
Angela Makolo is with Computer Science Department of the University of Ibadan and the University of Ibadan Bioinformatics Research Group (ui.bioinformatics.edu.ng). She has a PhD in Computer Science with Bioinformatics Option from the University of Ibadan.
Obotu Ojobo
Obotu Ojobo holds his B.Sc. degree at Benue State University and his M.Sc. degree at University of Ibadan. The degrees were all in Computer Science.
Angela Makolo
Angela Makolo is with Computer Science Department of the University of Ibadan and the University of Ibadan Bioinformatics Research Group (ui.bioinformatics.edu.ng). She has a PhD in Computer Science with Bioinformatics Option from the University of Ibadan.
Obotu Ojobo
Obotu Ojobo holds his B.Sc. degree at Benue State University and his M.Sc. degree at University of Ibadan. The degrees were all in Computer Science.
