The Application of the Weighted k-Partite Graph Problem to the Multiple Alignment for Metabolic Pathways
| Autor: | Wenbin Chen, William Hendrix, Nagiza F. Samatova |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
0301 basic medicine
Multiple sequence alignment Theoretical computer science Matching (graph theory) Structure (category theory) Computational Biology 03 medical and health sciences Computational Mathematics Metabolic pathway 030104 developmental biology Computational Theory and Mathematics Similarity (network science) Modeling and Simulation Protein Interaction Mapping Genetics Humans Graph (abstract data type) Computational problem Sequence Alignment Molecular Biology Algorithms Metabolic Networks and Pathways Topology (chemistry) Mathematics |
| Zdroj: | Journal of Computational Biology. 24:1195-1211 |
| ISSN: | 1557-8666 |
| Popis: | The problem of aligning multiple metabolic pathways is one of very challenging problems in computational biology. A metabolic pathway consists of three types of entities: reactions, compounds, and enzymes. Based on similarities between enzymes, Tohsato et al. gave an algorithm for aligning multiple metabolic pathways. However, the algorithm given by Tohsato et al. neglects the similarities among reactions, compounds, enzymes, and pathway topology. How to design algorithms for the alignment problem of multiple metabolic pathways based on the similarity of reactions, compounds, and enzymes? It is a difficult computational problem. In this article, we propose an algorithm for the problem of aligning multiple metabolic pathways based on the similarities among reactions, compounds, enzymes, and pathway topology. First, we compute a weight between each pair of like entities in different input pathways based on the entities' similarity score and topological structure using Ay et al.'s methods. We then construct a weighted k-partite graph for the reactions, compounds, and enzymes. We extract a mapping between these entities by solving the maximum-weighted k-partite matching problem by applying a novel heuristic algorithm. By analyzing the alignment results of multiple pathways in different organisms, we show that the alignments found by our algorithm correctly identify common subnetworks among multiple pathways. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|