Optimization Methods in Metabolic Networks E-Book

Costas D. Maranas

• Herausgeber: John Wiley & Sons
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 393

Veröffentlichungsjahr: 2016

Beschreibung

Provides a tutorial on the computational tools that use mathematical optimization concepts and representations for the curation, analysis and redesign of metabolic networks * Organizes, for the first time, the fundamentals of mathematical optimization in the context of metabolic network analysis * Reviews the fundamentals of different classes of optimization problems including LP, MILP, MLP and MINLP * Explains the most efficient ways of formulating a biological problem using mathematical optimization * Reviews a variety of relevant problems in metabolic network curation, analysis and redesign with an emphasis on details of optimization formulations * Provides a detailed treatment of bilevel optimization techniques for computational strain design and other relevant problems

Leseprobe

OPTIMIZATION METHODS IN METABOLIC NETWORKS

COSTAS D. MARANAS

Department of Chemical EngineeringThe Pennsylvania State University

ALI R. ZOMORRODI

Bioinformatics ProgramBoston University

Copyright © 2016 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New JerseyPublished simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Names: Maranas, Costas D., 1967–, author. | Zomorrodi, Ali R., author.Title: Optimization methods in metabolic networks / Costas D. Maranas, Ali R. Zomorrodi.Description: Hoboken, New Jersey : John Wiley & Sons Inc., [2016] | Includes bibliographical references and index. | Description based on print version record and CIP data provided by publisher; resource not viewed.Identifiers: LCCN 2015040810 (print) | LCCN 2015040236 (ebook) | ISBN 9781119188919 (Adobe PDF) | ISBN 9781119189015 (ePub) | ISBN 9781119028499 (cloth)Subjects: | MESH: Metabolic Networks and Pathways–physiology. | Computer Simulation. | Linear Models.Classification: LCC QP171 (print) | LCC QP171 (ebook) | NLM QU 120 | DDC 612.3/9–dc23LC record available at http://lccn.loc.gov/2015040810

Cover image courtesy of Costas D. Maranas and Ali R. Zomorrodi

To my wife, Michelle, my daughters, Cassandra and Christina, and my parents, Olga and Dimitris

Costas D. Maranas

To my wife, Assieh, my daughter, Tara, and my parents, Fatemeh and Hossein

Ali R. Zomorrodi

PREFACE

The objective of this book is to provide a tutorial on the computational tools that use mathematical optimization concepts and representations for the curation, analysis and redesign of metabolic networks. Emphasis is placed on explaining the optimization formulation fundamentals and relevant algorithmic solution techniques. This book does not aim to serve as a comprehensive optimization text as it provides only a condensed treatment of different classes of optimization problems. The main goal here is to use the language and tools of mathematical programming to describe and solve frequently occurring problems in the analysis and redesign of metabolic networks. The interested reader is thus encouraged to refer to dedicated optimization textbooks for a more thorough treatment of different classes of mathematical programming problems. Similarly, the description of metabolism in the book is limited, requiring frequent referral to relevant biochemistry and molecular biology resources. The reader is encouraged to consult the original journal publications for all described techniques. Nevertheless, the treatment presented here has benefited from many years of application and customization on a variety of projects. As a consequence, the day-to-day application, implementation and integration of these techniques may differ from their original exposition in the journal publications. Care is exercised to ensure that the metabolic network descriptions, nomenclature and assumptions are consistent throughout. Many important optimization-based techniques in metabolic networks are absent from this treatment due to space limitations, lack of working experience with them or difficulty in integrating them with the rest of the material. Course notes for a graduate elective on “Optimization in Biological Networks” taught at Pennsylvania State University – University Park formed the basis of the techniques described here.

This book can be used by itself or in combination with other books to support coursework on special topics in network analyses of biological and in particular metabolic networks. It can be used to introduce students with knowledge of metabolism to formal mathematical treatments of core computational tasks in metabolic networks or alternatively to expose students with a mathematical programming background to metabolism. The hope is that the book will serve as a starting point for the students for more in-depth investigations of relevant techniques and concepts found in the cited literature.

Chapter 1 uses a regulatory network inference problem to introduce modeling using mathematical programming formulations. Key concepts such as sets, parameters, variables, constraints and optimization formulations are introduced. This is followed by a formal introduction and definition of fundamental concepts in optimization that establish criteria for the existence of a local or global optimal solution. Chapter 2 introduces linear programming (LP), which underpins many analysis techniques in metabolic networks, and linear duality theory, which is used for solving bilevel optimization problems described in Chapter 8. Chapter 3 provides an introduction to metabolic network modeling and flux balance analysis (FBA) in particular. A number of core FBA analysis techniques that rely on LP are described here. Chapter 4 unveils the concept of discrete or binary variables alongside continuous variables for modeling a variety of tasks in metabolic networks. Both representations and solution techniques of mixed-integer linear programming (MILP) problems are highlighted. Chapter 5 describes how reaction free energy of change considerations can be used to restrict reaction directionality and eliminate thermodynamically infeasible cycles in metabolic networks. Chapter 6 addresses the task of resolving metabolic network gaps and growth prediction inconsistencies in metabolic networks using computational techniques relying on MILP problem formulations. Chapter 7 reviews optimization-based approaches for finding paths that link a source to a target metabolite. Chapter 8 addresses the use of bilevel programming for describing and solving metabolic network redesign problems to maximize the yield of a target product in microbial strain design. Chapter 9 introduces basic concepts, optimality criteria, and solution techniques for both unconstrained and constrained nonlinear programming problems (NLPs). Chapter 10 provides examples of how NLP underpins metabolic network analysis problems such as integration of kinetic expressions into genome-scale metabolic models and metabolic flux elucidation using carbon-labeled isotopes in metabolic flux analysis (MFA). Finally, Chapter 11 lays the foundation for the description and solution of mixed-integer NLP (MINLP) problems and highlights how the nonlinearities of kinetic expressions can be integrated in the strain design bilevel optimization formulations introduced in Chapter 8. A number of example problems are addressed in the text and suggested problems are provided at the end of every chapter. The source GAMS code for all examples in the book are available through a dedicated website for this book (www.maranasgroup.com). Alternative representations using MATLAB, LINGO, etc. can also be derived in a straightforward manner. In addition, Appendix A provides a short guide to GAMS.

The book is intended as a textbook for a graduate or advanced undergraduate elective in the use of optimization in metabolic networks. Topics covered in the book start with a formal treatment of the relevant optimization problem class followed by application in the context of metabolic network analysis. The class of optimization problems becomes progressively more complex starting with LP and MILP and concluding with NLP and MINLP problems. Many of the proofs of convergence and optimality theorems are geared toward the students with a more in-depth interest in optimization and can be skipped without loss of teaching material congruity. Hands-on implementation of all the discussed methods is encouraged to reinforce the introduced concepts.

We would like to acknowledge the people in the C. Maranas group for providing feedback and tirelessly helping with the preparation of the book. In particular, we would like to acknowledge the contribution of Ali Khodayari for assembling the initial set of lecture notes from the related graduate course at Penn State and for helping to create and improve figures; Anupam Chowdhury for performing simulations for examples of Chapters 3, 4, 7, 8, 10, and 11 and for preparing the related figures and computer codes; Chiam Yu Ng and Margaret Simons for helping to create figures and drafting the initial versions of the chapters; and Sarat Ram Gopalakrishnan for helpful feedback on section 10.3 of Chapter 10. Finally, we would like to express our gratitude to Margaret Simons for designing the cover image and for carefully editing the proofs and making numerous suggestions.

Costas D. MaranasAli R. Zomorrodi

1MATHEMATICAL OPTIMIZATION FUNDAMENTALS

This chapter reviews the fundamentals of mathematical optimization and modeling. It starts with a biological network inference problem as a prototype example to highlight the basic steps of formulating an optimization problem. This is followed by a review of some basic mathematical concepts and definitions such as set and function properties and convexity analysis.

1.1 MATHEMATICAL OPTIMIZATION AND MODELING

Mathematical optimization (programming) systematically identifies the best solution out of a set of possible choices with respect to a pre-specified criterion. The general form of an optimization problem is as follows:

where

x

is a

N

-dimensional vector referred to as, the vector of

variables

.

S

is the set from which the elements of

x

assume values. For example,

S

can be the set of real, nonnegative real or nonnegative integers. In general, variables in an optimization problem can be continuous, discrete (integer) or combinations thereof. The former is used to capture the continuously varying properties of a system (e.g., concentrations), whereas the latter is used for discrete decision making (e.g., whether or not to eliminate a reaction).

f

(

x

) is referred to as the

objective function

and serves as a mathematical description of the desired property of the system that should be optimized (i.e., maximized or minimized).

and

are constraints that must be satisfied as equalities or one-sided inequalities, respectively, and represent the feasible space of decision variables.

Any vector x that lies in S and satisfies h(x) and g(x) is called a feasible solution. In addition, if vector x minimizes (maximizes) the objective function, it is an optimal solution point to the optimization problem with an associated optimum solution value f(x). There are different classes of optimization problems depending on the (non)linearity properties of the objective function and constraints as well as the presence or absence of discrete (i.e., binary or integer) and/or continuous variables. Standard classes of optimization problems that generally require different solution techniques are as follows: