A robust pathfinding algorithm using chemical composition

Metabolic Pathfinding

Lahiri, Pratik ; Bhalerao ; Kaustubh

关键词: Metabolic Pathfinding;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/49798/Pratik_Lahiri.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Metabolic pathfinding is the task of finding preferred metabolic pathways frommetabolic large reaction databases. Representing metabolism via networksenables quick enumeration of paths between two compounds. Automatedpathfinding helps in working with ever increasing databases if reactions andin finding novel pathways for metabolic engineering. However, the numberof pathways between two compounds can be as large as 500,000 in somemetabolic models and even more as the size of the input database grows,which makes it imperative that the most relevant ones are ranked highly. Whilegraph theoretic representations of metabolic networks bring speed and easein enumeration of pathways, they also create the challenge of biochemicallyinsensible shortcuts through pool or currency metabolites.In the past, strategies to circumvent such irrelevant pathways have includedweighing networks using the degree of nodes or the manual curation of edgesin the metabolic network. The former method wrongfully penalizes someprimary metabolites central to metabolism, while the latter requires someoneto complete manual curation. KEGG RPAIR database is an annotation todescribe reactions in terms of reactant pairs and has been used for metabolicpathfinding. Here, I first study a few different centrality measures to identifycurrency metabolites and identify one better than the degree centrality. I thendescribe a method to augment the KEGG RPAIR based pathfinding methodusing a chemical composition score and evaluate its ability to augment andreplace the role of RPAIRs in pathfinding. The new algorithm is validatedagainst a set of 30 biochemical pathways in E.coli. Since this method useschemical composition as a fallback measure, it can be used in the absence ofexplicit RPAIR information, thus allowing the identification of putative pathsnot possible via methods using the RPAIR database alone.