Search

Discovering amino acid (AA) patterns on protein binding sites has recently become popular. We propose a method to discover the association relationship among AAs on binding sites. Such knowledge of binding sites is very helpful in predicting protein-protein interactions. In this paper, we focus on protein complexes which have protein-protein recognition. The association rule mining technique is used to discover geographically adjacent amino acids on a binding site of a protein complex. When mining, instead of treating all AAs of binding sites as a transaction, we geographically partition AAs of binding sites in a protein complex. AAs in a partition are treated as a transaction. For the partition process, AAs on a binding site are projected from three-dimensional to two-dimensional. And then, assisted with a circular grid, AAs on the binding site are placed into grid cells. A circular grid has ten rings: a central ring, the second ring with 6 sectors, the third ring with 12 sectors, and later rings are added to four sectors in order. As for the radius of each ring, we examined the complexes and found that 10Å is a suitable range, which can be set by the user. After placing these recognition complexes on the circular grid, we obtain mining records (i.e. transactions) from each sector. A sector is regarded as a record. Finally, we use the association rule to mine these records for frequent AA patterns. If the support of an AA pattern is larger than the predetermined minimum support (i.e. threshold), it is called a frequent pattern. With these discovered patterns, we offer the biologists a novel point of view, which will improve the prediction accuracy of protein-protein recognition. In our experiments, we produced the AA patterns by data mining. As a result, we found that arginine (arg) most frequently appears on the binding sites of two proteins in the recognition protein complexes, while cysteine (cys) appears the fewest. In addition, if we discriminate the shape of binding sites between concave and convex further, we discover that patterns {arg, glu, asp} and {arg, ser, asp} on the concave shape of binding sites in a protein more frequently (i.e. higher probability) make contact with {lys} or {arg} on the convex shape of binding sites in another protein. Thus, we can confidently achieve a rate of at least 78%. On the other hand {val, gly, lys} on the convex surface of binding sites in proteins is more frequently in contact with {asp} on the concave site of another protein, and the confidence achieved is over 81%. Applying data mining in biology can reveal more facts that may otherwise be ignored or not easily discovered by the naked eye. Furthermore, we can discover more relationships among AAs on binding sites by appropriately rotating these residues on binding sites from a three-dimension to two-dimension perspective. We designed a circular grid to deposit the data, which total to 463 records consisting of AAs. Then we used the association rules to mine these records for discovering relationships. The proposed method in this paper provides an insight into the characteristics of binding sites for recognition complexes.

The generation of frequent itemsets is an essential and time-consuming step in mining association rules. Most of the studies adopt the Apriori-based approach, which has great effort in generating candidate itemsets and needs multiple database accesses. Recent studies indicate that FP-tree approach has been utilized to avoid the generation of candidate itemsets and scan transaction database only twice, but they work with more complicated data structure. Besides, it needs to adjust the structure of FP-tree when it applied to incremental mining application. It is necessary to adjust the position of an item upward or downward in the structure of FP-tree when a new transaction increases or decreases the accumulation of the item. The process of the adjustment of the structure of FP-tree is the bottlenecks of the FP-tree in incremental mining application. Therefore, algorithms for efficient mining of frequent patterns are in urgent demand. This paper aims to improve both time and space efficiency in mining frequent itemsets and incremental mining application. We propose a novel QSD (Quick Simple Decomposition) algorithm using simple decompose principle which derived from minimal heap tree, we can discover the frequent itemsets quickly under one database scan. Meanwhile, QSD algorithm doesn't need to scan database and reconstruct data structure again when database is updated or minimum support is varied. It can be applied to on-line incremental mining applications without any modification. Comprehensive experiments have been conducted to assess the performance of the proposed algorithm. The experimental results show that the QSD algorithm outperforms previous algorithms.

This paper studied the use of class association rules to classify protein-protein interaction type. Transactions are generated from the residues on the binding site of a protein complex. A transaction is in the form of a pair of residue sets. Transactions from transient protein complexes and from obligate protein complexes are stored separately. Two sets of patterns are mined from the sets of transactions. An unseen pair of proteins is classified be three score measures. The best classification performance achieves 80% accuracy. A biologist can submit a query protein, and get proteins that are likely to do certain interaction with his protein. With the patterns, indexing for screening potential proteins can be implemented efficiently.

Self-organizing map (SOM) is a type of artificial neural network for cluster analysis. Each neuron in the map competes with others for the input data objects in order to learn the grouping of the input space. Besides competition, neighbor neurons of a winning neuron also learn. SOM has a natural propensity to cluster data into visually distinct clusters, which show the intrinsic grouping of data.The self-organizing map algorithm is heuristic in nature and will almost always converge. Since self-organizing map may be trapped in a local optimum, so we introduce momentum into the learning process thus the movement of a neuron may jump over local optimum. We expect this will be similar to the learning of neurons in back-propagation with momentum. Like the learning process in back-propagation, the timing for updating the amount of movement of a neuron is either batch mode or incremental mode. However, due to the neighborhood function, the movement of a non-winner neuron is relatively small as compare to when it is a winner. So when deciding the momentum, the previous movement of a neuron needs special consideration. Experiment result show that adding momentum to self-organizing map considerably contributes to the acceleration of the convergence.

Proteins interact with each other with their binding sites. In this paper, we classify types of interactions using physicochemical properties information of the binding site. We distinguish between permanent protein interactions and transient protein interactions. Basic data of the amino acids on binding sites are retrieved. A method using genetic programming to construct features from the basic data is proposed. The method achieves an average classification accuracy of 80%.

Study on protein-protein interaction is important for understanding the protein function in cell activity. Protein-protein recognition plays a crucial role of biology. Therefore, we use the properties of protein interface for protein recognition prediction because the interface offers important clues in biological functions. Genetic Programming (GP), one of artificial intelligence technologies, has been proposed in data classification research in biology. In this paper, we present a prediction method with GP for protein-protein recognition based on protein binding site features. We successfully predict recognition proteins with an average accuracy rate of 78% with ten-fold cross validation.

Many efficient association rule mining algorithms have been proposed in the literature. In this paper, we propose an algorithm FRM (Mining Frequent Itemsets by Frequent-Related Mechanism). Most of the studies adopt an Apriori-like candidate set generation-and-test approach. However, candidate generation is still costly when there exist a large number of long patterns. FRM scans database only four times and it does not adopt the Apriori-like approach in mining process. It uses the frequent-related mechanism to generate the itemsets which are the most possible to be frequent and it eliminates a great number of infrequent itemsets. So FRM is very suitable to mine the databases whose record length is very long.

Analysis of protein-protein recognition is a popular issue recently, which plays a crucial role in regulation of biochemical pathways and signaling transmittal. A protein is recognized with the other protein by combining a transient complex, otherwise which will become a permanent complex. Therefore, understanding physico-chemical properties of the protein interface can offer important clues for biological processes and functions. In this paper, we propose prediction method for protein-protein recognition based on features extracted from the residues. Residues on binding sites of two contacting proteins in a complex are projected from 3D to 2D plane. In order to have the same direction, each 2D plane is rotated by an angle decided by principal component analysis (PCA) method. Then, the 2D plane is partitioned into a 5times5 grid. The feature vector is composed of the residues distribution of polarity, electricity, and hydrophobicity on the 2D plane. Support vector machine (SVM) is adopted for prediction. Experimental results show that the prediction achieves an accuracy rate of 80%.

Concept hierarchies are important for generalization in many data mining applications. Abundant algorithms have been proposed for automatic construction of concept hierarchy. A typical application of such algorithms is constructing directories for documents in information retrieval community. However, the research result can not be directly adopted for automatic construction of concept hierarchies for objects with identifiers only, such as items in market basket database where items have no attribute and only similarities between items are available. So, the metrics for directories for documents are not suitable for hierarchies for identifier-only data. In this paper, we propose a measurement that considers the unevenness of similarities among objects in the child nodes. We use the unevenness value to express the balance of concept hierarchies. For constructing a concept hierarchy, we propose a hierarchical clustering with join/merge decision (HCJMD) which is modified from hierarchical agglomerative clustering (HAC).

In this paper, instead of proposing the fastest mining algorithm in the world, we present a new approach in mining association rules. We propose a new algorithm - GRA (Gradational Reduction Approach). It adopts three mechanisms to increase the performance of mining. First, GRA algorithm uses a hash based technique, Hash MAP, which is similar to Hash Table to increase the access efficiency. Second, GRA algorithm uses an infrequent itemsets filtering mechanism to avoid generating a great deal of infrequent sub-itemsets of transaction records. Third, in order to reduce the size of database, GRA algorithm uses gradational reduction mechanism which uses the frequent itemsets as the information of filtration mechanisms to erase the infrequent items from database at every phase. GRA algorithm can decrease a large number of non-frequent itemsets and increase the utility rate of memory.

Transforming sequences into numeric feature vectors is a promising method in bio-sequence similarity search. The process of transformation will lost some information of the origin sequence. In order to improve the accuracy, weight assignment can be used. Based on this notion, we proposed an adaptive weighting distance which is based on feature vector that contains three groups of features: count, RPD, and APD of a DNA sequence. In this paper, weighted LI distance is applied for computing the distance between two feature vectors. We compute the average of entropy of two sequences and then assign the weights to count, RPD and APD according to the weight table which is pointed by the variant of entropy of two sequences. The weight tables are then adjusted by genetic algorithms. Experiment shows that such adaptive weight distance mechanism helps reflect the distance between sequences.

The technology of data mining is more important in recent years, and it is generally applied to commercial forecast and decision supports. Sequential pattern mining algorithms in the field of data mining play one of the important roles. Many of sequential pattern mining algorithms were proposed to improve the efficiency of data mining or save the utility rate of memory. So, our major study tries to improve the efficiency of sequential pattern mining algorithms. We propose a new algorithm - GRS (A Gradational Reduction Approach for Mining Sequential Patterns) which is an efficient algorithm of mining sequential patterns. GRS algorithm uses gradational reduction mechanism to reduce the length of transactions and uses GraDec function to avoid generating large number of infrequent sequential patterns; and it is very suitable to mine the transactions of databases whose record lengths are very long. The GRS algorithm only generates some sequences which are very possible to be frequent. So, the GRS algorithm can decrease a large number of infrequent sequences and increase the utility rate of memory.

Similarity search in biology sequences has received substantial attention in the past decade. Sequence alignment is the essential task for similar sequence search in bioinformatics. The biological sequence databases have getting larger in past decade, finding sequences similar to the query sequence is a time consuming task. By transforming sequences into numeric feature vectors, we can quickly filter out sequences whose feature vectors are distant to the feature vector of the query sequence. We proposed an adaptive weighting distance which is based on feature vector that contains three groups of features: count, extended relative position dispersion (XRPD), and extended absolute position dispersion (XAPD) of a DNA sequence. Each group has four dimensions for A, C, T, and G. When computing distance between two feature vectors, Euclidean distance and L1 distance are commonly used. In this paper, we use weighted L1 distance for computing the distance between two feature vectors. We derive weights for the four nucleotides from the count group, and apply the weights to both XRPD and XAPD. In other words, if a certain kind of nucleotide appears much frequent than the other kinds of nucleotides, the weight for the kind of nucleotide should also be large in XRPD and XAPD groups. Experiments show that such distance of feature vectors helps reflect the distance between sequences.

Concept hierarchies are important in many generalized data mining applications, such as multiple level association rule mining. In literature, concept hierarchy is usually given by domain experts. In this paper, we propose algorithms to automatically build a concept hierarchy from a provided distance matrix. Our approach is modifying the traditional hierarchical clustering algorithms. For the purpose of algorithm evaluation, a distance matrix is derived from the concept hierarchy built by our algorithm. Root mean squared error between the provided distant matrix and the derived distance matrix is used as evaluation criterion. We compare the traditional hierarchical clustering and our modified algorithm under three strategies of computing cluster distance, namely single link, average link, and complete link. Empirical results show that the traditional algorithm under complete link strategy performs better than the other strategies. Our modified algorithms perform almost the same under the three strategies; and our algorithms perform better than the traditional algorithms under various situations.

Concept hierarchies are important for generalization in many data mining applications. We propose a method to automatically build a concept hierarchy from a provided distance matrix. The method is a modification of traditional agglomerative hierarchical clustering algorithm. When two closest clusters are selected for combining into a new cluster, the algorithm either creates a new cluster with the two original clusters as its sub-clusters, or let a cluster join the other without creating a new cluster at the higher level of the hierarchy. For the purpose of algorithm evaluation, a distance matrix is derived from the concept hierarchy built by algorithm. Root mean squared error between the provided distant matrix and the derived distance matrix is used as evaluation criterion. Empirical results show that the traditional algorithm under complete link strategy performs better than the other strategies, our algorithms perform almost the same under the three strategies, and our algorithms perform better than the traditional algorithms under various situations.

Memory-Based Reasoning and K-Nearest Neighbor Searching are frequently adopted data mining techniques. But, they suffer from scalability. Indexing is a promising solution. However, it is difficult to index categorical attributes, since there does not exist linear ordering property among categories in a nominal attribute. In this paper, we proposed heuristic algorithms to map categories to numbers. Distance relationships among categories are preserved as many as possible. We empirically studied the performance of the algorithms under different distance situations.

Transactions in areas such as real time databases and multimedia databases not only compete, but also cooperate. We propose a model for transactions to cooperate through rules and task communication and synchronization. In our model, transactions manipulate persistent and transient data objects. With event condition action (ECA) rules and three additional non ECA rules as tools, our model provides transactions with a new way of cooperation. Cooperation can be specified statically at transaction compile time, but also dynamically at transaction execution time through rules. Non ECA rules are proposed to improve transaction communication. For example, a non ECA rule can prohibit an action from being performed in a certain time interval. Actions of rules have time constraints. Rules specify time intervals within which actions are performed or prohibited upon the occurrences or absences of events. For a set of rules, we investigate the consistency property whether an action is both triggered and prohibited in overlapping time intervals.

This paper describes SciMMDB, a scientific multimedia database system designed for polymer science experiment data applications. SciMMDB maintains multimedia data types of video, test and picture (as well as other standard data types), and allows users to: form multimedia presentation streams about experiments; define a presentation which organizes a number of presentation streams for playout purposes; and control the playout of a presentation. To form video, text or picture streams, a presentation stream construction language is described. Queries in this language express spatial and temporal relationships involving content objects and efficient evaluation of such queries are facilitated by indexing structures. SciMMDB uses IB+trees for queries involving temporal intervals. In SciMMDB, presentation streams are formed into a presentation using the notion of presentation graphs. During the playout of a presentation, each presentation stream in the presentation is played out by a separate transaction, called an output agent. Such transactions communicate and synchronize with each other using the cooperative transaction model.

Agile manufacturing systems can benefit significantly from a database support. This paper describes AMDS, an agile manufacturing database system designed for capturing and manipulating the operational data of a manufacturing cell. AMDS is a continuous data-gathering real-time DBMS, and it can be logged either locally or remotely and used for off-line analysis as well. The temporal operational data obtained is used for performance and reliability analysis, high-level summary report generation, real-time monitoring and active interaction. This paper gives an overview of AMDS and its real-time features.

In this chapter, we describe the case study of a real-time database system for a specific kind of operational data generated by an agile manufacturing system. The term agile manufacturing refers to a manufacturing system that can fabricate various products simultaneously without long downtimes for retooling. The agile manufacturing increases competitiveness of companies in the market by decreasing the downtime and reconfiguration overhead incurred due to product changes. The agile manufacturing concept is already in a stage of practical use in some companies, for example, pager manufacturing at Motorola [19], or customized bicycles from Panasonic [5].

Cluster analysis is frequently used to study the trend of gene expression behaviours from microarray time series data. We adopt a partitioning-based clustering algorithm for such a task. After time series are discritised into sequences, a sequential pattern mining technique is applied to find patterns as the initial clusters. Longest Common Subseries Similarity is used to measure the similarity between time series which overcomes the 'shift-effect' influence. An object is re-assigned to the cluster which has most objects within the k nearest neighbours of the object. Similarity measurements, like Pearson correlation coefficient, are used to determine the neighbours.