A fast and accurate algorithm for comparative analysis of metabolic pathways

Ferhat Ay*, Tamer Kahvct, Valérie De Crécy-Lagard

*Corresponding author for this work

    Research output: Contribution to journalArticle

    16 Scopus citations

    Abstract

    Pathways show how different biochemical entities interact with one another to perform vital functions for the survival of an organism. Comparative analysis of pathways is crucial in identifying functional similarities that are difficult to identify by comparing individual entities that build up these pathways. When interacting entities are of single type, the problem of identifying similarities by aligning the pathways can be reduced to graph isomorphism problem. For pathways with varying types of entities such as metabolic pathways, alignment problem is even more challenging. In order to simplify this problem, existing methods often reduce metabolic pathways to graphs with restricted topologies and single type of nodes. However, these abstractions reduce the relevance of the alignment significantly as they cause losses in the information content. In this paper, we describe an algorithm to solve the pairwise alignment problem for metabolic pathways. A distinguishing feature of our method is that it aligns different types of entities, such as enzymes, reactions and compounds. Also, our approach is free of any abstraction in modeling the pathways. We pursue the intuition that both pairwise similarities of entities (homology) and the organization of their interactions (topology) are important for metabolic pathway alignment. In our algorithm, we account for both by creating an eigenvalue problem for each entity type. We enforce the consistency while combining the alignments of different entity types by considering the reachability sets of entities. Our experiments show that our method finds biologically and statistically significant alignments in the order of milliseconds.

    Original languageEnglish (US)
    Pages (from-to)389-428
    Number of pages40
    JournalJournal of Bioinformatics and Computational Biology
    Volume7
    Issue number3
    DOIs
    StatePublished - Jun 22 2009

    Keywords

    • Alternative enzyme identification
    • Metabolic pathway alignment
    • Metabolic reconstruction
    • Phylogenic reconstruction
    • Search in pathway databases

    ASJC Scopus subject areas

    • Biochemistry
    • Molecular Biology
    • Computer Science Applications

    Fingerprint Dive into the research topics of 'A fast and accurate algorithm for comparative analysis of metabolic pathways'. Together they form a unique fingerprint.

  • Cite this