SubMAP: Aligning metabolic pathways with subnetwork mappings

Ferhat Ay*, Tamer Kahveci

*Corresponding author for this work

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    8 Scopus citations

    Abstract

    We consider the problem of aligning two metabolic pathways. Unlike traditional approaches, we do not restrict the alignment to one-to-one mappings between the molecules of the input pathways. We follow the observation that in nature different organisms can perform the same or similar functions through different sets of reactions and molecules. The number and the topology of the molecules in these alternative sets often vary from one organism to another. In other words, given two metabolic pathways of arbitrary topology, we would like to find a mapping that maximizes the similarity between the molecule subsets of query pathways of size at most a given integer k. We transform this problem into an eigenvalue problem. The solution to this eigenvalue problem produces alternative mappings in the form of a weighted bipartite graph. We then convert this graph to a vertex weighted graph. The maximum weight independent subset of this new graph is the alignment that maximizes the alignment score while ensuring consistency. We call our algorithm SubMAP (Subnetwork Mappings in Alignment of Pathways). We evaluate its accuracy and performance on real datasets. Our experiments demonstrate that SubMAP can identify biologically relevant mappings that are missed by traditional alignment methods and it is scalable for real size metabolic pathways.

    Original languageEnglish (US)
    Title of host publicationResearch in Computational Molecular Biology - 14th Annual International Conference, RECOMB 2010, Proceedings
    Pages15-30
    Number of pages16
    DOIs
    StatePublished - Dec 23 2010
    Event14th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2010 - Lisbon, Portugal
    Duration: Apr 25 2010Apr 28 2010

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume6044 LNBI
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other14th Annual International Conference on Research in Computational Molecular Biology, RECOMB 2010
    CountryPortugal
    CityLisbon
    Period4/25/104/28/10

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'SubMAP: Aligning metabolic pathways with subnetwork mappings'. Together they form a unique fingerprint.

    Cite this