Search

Sorting a permutation by reversals is a famous problem in genome rearrangements. Since 1997, quite some biological evidence were found that in many genomes the reversed regions are usually flanked by a pair of inverted repeats. This type of reversals are called symmetric reversals, which, unfortunately, were largely ignored until recently. In this paper, we investigate the problem of sorting by symmetric reversals, which requires a series of symmetric reversals to transform one chromosome $A$ into the another chromosome $B$. The decision problem of sorting by symmetric reversals is referred to as {\em SSR} (when the input chromosomes $A$ and $B$ are given, we use {\em SSR(A,B)}) and the corresponding optimization version (i.e., when the answer for {\em SSR(A,B)} is yes, using the minimum number of symmetric reversals to convert $A$ to $B$), is referred to as {\em SMSR(A,B)}. The main results of this paper are summarized as follows, where the input is a pair of chromosomes $A$ and $B$ with $n$ repeats. (1) We present an $O(n^2)$ time algorithm to solve the decision problem {\em SSR(A,B)}, i.e., determine whether a chromosome $A$ can be transformed into $B$ by a series of symmetric reversals. (2) We design an $O(n^2)$ time algorithm for a special 2-balanced case of {\em SMSR(A,B)}, where chromosomes $A$ and $B$ both have duplication number 2 and every repeat appears twice in different orientations in $A$ and $B$. (3) We show that SMSR is NP-hard even if the duplication number of the input chromosomes are at most 2, hence showing that the above positive optimization result is the best possible. As a by-product, we show that the \emph{minimum Steiner tree} problem on \emph{circle graphs} is NP-hard, settling the complexity status of a 38-year old open problem., Comment: 35 pages, 12 figures

A facile method has been developed to prepare flexible and uniform porous carbon film/Ni (PCF/Ni) double-layer structure for simply and rapidly assembling flexible electrochemical capacitor (EC). The PCF/Ni is obtained by ambient pressure chemical vapor deposition and subsequent partial etching of Ni foil. The thickness of PCF can be controlled by etching time. The PCF has a porous structure and tightly interface with Ni, resulting in a good conductivity and large surface area. The ECs based on PCF/Ni exhibits good electrical properties. Area (volumetric) capacitance of PCF/Ni electrode with PCF thickness of 0.52 μm reaches 0.31 mF/cm2 (5.96 F/cm3) at scan rate of 50 mV/s. Maximum volumetric (gravimetric) power density reaches 2.72 W/cm3 (9.05 kW/kg). The performance can be further improved by increasing the PCF thickness. Furthermore, the EC based on PCF/Ni has a very short time constant (~ 170 μs) and allows for operations at high rate up to 500 V/s.

A new and simple approach is proposed for the first time to fabricate free-standing amorphous carbon films (FS-ACFs) with controllable thickness by ambient pressure chemical vapor deposition (APCVD). The approach uses methane as the carbon source and Ni foil as the catalytic substrate, in which a large number of carbon atoms are trapped by controlling the experimental conditions during the APCVD growth process, and FS-ACFs are obtained by a simple corrosion of the Ni foil after APCVD growth. FS-ACFs having a uniform and continuous morphology with variable sizes over one hundred square centimeters and a controllable thickness of tens to hundreds of nanometers are synthesized by controlling the experimental conditions. Microstructure observations show that FS-ACFs have porous and transparent characteristics, which can be transferred or bent on different substrates, thus allowing for a variety of potential applications in electrochemistry. As a proof of concept, an electrochemical supercapacitor device directly assembled by using the FS-ACF exhibits an ultrashort time constant of 46 μs, a wide frequency range (∼kHz) for capacitive feature, and a good capacitance performance with an area specific capacitance of 0.28 mF cm−2 at a scan rate of 50 mV s−1. Furthermore, the FS-ACF-based supercapacitor shows a high power density with a maximum volumetric power density of 17.76 W cm−3.

At present, several provinces' power supply companies have established harmonic monitoring platform in China, by real-time monitoring the voltage and current of power grid, then upload these data to the main station to analyze and settle. The platform can collect about 1 TB(1TB=1000GB) data every day[12], these data contain all the indexes of power quality, but we can only use this platform to do some basal data analysis work, but not processing analysis with multi-indexes, so that it does not show strong supporting effort to the power grid operation. With the development of energy internet and the third industry, more and more unstructured data are impacting the power grid operation, how to make better use of big data technology to deal with the data from monitoring platform has became the focus of the power grid company. In this paper, some introduces of contents and characteristics of harmonic real-time monitoring platform and big data technology has been made, by comparing the way of using and settling data of platform to the big data technology, meanwhile by combining with the characteristics of power quality data, we analyze the combination of the two prospects. At last, the development direction of the advanced application for the harmonic line monitoring system is discussed in this paper.

To improve fuel economy and reduce operating costs are one of the future developments of the air transport. From another part, it is continually called for higher speed to satisfy the global reach and make the world as a neighbor. An airworthiness problem of supersonic civil aircraft is the propulsion system noise. The ACE (adaptive cycle engine) noise is explored at the state of takeoff based on the description and analysis of aero engine noise and supersonic air transport. The conceptual scheme of ACE is shown and then the calculation method of each component is studied, including fan, combustor, turbine and nozzle. The total noise level (EPN dB) is calculated and the impact of components noise is analyzed. The research shows that the ACE noise is lower than the supersonic aircraft Concorde but higher than actual subsonic civil engine. The nozzle and fan should be paid an attention at the noise suppression and the airport location for supersonic aircraft could be a condition of market acceptation.

Based on m-stems and semi-extensible structure, a model is presented to represent RNA planar pseudoknots, and corresponding dynamic programming algorithm is designed and implemented to predict arbitrary planer pseudoknots and simple non-planar pseudoknots with O(n4) time and O(n3) space. The algorithm folds total 245 sequences in the Pseudobase database, and the test results indicate that the algorithm has good accuracy, sensitivity and specificity. *Supported by National Natural Science Foundation of China (Grant Nos. 60573024 and 60573181), the Research Project of Shandong Economic University (01610784), and NSF of Shandong Provice (2005BS01014)

Hybrid carbon films composed of graphene film and porous carbon film may give full play to the advantages of both carbon materials, and have great potential for application in energy storage and conversion devices. Unfortunately, there are very few reports on fabrication of hybrid carbon films. Here we demonstrate a simple approach to fabricate free-standing sandwich-structured hybrid carbon film composed of porous amorphous carbon film and multilayer graphene film by chemical vapor deposition in a controllable and scalable way. Hybrid carbon films reveal good electrical conductivity, excellent flexibility, and good compatibility with substrate. Supercapacitors assembled by hybrid carbon films exhibit ultrahigh rate capability, wide frequency range, good capacitance performance, and high-power density. Moreover, this approach may provide a general path for fabrication of hybrid carbon materials with different structures by using different metals with high carbon solubility, and greatly expands the application scope of carbon materials.

This paper briefly reviews NP-hard optimization problems and theirin approximability. The hardness of solving CLIQUE problem isspecifically discussed. A dynamic-programming algorithm and its improvedversion for CLIQUE are reviewed and some additional analysis ispresented. The analysis implies that the improved algorithm, HEWN(hierarchical edge-weighted network), only provides a heuristic oruseful method, but cannot be called a polynomial algorithm.

A review is presented of studies of polymeric membranes by applying positron annihilation lifetime spectroscopy (PALS). PALS has been used to study subnanometer-sized holes, to determine their size distribution and free-volume fractions, and to probe molecular-sized vacancies in glassy polymers. At present, PALS is believed to be a highly effective physical method for the examination of polymeric membranes.

This paper improves Itai and Rodeh's algorithm for finding a shortest cycle in an undirected unweighted graph. Given an undirected unweighted graph G with n vertices,the algorithm can determine a cycle whose length is at most k+1 where k is the length of the shortest cycle in G. The results of the experiment show that the improved algorithm runs faster than the original one when the input graph meets some special features.

Given an undirected graph with vertex and edge weights and a subset of vertices called terminals, the bounded size graph clustering (BSGC) problem is to partition the vertices into clusters of size at most a given budget such that each cluster contains at most one terminal and the total size of the clusters is minimized, where the size of a cluster is defined as the total vertex weight in the subset plus the total edge weight at the boundary of the cluster. For BSGC on trees, we present a pseudo-polynomial time exact algorithm, which can be modified via rounding to yield a (1+\epsilon)-approximation in polynomial time violating the given budget by a 1+\epsilon factor.

Given a graph G=(V,E) with real positive edge weights, where each edge (u, v) is labeled either + or – depending on whether u and v have been deemed to be similar or dissimilar, the problem of correlation clustering with l clusters is to partition the vertices of G into at most l clusters to minimize the total weight of + edges between clusters and – edges within clusters. This problem for general graphs is APX-complete. A fixed-parameter tractable (FPT) algorithm is presented, where the parameter k is defined as the maximum, over all blocks B of the graph, of the number of vertices that must be removed from B to obtain a forest.

The k-means clustering is one of the most popular schemes for discovering clusters in data. Its aim is to minimize the mean squared distance from each data to its nearest center. A lot of variants of Lloyd's heuristic have been studied. Unfortunately, many research results haven't given any approximate ratio. In this paper, an algorithm is presented which can obtain the optimal clustering with the ration of at most 2. The main idea of this algorithm is that k points are selected by means of a very simple, randomized seeding technique and then the local search is implemented to improve the accuracy. Some examples are selected to verify our algorithm and got better results both the speed and accuracy than the former methods. The main algorithmic contribution is that the input points are used as the candidate sets to obtain the optimal clustering with a constant ratio by means of local search technique and one method of selecting initial points.

A new kind of neural networks on solving shortest paths problem is presented, and the stability of the neural networks is proved. For a directed or undirected graph, the proposed neural network is always convergent to its single equilibrium, so that the shortest paths between every pair of nodes of the oriented graph are produced. This paper makes a new study on solving the optimization but not NP-hard problems by neural networks.

This paper gives an improved sufficient condition of ensuring the stability of delayed cellular neural networks (DCNN) by means of the analysis of a correspondent Lyapunov function. This result improved the limit given by Civalleri and gives an optional upper limit of the stability of DCNN.

It is difficult to reduce an NMR image's ringing artifacts and obtain better images. This paper uses the method of dyadic wavelets and self-adaptive threshold to process the images that have the ringing artifacts. The test results prove that the method is effective and it can process the NMR image's ringing artifacts. Finally the paper discusses using the fuzzy method.

In this paper the character of the associative memory is discussed emphatically from the viewpoint of the storage capacity and the associative ability of the network. The associative memory function can all be realized by utilizing the feedback network on competition. The competing classifying (CC) algorithm is presented here. Compared with any other associative memories that already exist, the neural network determined by the algorithm has very good performances such as high error-correcting capability, large storage capacity, no "rejected-point" and no spurious attractive center. The obtained network exceeds the storage capacity of HAM and BP networks.

The character of the associative memory is discussed emphatically from the viewpoint of the storage capacity and the associative ability of the network. The associative memory function can all be realized by utilizing the feedback network or the forward-feed network. The new algorithm, based on adaptive competing-classifying (ACC) algorithm, is presented here. Compared with other associative memories, the neural network determined by the algorithm has high error-correcting capability, large storage capacity, no "rejected-point" and no spurious attractive center. ACC algorithm can decrease the competition-number more than CC algorithm. The obtained network has the very strong ability of correcting errors and exceeds the storage capacity of HAM and BP networks.