A novel framework for large scale metabolic network alignments by compression

Michael Dang*, Ferhat Ay, Tamer Kahveci

*Corresponding author for this work

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

    Abstract

    Although the problem of aligning metabolic networks has been considered in the past, the running time and space complexity of these solutions has so far limited their use to moderately sized networks. In this paper, we address the problem of aligning two metabolic networks, particularly when both of them are too large to be dealt with using existing methods. We develop a generic framework that can be used with any existing method to significantly improve the scale of the networks that can be aligned in practical time. Our framework has three major phases, namely the compression phase, the alignment phase and the refinement phase. For the first phase, we develop an algorithm which transforms the given networks to a compressed domain where they are summarized using fewer nodes, termed supernodes, and interactions. In the second phase, we carry out the alignment in the compressed domain using an existing method as our base algorithm. This alignment results in supernode mappings in the compressed domain, each of which are smaller instances of network alignment. In the third phase, we solve each of the instances using the base alignment algorithm to refine the alignment results. Our experiments demonstrate that this method can reduce the sizes of metabolic networks by almost half at each compression level. For the overall framework, we demonstrate how well it increases the performance of an existing alignment method. We observe that we can align twice or more as large networks using the same amount of resources with our framework compared to a recent method for network alignment, namely SubMAP. Our results also suggest that the alignment obtained by only one level of compression captures the original alignment results with very high accuracy.

    Original languageEnglish (US)
    Title of host publication2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011
    Pages274-283
    Number of pages10
    DOIs
    StatePublished - Dec 1 2011
    Event2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, ACM-BCB 2011 - Chicago, IL, United States
    Duration: Aug 1 2011Aug 3 2011

    Publication series

    Name2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, BCB 2011

    Other

    Other2011 ACM Conference on Bioinformatics, Computational Biology and Biomedicine, ACM-BCB 2011
    CountryUnited States
    CityChicago, IL
    Period8/1/118/3/11

    ASJC Scopus subject areas

    • Biomedical Engineering
    • Health Informatics
    • Health Information Management

    Fingerprint Dive into the research topics of 'A novel framework for large scale metabolic network alignments by compression'. Together they form a unique fingerprint.

    Cite this