Abstract:In gene expression data analysis, discriminator genes are importantly informative genes for further research. Recently, a great deal of research has focused on the challenging task of identifying these informative genes from microarray data. However, the sizes of sample classes in microarray data are often unbalanced. The unbalance of samples has not been explicitly and correctly considered by the existing gene selection methods, especially nonparametric methods. Considering the unbalance of samples and the stability of the approach for identifying informative genes, a novel and model-free gene selection method is proposed in this paper. With considering within-class difference and between-class variation, as well as the homogeneities of the within-class difference and between-class variations, scoring functions of genes are constructed to select discriminator genes. This method is not only applicable in two-category case but also applicable in multi-category case. The experimental results on two publicly available microarray datasets, leukemia data and small round blue cell tumor data, show that the proposed method is very efficient and robust to select discriminator genes.

Abstract:Test set problem is a NP-hard problem with wide applications. Set cover greedy algorithm is one of the commonly used algorithms for the test set problem. It is an open problem if the approximation ratio 2ln n+1 directly derived from the set cover problem can be improved. The generalization of set cover greedy algorithm is used to solve the redundant test set problem arising in bioinformatics. This paper analyzes the distribution of the times for which the item pairs are differentiated, and proves that the approximation ratio of the set cover greedy algorithm for test set can be 1.5lnn+0.5lnlnn+2 by derandomization method, thus shrinks the gap in the analysis of the approximation ratio of this algorithm. In addition, this paper shows the tight lower bound (2 o(1))lnn (1) of the approximation ratio of set cover greedy algorithm for the weighted redundant test set with redundancy n 1.

Abstract:RNA secondary structure prediction based on free energy rules remains a major computational method in computational biology. Its basic dynamic programming algorithm needs O(n⁴) time to calculate the minimum free energy for RNA secondary structure, where n is the length of RNA sequence. There are two variants for handling this problem: either the internal loops are bounded by a maximal size k, giving a time complexity of O(n²×k²), or one uses the trick of Lyngso, which makes use of the rules of loop energies, to reduce time complexity to O(n³) for suboptimal free energy without restriction. Only with additional O(n) space, a new algorithm is proposed to eliminate the redundant calculation in the energy of internal loops and reduce the time complexity to O(n³) with unrestricted loop sizes for optimal free energy. While the optimized algorithm is time consuming, an efficient parallel algorithm with good load balancing in cluster systems is also proposed. The experimental results show that the parallel program achieves reasonable speedups.

Abstract:While SVO logic has been widely used in the analysis of non-repudiation protocols for its simplicity, its lack of the ability in time description makes it helpless in the analysis of timeliness, which is one of the most important properties of non-repudiation protocols. SVO logic is extended by adding a simple time expression and analysis method into it. Then a widely discussed fair non-repudiation proposed by Zhou and Gollmann in 1996 and one of its improvements are analyzed with the newly extended logic. The result shows that Zhou-Gollmann’s fair non-repudiation protocol does not provide timeliness while its improvement does. Therefore, the new logic is able to analyze timeliness of non-repudiation protocols. In addition, the new logic can be used to analyze other time-related properties of cryptographic protocols.

Abstract:A renaming is a function mapping propositional variable to itself or its complement, a variable renaming is a permutation over the set of propositional variables of a formula, and a literal renaming is a combination of a renaming and a variable renaming. Renaming for CNF formulas may help to improve DPLL algorithm. This paper investigates the complexity of decision problem: for propositional CNF formulas H and F,does there exist a variable (or literal) renaming ψ such that ψ(H)=F? Both MAX(1) and MARG(1) are subclasses of the minimal unsatisfiable formulas, and formulas in these subclasses can be represented by trees. The decision problem of isomorphism for trees is solvable in linear time. Formulas in the MAX(1) and MARG(1), it is shown that the literal renaming problems are solvable in linear time, and the variable renaming problems are solvable in quadratic time.

Abstract:The Voronoi diagram (VD) of a planar polygon has many applications, from path planning in robotics to collision detection in virtual reality. To study the complexity of algorithms based on Voronoi diagram, it is important to estimate the numbers of vertices and edges of a VD. Held proves that the inner Voronoi diagram of a simple polygon has at most n+k-2 vertices and 2(n+k)-3 edges, where n is the number of the polygon's vertices and k is the number of reflex vertices. But this conclusion holds not for a multiply-connected polygon, i.e. a polygon with "holes". In this paper, by constructing a rooted tree from a VD, and based on some properties of the rooted tree,new upper bounds on the numbers of vertices and edges in an inner Voronoi diagram of a multiply-connected polygon are proved. The average numbers of Voronoi vertices and edges on the boundary of a VD are also presented.The result of this paper has been used to analyze the complexity of VD-based visibility computing algorithm in SDU Virtual Museum.

Abstract:Natural and efficient 3D interaction techniques play one of the key roles in the development of virtual reality systems. Most of these techniques, which are used currently, mainly aim at supporting the implementation of interaction tasks in geometric level. As a result, they usually lack of the sufficient ability for executing those interaction tasks that orient to high-level application. Based on the cognitive principles in the real world, interaction objects in virtual environments not only include some geometric attributes in the visual view, but also own some specific semantic attributes such as interaction rules, constraints and affordances, which are related with interaction process tightly. In this paper these objects are called semantic objects, in the sense that they know how the user can interact with them, giving clues to aid the interaction. Through parsing and interpreting interaction semantics, these semantic objects can help to realize high-level interaction metaphors above “direct manipulation”. Because they hide low-level details about the implementation of interaction techniques, this kind of metaphors evidently improve the efficiency and usability of interaction techniques, and enable user to concentrate more on the high-level interaction control directly related with the special applications.

Abstract:Level-Set method is a good way to do metamorphosis. Narrowband and sparse-field algorithms improve its performance. Results of narrowband morphing are smoother when the sparse-field algorithm is faster. Sparse-field algorithm is mended to fit Euclidean distance model and the narrowband algorithm is used to make up the error of the sparse-field morphing. Topological relationship replaces distance band to define layer sets, and a single side active set is proposed to improve efficiency and robustness. To make up the error of the sparse-field algorithm, which causes obvious alias at the last half stage, two remedy methods are proposed. Averaging and translation method is simpler and more efficient. Narrowband evolution and back method is better for reserving the sharp shape.

Abstract:This paper proposes an efficient architecture composed of bit plane-parallel and pass-parallel coder for EBCOT (embedded block coding with optimized truncation) entropy encoder used in JPEG2000.After the detailed analysis of EBCOT architecture in JPEG2000, the coding information of each bit plane and the corresponding passes can be obtained simultaneously. Therefore, bit plane-parallel and pass-parallel coding (BPPP) is proposed, and its VLSI architecture is shown in details. The analysis and the corresponding experimental results show that the proposed architecture reduces the processing time greatly compared with others, and a FPGA prototype chip is designed and can process 512×512 gray level images with 30 frames per second at 65MHz working frequency. The quality of images reaches the results released by JPEG2000.

Abstract:A new approach for the representation of 3D general Julia sets is put forward on the basis of tri-dimensional polynomial maps. The condition for a 3D polynomial map to be equivariant is theoretically analyzed and proved. The equations of two classes of 3D polynomial maps that are equivariant with respect to the rotational symmetries of either a regular tetrahedron group or a regular octahedron group are strictly given, on the basis of which the properties of the general Julia sets created by these 3D polynomial maps are discussed and proved. A ray-tracing volume rendering algorithm, which defines the color and opacity of every discrete point within a Julia set according to its escaping distance, is proposed in order to acquire high quality 3D fractal images. Experimental results demonstrate that the approach of generating 3D Julia sets from 3D polynomial maps not only enables us to predict the characteristics of Julia sets according to the properties of the maps, but also makes it possible for us to obtain various kinds of Julia sets with different rotational symmetries by altering the parameters of the maps. Consequently, drawbacks such as monotone structure of the resulting fractals and inability to predict fractal shape in the existing methods for generating 3D fractal sets can be effectually avoided. Furthermore, the method of generating 3D Julia sets by 3D polynomial maps can be applied to the construction of other 3D fractals, and hence would result in a different perspective for the generation of 3D fractals.

Abstract:Unlike photorealistic rendering striven by traditional 3D computer graphics, NPR emphasizes artistic expression, subjective mood imbuing, and downplaying unimportant information. The paper presents a new automatic method for generating oil paintings via fluid simulation technology. A paintly rendering is built up in a series of layers, drawn with large, long and curved brush strokes, and aligned to normal of fluid reference image gradients. In this method, an improved reflectance model with multiple light sources is proposed, which can represent the variability of lighting conditions on artistic painting. Additionally, a technique for simulating the hierarchical physical appearance of oil paintings under lighting is designed. The painting is rendered by bump-mapping the painting’s colors with the image’s intensity map. Finally, color transfer technique is adopted to make the color characteristic of the generated image consistent with that of some specified artistic source images. Experimental results show that the proposed method can be used efficiently to create oil paintings similar to some Van Gogh’s style from a photograph.

Abstract:This paper considers the problem of quality assessment of image fusion result. A novel similarity-based measure for the performance of image fusion is proposed. From human visual features, this measure evaluates the similarity of the gradient fields between the source image and fused image. Compared with the existing similarity-based measures, the proposed one has an omnidirectional recognition ability; Compared with the mutual information method, it is more consistent with the human perception nature as it considers only the local image variations. Experimental results show that the proposed measure can evaluate the image fusion performance satisfactorily and is also perceptually meaningful.

Abstract:Routing technology at the network layer is pivotal in the architecture of wireless sensor networks. As an active branch of routing technology, cluster-based routing protocols excel in network topology management, energy minimization, data aggregation and so on. In this paper, cluster-based routing mechanisms for wireless sensor networks are analyzed. Cluster head selection, cluster formation and data transmission are three key techniques in cluster-based routing protocols. As viewed from the three techniques, recent representative cluster-based routing protocols are presented, and their characteristics and application areas are compared. Finally, the future research issues in this area are pointed out.

Abstract:The noninterference concept for actions of system to information domains is proposed. On the basis of this concept, the noninterference model is extended to nondeterministic systems. The noninterference concept based on actions of system simplifies the “purge” of the action sequence of the system. As a result, this model has concise unwinding conditions which are easy to understand and use. The extended model can be used to verify not only static but also dynamic information flow policies. Finally, a dynamic label based access control model is designed, in which the concrete semantic of the actions such as read, write and execute are defined, and its security is verified by the noninterference model.

Abstract:Effective multicast congestion control mechanism is urgently needed with the deployment of multimedia multicast application in Internet. Layered multicast is considered to be an efficient approach to cope with the network heterogeneity. A Differentiated Services (DiffServ)-based layered multicast model is presented firstly. Then a congestion control algorithm for DiffServ-based layered multicast, called DSLMCC (DiffServ-based layered multicast packet dropping), including DSLMPM (DiffServ-based layered multicast packet marking) and DSLMPD (DiffServ-based layered multicast packet dropping) algorithm, is proposed through introducing probability-based priority packet marking and dropping mechanisms. Simulation results show that DSLMCC algorithm is more responsive, more stable and fair, and can adapt to network heterogeneity better.

Abstract:Digital Fingerprinting is a technique for the merchant who can embed unique buyer identity marks into digital media copy, and also makes it possible to identify “traitors” who redistribute their illegal copies. At present,the fingerprinting scheme generally has many difficulties and disadvantages for large-size users, involved in code construction with shorter length and effective traitor-tracing. To resolve these problems, this paper presents the definition of Fingerprinting Information Code and a practical construction method by composing of convolutional codes and common fingerprinting codes based on Boneh-Shaw model. Its decoding algorithm is presented by improving Viterbi algorithm through introducing the idea of ‘Optional Subcode Set’. The security and performance are proved and analyzed by theory and example. The results indicate that the proposed scheme has shorter information encoding length and achieves optimal traitor searching in larger-size users.

Abstract:In a (t,n) secret sharing scheme, a dealer splits a secret into n shares and sends a share to each of n participants. If necessary, any t members can provide their secret shares together and recover the secret by using a publicly specified algorithm. Multisecret sharing schemes allow a dealer to share multiple secrets among a group of participants securely and efficiently. In recent, Shi proposed an efficient multisecret sharing authenticating scheme. In his scheme, not only the shares held by the participants are reusable, but also the shares distributed by the dealer and the shadow shares provided by the participants are verifiable. This paper analyzes the security of Shi’s scheme. It first points out a design error in his scheme, and then demonstrates an attack to show that both of his share-authenticating and shadow-key-authenticating methods are insecure. Specifically, using the attacks, a dishonest dealer can distribute false shares to participants, and malicious participants can easily forge false shadow shares such that the authenticating equality is satisfied. The result is that honest participants will be cheated and misled to believe that the recovered secret is correct. In addition, improvements are provided to avoid the identified design error and attacks.

Abstract:After the analysis and comparison of the existing vulnerability analysis methods, a new vulnerability model of distributed systems based on reliability theory is proposed. First, it models vulnerabilities of distributed systems from the aspects of security-related factors. Then it utilizes the model checking method to build Vulnerability State Graph (VSG) of distributed systems to depict the complete process of exploitation of vulnerabilities. Finally, it introduces reliability theory to perform analysis and quantitative evaluation of vulnerabilities of distributed systems, which provides a theoretical evidence for security enhancement.

Abstract:The logic relationship among the equality and inequality constraints in a standard constrained optimization problem (SCOP) is the logical AND. Various efficient, convergent and robust algorithms have been developed for such a SCOP. However, a more general constrained optimization problem (GCOP) with not only logic AND but also OR relationships exists in many practical applications. In order to solve such a generalized problem, a new mathematical transformations which can transfer a set of inequalities with logic OR into inequalities with logic AND relationships is developed. This transformation provides a necessary and sufficient condition which enables us to formulate real-time system design as a mixed Boolean-integer programming problem. A Branch and Bound Algorithm is applied to find the optimal solution. Experimental results have been presented to show its merits.

Abstract:In mobile and embedded devices, the energy supply is strictly constrained with the battery capacity and energy saving ability. In these energy-constrained settings, the available energy budget is not sufficient to meet the optimal performance objective. This paper presents an energy-constrained software prefetching optimization approach, which can obtain the optimal performance under the limited energy resource. The approach is based on DVS-enabled CPU and memory. Through inserting frequency-scaling instructions, CPU and memory frequencies are simultaneously adjusted to meet two performance objectives (one is the time; the other is the processor gain) under a given energy constraint. A detailed analytical model is built and then the effectiveness of the approach is validated by a set of array-intensive applications. Experimental results show that the approach is effective for energy-constrained prefetching optimization problem.