Study on Microsatellite Distribution in Complete Genomes of Tobacco Vein Clearing Virus

MATLAB software and optimal complete subgraph algorithm were used to extract and reveal the microsatellite distribution features in the complete genomes of the tobacco vein clearing virus （NC-003 378.1） from the NCBI database.The results showed that the repetitions number and their location of the N-base group has been extracted and displayed.The largest repetitions of N-base group in the complete genomes of the tobacco vein clearing virus was decreased as the exponential function with the increasing of N.The method used in this study could be applied to the extraction and revealing of the microsatellite distribution features in the complete genomes of other viruses,thereby provided a basis for the research of the structure and the law of function,inheritance and variation by the using of the microsatellite distribution features.

Robot coverage algorithm under rectangular decomposition environment

The environment modeling algorithm named rectangular decomposition, which is composed of cellular nodes and interleaving networks, is proposed. The principle of environment modeling is to divide the environment into individual square sub-areas. Each sub-area is orientated by the central point of the sub-areas called a node. The rectangular map based on the square map can enlarge the square area side size to increase the coverage efficiency in the case of there being an adjacent obstacle. Based on this algorithm, a new coverage algorithm, which includes global path planning and local path planning, is introduced. In the global path planning, uncovered subspaces are found by using a special rule. A one-dimensional array P, which is used to obtain the searching priority of node in every direction, is defined as the search rule. The array P includes the condition of coverage towards the adjacent cells, the condition of connectivity and the priorities defined by the user in all eight directions. In the local path planning, every sub-area is covered by using template models according to the shape of the environment. The simulation experiments show that the coverage algorithm is simple, efficient and adapted for complex two- dimensional environments.

Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem

As a typical representative of the NP-complete problem, the traveling salesman problem(TSP) is widely utilized in computer networks, logistics distribution, and other fields. In this paper, a discrete lion swarm optimization(DLSO) algorithm is proposed to solve the TSP. Firstly, we introduce discrete coding and order crossover operators in DLSO. Secondly, we use the complete 2-opt(C2-opt) algorithm to enhance the local search ability.Then in order to enhance the efficiency of the algorithm, a parallel discrete lion swarm optimization(PDLSO) algorithm is proposed.The PDLSO has multiple populations, and each sub-population independently runs the DLSO algorithm in parallel. We use the ring topology to transfer information between sub-populations. Experiments on some benchmarks TSP problems show that the DLSO algorithm has a better accuracy than other algorithms, and the PDLSO algorithm can effectively shorten the running time.

A Complete Critical Path Algorithm for Test Generation of Combinational Circuits

It is known that critical path test generation method is not a complete algorithm for combinational circuits with reconvergent-fanout.In order to make it a complete algorithm,we put forward a reconvergent-fanout- oriented technique,the principal critical path algorithm,propagating the critical value back to primary inputs along a single path,the principal critical path,and allowing multiple path sensitization if needed.Relationship among test patterns is also discussed to accelerate test generation.

APPROXIMATE LAGRANGE MULTIPLIER ALGORITHM FOR STOCHASTIC PROGRAMS WITH COMPLETE RECOURSE:NONLINEAR DETERMINISTIC CONSTRAINTS

In this paper we design an approximation method for solving stochastic programs with com-plete recourse and nonlinear deterministic constraints. This method is obtained by combiningapproximation method and Lagrange multiplier algorithm of Bertsekas type. Thus this methodhas the advantages of both the two.

Solving SAT problem by heuristic polarity decision-making algorithm

This paper presents a heuristic polarity decision-making algorithm for solving Boolean satisfiability （SAT）. The algorithm inherits many features of the current state-of-the-art SAT solvers, such as fast BCP, clause recording, restarts, etc. In addition, a preconditioning step that calculates the polarities of variables according to the cover distribution of Karnaugh map is introduced into DPLL procedure, which greatly reduces the number of conflicts in the search process. The proposed approach is implemented as a SAT solver named DiffSat. Experiments show that DiffSat can solve many ＂real-life＂ instances in a reasonable time while the best existing SAT solvers, such as Zchaff and MiniSat, cannot. In particular, DiffSat can solve every instance of Bart benchmark suite in less than 0.03 s while Zchaff and MiniSat fail under a 900 s time limit. Furthermore, DiffSat even outperforms the outstanding incomplete algorithm DLM in some instances.