Container loading and unloading scheduling for a Mobile Harbor system: a global and local search method

Mobile Harbor (MH) is a type of mobile floating port system with an on-board crane for off-shore container handling capability. Due to its unique operational features, it creates a new type of operational scheduling problem. Container loading and unloading sequence schedule for the MH on-board crane is one such problem. An optimal schedule should minimize the on-board crane’s moves in a stem-to-stern direction while satisfying MH’s stability constraint. This paper presents a mathematical programming model to formally define the problem, and two heuristic methods, Genetic Algorithm (GA) method and local search method, are developed. Experimental results show that both GA and the local search method generate solutions of similar quality when the stability constraint is loose and that the local search method is not effective in finding a feasible solution for problems with a tight stability constraint.     

Computing the minimum recombinant haplotype configuration from incomplete genotype data on a pedigree by integer linear programming.

We study the problem of reconstructing haplotype configurations from genotypes on pedigree data with missing alleles under the Mendelian law of inheritance and the minimum-recombination principle, which is important for the construction of haplotype maps and genetic linkage/association analyses. Our previous results show that the problem of finding a minimum-recombinant haplotype configuration (MRHC) is in general NP-hard. This paper presents an effective integer linear programming (ILP) formulation of the MRHC problem with missing data and a branch-and-bound strategy that utilizes a partial order relationship and some other special relationships among variables to decide the branching order. Nontrivial lower and upper bounds on the optimal number of recombinants are introduced at each branching node to effectively prune the search tree. When multiple solutions exist, a best haplotype configuration is selected based on a maximum likelihood approach. The paper also shows for the first time how to incorporate marker interval distance into a rule-based haplotyping algorithm. Our results on simulated data show that the algorithm could recover haplotypes with 50 loci from a pedigree of size 29 in seconds on a Pentium IV computer. Its accuracy is more than 99.8% for data with no missing alleles and 98.3% for data with 20% missing alleles in terms of correctly recovered phase information at each marker locus. A comparison with a statistical approach SimWalk2 on simulated data shows that the ILP algorithm runs much faster than SimWalk2 and reports better or comparable haplotypes on average than the first and second runs of SimWalk2. As an application of the algorithm to real data, we present some test results on reconstructing haplotypes from a genome-scale SNP dataset consisting of 12 pedigrees that have 0.8% to 14.5% missing alleles.     

基于Progressive多序列比对方法的求解多序列比对的启发式算法

在生物信息学研究中,生物序列比对问题占有重要的地位。多序列比对问题是一个NPC问题,由于时间和空间的限制不能够求出精确解。文中简要介绍了Feng和Doolittle提出的多序列比对算法的基本思想,并改进了该算法使之具有更好的比对精度。实验结果表明,新算法对解决一般的progressive多序列比对方法中遇到的局部最优问题有较好的效果。     

Exact Hybrid Particle/Population Simulation of Rule-Based Models of Biochemical Systems

Detailed modeling and simulation of biochemical systems is complicated by the problem of combinatorial complexity, an explosion in the number of species and reactions due to myriad protein-protein interactions and post-translational modifications. Rule-based modeling overcomes this problem by representing molecules as structured objects and encoding their interactions as pattern-based rules. This greatly simplifies the process of model specification, avoiding the tedious and error prone task of manually enumerating all species and reactions that can potentially exist in a system. From a simulation perspective, rule-based models can be expanded algorithmically into fully-enumerated reaction networks and simulated using a variety of network-based simulation methods, such as ordinary differential equations or Gillespie''s algorithm, provided that the network is not exceedingly large. Alternatively, rule-based models can be simulated directly using particle-based kinetic Monte Carlo methods. This “network-free” approach produces exact stochastic trajectories with a computational cost that is independent of network size. However, memory and run time costs increase with the number of particles, limiting the size of system that can be feasibly simulated. Here, we present a hybrid particle/population simulation method that combines the best attributes of both the network-based and network-free approaches. The method takes as input a rule-based model and a user-specified subset of species to treat as population variables rather than as particles. The model is then transformed by a process of “partial network expansion” into a dynamically equivalent form that can be simulated using a population-adapted network-free simulator. The transformation method has been implemented within the open-source rule-based modeling platform BioNetGen, and resulting hybrid models can be simulated using the particle-based simulator NFsim. Performance tests show that significant memory savings can be achieved using the new approach and a monetary cost analysis provides a practical measure of its utility.     

Decision support based automatic container sequencing system using heuristic rules

Container terminals in seaports constitute interfaces between the seaborne transport and transport-over-land of goods in global transport chains. The loading and unloading of containers are performed using quay cranes (QCs), which is the most important equipment for handling servicing vessels at a container terminal. Following tremendous growth in global container transshipments, terminals are facing increasing demand. Terminals at Shanghai are equipped with Tandem Lift which can lift two 40’ containers simultaneously to improve the efficiency of the QCs. A reasonable container combinations of Tandem Lift and container operation sequence are required to improve the servicing of vessels, meanwhile the dual cycling container operation of quay cranes has to be investigated. This paper presents a two-stage mathematical model and two-level heuristic algorithm for planning the container operation sequence using Tandem Lift in a feasible computational time. Based on the proposed methodology, a decision support system, called the Tandem Lift Container Sequence System (TLCSS). A case study of Shanghai Shengdong International Port Company (SSICT) proves that consideration of the container sequence with Tandem Lift dramatically shortens servicing time of vessels with the TLCSS.     

Constructing a fuzzy rule-based system using the ILFN network and Genetic Algorithm.

In this paper, a method for automatic construction of a fuzzy rule-based system from numerical data using the Incremental Learning Fuzzy Neural (ILFN) network and the Genetic Algorithm is presented. The ILFN network was developed for pattern classification applications. The ILFN network, which employed fuzzy sets and neural network theory, equips with a fast, one-pass, on-line, and incremental learning algorithm. After trained, the ILFN network stored numerical knowledge in hidden units, which can then be directly interpreted into if then rule bases. However, the rules extracted from the ILFN network are not in an optimized fuzzy linguistic form. In this paper, a knowledge base for fuzzy expert system is extracted from the hidden units of the ILFN classifier. A genetic algorithm is then invoked, in an iterative manner, to reduce number of rules and select only discriminate features from input patterns needed to provide a fuzzy rule-based system. Three computer simulations using a simulated 2-D 3-class data, the well-known Fisher's Iris data set, and the Wisconsin breast cancer data set were performed. The fuzzy rule-based system derived from the proposed method achieved 100% and 97.33% correct classification on the 75 patterns for training set and 75 patterns for test set, respectively. For the Wisconsin breast cancer data set, using 400 patterns for training and 299 patterns for testing, the derived fuzzy rule-based system achieved 99.5% and 98.33% correct classification on the training set and the test set, respectively.     

A fast algorithm to build a supertree with a set of gene trees

Important desired properties of an algorithm to construct a supertree (species tree) by reconciling input trees are its low complexity and applicability to large biological data. In its common statement the problem is proved to be NP-hard, i.e. to have an exponential complexity in practice. We propose a reformulation of the supertree building problem that allows a computationally effective solution. We introduce a biologically natural requirement that the supertree is sought for such that it does not contain clades incompatible with those existing in the input trees. The algorithm was tested with simulated and biological trees and was shown to possess an almost square complexity even if horizontal transfers are allowed. If HGTs are not assumed, the algorithm is mathematically correct and possesses the longest running time of n3 x[V0]3, where n is the number of input trees and [V0] is the total number of species. The authors are unaware of analogous solutions in published evidence. The corresponding inferring program, its usage examples and manual are freely available at http://lab6.iitp.ru/en/super3gl. The available program does not implement HGTs. The generalized case is described in the publication "A tree nearest in average to a set of trees" (Information Transmission Problems, 2011).     

One Giant Leap for Categorizers: One Small Step for Categorization Theory

We explore humans’ rule-based category learning using analytic approaches that highlight their psychological transitions during learning. These approaches confirm that humans show qualitatively sudden psychological transitions during rule learning. These transitions contribute to the theoretical literature contrasting single vs. multiple category-learning systems, because they seem to reveal a distinctive learning process of explicit rule discovery. A complete psychology of categorization must describe this learning process, too. Yet extensive formal-modeling analyses confirm that a wide range of current (gradient-descent) models cannot reproduce these transitions, including influential rule-based models (e.g., COVIS) and exemplar models (e.g., ALCOVE). It is an important theoretical conclusion that existing models cannot explain humans’ rule-based category learning. The problem these models have is the incremental algorithm by which learning is simulated. Humans descend no gradient in rule-based tasks. Very different formal-modeling systems will be required to explain humans’ psychology in these tasks. An important next step will be to build a new generation of models that can do so.     

Two hybrid compaction algorithms for the layout optimization problem

In this paper we present two new algorithms for the layout optimization problem: this concerns the placement of circular, weighted objects inside a circular container, the two objectives being to minimize imbalance of mass and to minimize the radius of the container. This problem carries real practical significance in industrial applications (such as the design of satellites), as well as being of significant theoretical interest. We present two nature-inspired algorithms for this problem, the first based on simulated annealing, and the second on particle swarm optimization. We compare our algorithms with the existing best-known algorithm, and show that our approaches out-perform it in terms of both solution quality and execution time.     

DQB: A novel dynamic quantitive classification model using artificial bee colony algorithm with application on gene expression profiles

In the medical domain, it is very significant to develop a rule-based classification model. This is because it has the ability to produce a comprehensible and understandable model that accounts for the predictions. Moreover, it is desirable to know not only the classification decisions but also what leads to these decisions. In this paper, we propose a novel dynamic quantitative rule-based classification model, namely DQB, which integrates quantitative association rule mining and the Artificial Bee Colony (ABC) algorithm to provide users with more convenience in terms of understandability and interpretability via an accurate class quantitative association rule-based classifier model. As far as we know, this is the first attempt to apply the ABC algorithm in mining for quantitative rule-based classifier models. In addition, this is the first attempt to use quantitative rule-based classification models for classifying microarray gene expression profiles. Also, in this research we developed a new dynamic local search strategy named DLS, which is improved the local search for artificial bee colony (ABC) algorithm. The performance of the proposed model has been compared with well-known quantitative-based classification methods and bio-inspired meta-heuristic classification algorithms, using six gene expression profiles for binary and multi-class cancer datasets. From the results, it can be concludes that a considerable increase in classification accuracy is obtained for the DQB when compared to other available algorithms in the literature, and it is able to provide an interpretable model for biologists. This confirms the significance of the proposed algorithm in the constructing a classifier rule-based model, and accordingly proofs that these rules obtain a highly qualified and meaningful knowledge extracted from the training set, where all subset of quantitive rules report close to 100% classification accuracy with a minimum number of genes. It is remarkable that apparently (to the best of our knowledge) several new genes were discovered that have not been seen in any past studies. For the applicability demand, based on the results acqured from microarray gene expression analysis, we can conclude that DQB can be adopted in a different real world applications with some modifications.     

CODA: a combined algorithm for predicting the structurally variable regions of protein models

CODA, an algorithm for predicting the variable regions in proteins, combines FREAD a knowledge based approach, and PETRA, which constructs the region ab initio. FREAD selects from a database of protein structure fragments with environmentally constrained substitution tables and other rule-based filters. FREAD was parameterized and tested on over 3000 loops. The average root mean square deviation ranged from 0.78 A for three residue loops to 3.5 A for eight residue loops on a nonhomologous test set. CODA clusters the predictions from the two independent programs and makes a consensus prediction that must pass a set of rule-based filters. CODA was parameterized and tested on two unrelated separate sets of structures that were nonhomologous to one another and those found in the FREAD database. The average root mean square deviation in the test set ranged from 0.76 A for three residue loops to 3.09 A for eight residue loops. CODA shows a general improvement in loop prediction over PETRA and FREAD individually. The improvement is far more marked for lengths six and upward, probably as the predictive power of PETRA becomes more important. CODA was further tested on several model structures to determine its applicability to the modeling situation. A web server of CODA is available at http://www-cryst.bioc.cam.ac.uk/~charlotte/Coda/search_coda.html.     

基于知识的颅内出血（ICH）三维医学图像分割方法

本文描述一种基于知识的三维医学图像自动分割方法,用于进行人体颅内出血(Intracranial Hemorrhage,ICH)的分割和分析。首先,数字化CT胶片,并自动对数字化后的胶片按照有无异常分类。然后,阀值结合模糊C均值聚类算法将图像分类成多个具有统一亮度的区域。最后,在先验知识以及预定义的规则的基础上,借助基于知识的专家系统将各个区域标记为背景、钙化点、血肿、颅骨、脑干。     

Determination of metformin hydrochloride using precolumn derivatization with acetaldehyde and capillary electrophoresis coupled with electrochemiluminescence

A novel method was developed using capillary electrophoresis (CE) coupled with tris(2,2′‐bipyridyl)ruthenium(II) electrogenerated chemiluminescence (ECL) for highly sensitive detection of metformin hydrochloride (MH) derivatizatized with acetaldehyde. The precolumn derivatization of MH with acetaldehyde was performed in phosphate buffer solution (0.3 mol/L, pH 7.5) at room temperature for 120 min. The effects of acetaldehyde concentration, buffer pH, electrokinetic voltage and injection time were investigated. Under optimized detection conditions, the MH ECL detection sensitivity was more than 120 times that without derivatization. The linear concentration range for MH was 0.001–15.00 μg/mL (with a correlation coefficient of 0.9992). The detection limit was 0.31 ng/mL with a signal:noise ratio of 3. The recoveries of MH in human urine were in the range 98.50–99.72%. Copyright © 2011 John Wiley & Sons, Ltd.     

Branch-and-terminate: a combinatorial optimization algorithm for protein design.

BACKGROUND: Several deterministic and stochastic combinatorial optimization algorithms have been applied to computational protein design and homology modeling. As structural targets increase in size, however, it has become necessary to find more powerful methods to address the increased combinatorial complexity. RESULTS: We present a new deterministic combinatorial search algorithm called 'Branch-and-Terminate' (B&T), which is derived from the Branch-and-Bound search method. The B&T approach is based on the construction of an efficient but very restrictive bounding expression, which is used for the search of a combinatorial tree representing the protein system. The bounding expression is used both to determine the optimal organization of the tree and to perform a highly effective pruning procedure named 'termination'. For some calculations, the B&T method rivals the current deterministic standard, dead-end elimination (DEE), sometimes finding the solution up to 21 times faster. A more significant feature of the B&T algorithm is that it can provide an efficient way to complete the optimization of problems that have been partially reduced by a DEE algorithm. CONCLUSIONS: The B&T algorithm is an effective optimization algorithm when used alone. Moreover, it can increase the problem size limit of amino acid sidechain placement calculations, such as protein design, by completing DEE optimizations that reach a point at which the DEE criteria become inefficient. Together the two algorithms make it possible to find solutions to problems that are intractable by either algorithm alone.     

Gossip-Based Solutions for Discrete Rendezvous in Populations of Communicating Agents

The objective of the rendezvous problem is to construct a method that enables a population of agents to agree on a spatial (and possibly temporal) meeting location. We introduce the buffered gossip algorithm as a general solution to the rendezvous problem in a discrete domain with direct communication between decentralized agents. We compare the performance of the buffered gossip algorithm against the well known uniform gossip algorithm. We believe that a buffered solution is preferable to an unbuffered solution, such as the uniform gossip algorithm, because the use of a buffer allows an agent to use multiple information sources when determining its desired rendezvous point, and that access to multiple information sources may improve agent decision making by reinforcing or contradicting an initial choice. To show that the buffered gossip algorithm is an actual solution for the rendezvous problem, we construct a theoretical proof of convergence and derive the conditions under which the buffered gossip algorithm is guaranteed to produce a consensus on rendezvous location. We use these results to verify that the uniform gossip algorithm also solves the rendezvous problem. We then use a multi-agent simulation to conduct a series of simulation experiments to compare the performance between the buffered and uniform gossip algorithms. Our results suggest that the buffered gossip algorithm can solve the rendezvous problem faster than the uniform gossip algorithm; however, the relative performance between these two solutions depends on the specific constraints of the problem and the parameters of the buffered gossip algorithm.     

Mild hypothermia protects hippocampal neurons from oxygen-glucose deprivation injury through inhibiting caspase-3 activation

Mild hypothermia (MH) is thought to be one of the most effective therapeutic methods to treat hypoxic-ischemic encephalopathy (HIE) after cardiac arrest (CA). However, its precise mechanisms remain unclear. In this research, hippocampal neurons were cultured and treated with mild hypothermia and Ac-DEVD-CHO after oxygen-glucose deprivation (OGD). The activity of caspase-3 was detected, in order to find the precise concentration of Ac-DEVD-CHO with the same protective role in OGD injury as MH treatment. Western blot and immunofluorescence staining were conducted to analyze the effects of MH and Ac-DEVD-CHO on the expressions of caspase-3, caspase-8, and PARP. The neuronal morphology was observed with an optical microscope. The lactic acid dehydrogenase (LDH) release rate, neuronal viability, and apoptotic rate were also detected. We found that MH (32 °C) and Ac-DEVD-CHO (5.96 μMol/L) had equal effects on blocking the activation of caspase-3 and the OGD-induced cleavage of PARP, but neither had any effect on the activation of caspase-8, which goes on to activate caspase-3 in the apoptotic pathway. Meanwhile, both MH and Ac-DEVD-CHO had similar effects in protecting cell morphology, reducing LDH release, and inhibiting OGD-induced apoptosis in neurons. They also similarly improved neuronal viability after OGD. In conclusion, caspase-3 serves as a key intervention point of the key modulation site or regulatory region in MH treatment that protects neuronal apoptosis against OGD injury. Inhibiting the expression of caspase-3 had a protective effect against OGD injury in MH treatment, and caspase-3 activation could be applied to evaluate the neuroprotective effectiveness of MH on HIE.     

The storage capacity expansion and space leasing for container depots

Positioning empty containers is one of the most effective ways to solve the container imbalance problem and is affected by the capacity of depots. A shipping company will be more competitive if the depot capacity is large. This study provides a decision tool for planning the expansion of depot capacity. Mathematical models are utilized to minimize the total relevant costs that include the capacity expansion cost, storage space leasing cost, inventory holding cost, container leasing cost, and positioning cost. The problem is formulated as a mixed integer program. Then, we develop a heuristic algorithm that is based on Lagrangian relaxation. Computational experiments are conducted to evaluate the performance of the proposed algorithm.     

Offshore port service concepts: classification and economic feasibility

Most prevalent among the approaches to address the ever increasing demands for port capacity are the construction of new berths, installation of faster cranes and optimization of existing resources. A less common approach is to employ offshore port service concepts. Here, we endeavor to provide a complete survey of such nontraditional offshore service concepts and demonstrate that all, except a few very unusual concepts, can be well classified into one of thirty two structures or their combinations. Advantages, disadvantages and the container handling chain are discussed. We identify which of these structures can provide any of six possible operational modes. We next focus on a subset of the thirty two structures called the mobile harbor. This concept has recently been proposed and shares some similarities with midstream operation in Hong Kong. We endeavor to address the fundamental question: “Should such a concept be implemented?” We develop an estimate of the cost per unit threshold below which this concept will be viable. The per unit cost estimate of current MH designs is within about 6% of the economic viability threshold for traditional operation in Hong Kong. Other operational modes are not as favorable. As our focus is on the feasibility of the operational paradigm, we do not here address technology issues except to note ongoing efforts to resolve technology hurdles.     

Anticlastogenic effect of Spirulina maxima extract on the micronuclei induced by maleic hydrazide in Tradescantia

The aim of this investigation was to determine if extracts of Spirulina maxima reduce the genotoxic damage induced by maleic hydrazide (MH) using the Tradescantia biosssay. Two types of extracts from the alga were prepared: an aqueous extract with two different concentrations, 100 and 500 mg/ml, and a second one, the extract of a 1% solution of dimethyl sulfoxide (DMSO) which corresponded to 100 mg/ml of the alga. The capacity of MH to induce micronuclei (MN) was initially established by administering 0.005, 0.01, and 0.015 mg/ml of the chemical to the Tradescantia inflorescences, and observing its effect after 24 h.The results of this experiment showed a significant MN increase with the two high concentrations tested, although no dose-response effect was observed. For the anticlastogenic assay, the extracts of Spirulina were applied to the inflorescences alone or immediately before the application of MH (0.01 mg/ml) and the induced MN were observed 24 h later. We found that none of the extracts increased the MN level with respect to the untreated plants; also, that MH more or less doubled the basal micronuclei frequency, and finally, that all tested extracts reduced the genotoxic damage caused by MH. The inhibitory indices obtained for the aqueous extracts (100 and 500 mg/ml) and for the DMSO extract were respectively 59, 85, and 56.3%. These data indicate that Spirulina is an anticlastogenic agent and suggest that it is advisable to extend studies on this matter using other biological models.     

On finite-horizon control of genetic regulatory networks with multiple hard-constraints

Background

Probabilistic Boolean Networks (PBNs) provide a convenient tool for studying genetic regulatory networks. There are three major approaches to develop intervention strategies: (1) resetting the state of the PBN to a desirable initial state and letting the network evolve from there, (2) changing the steady-state behavior of the genetic network by minimally altering the rule-based structure and (3) manipulating external control variables which alter the transition probabilities of the network and therefore desirably affects the dynamic evolution. Many literatures study various types of external control problems, with a common drawback of ignoring the number of times that external control(s) can be applied.

Results

This paper studies the intervention problem by manipulating multiple external controls in a finite time interval in a PBN. The maximum numbers of times that each control method can be applied are given. We treat the problem as an optimization problem with multi-constraints. Here we introduce an algorithm, the "Reserving Place Algorithm'', to find all optimal intervention strategies. Given a fixed number of times that a certain control method is applied, the algorithm can provide all the sub-optimal control policies. Theoretical analysis for the upper bound of the computational cost is also given. We also develop a heuristic algorithm based on Genetic Algorithm, to find the possible optimal intervention strategy for networks of large size.

Conclusions

Studying the finite-horizon control problem with multiple hard-constraints is meaningful. The problem proposed is NP-hard. The Reserving Place Algorithm can provide more than one optimal intervention strategies if there are. Moreover, the algorithm can find all the sub-optimal control strategies corresponding to the number of times that certain control method is conducted. To speed up the computational time, a heuristic algorithm based on Genetic Algorithm is proposed for genetic networks of large size.