Solar activities are caused by the evolution of solar magnetic fields. Magnetic field parameters derived from photo-spheric vector magneto grams of solar active regions have been used to analyze and forecast extreme space weather events such as flares and coronal mass ejections. Unfortunately, the most recent Solar Cycle 24 was relatively weak with few large events, though it is the only solar cycle in which time-series vector magnetograms have been available. In this paper, we focus on two NASA instru-ments, namely the Michelson Doppler Imager (MDI) onboard the Solar and Heliospheric Observatory (SOHO) launched in Solar Cycle 23 (1996–2008), and the Helioseismic and Magnetic Imager (HMI) onboard the Solar Dynamics Observatory (SDO) launched in Solar Cycle 24 (2008–2019). While SOHOIMDI provides data from the more active Solar Cycle 23, it only offers line-of-sight (LOS) magneto grams without vector magnetograms. We propose Solar Image GAN (SIGAN), a generative adversarial network model designed to synthesize vector magnetic field images for Solar Cycles 23 and 24. SIGAN is trained using Hα images, SDOIHMI LOS, and vector magnetograms. It can generate vector magneto grams for both SDOIHMI and SOHOIMDI using Hα images and LOS magneto grams as input. Extensive experiments demonstrated the good performance of the proposed approach.

We propose to incorporate three interpretable methods, namely SHAP (SHapley Additive exPlanations), PDP (partial dependence plots) and Anchors, into a deep learning-based model, called SolarFlareNet, for operational flare forecasting. SolarFlareNet takes as input a sample of SHARP (Space-weather HMI Active Region Patches) magnetic parameters and predicts as output whether a solar flare would occur within the next 24 hours. We analyze flare events that occurred from May 2010 to December 2022 using the Geostationary Operational Environmental Satellite's X-ray flare catalogs and construct a database of flares with identified active regions in the catalogs. This database, together with the SHARP magnetic parameters, is used to train and test the SolarFlareNet model. Our experimental results describe the use of the three proposed methods (SHAP, PDP, and Anchors) to interpret the SolarFlareNet model and demonstrate the effectiveness of the methods.

Deep learning models are often considered black box models as their internal workings tend to be opaque to the user. Because of this lack of transparency, it is challenging to understand the reasoning behind the model’s predictions. Here, we present an approach to making a solar flare prediction model interpretable. This model, built based on a long short-term memory (LSTM) network with an attention mechanism, aims to predict whether an active region (AR) on the Sun’s surface would produce a large flare, namely an M- or X-class flare, within 24 hours. The flare events used in this study are collected from the Geostationary Operational Environmental Satellite X-ray flare catalogs provided by the National Centers for Environmental Information. The crux of our approach is to model data samples in an AR as time series and use the LSTM network to capture the temporal dynamics of the data samples. Each data sample has 22 features including magnetic parameters and flare history parameters. To make the model’s predictions accountable and reliable, we leverage post hoc model-agnostic techniques, which help elucidate the factors contributing to the predicted output for an input sequence and provide insights into the model’s behavior across multiple sequences within an AR. To our knowledge, this is the first time that interpretability has been added to an LSTM-based flare prediction model.

In this paper we present a new approach, named DLGraph, for malware detection using deep learning and graph embedding. DLGraph employs two stacked denoising autoencoders (SDAs) for representation learning, taking into consideration computer programs' function-call graphs and Windows application programming interface (API) calls. Given a program, we first use a graph embedding technique that maps the program's function-call graph to a vector in a low-dimensional feature space. One SDA in our deep learning model is used to learn a latent representation of the embedded vector of the function-call graph. The other SDA in our model is used to learn a latent representation of the given program's Windows API calls. The two learned latent representations are then merged to form a combined feature vector. Finally, we use softmax regression to classify the combined feature vector for predicting whether the given program is malware or not. Experimental results based on different datasets demonstrate the effectiveness of the proposed approach and its superiority over a related method.

Directed networks find many applications in computer science, social science and biomedicine, among others. In this paper we propose a new graph mining algorithm that is capable of locating all frequent induced subgraphs in a given set of directed networks. We present an incremental coding scheme f or representing the canonical form of a graph, study its properties, and develop new techniques for pattern generation suitable for directed networks. We prove that our algorithm is complete, meaning that no qualified pattern is missed by the algorithm. Furthermore, our algorithm is correct in the sense that all patterns found by the algorithm are frequent induced subgraphs in the given networks. Experimental results based on synthetic data and gene regulatory networks show the good performance of our algorithm, and its application in network inference.

In systems biology, two important regulatory networks are gene regulatory networks (GRNs) and regulatory networks of microRNAs (RNMs). A GRN is modeled as a directed graph in which a node represents a gene or transcription factor (TF), and an edge from a TF to a gene indicates that the TF regulates the expression of the gene. An RNM is modeled as a bipartite directed graph with two disjoint sets of nodes: a set of nodes that represent microRNAs (miRNAs) and a set of nodes that represent genes or TFs. Directed edges between these two sets of nodes represent miRNA-target interactions or TF-miRNA regulatory relations. In this paper, we present an approach to reverse engineering GRNs and RNMs using a dynamic Bayesian network and mutual information scoring function. Our approach is able to automatically infer both GRNs and RNMs from time series of expression data. Experimental results on different datasets show that our approach is more accurate than other time-series based network inference methods.

Biologists are stepping up their efforts in understanding the biological processes that underlie disease pathways in the clinical contexts. This has resulted in a flood of biological and clinical data—genomic sequences, DNA microarrays, protein interactions, biomedical images, disease pathways, etc. The rapid adoption of Electronic Health Records (EHRs) across healthcare systems, coupled with the capability of linking EHRs to research biorepositories, provides a unique opportunity for conducting large-scale Precision Medicine research. As a result, data mining techniques, for knowledge discovery and deriving data driven insights from various data sources, are increasingly important in modern biology and healthcare. The purpose of this special section is to bring together the researchers in bioinformatics, healthcare informatics, and data mining to share about their current research, and their visions on future directions.

Supervised methods for inferring gene regulatory networks (GRNs) perform well with good training data. However, when training data is absent, these methods are not applicable. Unsupervised methods do not need training data but their accuracy is low. In this paper, we combine supervised and unsupervised methods to infer GRNs using time-series gene expression data. Specifically, we use results obtained from unsupervised methods to train supervised methods. Since the results contain noise, we develop a data cleaning algorithm to remove noise, hence improving the quality of the training data. These refined training data are then used to guide classifiers including support vector machines and deep learning tools to infer GRNs through link prediction. Experimental results on several data sets demonstrate the good performance of the classifiers and the effectiveness of our data cleaning algorithm.

BACKGROUND: RNA pseudoknots play important roles in many biological processes. Previous methods for comparative pseudoknot analysis mainly focus on simultaneous folding and alignment of RNA sequences. Little work has been done to align two known RNA secondary structures with pseudoknots taking into account both sequence and structure information of the two RNAs. RESULTS: In this article we present a novel method for aligning two known RNA secondary structures with pseudoknots. We adopt the partition function methodology to calculate the posterior log-odds scores of the alignments between bases or base pairs of the two RNAs with a dynamic programming algorithm. The posterior log-odds scores are then used to calculate the expected accuracy of an alignment between the RNAs. The goal is to find an optimal alignment with the maximum expected accuracy. We present a heuristic to achieve this goal. The performance of our method is investigated and compared with existing tools for RNA structure alignment. An extension of the method to multiple alignment of pseudoknot structures is also discussed. CONCLUSIONS: The method described here has been implemented in a tool named RKalign, which is freely accessible on the Internet. As more and more pseudoknots are revealed, collected and stored in public databases, we anticipate a tool like RKalign will play a significant role in data comparison, annotation, analysis, and retrieval in these databases.

We consider a new tree mining problem that aims to discover restrictedly embedded subtree patterns from a set of rooted labeled unordered trees. We study the properties of a canonical form of unordered trees, and develop new Apriori-based techniques to generate all candidate subtrees level by level through two efficient rightmost expansion operations: 1) pairwise joining and 2) leg attachment. Next, we show that restrictedly embedded subtree detection can be achieved by calculating the restricted edit distance between a candidate subtree and a data tree. These techniques are then integrated into an efficient algorithm, named frequent restrictedly embedded subtree miner (FRESTM), to solve the tree mining problem at hand. The correctness of the FRESTM algorithm is proved and the time and space complexities of the algorithm are discussed. Experimental results on synthetic and real-world data demonstrate the effectiveness of the proposed approach.

Motif finding in DNA, RNA and proteins plays an important role in life science research. In this paper, we present a computational approach to searching for RNA tertiary motifs in genomic sequences. Specifically, we describe a method, named CSminer, and show, as a case study, the application of CSminer to genome-wide search for coaxial helical stackings in RNA 3-way junctions. A coaxial helical stacking motif occurs in an RNA 3-way junction where two separate helical elements form a pseudocontiguous helix and provide thermodynamic stability to the RNA molecule as a whole. Experimental results demonstrate the effectiveness of our approach.

MicroRNAs (miRNAs) are non-coding RNAs with approximately 22 nucleotides (nt) that are derived from precursor molecules. These precursor molecules or pre-miRNAs often fold into stem-loop hairpin structures. However, a large number of sequences with pre-miRNA-like hairpins can be found in genomes. It is a challenge to distinguish the real pre-miRNAs from other hairpin sequences with similar stem-loops (referred to as pseudo pre-miRNAs). Several computational methods have been developed to tackle this challenge. In this paper we propose a new method, called MirlD, for identifying and classifying microRNA precursors. We collect 74 features from the sequences and secondary structures of pre-miRNAs; some of these features are taken from our previous studies on non-coding RNA prediction while others were suggested in the literature. We develop a combinatorial feature mining algorithm to identify suitable feature sets. These feature sets are then used to train support vector machines to obtain classification models, based on which classifier ensemble is constructed. Finally we use a boosting algorithm to further enhance the accuracy of the classifier ensemble. Experimental results on a variety of species demonstrate the good performance of the proposed method, and its superiority over existing tools.

We study a data mining problem concerning the elastic peak detection in 2D liquid chromatography-mass spectrometry (LC-MS) data. These data can be modeled as time series, in which the X-axis represents time points and the Y-axis represents intensity values. A peak occurs in a set of 2D LC-MS data when the sum of the intensity values in a sliding time window exceeds a user-determined threshold. The elastic peak detection problem is to locate all peaks across multiple window sizes of interest in the data set. We propose a new data structure, called a Shifted Aggregation Tree or AggTree for short, and use the data structure to find the different peaks. Our method, called PeakID, solves the elastic peak detection problem in 2D LC-MS data yielding neither false positives nor false negatives. The method works by first constructing an AggTree in a bottom-up manner from the given data set, and then searching the AggTree for the peaks in a top-down manner. We describe a state-space algorithm for finding the topology and structure of an efficient AggTree to be used by PeakID. Our experimental results demonstrate the superiority of the proposed method over other methods on both synthetic and real-world data.

We study a new data mining problem concerning the discovery of frequent agreement subtrees (FASTs) from a set of phylogenetic trees. A phylogenetic tree, or phylogeny, is an unordered tree in which the order among siblings is unimportant. Furthermore, each leaf in the tree has a label representing a taxon (species or organism) name, whereas internal nodes are unlabeled. The tree may have a root, representing the common ancestor of all species in the tree, or may be unrooted. An unrooted phylogeny arises due to the lack of sufficient evidence to infer a common ancestor of the taxa in the tree. The FAST problem addressed here is a natural extension of the maximum agreement subtree (MAST) problem widely studied in the computational phylogenetics community. The paper establishes a framework for tackling the FAST problem for both rooted and unrooted phylogenetic trees using data mining techniques. We first develop a novel canonical form for rooted trees together with a phylogeny-aware tree expansion scheme for generating candidate subtrees level by level. Then, we present an efficient algorithm to find all FASTs in a given set of rooted trees, through an Apriori-like approach. We show the correctness and completeness of the proposed method. Finally, we discuss the extensions of the techniques to unrooted trees. Experimental results demonstrate that the proposed methods work well, and are capable of finding interesting patterns in both synthetic data and real phylogenetic trees.

In this paper we propose a new method for aligning two RNA secondary structures by taking into account the presence of conserved RNA substructures, or constraints, in the alignment process. Our method allows the incorporation of specific knowledge about the RNA structures being analyzed while computing their alignment and thus is very useful for RNA motif detection. We develop statistical measures to assess the significance of alignment scores. Experimental results obtained by using the constrained alignment method to search for structural motifs in the untranslated regions of Trypanosoma brucei mRNAs demonstrate the good performance of the proposed method and its superiority over existing methods.

In this poster we propose a method for addressing the genomic nomenclature problem by using phylogenetic tools along with the BIO-AJAX data cleaning framework.

In this paper we present RADAR, a web-based toolkit for RNA data analysis and research. The toolkit is capable of performing database search, multiple structure alignment, and pairwise structure comparison. In addition, RADAR provides two salient features: (1) constrained alignment of RNA secondary structures, and (2) prediction of the consensus for a set of RNA secondary structures. RADAR assists scientists in performing many important RNA mining operations, including understanding the functionality of RNA sequences, the detection of structural RNA motifs and the clustering of RNA molecules, among others. The toolkit is fully operational and accessible on the Web at http://datalab.njit.edu/biodata/rna/RSmatch/server.htm.

Support vector machines (SVMs) are a state-of-the-art machine learning tool widely used in speech recognition, image processing and biological sequence analysis. An essential step in SVMs is to devise a kernel function to compute the similarity between two data points in Euclidean space. In this paper we present a new kernel that takes advantage of both global and local structural information in RNAs and uses the information together to classify RNAs with support vector machines. Experimental results demonstrate the good performance of the new kernel and show that it outperforms existing kernels when applied to classifying non-coding RNA sequences.

We present a new data mining problem to discover frequent agreement subtree patterns from a database of rooted phylogenetic trees. This problem is a natural extension of the traditional MAST (maximum agreement subtree) problem. To solve the problem, we first present a novel canonical form for leaf-labeled trees and an efficient tree expansion algorithm for generating candidate subtrees level by level. We then show how to efficiently discover all frequent agreement subtrees from a given set of phylogenetic trees, through an Apriori-like data mining approach. We discuss the correctness and completeness of the proposed method. Experimental results demonstrate that the proposed method can discover interesting patterns from different phylogenetic trees for multiple species. The algorithms were implemented in C++ and integrated into an online toolkit, which is fully operational and accessible on the World Wide Web.

Currently, phylogenetic tree techniques are being used in multiple areas, from Tree of Life problems to pathogen recognition to drug discovery. With all of these applications for phylogenetic tree techniques, methods are needed to exploit the knowledge modeled in phylogenetic trees more thoroughly. One such information point of interest is the behavior of frequent patterns in phylogenetic trees. While there are many techniques that look at maximal, consensus and supertreepatterns, there are few techniques that look at frequent, but not maximal pattern. This demonstration paper presents PhyloMiner, a tool that automatically discovers frequent agreement subtrees from multiple phylogenies. It introduces this topic of frequent agreement subtrees and then concludes with describing the PhyloMiner tool that implements these concepts and is available freely on the World Wide Web.

BACKGROUND: Alignment of RNA secondary structures is important in studying functional RNA motifs. In recent years, much progress has been made in RNA motif finding and structure alignment. However, existing tools either require a large number of prealigned structures or suffer from high time complexities. This makes it difficult for the tools to process RNAs whose prealigned structures are unavailable or process very large RNA structure databases. RESULTS: We present here an efficient tool called RSmatch for aligning RNA secondary structures and for motif detection. Motivated by widely used algorithms for RNA folding, we decompose an RNA secondary structure into a set of atomic structure components that are further organized by a tree model to capture the structural particularities. RSmatch can find the optimal global or local alignment between two RNA secondary structures using two scoring matrices, one for single-stranded regions and the other for double-stranded regions. The time complexity of RSmatch is O(mn) where m is the size of the query structure and n that of the subject structure. When applied to searching a structure database, RSmatch can find similar RNA substructures, and is capable of conducting multiple structure alignment and iterative database search. Therefore it can be used to identify functional RNA motifs. The accuracy of RSmatch is tested by experiments using a number of known RNA structures, including simple stem-loops and complex structures containing junctions. CONCLUSION: With respect to computing efficiency and accuracy, RSmatch compares favorably with other tools for RNA structure alignment and motif detection. This tool shall be useful to researchers interested in comparing RNA structures obtained from wet lab experiments or RNA folding programs, particularly when the size of the structure dataset is large.

In this paper, we present an embedding technique, called MetricMap, which is capable of estimating distances in a pseudometric space. Given a database of objects and a distance function for the objects, which is a pseudometric, we map the objects to vectors in a pseudo-Euclidean space with a reasonably low dimension while preserving the distance between two objects approximately. Such an embedding technique can be used as an approximate oracle to process a broad class of distance-based queries. It is also adaptable to data mining applications such as data clustering and classification. We present the theory underlying MetricMap and conduct experiments to compare MetricMap with other methods including MVP-tree and M-tree in processing the distance-based queries. Experimental results on both protein and RNA data show the good performance and the superiority of MetricMap over the other methods.

Frequent structure mining (FSM) aims to discover and extract patterns frequently occurring in structural data, such as trees and graphs. FSM finds many applications in bioinformatics, XML processing, Web log analysis, and so on. We present a new FSM technique for finding patterns in rooted unordered labeled trees. The patterns of interest are cousin pairs in these trees. A cousin pair is a pair of nodes sharing the same parent, the same grandparent, or the same great-grandparent, etc. Given a tree T, our algorithm finds all interesting cousin pairs of T in O(|T|/sup 2/) time where |T| is the number of nodes in T. Experimental results on synthetic data and phylogenies show the scalability and effectiveness of the proposed technique. To demonstrate the usefulness of our approach, we discuss its applications to locating co-occurring patterns in multiple evolutionary trees, evaluating the consensus of equally parsimonious trees, and finding kernel trees of groups of phylogenies. We also describe extensions of our algorithms for undirected acyclic graphs (or free trees).

XML is increasingly important in data exchange and information management. A large amount of efforts have been spent in developing efficient techniques for storing, querying, indexing and accessing XML documents. In This work we propose a new approach to clustering XML data. In contrast to previous work, which focused on documents defined by different DTDs, the proposed method works for documents with the same DTD. Our approach is to extract features from documents, modeled by ordered labeled trees, and transform the documents to vectors in a high-dimensional Euclidean space based on the occurrences of the features in the documents. We then reduce the dimensionality of the vectors by principal component analysis (PCA) and cluster the vectors in the reduced dimensional space. The PCA enables one to identify vectors with co-occurrent features, thereby enhancing the accuracy of the clustering. Experimental results based on documents obtained from Wisconsin's XML data bank show the effectiveness and good performance of the proposed techniques.

The widespread use of spatio-temporal databases and applications has fuelled an urgent need to discover interesting time and space patterns in such databases. While much work has been done in discovering time/sequence patterns or spatial patterns, discovering of patterns involving both time and space dimensions is still in its infancy, We introduce the concept of flow patterns. Flow patterns are intended to describe the change of events over space and time. These flow patterns are useful to the understanding of many real-life applications. We present a disk-based algorithm, FlowMiner, which utilizes temporal relationships and spatial relationships amid events to generate flow patterns. Our performance study shows that FlowMiner is both scalable and efficient. Experiments on real-life datasets also reveal interesting flow patterns.

Phylogenetic trees are unordered labeled trees in which each leaf node has a label and the order among siblings is unimportant. In this paper we propose a new similarity measure, called TreeRank, for phylogenetic trees and present an algorithm for computing TreeRank scores. Given a query or pattern tree P and a data tree D, the TreeRank score from P to D is a measure of the topological relationships in P that are found to be the same or similar in D. The proposed algorithm calculates the TreeRank score in O(M/sup 2/ + N) time where M is the number of nodes appearing in both P and D, and N is the number of nodes in D. We then develop a search engine that, given a query or pattern tree P and a database of trees D, finds and ranks the nearest neighbors of P in D where the "nearness" is measured by the proposed similarity function. This structure-based search engine is fully operational and is available on the World Wide Web.

In this paper we present a new system, called GeneScout, for predicting gene structures in vertebrate genomic DNA. The system contains specially designed hidden Markov models (HMMs) for detecting functional sites including protein-translation start sites, mRNA splicing junction donor and acceptor sites, etc. Our main hypothesis is that, given a vertebrate genomic DNA sequence S, it is always possible to construct a directed acyclic graph G such that the path for the actual coding region of S is in the set of all paths on G. Thus, the gene detection problem is reduced to that of analyzing the paths in the graph G. A dynamic programming algorithm is used to find the optimal path in G. The proposed system is trained using an expectation-maximization (EM) algorithm and its performance on vertebrate gene prediction is evaluated using the 10-way cross-validation method. Experimental results show the good performance of the proposed system and its complementarity to a widely used gene detection system.

Modern search engines answer keyword-based queries extremely efficiently. The impressive speed is due to clever inverted index structures, caching, a domain-independent knowledge of strings, and thousands of machines. Several research efforts have attempted to generalize keyword search to keytree and keygraph searching, because trees and graphs have many applications in next-generation database systems. This paper surveys both algorithms and applications, giving some emphasis to our own work.

Phylogenetic trees are essential for understanding the relationships among organisms or taxa. Many of the current techniques for searching phylogenetic repositories allow the user to perform a keyword-type search or an aligned sequence data search, or to browse a hierarchical list of taxa. Here we describe a new search engine that allows the user to present an example phylogeny, or a query tree, and then searches a phylogenetic database for trees that contain the query structure. The presented search engine is fully operational and is available on the World Wide Web.

An unordered labeled tree is a tree in which each node has a string label and the parent-child relationship is significant, but the order among siblings is unimportant. This paper presents an approach to the nearest neighbor search problem for these trees. Given a database D of unordered labeled trees and a query tree Q, the goal is to find those trees in D that "approximately" contain Q. Our approach is based on storing the paths of the trees in a suffix array and then counting the number of mismatching paths between the query tree and a data tree. To speed up a search, we use a hash-based technique to filter out unqualified data trees at an early stage of the search. Experimental results obtained by running our techniques on phylogenetic trees and synthetic data demonstrate the good performance of the proposed approach. We also discuss the use of our work in XML and scientific database management.

XML's tree structure provides a rich background for complicated structural searches. In this paper we present a new system, called XML Query by Example (XML QBE) that allows the user to query XML documents exploiting their inherent tree structure. We present some interesting queries and describe the underlying query processing algorithms. We also describe the system's architecture and report its implementation status. Finally we conclude the paper by pointing out some future work.

Presents a method for finding patterns in 3D graphs. Each node in a graph is an undecomposable or atomic unit and has a label. Edges are links between the atomic units. Patterns are rigid substructures that may occur in a graph after allowing for an arbitrary number of whole-structure rotations and translations as well as a small number (specified by the user) of edit operations in the patterns or in the graph. (When a pattern appears in a graph only after the graph has been modified, we call that appearance "approximate occurrence.") The edit operations include relabeling a node, deleting a node and inserting a node. The proposed method is based on the geometric hashing technique, which hashes node-triplets of the graphs into a 3D table and compresses the label-triplets in the table. To demonstrate the utility of our algorithms, we discuss two applications of them in scientific data mining. First, we apply the method to locating frequently occurring motifs in two families of proteins pertaining to RNA-directed DNA polymerase and thymidylate synthase and use the motifs to classify the proteins. Then, we apply the method to clustering chemical compounds pertaining to aromatic compounds, bicyclicalkanes and photosynthesis. Experimental results indicate the good performance of our algorithms and high recall and precision rates for both classification and clustering.

Presents new techniques for biosequence classification, with a focus on recognizing E. Coli promoters in DNA. Specifically, given an unlabeled DNA sequence S, we want to determine whether or not S is an E. Coli promoter. We use an expectation maximization (EM) algorithm to locate the -35 and -10 binding sites in an E. Coli promoter sequence. The EM algorithm differs from previously published EM algorithms in that, instead of assuming a uniform distribution for the lengths of the spacer between the -35 binding site and the -10 binding site as well as between the -10 binding site and the transcriptional start site, our algorithm deduces the probability distribution for these lengths. Based on the located binding sites, we select features in each E. Coli promoter sequence according to their information contents and represent the features using an orthogonal encoding method. We then feed the features to a neural network for promoter recognition. Empirical studies show that the proposed approach achieves good performance on different data sets.

Biological data mining aims to extract signi cant information from DNA, RNA and proteins.The signi cant information may refer to motifs, functional sites, clustering and classi cation rules.This paper presents an example of biological data mining: the classi cation of protein sequences using neural netw orks.We proposenew tec hniques to extract features from protein data and use them in combination with the Ba yesianneural network to classify protein sequences obtained from the PIR protein database maintained at the National Biomedical Research F oundation.T o evaluate the performance of the proposed approach, we c o mpare it with other protein classi ers built based on sequence alignment and machine learning methods.Experimental results sho w the high precision of the proposed classi er and the complementarity of the tools studied in the paper.

A distance-mapping algorithm takes a set of objects and a distance metric and then maps those objects to a Euclidean or pseudo-Euclidean space in such a way that the distances among objects are approximately preserved. Distancemapping algorithms are a useful tool for clustering and visualization in data intensive applications, because they replace expensive distance calculations by sum-of-square calculations. This can make clustering in large databases with expensive distance metrics practical. In this paper we present five distance-mapping algorithms and conduct experiments to compare their performance in data clustering applications. These include two algorithms called FastMap and MetricMap, and three hybrid heuristics that combine the two algorithms in different ways. Experimental results on both synthetic and RNA data show the superiority of the hybrid algorithms. The results imply that FastMap and MetricMap capture complementary information about distance metrics and therefore ca...

Given a database D of three dimensional (3D) objects and a target object Q, the similarity search problem (also known as good-match retrieval) is defined as finding the objects D in D that approximately match Q, possibly in the presence of rotation, translation, node insert, delete and relabeling in D or Q. This type of query arises in many AI applications. We study the similarity search problem and a class of related queries. We present a computer vision based technique called geometric hashing for processing these queries. Experimental results on a database of 3D molecules obtained from the National Cancer Institute indicate the good performance of the presented technique.

Scientific data mining is the activity of finding significant information in scientific data. This paper presents an example of scientific data mining: the discovery of approximately common patterns in RNA secondary structures. We represent an RNA secondary structure by an ordered labeled tree based on a previously proposed scheme. The patterns in the trees are substructures that can differ in both substitutions and deletions/insertions of nodes of the trees. Our techniques incorporate approximate tree matching algorithms and novel heuristics for discovery and optimization. Experimental results obtained by running these algorithms on both generated data and RNA secondary structures show the good performance of the algorithms. It is shown that the optimization heuristics speed up the discovery algorithm by a factor of 10. Moreover, our optimized approach is 100,000 times faster than the brute force method.

Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology and natural language processing. We consider a substructure of an ordered labeled tree T to be a connected subgraph of T. Given two ordered labeled trees T/sub 1/ and T/sub 2/ and an integer d, the largest approximately common substructure problem is to find a substructure U/sub 1/ of T/sub 1/ and a substructure U/sub 2/ of T/sub 2/ such that U/sub 1/ is within edit distance d of U/sub 2/ and where there does not exist any other substructure V/sub 1/ of T/sub 1/ and V/sub 2/ of T/sub 2/ such that V/sub 1/ and V/sub 2/ satisfy the distance constraint and the sum of the sizes of V/sub 1/ and V/sub 2/ is greater than the sum of the sizes of U/sub 1/ and U/sub 2/. We present a dynamic programming algorithm to solve this problem, which runs as fast as the fastest known algorithm for computing the edit distance of two trees when the distance allowed in the common substructures is a constant independent of the input trees. To demonstrate the utility of our algorithm, we discuss its application to discovering motifs in multiple RNA secondary structures (which are ordered labeled trees).

Change detection in structured documents (e.g. SGML) is important in many applications including data warehousing, digital libraries and Internet databases. The paper presents a graphical environment for detecting changes in the structured documents. The authors represent each document by an ordered labeled tree based on the underlying markup language. They then compare two documents by using previously developed algorithms for pattern matching and pattern discovery in trees. Several operators are developed to support the comparison of the documents; graphical devices are provided to facilitate the use of the operators. They believe the proposed tool is useful for not only document management, but also software maintenance, particularly configuration management and version control, where programs are represented as parse trees and detecting changes in the trees provides a way to find the syntactic differences of two program versions.

Scientific data classification is the activity of determining whether or not an unlabeled scientific object belongs to an existing class. It is an important operation in the management of scientific databases. The authors present a case study for scientific data classification. Specifically, they develop a tool for DNA sequence classification. The tool works by generating and matching gapped fingerprints of DNA sequences. Experimental results obtained by applying our tool to classifying a set of Alu sequences demonstrate the good performance of the tool. While the reported research focuses on DNA classification, the techniques should generalize to any domain (e.g. multimedia) where data are naturally represented as sequences.

Structural matching and discovery in documents such as SGML and HTML is important for data warehousing [6], version management [7, 11], hypertext authoring, digital libraries [4] and Internet databases. As an example, a user of the World Wide Web may be interested in knowing changes in an HTML document [2, 5, 10]. Such changes can be detected by comparing the old and new version of the document (referred to as structural matching of documents). As another example, in hypertext authoring, a user may wish to find the common portions in the history list of a document or in a database of documents (referred to as structural discovery of documents). In SIGMOD 95 demo sessions, we exhibited a software package, called TreeDiff [13], for comparing two latex documents and showing their differences. Given two documents, the tool represents the documents as ordered labeled trees and finds an optimal sequence of edit operations to transform one document (tree) to the other. An edit operation could be an insert, delete, or change of a node in the trees. The tool is so named because documents are represented and compared using approximate tree matching techniques [9, 12, 14].

This paper presents an index structure for retrieving electronic messages that contain mistyped words or spelling errors. Given a query string (e.g., a search key), we want to find those messages that approximately contain the query, i.e., certain inserts, deletes and mismatches are allowed when matching the query with a word (or phrase) in the messages. Our approach is to store the messages sequentially in a database and hash their "fingerprints" into a number of "fingerprint files." When the query is given, its fingerprints are also hashed into the files and a histogram of votes is constructed on the messages. We derive a lower bound, based on which one can prune a large number of nonqualifying messages (i.e., those whose votes are below the lower bound) during searching. The paper presents some experimental results, which demonstrate the effectiveness of the index structure and the lower bound.

A knowledge-based tutoring system (KBTS) is a computer-based instructional system that uses artificial intelligence techniques to help people learn some subjects. We found that the knowledge communication process involving a KBTS and a human student can be decomposed into a series of communication cycles, where each cycle concentrates on one topic and contains four major phases: planning, discussing, evaluating and remedying. The major contributions of this work are the development of a generic architecture for supporting the knowledge communication between a KBTS and a student, and a graphical notation and schema for supporting the curriculum knowledge representation and manipulation during the planning phase of a tutoring process. The curriculum knowledge about a course can help a tutoring system determine the sequences in which the topics will be discussed with the students effectively and diagnose the students' mistakes. The curriculum knowledge base contains the goal structure of the course, prerequisite relations, and multiple ways of organizing topics, among others. As an example, we focus on developing SQL-TUTOR, a KBTS for the domain of SQL programming. This system has features such as an efficient control mechanism, explicit curriculum knowledge representation, and individualized private tutoring. For allowing the students relative freedom to decide how to study the domain knowledge about a subject, the system provides the students with a group of operators to hand-tailor the learning schedules according to their special backgrounds, requests, and interests.

This paper presents an index structure for retrieving electronic documents in digital libraries. The documents considered may contain mistyped words or spelling errors. Given a query string (e.g., a search key), we want to find those documents that approximately contain the query, i.e., certain inserts, deletes and mismatches are allowed when matching the query with a word, (or phrase) in the documents. Our approach is to store the documents sequentially in a database and hash their "fingerprints" into a number of "fingerprint files". When the query is given, its fingerprints are also hashed into the files and a histogram of votes is constructed on the documents. We derive a lower bound, based on which one can prune a large number of nonqualifying documents (i.e., those whose votes are below the lower bound) during searching. The paper presents some experimental results, which demonstrate the effectiveness of the index structure and the lower bound.

Over the past several years we have created or borrowed algorithms for combinatorial pattern matching and pattern discovery on sequences [2] and trees.In matching problems, given a pattern, a set of data objects and a distance metric, we find the distance between the pattern and one or more data objects. In discovery problems by contrast, given a set of objects, a metric, and a distance, we seek a pattern that matches many of those objects within the given distance. (So, discovery is a lot like data mining.) Our toolkit performs both matching and discovery with current targeted applications in molecular biology and document comparison.

Labeled graphs are graphs in which each node and edge has a label. The distance between two labeled graphs is considered to be the weighted sum of the costs of edit operations (insert, delete and relabel the nodes and edges) to transform one graph to the other. The paper considers two variants of the approximate graph matching (AGM) problem: given a pattern graph P and a data graph D, what is the distance between P and D? and what is the minimum distance between P and D when subgraphs can be freely removed from D? We show that no efficient algorithm can solve either variant of the AGM, unless P=NP. We then give a polynomial-time approximation algorithm to solve this problem.

We consider the problem of comparison between labeled graphs. The criterion for comparison is the distance as measured by a weighted sum of the costs of deletion, insertion, and relabel operations on graph nodes and edges. Specifically, we consider two variants of the approximate graph matching problem: Given a pattern graph P and a data graph D, what is the distance between P and D? What is the minimum distance between P and D when subgraphs can be freely removed from D? We first observe that no efficient algorithm con solve either variant of the problem, unless P=NP. Then we present several heuristic algorithms based on probabilistic hill climbing techniques. Finally we evaluate the accuracy and time efficiency of the heuristics by applying them to a set of generated graphs and DNA molecules.>

This paper presents the design of a knowledge-based tutoring system (KBTS) for teaching students to write SQL programs. After analyzing the underlying control mechanism in a tutoring process, we propose a novel architecture to support the process. Our system has many features such as the use of a uniform control flow strategy, the employment of a graph-based scheme to represent global knowledge, and the allowing of multiple teaching sequences and multiple viewpoints for a teaching goal. We argue that these features are essential for not only SQL tutoring systems, but also KBTSs in other domains. Thus, the paper establishes a generic framework for developing the various KBTSs. We also report some implementation considerations for the proposed system.>

Suppose you are given a set of natural entities (e.g., proteins, organisms, weather patterns, etc.) that possess some important common externally observable properties. You also have a structural description of the entities (e.g., sequence, topological, or geometrical data) and a distance metric. Combinatorial pattern discovery is the activity of finding patterns in the structural data that might explain these common properties based on the metric.

Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology, programming compilation, and natural language processing. Many of the applications involve comparing trees or retrieving/extracting information from a repository of trees. Examples include classification of unknown patterns, analysis of newly sequenced RNA structures, semantic taxonomy for dictionary definitions, generation of interpreters for nonprocedural programming languages, and automatic error recovery and correction for programming languages. Previous systems use exact matching (or generalized regular expression matching) for tree comparison. This paper presents a system, called approximate-tree-by-example (ATBE), which allows inexact matching of trees. The ATBE system interacts with the user through a simple but powerful query language; graphical devices are provided to facilitate inputing the queries. The paper describes the architecture of ATBE, illustrates its use and describes some aspects of ATBE implementation. We also discuss the underlying algorithms and provide some sample applications.>

We consider the problem of comparison between unordered trees, i.e., trees for which the order among siblings is unimportant. The criterion for comparison is the distance as measured by a weighted sum of the costs of deletion, insertion and relabel operations on tree nodes. Such comparisons may contribute to pattern recognition efforts in any field (e.g., genetics) where data can naturally be characterized by unordered trees. In companion work, we have shown this problem to be NP-complete. This paper presents an efficient enumerative algorithm and several heuristics leading to approximate solutions. The algorithms are based on probabilistic hill climbing and bipartite matching techniques. The paper evaluates the accuracy and time efficiency of the heuristics by applying them to a set of trees transformed from industrial parts based on a previously proposed morphological model.>

Office information systems (OISs) are employed to support office workers in their management of information and to assist them in their daily work. In the OISs, document classification is one of the major functional capabilities. Classifying a document can be facilitated through the layout analysis of the document. A new approach to the layout analysis, called nested segmentation, is introduced. The layout relationships of components of a document are defined in terms of the adjacency of blocks. Given the adjacency of blocks, an adjacent block graph is introduced where the problem of the nested segmentation is transformed to a classic minimal cut problem for the graph. Also, an ordered labeled tree structure (L-S-Tree) is introduced to represent the segmented document for document classification.>

The authors present the design of a tool for classifying office documents. They represent a document's layout structure using an ordered labeled tree, called the layout structure tree (L-S-tree), based on a nested segmentation procedure. The tool uses a sample-based approach for learning, where concepts are learned by retaining samples and new documents are classified by matching their L-S-trees with samples. The matching process involves both computing the edit distance between two trees using a previously developed pattern matching toolkit, and calculating the degree of conceptual closeness between the documents and samples. The experimental results show that the tool is capable of classifying various types of office documents, even with very few samples in the sample base.

The problem of comparison between unordered trees, i.e. trees for which the order among siblings is unimportant, is considered. The criterion for comparison is the distance as measured by a weighted sum of the costs of deletion, insertion, and relabel operations on tree nodes. Such comparisons may contribute to pattern recognition efforts in any field (e.g. genetics) where data can naturally be characterized by unordered trees. It is observed that the problem is NP-complete. An enumerative algorithm and several heuristics leading to approximate solutions are given. The algorithms are based on probabilistic hill climbing and bipartite matching techniques. The accuracy and time efficiency of the heuristics are evaluated by applying them to a set of trees transformed from industrial parts based on a previously proposed morphological model.>

This paper presents the design of an intelligent document processing system, called TEXPROS. The system is a combination of filing and retrieval systems, which supports storing, extracting, classifying, categorizing, retrieving and browsing information from a variety of documents. TEXPROS is built based on object-oriented programming and rule-based specification techniques. In this paper, we describe main design goals of the system, its data model, logical file structure, and strategies for document classification and categorization. We also illustrate various retrieval methods and query processing techniques through examples. Finally applications of TEXPROS are presented, where we suggest ways in which the use of the system may alter the software process model.

A description is presented of a system, called approximate-tree-by-example (ATBE), which supports AI applications that involve comparing ordered labeled trees or retrieving/extracting information from repositories of such trees. The ATBE system interacts with users through a powerful query language; graphical devices are provided to facilitate inputting the queries. The system is designed to be extensible, customizable, and portable, which makes it a very useful tool for tree pattern matching in various environments. The use of the tool is illustrated. Several examples taken directly from the complete implementation are discussed.>

Consider the class of distributed database systems consisting of a set of nodes connected by a high bandwidth network. Each node consists of a processor, a random access memory, and a slower but much larger memory such as a disk. There is no shared memory among the nodes. The data are horizontally partitioned often using a hash function. Such a description characterizes many parallel or distributed database systems that have recently been proposed, both commercial and academic. We study the optimization problem that arises when the query processor must repartition the relations and intermediate results participating in a multijoin query. Using estimates of the sizes of intermediate relations, we show (1) optimum solutions for closed chain queries; (2) the NP-completeness of the optimization problem for star, tree, and general graph queries; and (3) effective heuristics for these hard cases. Our general approach and many of our results extend to other attribute partitioning schemes, for example, sort-partitioning on attributes, and to partitioned object databases.

A scheme to answer best-match queries from a file containing a collection of objects is described. A best-match query is to find the objects in the file that are closest (according to some (dis)similarity measure) to a given target. Previous work [5, 331] suggests that one can reduce the number of comparisons required to achieve the desired results using the triangle inequality, starting with a data structure for the file that reflects some precomputed intrafile distances. We generalize the technique to allow the optimum use of any given set of precomputed intrafile distances. Some empirical results are presented which illustrate the effectiveness of our scheme, and its performance relative to previous algorithms.