BACKGROUND: Serratia marcescens is a chitinolytic bacterium that can potentially be used for consolidated bioprocessing to convert chitin to value-added chemicals. Currently, S. marcescens is poorly characterized and studies on intracellular metabolic and regulatory mechanisms would expedite development of bioprocessing applications. RESULTS: In this study, our goal was to characterize the metabolic profile of S. marcescens to provide insight for metabolic engineering applications and fundamental biological studies. Hereby, we constructed a constraint-based genome-scale metabolic model (iSR929) including 929 genes, 1185 reactions and 1164 metabolites based on genomic annotation of S. marcescens Db11. The model was tested by comparing model predictions with experimental data and analyzed to identify essential aspects of the metabolic network (e.g. 138 essential genes predicted). The model iSR929 was refined by integrating RNAseq data of S. marcescens growth on three different carbon sources (glucose, N-acetylglucosamine, and glycerol). Significant differences in TCA cycle utilization were found for growth on the different carbon substrates, For example, for growth on N-acetylglucosamine, S. marcescens exhibits high pentose phosphate pathway activity and nucleotide synthesis but low activity of the TCA cycle. CONCLUSIONS: Our results show that S. marcescens model iSR929 can provide reasonable predictions and can be constrained to fit with experimental values. Thus, our model may be used to guide strain designs for metabolic engineering to produce chemicals such as 2,3-butanediol, N-acetylneuraminic acid, and n-butanol using S. marcescens.

We introduce a framework for finding and analyzing all optimal solutions to a linear-programming-based model for cellular metabolism. The implementation of a pivoting-based method for generating alternate optimal reaction fluxes is described. We present a novel strongly polynomial algorithm to decompose a matrix of alternate optimal solutions of an optimization problem into independent subsets of variables and their respective alternate solutions. The matrix can be reconstructed as a Cartesian product of these subsets of alternate solutions. We demonstrate that our strategy for enumeration is more efficient than other methods, and that our Cartesian product matrix decomposition can quickly recover independent substructures. The framework is applied to analyze the metabolic reconstruction of a disease-causing organism, revealing metabolic pathways that are independently regulated. Data and the online supplement are available at https://doi.org/10.1287/ijoc.2016.0724 .

Solution methods are presented for a mixed-integer program (MIP) associated with a method for constrained discrimination. In constrained discrimination, one wishes to maximize the probability of correct classification subject to intergroup misclassification limits. The misclassification limits are satisfied by allowing the placement of observations in a reserved judgment group. The approach investigated here involves modifying a standard classification rule by solving an optimization problem. A polynomial-time algorithm for solving the problem is given for two-group discrimination. The decision problem upon which the optimization problem is based is shown to be NP complete for a general number of groups. For three or more groups, an MIP is used to solve the problem. Solution methods incorporating cutting planes from conflict graphs are presented for solving instances in a branch-and-bound framework. These methods are used to enhance industry-standard software, and are shown to provide as much as a 20-fold reduction in computational time over the software alone. Computational experiments illustrate the tradeoff between misclassification rates and reserved judgment rates. Some base classifiers are not well suited to be modified to a constrained discrimination rule. The method for constrained discrimination studied here performs particularly well in the presence of class imbalance. For certain other data sets, however, the method is outperformed by a simple centroid method.

Genome-scale reconstructions are often used for studying relationships between fundamental components of a metabolic system. In this study, we develop a novel computational method for analyzing predicted flux distributions for metabolic reconstructions. Because chemical reactions may have multiple reactants and products, a directed hypergraph where hyperarcs may have multiple tail vertices and head vertices is a more appropriate representation of the metabolic network than a conventional network. We use this view to represent predicted flux distributions by maximum generalized flows on hypergraphs. We then demonstrate that the generalized hyperflow problem may be transformed to an equivalent network flow problem with side constraints. This transformation allows a flux to be decomposed into chains of reactions. Subsequent analysis of these chains helps to characterize active pathways in a flux distribution. Such characterizations facilitate comparisons of flux distributions for different environmental conditions. The proposed method is applied to compare predicted flux distributions for Salmonella typhimurium to study changes in metabolism that cause enhanced virulence during a space flight. The differences between flux distributions corresponding to normal and enhanced virulence states confirm previous observations concerning infection mechanisms and suggest new pathways for exploration.

Abstract Ryser's conjecture postulates that for r ‐partite hypergraphs, τ ≤ (r ‐ 1)ν where τ is the covering number of the hypergraph and ν is the matching number. Although this conjecture has been open since the 1960s, researchers have resolved it for special cases such as for intersecting hypergraphs where r ≤ 5. In this article, we prove several results pertaining to matchings and coverings in r ‐partite intersecting hypergraphs. First, we prove that finding a minimum cardinality vertex cover for an r ‐partite intersecting hypergraph is NP‐hard. Second, we note Ryser's conjecture for intersecting hypergraphs is easily resolved if a given hypergraph does not contain a particular subhypergraph, which we call a “tornado.” We prove several bounds on the covering number of tornados. Finally, we prove the integrality gap for the standard integer linear programming formulation of the maximum cardinality r ‐partite hypergraph matching problem is at least r ‐ k where k is the smallest positive integer such that r ‐ k is a prime power. © 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 2012

The paper introduces various local models for solving machine learning (i.e., data mining) problems. In particular (and, due to their superior results) it focuses on a novel design of locally linear support vector machines classifiers. It presents them as powerful alternatives to the global (over the whole input space) nonlinear classifiers. Locally linear support vector machine (LL SVM) maximizes the margin in the original input features space and it never performs the nonlinear mapping to some kernel induced feature space. In performing such a task it uses only the K closest points to the query data point q. In this way it grasps the local decision function better than the standard global SVM does. This is shown to be a powerful approach when data are unevenly distributed in the input space and when a suitable decision function possesses different nonlinear characteristics in various parts of the input space. Experiments on eleven benchmark data sets display both the superior performance of LL SVMs as well as great performances of other classic locally linear classifiers. In addition, this is the first paper which proves the stability bounds for local SVMs and it shows that they are tighter than the ones for traditional, global, SVM. LL SVM is a natural classifier for multiclass problems which means that it can be easily adopted for solving regression tasks.