%0 Journal Article %1 Markus2009 %A Markus, Heinonen %A Sampsa, Lappalainen %A Mielikäinen, Taneli %A Rousu, Juho %D 2009 %K network pathway %T Computing Atom Mappings for Biochemical Reactions without Subgraph Isomorphism %U http://eprints.pascal-network.org/archive/00005704/ %X The ability to trace the fate of individual atoms through the metabolic pathways is needed in many applications of systems biology and drug discovery. However, this information is not immediately available from the most common metabolome studies and needs to be separately acquired. Automatic discovery of correspondence of atoms in biochemical reactions is called the atom mapping problem. We suggest an effcient approach for solving the atom mapping problem exactly finding mappings of minimum edge edit distance. The algorithm is based on A* search equipped with sophisticated heuristics for pruning the search space. This approach has clear advantages over the commonly used heuristic approach of iterative maximum common subgraph (MCS) algorithm: we explicitly minimize an objective function, we produce so- lutions that typically require less manual curation. The two methods are similar in computational resource demands. We compare the performance of the proposed algorithm against sev- eral alternatives on data obtained from the KEGG LIGAND and RPAIR databases: greedy search, bi-partite graph matching and the MCS ap- proach. Our experiments show that alternative approaches often fail in nding mappings with minimum edit distance.

@article{Markus2009, abstract = {The ability to trace the fate of individual atoms through the metabolic pathways is needed in many applications of systems biology and drug discovery. However, this information is not immediately available from the most common metabolome studies and needs to be separately acquired. Automatic discovery of correspondence of atoms in biochemical reactions is called the atom mapping problem. We suggest an effcient approach for solving the atom mapping problem exactly finding mappings of minimum edge edit distance. The algorithm is based on A* search equipped with sophisticated heuristics for pruning the search space. This approach has clear advantages over the commonly used heuristic approach of iterative maximum common subgraph (MCS) algorithm: we explicitly minimize an objective function, we produce so- lutions that typically require less manual curation. The two methods are similar in computational resource demands. We compare the performance of the proposed algorithm against sev- eral alternatives on data obtained from the KEGG LIGAND and RPAIR databases: greedy search, bi-partite graph matching and the MCS ap- proach. Our experiments show that alternative approaches often fail in nding mappings with minimum edit distance.}, added-at = {2010-03-28T09:50:40.000+0200}, author = {Markus, Heinonen and Sampsa, Lappalainen and Mielikäinen, Taneli and Rousu, Juho}, biburl = {https://www.bibsonomy.org/bibtex/2a63526b6b7290ad6d1975a54c93a4cb4/wnpxrz}, description = {Scientific Commons: Computing Atom Mappings for Biochemical Reactions without Subgraph Isomorphism (2009), 2009-09-04 [Markus, Heinonen, Sampsa, Lappalainen, Mielikäinen, Taneli, Rousu, Juho]}, institution = {PASCAL EPrints [http://eprints.pascal-network.org/perl/oai2] (United Kingdom)}, interhash = {0b4f7b3485e928d703c33f287b09db7b}, intrahash = {a63526b6b7290ad6d1975a54c93a4cb4}, keywords = {network pathway}, location = {http://www.scientificcommons.org/55335635}, timestamp = {2010-03-28T09:50:40.000+0200}, title = {Computing Atom Mappings for Biochemical Reactions without Subgraph Isomorphism}, url = {http://eprints.pascal-network.org/archive/00005704/}, year = 2009 }