Reference : Metabolic networks are NP-hard to reconstruct.
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Metabolic networks are NP-hard to reconstruct.
Nikoloski, Zoran [> >]
Grimbs, Sergio [> >]
May, Patrick mailto [Max-Planck-Institute for Molecular Plant Physiology > Bioinformatics]
Selbig, Joachim [> >]
Journal of Theoretical Biology
Yes (verified by ORBilu)
[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.

File(s) associated to this reference

Fulltext file(s):

Limited access
YJTBI5222.pdfPublisher postprint566.12 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.