{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/49798"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/49798","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A robust pathfinding algorithm using chemical composition","abstract":"Metabolic pathfinding is the task of finding preferred metabolic pathways from metabolic large reaction databases. Representing metabolism via networks enables quick enumeration of paths between two compounds. Automated pathfinding helps in working with ever increasing databases if reactions and in finding novel pathways for metabolic engineering. However, the number of pathways between two compounds can be as large as 500,000 in some metabolic models and even more as the size of the input database grows, which makes it imperative that the most relevant ones are ranked highly. While graph theoretic representations of metabolic networks bring speed and ease in enumeration of pathways, they also create the challenge of biochemically insensible shortcuts through pool or currency metabolites. In the past, strategies to circumvent such irrelevant pathways have included weighing networks using the degree of nodes or the manual curation of edges in the metabolic network. The former method wrongfully penalizes some primary metabolites central to metabolism, while the latter requires someone to complete manual curation. KEGG RPAIR database is an annotation to describe reactions in terms of reactant pairs and has been used for metabolic pathfinding. Here, I first study a few different centrality measures to identify currency metabolites and identify one better than the degree centrality. I then describe a method to augment the KEGG RPAIR based pathfinding method using a chemical composition score and evaluate its ability to augment and replace the role of RPAIRs in pathfinding. The new algorithm is validated against a set of 30 biochemical pathways in E.coli. Since this method uses chemical composition as a fallback measure, it can be used in the absence of explicit RPAIR information, thus allowing the identification of putative paths not possible via methods using the RPAIR database alone.","abstract_html":"Metabolic pathfinding is the task of finding preferred metabolic pathways from metabolic large reaction databases. Representing metabolism via networks enables quick enumeration of paths between two compounds. Automated pathfinding helps in working with ever increasing databases if reactions and in finding novel pathways for metabolic engineering. However, the number of pathways between two compounds can be as large as 500,000 in some metabolic models and even more as the size of the input database grows, which makes it imperative that the most relevant ones are ranked highly. While graph theoretic representations of metabolic networks bring speed and ease in enumeration of pathways, they also create the challenge of biochemically insensible shortcuts through pool or currency metabolites. In the past, strategies to circumvent such irrelevant pathways have included weighing networks using the degree of nodes or the manual curation of edges in the metabolic network. The former method wrongfully penalizes some primary metabolites central to metabolism, while the latter requires someone to complete manual curation. KEGG RPAIR database is an annotation to describe reactions in terms of reactant pairs and has been used for metabolic pathfinding. Here, I first study a few different centrality measures to identify currency metabolites and identify one better than the degree centrality. I then describe a method to augment the KEGG RPAIR based pathfinding method using a chemical composition score and evaluate its ability to augment and replace the role of RPAIRs in pathfinding. The new algorithm is validated against a set of 30 biochemical pathways in E.coli. Since this method uses chemical composition as a fallback measure, it can be used in the absence of explicit RPAIR information, thus allowing the identification of putative paths not possible via methods using the RPAIR database alone.","abstract_has_math":false,"creators":["Lahiri, Pratik"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Bioengineering","degree_department":null,"school":null,"contributors":["Bhalerao, Kaustubh"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-05-30T17:18:18Z","date_published":"2014-05-30T17:18:18Z","updated_at":"2026-07-22T22:25:40Z","subjects":["Metabolic Pathfinding"],"languages":["en"],"rights":["Copyright 2014 Pratik Lahiri"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/49798","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Bhalerao, Kaustubh"]},{"key":"dc:creator","label":"Author","values":["Lahiri, Pratik"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-05-30T17:18:18Z","2016-09-22T20:59:19Z","2014-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Bioengineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Metabolic Pathfinding"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Pratik Lahiri"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/49798"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Metabolic pathfinding is the task of finding preferred metabolic pathways from metabolic large reaction databases. Representing metabolism via networks enables quick enumeration of paths between two compounds. Automated pathfinding helps in working with ever increasing databases if reactions and in finding novel pathways for metabolic engineering. However, the number of pathways between two compounds can be as large as 500,000 in some metabolic models and even more as the size of the input database grows, which makes it imperative that the most relevant ones are ranked highly. While graph theoretic representations of metabolic networks bring speed and ease in enumeration of pathways, they also create the challenge of biochemically insensible shortcuts through pool or currency metabolites. In the past, strategies to circumvent such irrelevant pathways have included weighing networks using the degree of nodes or the manual curation of edges in the metabolic network. The former method wrongfully penalizes some primary metabolites central to metabolism, while the latter requires someone to complete manual curation. KEGG RPAIR database is an annotation to describe reactions in terms of reactant pairs and has been used for metabolic pathfinding. Here, I first study a few different centrality measures to identify currency metabolites and identify one better than the degree centrality. I then describe a method to augment the KEGG RPAIR based pathfinding method using a chemical composition score and evaluate its ability to augment and replace the role of RPAIRs in pathfinding. The new algorithm is validated against a set of 30 biochemical pathways in E.coli. Since this method uses chemical composition as a fallback measure, it can be used in the absence of explicit RPAIR information, thus allowing the identification of putative paths not possible via methods using the RPAIR database alone.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-04-30T14:53:38Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Lahiri_Pratik.pdf: 1461558 bytes, checksum: 829ae14af4f6be6d82512bafd92b75d7 (MD5)","Made available in DSpace on 2014-05-30T17:18:18Z (GMT). No. of bitstreams: 2 Pratik_Lahiri.pdf: 1461563 bytes, checksum: 225483db568f77ab276ee50e655c4130 (MD5) license.txt: 4063 bytes, checksum: b29ff13e1069c8857e7bb477e29d6481 (MD5)","Item marked as restricted to the 'Administrator' Group (id=1) by Seth Robbins (robbins.sd@gmail.com) on 2014-05-30T17:21:31Z Item is restricted until 2016-05-30T17:21:23Z","Restriction data tranferred 2014-07-01T11:39:40-05:00 Original Data Group with Access Administrator Release Date: 2016-05-30 12:21:23 UTC Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","Limited Restriction Lifted for Item 49849 on 2016-09-22T20:59:19Z."]},{"key":"dc:title","label":"Title","values":["A robust pathfinding algorithm using chemical composition"]}]}],"canonical_facts":{"dc:contributor":["Bhalerao, Kaustubh"],"dc:creator":["Lahiri, Pratik"],"dc:date":["2014-05-30T17:18:18Z","2016-09-22T20:59:19Z","2014-05"],"dc:description":["Metabolic pathfinding is the task of finding preferred metabolic pathways from metabolic large reaction databases. Representing metabolism via networks enables quick enumeration of paths between two compounds. Automated pathfinding helps in working with ever increasing databases if reactions and in finding novel pathways for metabolic engineering. However, the number of pathways between two compounds can be as large as 500,000 in some metabolic models and even more as the size of the input database grows, which makes it imperative that the most relevant ones are ranked highly. While graph theoretic representations of metabolic networks bring speed and ease in enumeration of pathways, they also create the challenge of biochemically insensible shortcuts through pool or currency metabolites. In the past, strategies to circumvent such irrelevant pathways have included weighing networks using the degree of nodes or the manual curation of edges in the metabolic network. The former method wrongfully penalizes some primary metabolites central to metabolism, while the latter requires someone to complete manual curation. KEGG RPAIR database is an annotation to describe reactions in terms of reactant pairs and has been used for metabolic pathfinding. Here, I first study a few different centrality measures to identify currency metabolites and identify one better than the degree centrality. I then describe a method to augment the KEGG RPAIR based pathfinding method using a chemical composition score and evaluate its ability to augment and replace the role of RPAIRs in pathfinding. The new algorithm is validated against a set of 30 biochemical pathways in E.coli. Since this method uses chemical composition as a fallback measure, it can be used in the absence of explicit RPAIR information, thus allowing the identification of putative paths not possible via methods using the RPAIR database alone.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-04-30T14:53:38Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Lahiri_Pratik.pdf: 1461558 bytes, checksum: 829ae14af4f6be6d82512bafd92b75d7 (MD5)","Made available in DSpace on 2014-05-30T17:18:18Z (GMT). No. of bitstreams: 2 Pratik_Lahiri.pdf: 1461563 bytes, checksum: 225483db568f77ab276ee50e655c4130 (MD5) license.txt: 4063 bytes, checksum: b29ff13e1069c8857e7bb477e29d6481 (MD5)","Item marked as restricted to the 'Administrator' Group (id=1) by Seth Robbins (robbins.sd@gmail.com) on 2014-05-30T17:21:31Z Item is restricted until 2016-05-30T17:21:23Z","Restriction data tranferred 2014-07-01T11:39:40-05:00 Original Data Group with Access Administrator Release Date: 2016-05-30 12:21:23 UTC Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","Limited Restriction Lifted for Item 49849 on 2016-09-22T20:59:19Z."],"dc:identifier":["http://hdl.handle.net/2142/49798"],"dc:language":["en"],"dc:rights":["Copyright 2014 Pratik Lahiri"],"dc:subject":["Metabolic Pathfinding"],"dc:title":["A robust pathfinding algorithm using chemical composition"],"dc:type":["text"],"thesis:degree_discipline":["Bioengineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:40Z"}