Calculating Elementary Flux Modes with Variable Neighbourhood Search

详细信息    查看全文

• 关键词：Elementary Flux Modes ; Metaheuristics ; Metabolic networks ; Variable neighbourhood search
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9656
• 期：1
• 页码：304-314
• 全文大小：328 KB
• 参考文献：1.Behre, J., Wilhelm, T., von Kamp, A., Ruppin, E., Schuster, S.: Structural robustness of metabolic networks with respect to multiple knockouts. J. Theor. Biol. 252(3), 433–441 (2008)CrossRef
  2.Berkelaar, M., et al.: lpSolve: Interface to Lp_solve v. 5.5 to Solve Linear/Integer Programs (2015), rpackageversion5.6.11. http://​CRAN.​R-project.​org/​package=​lpSolve
  3.Blum, T., Kohlbacher, O.: Using atom mapping rules for an improved detection of relevant routes in weighted metabolic networks. J. Comput. Biol. 15(6), 565–576 (2008)MathSciNet CrossRef
  4.Carlson, R., Srienc, F.: Fundamental Escherichia coli biochemical pathways for biomass and energy production: identification of reactions. Biotechnol. Bioeng. 85(1), 1–19 (2004)CrossRef
  5.Croes, D., Couche, F., Wodak, S.J., van Helden, J.: Inferring meaningful pathways in weighted metabolic networks. J. Mol. Biol. 356(1), 222–236 (2006)CrossRef
  6.Dávid, L., Bockmayr, A.: Computing elementary flux modes involving a set of target reactions. IEEE/ACM Trans. Comput. Biol. Bioinform. 11(6), 1099–1107 (2014)CrossRef
  7.Feist, A.M., Palsson, B.Ø.: The growing scope of applications of genome-scale metabolic reconstructions using Escherichia coli. Nat. Biotech. 26(6), 659–667 (2008)CrossRef
  8.de Figueiredo, L.F., Schuster, S., Kaleta, C., Fell, D.A.: Can sugars be produced from fatty acids? a test case for pathway analysis tools. Bioinformatics 25(1), 152–158 (2009)CrossRef
  9.Hansen, P., Mladenović, N., Moreno-Pérez, J.: Variable neighborhood search: methods and applications. Ann. Oper. Res. 175(1), 367–407 (2010)MathSciNet CrossRef MATH
  10.Céspedes, J.F.H., De Asís Guil Asensio, F., Carrasco, J.M.G.: A new approach to obtain EFMs using graph methods based on the shortest path between end nodes. In: Ortuño, F., Rojas, I. (eds.) IWBBIO 2015, Part I. LNCS, vol. 9043, pp. 641–649. Springer, Heidelberg (2015)
  11.Kaleta, C., de Figueiredo, L.F., Schuster, S.: Can the whole be less than the sum of its parts? pathway analysis in genome-scale metabolic networks using elementary flux patterns. Genome Res. 19(10), 1872–1883 (2009)CrossRef
  12.Kaleta, C., de Figueiredo, L.F., Schuster, S.: EFMEvolver: computing elementary flux modes in genome-scale metabolic networks. LNCS 157, 179–189 (2009)
  13.Klamt, S., Stelling, J.: Combinatorial complexity of pathway analysis in metabolic networks. Mol. Biol. Rep. 29(1–2), 233–236 (2002)CrossRef
  14.Luque, G., Alba, E.: Enhancing parallel cooperative trajectory based metaheuristics with path relinking. In: Proceedings of the 16th Annual Conference on Genetic and Evolutionary Computation (GECCO14), pp. 1039–1046 (2014)
  15.Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)MathSciNet CrossRef MATH
  16.Nash, J.C.: The (Dantzig) simplex method for linear programming. Comput. Sci. Eng. 2(1), 29–31 (2000)CrossRef
  17.Pey, J., Planes, F.J.: Direct calculation of elementary flux modes satisfying several biological constraints in genome-scale metabolic networks. Bioinform. Accepted (2015). doi:10.​1093/​bioinformatics/​btu193
  18.Pey, J., Villar, J.A., Tobalina, L., Rezola, A., García, J.M., Beasley, J.E., Planes, F.J.: TreeEFM: calculating elementary flux modes using linear optimization in a tree-based algorithm. Bioinformatics 31(6), 897–904 (2015)CrossRef
  19.Planes, F.J., Beasley, J.E.: A critical examination of stoichiometric and path-finding approaches to metabolic pathways. Briefings Bioinform. 9(5), 422–436 (2008)CrossRef
  20.Quek, L.E., Nielsen, L.K.: A depth-first search algorithm to compute elementary flux modes by linear programming. BMC Syst. Biol. 8(1), 94 (2014)CrossRef
  21.R Development Core Team: R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria (2008). http://​www.​R-project.​org , ISBN 3-900051-07-0
  22.Rahman, S.A., Advani, P., Schunk, R., Schrader, R., Schomburg, D.: Metabolic pathway analysis web service (pathway hunter tool at cubic). Bioinformatics 21(7), 1189–1193 (2005)CrossRef
  23.Schuster, S., Dandekar, T., Fell, D.A.: Detection of elementary flux modes in biochemical networks: a promising tool for pathway analysis and metabolic engineering. Trends Biotechnol. 17(2), 53–60 (1999)CrossRef
  24.Stelling, J., Klamt, S., Bettenbrock, K., Schuster, S., Gilles, E.D.: Metabolic network structure determines key aspects of functionality and regulation. Nature 420(6912), 190–193 (2002)CrossRef
  25.Stephanopoulos, G.N., Aristidou, A.A., Nielsen, J.H.: Metabolic engineering : principles and methodologies. California Academic Press, San Diego (1998)
  26.Szallasi, Z., Stelling, J., Periwal, V. (eds.): System Modeling in Cellular Biology: From Concepts to Nuts and Bolts, 1st edn. The MIT Press, Canada (2006)MATH
  27.Terzer, M., Stelling, J.: Large-scale computation of elementary flux modes with bit pattern trees. Bioinformatics 24(19), 2229–2235 (2008)CrossRef
  28.Trinh, C.T., Unrean, P., Srienc, F.: Minimal Escherichia coli cell for the most efficient production of ethanol from hexoses and pentoses. Appl. Environ. Microbiol. 74(12), 3634–3643 (2008)CrossRef
  29.Yeung, M., Thiele, I., Palsson, B.Ø.: Estimation of the number of extreme pathways for metabolic networks. BMC Bioinformatics 8(1), 363 (2007)CrossRef
  30.Zanghellini, J., Ruckerbauer, D.E., Hanscho, M., Jungreuthmayer, C.: Elementary flux modes in a nutshell: properties, calculation and applications. Biotechnol. J. 8(9), 1009–1016 (2013)CrossRef
  
• 作者单位：Jose A. Egea (15)
  José M. García (16)
  
  15. Department of Applied Mathematics and Statistics, Technical University of Cartagena, C/ Dr. Fleming s/n, 30202, Cartagena, Spain
  16. Parallel Computer Architecture Group, Facultad de Informática, University of Murcia, Campus Universitario de Espinardo, 30100, Murcia, Spain
  
• 丛书名：Bioinformatics and Biomedical Engineering
• ISBN：978-3-319-31744-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In this work, we calculate Elementary Flux Modes (EFMs) from metabolic networks using a trajectory-based metaheuristic, Variable Neighbourhood Search (VNS). This method is based on the local exploration around an incumbent solution and the subsequent visits to “neighbourhoods” (i.e., other areas of the search space) when the exploration is not successful on improving an objective function. This strategy ensures a suitable balance between exploration and exploitation, which is the key point in metaheuristic-based optimization. Making use of linear programming and the Simplex method, a VNS-based metaheuristic has been designed and implemented. This algorithm iteratively solves the linear programs resulting from the formulation of different hypotheses about the metabolic network. These solutions are, when feasible, EFMs. The application of the proposed method on a benchmark problem corroborates its efficacy.