Designing connected nature reserve networks using a graph theory approach

Habitat fragmentation has been cited as one of the critical reasons for biodiversity loss. Establishing connected nature reserve networks is an effective way to reduce habit fragmentation. However, the resources devoted to nature reserves have always been scarce. Therefore it is important to allocate our scarce resources in an optimal way. The optimal design of a reserve network which is effective both ecologically and economically has become an important research topic in the reserve design literature. The problem of optimal selection of a subset from a larger group of potential habitat sites is solved using either heuristic or formal optimization methods. The heuristic methods, although flexible and computationally fast, can not guarantee the solution is optimal therefore may lead to scarce resources being used in an ineffective way. The formal optimization methods, on the other hand, guarantees the solution is optimal, but it has been argued that it would be difficult to model site selection process using optimization models, especially when spatial attributes of the reserve have to be taken into account. This paper presents a linear integer programming model for the design of a minimal connected reserve network using a graph theory approach. A connected tree is determined corresponding to a connected reserve. Computational performance of the model is tested using datasets randomly generated by the software GAMS. Results show that the model can solve a connected reserve design problem which includes 100 potential sites and 30 species in a reasonable period of time. As an empirical application, the model is applied to the protection of endangered and threatened bird species in the Cache River basin area in Illinois, US. Two connected reserve networks are determined for 13 bird species.     

Designing connected nature reserve networks using a graph theory approach

Habitat fragmentation has been cited as one of the critical reasons for biodiversity loss. Establishing connected nature reserve networks is an effective way to reduce habit fragmentation. However, the resources devoted to nature reserves have always been scarce. Therefore it is important to allocate our scarce resources in an optimal way. The optimal design of a reserve network which is effective both ecologically and economically has become an important research topic in the reserve design literature. The problem of optimal selection of a subset from a larger group of potential habitat sites is solved using either heuristic or formal optimization methods. The heuristic methods, although flexible and computationally fast, can not guarantee the solution is optimal therefore may lead to scarce resources being used in an ineffective way. The formal optimization methods, on the other hand, guarantees the solution is optimal, but it has been argued that it would be difficult to model site selection process using optimization models, especially when spatial attributes of the reserve have to be taken into account. This paper presents a linear integer programming model for the design of a minimal connected reserve network using a graph theory approach. A connected tree is determined corresponding to a connected reserve. Computational performance of the model is tested using datasets randomly generated by the software GAMS. Results show that the model can solve a connected reserve design problem which includes 100 potential sites and 30 species in a reasonable period of time. As an empirical application, the model is applied to the protection of endangered and threatened bird species in the Cache River basin area in Illinois, US. Two connected reserve networks are determined for 13 bird species.     

Efficient algorithms for protein sequence design and the analysis of certain evolutionary fitness landscapes.

Protein sequence design is a natural inverse problem to protein structure prediction: given a target structure in three dimensions, we wish to design an amino acid sequence that is likely fold to it. A model of Sun, Brem, Chan, and Dill casts this problem as an optimization on a space of sequences of hydrophobic (H) and polar (P) monomers; the goal is to find a sequence that achieves a dense hydrophobic core with few solvent-exposed hydrophobic residues. Sun et al. developed a heuristic method to search the space of sequences, without a guarantee of optimality or near-optimality; Hart subsequently raised the computational tractability of constructing an optimal sequence in this model as an open question. Here we resolve this question by providing an efficient algorithm to construct optimal sequences; our algorithm has a polynomial running time, and performs very efficiently in practice. We illustrate the implementation of our method on structures drawn from the Protein Data Bank. We also consider extensions of the model to larger amino acid alphabets, as a way to overcome the limitations of the binary H/P alphabet. We show that for a natural class of arbitrarily large alphabets, it remains possible to design optimal sequences efficiently. Finally, we analyze some of the consequences of this sequence design model for the study of evolutionary fitness landscapes. A given target structure may have many sequences that are optimal in the model of Sun et al.; following a notion raised by the work of J. Maynard Smith, we can ask whether these optimal sequences are "connected" by successive point mutations. We provide a polynomial-time algorithm to decide this connectedness property, relative to a given target structure. We develop the algorithm by first solving an analogous problem expressed in terms of submodular functions, a fundamental object of study in combinatorial optimization.     

Place prioritization for biodiversity conservation using probabilistic surrogate distribution data

We analyse optimal and heuristic place prioritization algorithms for biodiversity conservation area network design which can use probabilistic data on the distribution of surrogates for biodiversity. We show how an Expected Surrogate Set Covering Problem (ESSCP) and a Maximal Expected Surrogate Covering Problem (MESCP) can be linearized for computationally efficient solution. For the ESSCP, we study the performance of two optimization software packages (XPRESS and CPLEX) and five heuristic algorithms based on traditional measures of complementarity and rarity as well as the Shannon and Simpson indices of α‐diversity which are being used in this context for the first time. On small artificial data sets the optimal place prioritization algorithms often produced more economical solutions than the heuristic algorithms, though not always ones guaranteed to be optimal. However, with large data sets, the optimal algorithms often required long computation times and produced no better results than heuristic ones. Thus there is generally little reason to prefer optimal to heuristic algorithms with probabilistic data sets.     

Algorithms for the design of maximum hydropathic complementarity molecules

In this article, we address the problem of designing a string with optimal complementarity properties with respect to another given string according to a given criterion. The motivation comes from a drug design application, in which the complementarity between two sequences (proteins) is measured according to the values of the hydropathic coefficients associated with the sequence elements (amino acids). We present heuristic and exact optimization algorithms, and we report on some computational experiments on amino peptides taken from Semaphorin and human Interleukin-1β, which have already been investigated in the literature using heuristic algorithms. With our techniques, we proved the optimality of a known solution for Semaphorin-3A, and we discovered several other optimal and near-optimal solutions in a short computing time; we also found in fractions of a second an optimal solution for human interleukin-1β, whose complementary value is one order of magnitude better than previously known ones. The source code of a prototype C++ implementation of our algorithms is freely available for noncommercial use on the web. As a main result, we showed that in this context mathematical programming methods are more successful than heuristics, such as simulated annealing. Our algorithm unfolds its potential, especially when different measures could be used for scoring peptides, and is able to provide not only a single optimal solution, but a ranking of provable good ones; this ranking can then be used by biologists as a starting basis for further refinements, simulations, or in vitro experiments.     

Critical Assessment of the C-Optimality Design Criteria for Estimating the Median Effective Dose in Quantal Dose-Response Curves

In this paper the properties of C-optimal designs constructed for estimating the median effective dose within the framework of two-parametric linear logistic models are critically assessed. It is well known that this design criterion which is based on the first-order variance approximation of the exact variance of the maximum likelihood estimate of the ED50 leads to a one-point design where the maximum likelihood theory breaks down. The single dose used in this design is identical with the true but unknown value of the ED50. It will be shown, that at this one-point design the asymptotic variance does not exist. A two-point design in the neighbourhood of the one-point design which is symmetrical about the ED50 and associated with a small dose-distance would be nearly optimal, but extremely nonrobust if the best guess of the ED50 differs from the true value. In this situation the asymptotic variance of the two-point design converging towards the one-point design tends to infinity. Moreover, taking in consideration, that for searching an optimal design the exact variance is of primary interest and the asymptotic variance serves only as an approximation of the exact variance, we calculate the exact variance of the estimator from balanced, symmetric 2-point designs in the neighbourhood of the limiting 1-point design for various dose distances and initial best guesses of the ED50. We compare the true variance of the estimate of the ED50 with the asymptotic variance and show that the approximations generally do not represent suitable substitutes for the exact variance even in case of unrealistically large sample sizes. Kalish (1990) proposed a criterion based on the second-order asymptotic variance of the maximum likelihood estimate of the ED50 to overcome the degenerated 1-point design as the solution of the optimization procedure. In fact, we are able to show that this variance approximation does not perform substantially better than the first–order variance. From these considerations it follows, that the C-optimality criterion is not useful in this estimation problem. Other criteria like the F-optimality should be used.     

基于启发式广度优先搜索的SVR参数优化方法研究

支持向量回归机(Support vector regressio,SVR)模型的拟合精度和泛化能力取决于其相关参数的选择,其参数选择实质上是一个优化搜索过程。根据启发式广度优先搜索(Heuristic Breadth first Search,HBFS)算法在求解优化问题上高效的特点,提出了一种以k-fold交叉验证的最小化误差为目标,HBFS为寻优策略的SVR参数选择方法,通过3个基准数据集对该模型进行了仿真实验,结果表明该方法在保证预测精度前提下,大幅度的缩短了训练建模时间,为大样本的SVR参数选择提供了一种新的有效解决方案。     

A comparison of physical mapping algorithms based on the maximum likelihood model

MOTIVATION: Physical mapping of chromosomes using the maximum likelihood (ML) model is a problem of high computational complexity entailing both discrete optimization to recover the optimal probe order as well as continuous optimization to recover the optimal inter-probe spacings. In this paper, two versions of the genetic algorithm (GA) are proposed, one with heuristic crossover and deterministic replacement and the other with heuristic crossover and stochastic replacement, for the physical mapping problem under the maximum likelihood model. The genetic algorithms are compared with two other discrete optimization approaches, namely simulated annealing (SA) and large-step Markov chains (LSMC), in terms of solution quality and runtime efficiency. RESULTS: The physical mapping algorithms based on the GA, SA and LSMC have been tested using synthetic datasets and real datasets derived from cosmid libraries of the fungus Neurospora crassa. The GA, especially the version with heuristic crossover and stochastic replacement, is shown to consistently outperform the SA-based and LSMC-based physical mapping algorithms in terms of runtime and final solution quality. Experimental results on real datasets and simulated datasets are presented. Further improvements to the GA in the context of physical mapping under the maximum likelihood model are proposed. AVAILABILITY: The software is available upon request from the first author.     

最优化设计连续的自然保护区

生境破碎是导致生物多样性损失的重要原因之一,避免生境破碎的一个有效方式是建立连续的自然保护区使物种可在保护区内自由移动。不加选择地把大片土地都转为保护区是实现连续的一个途径,但资源是有限的,应当以最优的方式分配。如何最优化设计生态上和经济上都有效的保护区成为生物保护领域一个重要议题。从一组备选地块中选择一部分组成自然保护区,这样的问题主要有两种解法:启发式方法和最优化方法。启发式方法虽然灵活且运算速度快但不能保证最优解因而可能导致稀缺资源的浪费,最优化方法保证得到的解是最优的但建模和运算存在困难。建立一个线性整数规划模型用于设计一个最小的连续保护区,用Dantzig剪切法消除循环确保形成一个连续的树,对应一个连续的保护区,检验了模型的计算效率。结果显示,模型可在合理时间内解决一个包含100个备选地块和30个物种的连续保护区设计问题,计算效率显著优于同类目的的其它方法。以美国伊利诺伊州Cache河流域11种濒危鸟类的保护区设计为例说明了该方法的应用,设计了两种情况下连续的保护区。讨论了模型的局限和数据问题。     

Implied alignment: a synapomorphy-based multiple-sequence alignment method and its use in cladogram search

A method to align sequence data based on parsimonious synapomorphy schemes generated by direct optimization (DO; earlier termed optimization alignment) is proposed. DO directly diagnoses sequence data on cladograms without an intervening multiple-alignment step, thereby creating topology-specific, dynamic homology statements. Hence, no multiple-alignment is required to generate cladograms. Unlike general and globally optimal multiple-alignment procedures, the method described here, implied alignment (IA), takes these dynamic homologies and traces them back through a single cladogram, linking the unaligned sequence positions in the terminal taxa via DO transformation series. These "lines of correspondence" link ancestor-descendent states and, when displayed as linearly arrayed columns without hypothetical ancestors, are largely indistinguishable from standard multiple alignment. Since this method is based on synapomorphy, the treatment of certain classes of insertion-deletion (indel) events may be different from that of other alignment procedures. As with all alignment methods, results are dependent on parameter assumptions such as indel cost and transversion:transition ratios. Such an IA could be used as a basis for phylogenetic search, but this would be questionable since the homologies derived from the implied alignment depend on its natal cladogram and any variance, between DO and IA + Search, due to heuristic approach. The utility of this procedure in heuristic cladogram searches using DO and the improvement of heuristic cladogram cost calculations are discussed.     

Early eukaryote evolution based on mitochondrial gene order breakpoints.

The comparison of the gene orders in a set of genomes can be used to infer their phylogenetic relationships and to reconstruct ancestral gene orders. For three genomes this is done by solving the "median problem for breakpoints"; this solution can then be incorporated into a routine for estimating optimal gene orders for all the ancestral genomes in a fixed phylogeny. For the difficult (and most prevalent) case where the genomes contain partially different sets of genes, we present a general heuristic for the median problem for induced breakpoints. A fixed-phylogeny optimization based on this is applied in a phylogenetic study of a set of completely sequenced protist mitochondrial genomes, confirming some of the recent sequence-based groupings which have been proposed and, conversely, confirming the usefulness of the breakpoint method as a phylogenetic tool even for small genomes.     

A Scheme to Optimize Flow Routing and Polling Switch Selection of Software Defined Networks

This paper aims at minimizing the communication cost for collecting flow information in Software Defined Networks (SDN). Since flow-based information collecting method requires too much communication cost, and switch-based method proposed recently cannot benefit from controlling flow routing, jointly optimize flow routing and polling switch selection is proposed to reduce the communication cost. To this end, joint optimization problem is formulated as an Integer Linear Programming (ILP) model firstly. Since the ILP model is intractable in large size network, we also design an optimal algorithm for the multi-rooted tree topology and an efficient heuristic algorithm for general topology. According to extensive simulations, it is found that our method can save up to 55.76% communication cost compared with the state-of-the-art switch-based scheme.     

Simultaneous versus sequential optimal experiment design for the identification of multi-parameter microbial growth kinetics as a function of temperature

Optimal experiment design for parameter estimation (OED/PE) has become a popular tool for efficient and accurate estimation of kinetic model parameters. When the kinetic model under study encloses multiple parameters, different optimization strategies can be constructed. The most straightforward approach is to estimate all parameters simultaneously from one optimal experiment (single OED/PE strategy). However, due to the complexity of the optimization problem or the stringent limitations on the system's dynamics, the experimental information can be limited and parameter estimation convergence problems can arise. As an alternative, we propose to reduce the optimization problem to a series of two-parameter estimation problems, i.e., an optimal experiment is designed for a combination of two parameters while presuming the other parameters known. Two different approaches can be followed: (i) all two-parameter optimal experiments are designed based on identical initial parameter estimates and parameters are estimated simultaneously from all resulting experimental data (global OED/PE strategy), and (ii) optimal experiments are calculated and implemented sequentially whereby the parameter values are updated intermediately (sequential OED/PE strategy).This work exploits OED/PE for the identification of the Cardinal Temperature Model with Inflection (CTMI) (Rosso et al., 1993). This kinetic model describes the effect of temperature on the microbial growth rate and encloses four parameters. The three OED/PE strategies are considered and the impact of the OED/PE design strategy on the accuracy of the CTMI parameter estimation is evaluated. Based on a simulation study, it is observed that the parameter values derived from the sequential approach deviate more from the true parameters than the single and global strategy estimates. The single and global OED/PE strategies are further compared based on experimental data obtained from design implementation in a bioreactor. Comparable estimates are obtained, but global OED/PE estimates are, in general, more accurate and reliable.     

Optimization of physical parameters for exo-biopolymer production in submerged mycelial cultures of two entomopathogenic fungi Paecilomyces japonica and Paecilomyces tenuipes

AIMS: In the present study, two different optimization techniques were used to determine the suitable operating parameters for exo-biopolymer production in submerged mycelial cultures of two entomopathogenic fungi Paecilomyces japonica and Paecilomyces tenuipes. METHODS AND RESULTS: First, the rotating simplex method, a nonstatistical optimization technique, was employed to obtain the best combination of physical parameters (viz. pH, agitation intensity, aeration rate) for maximum exo-biopolymer production by P. japonica in a batch bioreactor. The optimal combination was determined to be a pH of 8.06, an aeration of 3 vvm, without any impeller agitation, producing a 17-time increase in exopolymer production (34.5 g l(-1)) when compared with that achieved in unoptimized flask cultures. Second, the uniform design method, a statistical optimization technique, was employed to determine the best operating parameters for submerged culture of P. tenuipes. The optimal combination for mycelial growth was determined to be a pH of 4.88, an aeration of 2 vvm and an agitation of 350 rpm, while a pH of 4, an aeration of 2 vvm and an agitation of 150 rpm was best for exo-biopolymer production. CONCLUSIONS: The exo-biopolymer production in P. japonica optimized by the rotating simplex method was strikingly improved (max. 34.5 g l(-1)), and the exo-biopolymer production in P. tenuipes optimized by the uniform design method was also significantly increased (max. 3.4 g l(-1)). SIGNIFICANCE AND IMPACT OF THE STUDY: The successful application of these two different optimization techniques in this study implies that these methods are worthy of applying to other fermentation systems for the production of bioactive mycelial biomass and exo-biopolymers in liquid culture of higher fungi.     

Metaheuristics for the bi-objective orienteering problem

In this paper, heuristic solution techniques for the multi-objective orienteering problem are developed. The motivation stems from the problem of planning individual tourist routes in a city. Each point of interest in a city provides different benefits for different categories (e.g., culture, shopping). Each tourist has different preferences for the different categories when selecting and visiting the points of interests (e.g., museums, churches). Hence, a multi-objective decision situation arises. To determine all the Pareto optimal solutions, two metaheuristic search techniques are developed and applied. We use the Pareto ant colony optimization algorithm and extend the design of the variable neighborhood search method to the multi-objective case. Both methods are hybridized with path relinking procedures. The performances of the two algorithms are tested on several benchmark instances as well as on real world instances from different Austrian regions and the cities of Vienna and Padua. The computational results show that both implemented methods are well performing algorithms to solve the multi-objective orienteering problem.     

Modeling and design optimization of asynchronous flexible assembly systems with statistical process control and repair

This article presents the implementation of hybrid procedures involving the use of analytical performance evaluation techniques, discrete event simulation, and Monte Carlo optimization methods for the stochastic design optimization of asynchronous flexible assembly systems (AFASs) with statistical process control (SPC) and repair loops. AFASs are extremely complex and difficult to analyze in that such systems are subject to starvation and blocking effects, random jam occurrences at workstations, and splitting and merging of the assembly flow due to repair loops. Hence, an integrated approach simultaneously analyzing the interactions between product quality and optimal/near optimal system design is pursued. In the analytical analysis stage, a model based on GI/G/1 queueing network theory is used. In the Monte Carlo optimization stage, two alternative stochastic optimization approaches, namely, heuristic versions of stochastic quasigradient and simulated annealing algorithms, are implemented and compared in terms of their capabilities of solving complex AFAS design problems. The hybrid procedures presented appear to perform reasonably well in designing AFASs to reach a target production rate.     

Solving and analyzing side-chain positioning problems using linear and integer programming

MOTIVATION: Side-chain positioning is a central component of homology modeling and protein design. In a common formulation of the problem, the backbone is fixed, side-chain conformations come from a rotamer library, and a pairwise energy function is optimized. It is NP-complete to find even a reasonable approximate solution to this problem. We seek to put this hardness result into practical context. RESULTS: We present an integer linear programming (ILP) formulation of side-chain positioning that allows us to tackle large problem sizes. We relax the integrality constraint to give a polynomial-time linear programming (LP) heuristic. We apply LP to position side chains on native and homologous backbones and to choose side chains for protein design. Surprisingly, when positioning side chains on native and homologous backbones, optimal solutions using a simple, biologically relevant energy function can usually be found using LP. On the other hand, the design problem often cannot be solved using LP directly; however, optimal solutions for large instances can still be found using the computationally more expensive ILP procedure. While different energy functions also affect the difficulty of the problem, the LP/ILP approach is able to find optimal solutions. Our analysis is the first large-scale demonstration that LP-based approaches are highly effective in finding optimal (and successive near-optimal) solutions for the side-chain positioning problem.     

Systematic optimization model and algorithm for binding sequence selection in computational enzyme design

A systematic optimization model for binding sequence selection in computational enzyme design was developed based on the transition state theory of enzyme catalysis and graph‐theoretical modeling. The saddle point on the free energy surface of the reaction system was represented by catalytic geometrical constraints, and the binding energy between the active site and transition state was minimized to reduce the activation energy barrier. The resulting hyperscale combinatorial optimization problem was tackled using a novel heuristic global optimization algorithm, which was inspired and tested by the protein core sequence selection problem. The sequence recapitulation tests on native active sites for two enzyme catalyzed hydrolytic reactions were applied to evaluate the predictive power of the design methodology. The results of the calculation show that most of the native binding sites can be successfully identified if the catalytic geometrical constraints and the structural motifs of the substrate are taken into account. Reliably predicting active site sequences may have significant implications for the creation of novel enzymes that are capable of catalyzing targeted chemical reactions.     

A method for solution of the multi-objective inverse problems under uncertainty

We describe a method to solve multi-objective inverse problems under uncertainty. The method was tested on non-linear models of dynamic series and population dynamics, as well as on the spatiotemporal model of gene expression in terms of non-linear differential equations. We consider how to identify model parameters when experimental data contain additive noise and measurements are performed in discrete time points. We formulate the multi-objective problem of optimization under uncertainty. In addition to a criterion of least squares difference we applied a criterion which is based on the integral of trajectories of the system spatiotemporal dynamics, as well as a heuristic criterion CHAOS based on the decision tree method. The optimization problem is formulated using a fuzzy statement and is constrained by penalty functions based on the normalized membership functions of a fuzzy set of model solutions. This allows us to reconstruct the expression pattern of hairy gene in Drosophila even-skipped mutants that is in good agreement with experimental data. The reproducibility of obtained results is confirmed by solution of inverse problems using different global optimization methods with heuristic strategies.