Exact Graph Pattern Matching:Applications,Progress and Prospects

Graph pattern matching(GPM)can be used to mine the key information in graphs.Exact GPM is one of the most commonly used methods among all the GPM-related methods,which aims to exactly find all subgraphs for a given query graph in a data graph.The exact GPM has been widely used in biological data analyses,social network analyses and other fields.In this paper,the applications of the exact GPM were first introduced,and the research progress of the exact GPM was summarized.Then,the related algorithms were introduced in detail,and the experiments on the state-of-the-art exact GPM algorithms were conducted to compare their performance.Based on the experimental results,the applicable scenarios of the algorithms were pointed out.New research opportunities in this area were proposed.

Parallel Quick Search Algorithm for the Exact String Matching Problem Using OpenMP

String matching is seen as one of the essential problems in computer science. A variety of computer applications provide the string matching service for their end users. The remarkable boost in the number of data that is created and kept by modern computational devices influences researchers to obtain even more powerful methods for coping with this problem. In this research, the Quick Search string matching algorithm are adopted to be implemented under the multi-core environment using OpenMP directive which can be employed to reduce the overall execution time of the program. English text, Proteins and DNA data types are utilized to examine the effect of parallelization and implementation of Quick Search string matching algorithm on multi-core based environment. Experimental outcomes reveal that the overall performance of the mentioned string matching algorithm has been improved, and the improvement in the execution time which has been obtained is considerable enough to recommend the multi-core environment as the suitable platform for parallelizing the Quick Search string matching algorithm.

Maximal sequence length of exact match between members from a gene family during early evolution

Mutation (substitution, deletion, insertion, etc.) in nucleotide acid causes the maximal sequence lengths of exact match (MALE) between paralogous members from a duplicate event to become shorter during evolution. In this work, MALE changes between members of 26 gene families from four representative species (Arabidopsis thaliana, Oryza sativa, Mus mus- culus and Homo sapiens) were investigated. Comparative study of paralogous’ MALE and amino acid substitution rate (dA<0.5) indicated that a close relationship existed between them. The results suggested that MALE could be a sound evolutionary scale for the divergent time for paralogous genes during their early evolution. A reference table between MALE and divergent time for the four species was set up, which would be useful widely, for large-scale genome alignment and comparison. As an example, de- tection of large-scale duplication events of rice genome based on the table was illustrated.

Set (k, n)-Exactly covering problem

With the （ k, n ）-threshold scheme of secret sharing in the field of information security technology as an application background, the concept of set （ k, n ）-exact cover is presented in this paper. It is a modification of the original concept of set covering problem. It is also different from the concept of exact cover defined by J.E. Hopcmft. Some properties of （k, n ） -exact cover are investigated; a sufficient condition for a set to be （ k, n ） -exactly coverable is given. It follows that a feasible assignment scheme of a set for the （ k, n） -exact eover is obtained if this set satisfies the sufficient condition.

OBTAINING MULTI-AXIAL ELASTIC POTENTIALS FOR RUBBER-LIKE MATERIALS VIA AN EXPLICIT,EXACT APPROACH BASED ON SPLINE INTERPOLATION

An explicit, exact approach is proposed to obtain multi-axial elastic potentials for isotropic rubber-like materials undergoing large incompressible deformations. By means of two direct, explicit procedures, this approach reduces the problem of determining multi-axial poten- tials to that of determining one-dimensional elastic potentials. To this end, two one-dimensional potentials for uniaxial case and simple shear case are respectively determined via spline inter- polation and, then, the two potentials are extended to generate a multi-axial elastic potential using a novel method based on certain logarithmic invariants. Eventually, each of the multi-axial potentials will exactly match the finite strain data from four benchmark tests.