MINIMUM MUTATION ALGORITHM FOR GAPLESS METABOLIC NETWORK EVOLUTION

Esa Pitkänen, Juho Rousu, Mikko Arvas

2011

Abstract

We present a method for inferring the structure of ancestral metabolic networks directly from the networks of observed species and their phylogenetic tree. Our method aims to minimize the number of mutations on the phylogenetic tree, whilst keeping the ancestral networks structurally feasible, i.e., free of reaction gaps. To this end, we present a parsimony-based method that generates metabolic network phylogenies where the ancestral nodes are required to represent gapless metabolic networks, networks where all reactions are reachable from external substrates. In particular, we introduce the gapless minimum mutation problem: finding phylogenies of gapless metabolic networks when the topology of the phylogenetic tree is given, but the content of ancestral nodes is unknown. The gapless minimum mutation problem is shown to be computationally hard to solve even approximatively. We then propose an efficient dynamic programming based heuristic that combines knowledge on both the metabolic network topology and phylogeny of species. Specifically, the reconstruction of each ancestral network is guided by the heuristic to minimize the total phylogeny cost. We experiment by reconstructing phylogenies generated under a simple random model and derived from KEGG for a number of fungal species.

Paper Citation

in Harvard Style

Pitkänen E., Rousu J. and Arvas M. (2011). MINIMUM MUTATION ALGORITHM FOR GAPLESS METABOLIC NETWORK EVOLUTION . In Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms - Volume 1: BIOINFORMATICS, (BIOSTEC 2011) ISBN 978-989-8425-36-2, pages 28-38. DOI: 10.5220/0003132200280038

in Bibtex Style

@conference{bioinformatics11,
author={Esa Pitkänen and Juho Rousu and Mikko Arvas},
title={MINIMUM MUTATION ALGORITHM FOR GAPLESS METABOLIC NETWORK EVOLUTION},
booktitle={Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms - Volume 1: BIOINFORMATICS, (BIOSTEC 2011)},
year={2011},
pages={28-38},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003132200280038},
isbn={978-989-8425-36-2},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms - Volume 1: BIOINFORMATICS, (BIOSTEC 2011)
TI - MINIMUM MUTATION ALGORITHM FOR GAPLESS METABOLIC NETWORK EVOLUTION
SN - 978-989-8425-36-2
AU - Pitkänen E.
AU - Rousu J.
AU - Arvas M.
PY - 2011
SP - 28
EP - 38
DO - 10.5220/0003132200280038