Reference : Metabolic networks are NP-hard to reconstruct.
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/10993/552
Metabolic networks are NP-hard to reconstruct.
English
Nikoloski, Zoran [> >]
Grimbs, Sergio [> >]
May, Patrick mailto [Max-Planck-Institute for Molecular Plant Physiology > Bioinformatics]
Selbig, Joachim [> >]
2008
Journal of Theoretical Biology
254
4
807-16
Yes (verified by ORBilu)
International
0022-5193
1095-8541
Netherlands
[en] Animals ; Computational Biology/methods ; Databases, Protein ; Enzymes/metabolism ; Genome ; Metabolic Networks and Pathways ; Pattern Recognition, Automated ; Probability ; Protein Interaction Mapping
[en] High-throughput data from various omics and sequencing techniques have rendered the automated metabolic network reconstruction a highly relevant problem. Our approach reflects the inherent probabilistic nature of the steps involved in metabolic network reconstruction. Here, the goal is to arrive at networks which combine probabilistic information with the possibility to obtain a small number of disconnected network constituents by reduction of a given preliminary probabilistic metabolic network. We define automated metabolic network reconstruction as an optimization problem on four-partite graph (nodes representing genes, enzymes, reactions, and metabolites) which integrates: (1) probabilistic information obtained from the existing process for metabolic reconstruction from a given genome, (2) connectedness of the raw metabolic network, and (3) clustering of components in the reconstructed metabolic network. The practical implications of our theoretical analysis refer to the quality of reconstructed metabolic networks and shed light on the problem of finding more efficient and effective methods for automated reconstruction. Our main contributions include: a completeness result for the defined problem, polynomial-time approximation algorithm, and an optimal polynomial-time algorithm for trees. Moreover, we exemplify our approach by the reconstruction of the sucrose biosynthesis pathway in Chlamydomonas reinhardtii.
http://hdl.handle.net/10993/552
10.1016/j.jtbi.2008.07.015
http://www.sciencedirect.com/science/article/pii/S0022519308003706

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
YJTBI5222.pdfPublisher postprint566.12 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.