A Novel Mathematical Model for Similarity Search in Pattern Matching Algorithms

Modern applications require large databases to be searched for regions that are similar to a given pattern. The DNA sequence analysis, speech and text recognition, artificial intelligence, Internet of Things, and many other applications highly depend on pattern matching or similarity searches. In this paper, we discuss some of the string matching solutions developed in the past. Then, we present a novel mathematical model to search for a given pattern and it’s near approximates in the text.

Efficient secure and verifiable KNN set similarity search over outsourced clouds

KNN set similarity search is a foundational operation in various realistic applications in cloud computing.However,for security consideration,sensitive data will always be encrypted before uploading to the cloud servers,which makes the search processing a challenging task.In this paper,we focus on the problem of KNN set similarity search over the encrypted datasets.We use Yao’s garbled circuits and secret sharing as underlying tools.To achieve better querying efficiency,we construct a secure R-Tree index structure based on a novel secure grouping protocol,which enables grouping appropriate private values in an oblivious way.Along with several elaborately designed secure arithmetic subroutines,we propose an efficient secure and verifiable KNN set similarity search framework over outsourced clouds.Theoretically,we analyze the complexity of our schemes in detail,and prove the security in the presence of semi-honest adversaries.Finally,we evaluate the performance and feasibility of our proposed methods by extensive experiments.

An Incremental Partitioning Graph Similarity Search Based on Tree Structure Index

Graph similarity search is a common operation of graph database,and graph editing distance constraint is the most common similarity measure to solve graph similarity search problem.However,accurate calculation of graph editing distance is proved to be NP hard,and the filter and verification framework are adopted in current method.In this paper,a dictionary tree based clustering index structure is proposed to reduce the cost of candidate graph,and is verified in the filtering stage.An efficient incremental partition algorithm was designed.By calculating the distance between query graph and candidate graph partition,the filtering effect was further enhanced.Experiments on real large graph datasets show that the performance of this algorithm is significantly better than that of the existing algorithms.

String similarity search and join： a survey

String similarity search and join are two impor- tant operations in data cleaning and integration, which ex- tend traditional exact search and exact join operations in databases by tolerating the errors and inconsistencies in the data. They have many real-world applications, such as spell checking, duplicate detection, entity resolution, and webpage clustering. Although these two problems have been exten- sively studied in the recent decade, there is no thorough sur- vey. In this paper, we present a comprehensive survey on string similarity search and join. We first give the problem definitions and introduce widely-used similarity functions to quantify the similarity. We then present an extensive set of algorithms for siring similarity search and join. We also dis- cuss their variants, including approximate entity extraction, type-ahead search, and approximate substring matching. Fi- nally, we provide some open datasets and summarize some research challenges and open problems.

Similarity Search Algorithm over Data Supply Chain Based on Key Points

In this paper, we target a similarity search among data supply chains, which plays an essential role in optimizing the supply chain and extending its value. This problem is very challenging for application-oriented data supply chains because the high complexity of the data supply chain makes the computation of similarity extremely complex and inefficient. In this paper, we propose a feature space representation model based on key points,which can extract the key features from the subsequences of the original data supply chain and simplify it into a feature vector form. Then, we formulate the similarity computation of the subsequences based on the multiscale features. Further, we propose an improved hierarchical clustering algorithm for a similarity search over the data supply chains. The main idea is to separate the subsequences into disjoint groups such that each group meets one specific clustering criteria; thus, the cluster containing the query object is the similarity search result. The experimental results show that the proposed approach is both effective and efficient for data supply chain retrieval.

Efficient Similarity Search Based on Semantic Trajectories in Road Networks

In recent years, a few researches focus on the similarity measure of semantic trajectories in road networks, since semantic trajectories in road networks have smaller volumes, higher qualities and can better reflect user behaviors. However, these works do not further discuss how to efficiently search similar trajectories. Thus, to implement an efficient similarity search, we design an index called SIET based on the structures of road networks. Then, we propose a novel algorithm called SSN-BF to search similar trajectories efficiently by using best-first strategy. At last, we take the experimental evaluations on real dataset and prove the efficiency of our algorithm.

Using Multiple Satellites to Search for Maritime Moving Targets Based on Reinforcement Learning

Searching for maritime moving targets using satellites is an attracting but rather difficult problem due to the satellites' orbits and discontinuous visible time windows.From a long term cyclic view,a non-myopic method based on reinforcement learning(RL)for multi-pass multi-targets searching was proposed.It learnt system behaviors step by step from each observation which resulted in a dynamic progressive way.Then it decided and adjusted optimal actions in each observation opportunity.System states were indicated by expected information gain.Neural networks algorithm was used to approximate parameters of control policy.Simulation results show that our approach with sufficient training performs significantly better than other myopic approaches which make local optimal decisions for each individual observation opportunity.

Self-selective memristor-enabled in-memory search for highly efficient data mining

Similarity search,that is,finding similar items in massive data,is a fundamental computing problem in many fields such as data mining and information retrieval.However,for large-scale and high-dimension data,it suffers from high computational complexity,requiring tremendous computation resources.Here,based on the low-power self-selective memristors,for the first time,we propose an in-memory search(IMS)system with two innovative designs.First,by exploiting the natural distribution law of the devices resistance,a hardware locality sensitive hashing encoder has been designed to transform the realvalued vectors into more efficient binary codes.Second,a compact memristive ternary content addressable memory is developed to calculate the Hamming distances between the binary codes in parallel.Our IMS system demonstrated a 168energy efficiency improvement over all-transistors counterparts in clustering and classification tasks,while achieving a software-comparable accuracy,thus providing a low-complexity and low-power solution for in-memory data mining applications.

Meta-Path-Based Search and Mining in Heterogeneous Information Networks

Information networks that can be extracted from many domains are widely studied recently. Different functions for mining these networks are proposed and developed, such as ranking, community detection, and link prediction. Most existing network studies are on homogeneous networks, where nodes and links are assumed from one single type. In reality, however, heterogeneous information networks can better model the real-world systems, which are typically semi-structured and typed, following a network schema. In order to mine these heterogeneous information networks directly, we propose to explore the meta structure of the information network, i.e., the network schema. The concepts of meta-paths are proposed to systematically capture numerous semantic relationships across multiple types of objects, which are defined as a path over the graph of network schema. Meta-paths can provide guidance for search and mining of the network and help analyze and understand the semantic meaning of the objects and relations in the network. Under this framework, similarity search and other mining tasks such as relationship prediction and clustering can be addressed by systematic exploration of the network meta structure. Moreover, with user＇s guidance or feedback, we can select the best meta-path or their weighted combination for a specific mining task.

A Brief Review of Computational Gene Prediction Methods

With the development of genome sequencing for many organisms, more and moreraw sequences need to be annotated. Gene prediction by computational methods for finding thelocation of protein coding regions is one of the essential issues in bioinformatics. Two classes ofmethods are generally adopted: similarity based searches and ab initio prediction. Here, we reviewthe development of gene prediction methods, summarize the measures for evaluating predictor quality,highlight open problems in this area, and discuss future research directions.

A Multi-dimensional Index Structure Based on Improved VA-file and CAN in the Cloud

Currently,the cloud computing systems use simple key-value data processing,which cannot support similarity search efectively due to lack of efcient index structures,and with the increase of dimensionality,the existing tree-like index structures could lead to the problem of"the curse of dimensionality".In this paper,a novel VF-CAN indexing scheme is proposed.VF-CAN integrates content addressable network(CAN)based routing protocol and the improved vector approximation fle(VA-fle) index.There are two index levels in this scheme:global index and local index.The local index VAK-fle is built for the data in each storage node.VAK-fle is thek-means clustering result of VA-fle approximation vectors according to their degree of proximity.Each cluster forms a separate local index fle and each fle stores the approximate vectors that are contained in the cluster.The vector of each cluster center is stored in the cluster center information fle of corresponding storage node.In the global index,storage nodes are organized into an overlay network CAN,and in order to reduce the cost of calculation,only clustering information of local index is issued to the entire overlay network through the CAN interface.The experimental results show that VF-CAN reduces the index storage space and improves query performance efectively.

Isochamaejasmin induces apoptosis in leukemia cells through inhibiting Bcl-2 family proteins

The biflavonoid isochamaejasmin is mainly distributed in the root of Stellera chamaejasme L.(Thymelaeaceae) that is used in traditional Chinese medicine(TCM) to treat tumors, tuberculosis, and psoriasis. Herein, isochamaejasmin was found to show similar bioactivity against Bcl-2 family proteins to the reference Bcl-2 ligand(–)-gossypol through 3D similarity search. It selectively bound to Bcl-xL and Mcl-1 with Ki values being 1.93 ± 0.13 μmol·L-1 and 9.98 ± 0.21 μmol·L-1, respectively. In addition, isochamaejasmin showed slight growth inhibitory activity against HL-60 with IC50 value being 50.40 ± 1.21 μmol·L-1 and moderate growth inhibitory activity against K562 cells with IC50 value being 24.51 ± 1.62 μmol·L-1. Furthermore, isochamaejasmin induced apoptosis of K562 cells by increasing the intracellular expression levels of proteins of the cleavage of caspase-9, caspase-3, and PARP which involved in the Bcl-2-induced apoptosis pathway. These results indicated that isochamaejasmin induces apoptosis in leukemia cells by inhibiting the activity of Bcl-2 family proteins, providing evidence for further studying the underlying anti-cancer mechanism of S. chamaejasme L..

Exploring the Pathways and Targets of Shexiang Baoxin Pill for Coronary Heart Disease through a Network Pharmacology Approach

Objective: To investigate the network pharmacology of Shexiang Baoxin pill(SBP) and systematically analyze the mechanisms of SBP.Methods: In this study, we excavated all the targets of 26 constituents of SBP which were identified in rat plasma though literature mining and target calculation(reverse docking and similarity search) and analyzed the multiple pharmacology actions of SBP comprehensively through a network pharmacology approach.Results: In the end, a total of 330 Homo sapiens targets were identified for 26 blood constituents of SBP.Moreover, the pathway enrichment analysis found that these targets mapped into 171 KEGG pathways and 31 of which were more enriched.Among these identified pathways, 3 pathways were selected for analyzing the mechanisms of SBP for treating coronary heart disease.Conclusion: This study systematically illustrated the mechanisms of the SBP by analyzing the corresponding "drug-target-pathway-disease" interaction network.

CORE:Common Region Extension Based Multiple Protein Structure Alignment for Producing Multiple Solution

Over the past several decades, biologists have conducted numerous studies examining both general and specific functions of proteins. Generally, if similarities in either the structure or sequence of amino acids exist for two proteins, then a common biological function is expected. Protein function is determined primarily based on the structure rather than the sequence of amino acids. The algorithm for protein structure alignment is an essential tool for the research. The quality of the algorithm depends on the quality of the similarity measure that is used, and the similarity measure is an objective function used to determine the best alignment because of their individual strength and weakness However, none of existing similarity measures became golden standard They require excessive filtering to find a single alignment. In this paper, we introduce a new strategy that finds not a single alignment, but multiple alignments with different lengths. This method has obvious benefits of high quality alignment. However, this novel method leads to a new problem that the running time for this method is considerably longer than that for methods that find only a single alignment. To address this problem~ we propose algorithms that can locate a common region （CORE） of multiple alignment candidates, and can then extend the CORE into multiple alignments. Because the CORE can be defined from a final alignment, we introduce CORE＊ that is similar to CORE and propose an algorithm to identify the CORE＊. By adopting CORE＊ and dynamic programming, our proposed method produces multiple alignments of various lengths with higher accuracy than previous methods. In the experiments, the alignments identified by our algorithm are longer than those obtained by TM-align by 17% and 15.48%, on average, when the comparison is conducted at the level of super-family and fold, respectively.

A novel method for multi-angle SAR image matching

Multi-angle synthetic aperture radar（SAR） image matching is very challenging, because the same object may cause different backscattering patterns, heavily depending on the radar incident angle. A technique based on the relations between the invariant positions of ground targets among the reference and sensed images is proposed to accommodate the nonmatching patterns. It involves a target extraction using wavelet coefficient fusion, as well as a geometric voting matching routine for searching the matched control points（CPs） in the reference and sensed images, respectively. To accelerate the speed of the search, a robust, rapidly corresponding CPs determination strategy is exploited by utilizing the global spatial transformation model, as well as a procedure of outlier removal to ensure the desired accuracy. Meanwhile, the positions of the matched point pairs are relocated using mutual information. The final warping of the images according to the CPs is performed by using a polynomial function. The results show the possibility of matching multi-angle SAR images in general cases.