SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings
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 (nodes) of the input pathways (graphs). We follow the observation that, in nature, different organisms can perform the same or simi...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Mary Ann Liebert
2011
|
| Online Access: | http://hdl.handle.net/1721.1/66120 |
| _version_ | 1811095419641397248 |
|---|---|
| author | Ay, Ferhat Kellis, Manolis |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ay, Ferhat Kellis, Manolis |
| author_sort | Ay, Ferhat |
| collection | MIT |
| description | 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 (nodes) of the input pathways (graphs). 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. With the motivation that an accurate biological alignment should be able to reveal these functionally similar molecule sets across different species, we develop an algorithm that first measures the similarities between different nodes using a mixture of homology and topological similarity. We combine the two metrics by employing an eigenvalue formulation. We then search for an alignment between the two input pathways that maximizes a similarity score, evaluated as the sum of the similarities of the mapped subnetworks of size at most a given integer k, and also does not contain any conflicting mappings. Here we prove that this maximization is NP-hard by a reduction from the maximum weight independent set (MWIS) problem. We then convert our problem to an instance of MWIS and use an efficient vertex-selection strategy to extract the mappings that constitute our alignment. We name our algorithm SubMAP (Subnetwork Mappings in Alignment of Pathways). We evaluate its accuracy and performance on real datasets. Our empirical results demonstrate that SubMAP can identify biologically relevant mappings that are missed by traditional alignment methods. Furthermore, we observe that SubMAP is scalable for metabolic pathways of arbitrary topology, including searching for a query pathway of size 70 against the complete KEGG database of 1,842 pathways. Implementation in C++ is available at http://bioinformatics.cise.ufl.edu/SubMAP.html. |
| first_indexed | 2024-09-23T16:16:28Z |
| format | Article |
| id | mit-1721.1/66120 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:16:28Z |
| publishDate | 2011 |
| publisher | Mary Ann Liebert |
| record_format | dspace |
| spelling | mit-1721.1/661202022-09-29T19:16:56Z SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings Ay, Ferhat Kellis, Manolis Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Kellis, Manolis Ay, Ferhat Kellis, Manolis 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 (nodes) of the input pathways (graphs). 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. With the motivation that an accurate biological alignment should be able to reveal these functionally similar molecule sets across different species, we develop an algorithm that first measures the similarities between different nodes using a mixture of homology and topological similarity. We combine the two metrics by employing an eigenvalue formulation. We then search for an alignment between the two input pathways that maximizes a similarity score, evaluated as the sum of the similarities of the mapped subnetworks of size at most a given integer k, and also does not contain any conflicting mappings. Here we prove that this maximization is NP-hard by a reduction from the maximum weight independent set (MWIS) problem. We then convert our problem to an instance of MWIS and use an efficient vertex-selection strategy to extract the mappings that constitute our alignment. We name our algorithm SubMAP (Subnetwork Mappings in Alignment of Pathways). We evaluate its accuracy and performance on real datasets. Our empirical results demonstrate that SubMAP can identify biologically relevant mappings that are missed by traditional alignment methods. Furthermore, we observe that SubMAP is scalable for metabolic pathways of arbitrary topology, including searching for a query pathway of size 70 against the complete KEGG database of 1,842 pathways. Implementation in C++ is available at http://bioinformatics.cise.ufl.edu/SubMAP.html. National Science Foundation (U.S.) (Grant CCF-0829867) National Science Foundation (U.S.) (Grant IIS-0845439) 2011-09-29T21:16:17Z 2011-09-29T21:16:17Z 2011-03 Article http://purl.org/eprint/type/JournalArticle 1066-5277 1557-8666 http://hdl.handle.net/1721.1/66120 Ay, Ferhat, Manolis Kellis, and Tamer Kahveci. “SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings.” Journal of Computational Biology 18 (3) (2011): 219-235. Copyright © 2011, Mary Ann Liebert, Inc. en_US http://dx.doi.org/10.1089/cmb.2010.0280 Journal of Computational Biology Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Mary Ann Liebert Mary Ann Liebert |
| spellingShingle | Ay, Ferhat Kellis, Manolis SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings |
| title | SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings |
| title_full | SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings |
| title_fullStr | SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings |
| title_full_unstemmed | SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings |
| title_short | SubMAP: Aligning Metabolic Pathways with Subnetwork Mappings |
| title_sort | submap aligning metabolic pathways with subnetwork mappings |
| url | http://hdl.handle.net/1721.1/66120 |
| work_keys_str_mv | AT ayferhat submapaligningmetabolicpathwayswithsubnetworkmappings AT kellismanolis submapaligningmetabolicpathwayswithsubnetworkmappings |