Discovering Frequent Subtrees from XML Data Using Neural Networks

By rapid progress of network and storage technologies, a huge amount of electronic data such as Web pages and XML has been available on Internet. In this paper, we study a data-mining problem of discovering frequent ordered sub-trees in a large collection of XML data, where both of the patterns and the data are modeled by labeled ordered trees. We present an efficient algorithm of Ordered Subtree Miner （OSTMiner） based on two- layer neural networks with Hebb rule, that computes all ordered sub-trees appearing in a collection of XML trees with frequent above a user-specified threshold using a special structure EM-tree. In this algo- rithm, EM-tree is used as an extended merging tree to supply scheme information for efficient pruning and mining frequent sub-trees. Experiments results showed that OSTMiner has good response time and scales well.

Mining Compressed Frequent Subtrees Set

The number of frequent subtrees usually grows exponentially with the tree size because of combinatorial explosion. As a result, there are too many frequent subtrees for users to manage and use. To solve this problem, we generalize a compressed frame based on δ-cluster to the problem of compressing frequent-subtree sets, and propose an algorithm RPTlocal which can mine compressed frequent subtrees set directly. This algorithm sacrifices the theoretical bounds but still has good compression quality. By pruning the search space and generating frequent subtrees directly, this algorithm is also efficient. Experiment result shows that the representative subtrees mining by RPTlocal is almost two orders of magnitude less than the whole collection of the closed subtrees, and is more efficient than CMtreeMiner, the algorithm for mining both closed and Maximal frequent subtrees.

Historical relationships of the Mesoamerican highlands,with emphasis on tropical montane cloud forests:a temporal cladistic biogeographical analysis

The historical relationships of nine areas of endemism of the tropical montane cloud forests(TMCFs)were analysed based on a temporal cladistic biogeographical approach.Three cladistic biogeographical analyses were conducted based on 29cladograms of terrestrial taxa by partitioning them into three time-slices,namely,Miocene,Pliocene,and Pleistocene.The results showed different area relationships over time.For the Miocene and Pliocene time slices,the Isthmus of Tehuantepec acted as a geographic barrier that fragmented the TMCFs into two portions:west of the Isthmus and east of the Isthmus.In the case of the Pleistocene,the TMCFs were broken into two portions,one related to the Neotropical region and the other to the Nearctic region.Furthermore,the analyses allowed us to detect the influences of different geological and paleoclimatological events on the distribution of the TMCFs over time.Therefore,the TMCFs current distribution might have been driven by geological events during the Miocene-Pliocene,whereas climatic fluctuations have the highest impact during the Pleistocene.

Mining condensed frequent subtree base

In frequent tree pattern mining, the number of frequent subtrees generated is often too large. To tackle this problem, the concept of condensed frequent subtree base is proposed. The base consists of the maximal frequent subtrees for a series of support thresholds. It is a subset of frequent subtrees, and is used to approximate the support of arbitrary frequent subtrees with guaranteed maximal error bound. In addition, an algorithm is developed to mine such a condensed subtree base in a database of labeled rooted ordered trees. The algorithm adopts the way of fight-most extension to generate systematically all frequent rooted ordered subtrees. Several techniques are proposed to prune the branches that do not correspond to the maximal frequent subtrees. Heuristic techniques are used to arrange the order of computation so that relatively expensive computation is avoided as much as possible. Experimental results show that the size of the base is less than 10% of that of the complete set, and the algorithm outperforms the previous algorithms.

Subtree, TASS and an Analysis of the Genus Caragana

Subtree analysis and three area satements (TASS) procedure are used to deal with the area relationship in historical biogeography. On the basis of the taxon cladogram, the procedure could identify and eliminate the paralogy node and determine the informative subtree. The area relationships are generally illustrated in several subtrees and the consensus tree. The distribution pattern of the genus Caragana comprising about 72 species and occurring in 13 areas, was analyzed by using subtree method and TASS procedure in this study. The results showed seven subtrees representing the area relationships of section and series of the genus, and the consensus tree provided the 13 area relationships. These results are congruent with our former result using component analysis for Caragana.

Burning Numbers of Barbells

Motivated by a discrete-time process intended to measure the speed of the spread of contagion in a graph,the burning number b(G)of a graph G,is defined as the smallest integer k for which there are vertices x1,…xk such that for every vertex u of G,there exists i∈{1,…k}with dG(u,xi)≤k−i,and dG(xi,xj)≥j−i for any 1≤i<j≤k.The graph burning problem has been shown to be NP-complete even for some acyclic graphs with maximum degree three.In this paper,we determine the burning numbers of all short barbells and long barbells,respectively.

Structure Polynomials and Subgraphs of Rooted Regular Trees

We introduce an algebraic structure allowing us to describe subgraphs of a regular rooted tree. Its elements are called structure polynomials, and they are in a one- to-one correspondence with the set of all subgraphs of the tree. We define two operations, the sum and the product of structure polynomials, giving a graph interpretation of them. Then we introduce an equivalence relation between polynomials, using the action of the full automorphism group of the tree, and we count equivalence classes of subgraphs modulo this equivalence. We also prove that this action gives rise to symmetric Gelfand pairs. Finally, when the regularity degree of the tree is a prime p, we regard each level of the tree as a finite dimensional vector space over the finite field Fp, and we are able to completely characterize structure polynomials corresponding to subgraphs whose leaf set is a vector subspace.

MTMO： an efficient network-centric algorithm for subtree counting and enumeration

Background： The frequency of small subtrees in biological, social, and other types of networks could shed light into the structure, function, and evolution of such networks. However, counting all possible subtrees of a prescribed size can be computationally expensive because of their potentially large number even in small, sparse networks. Moreover, most of the existing algorithms for subtree counting belong to the subtree-centric approaches, which search for a specific single subtree type at a time, potentially taking more time by searching again on the same network. Methods： In this paper, we propose a network-centric algorithm （MTMO） to efficiently count k-size subtrees. Our algorithm is based on the enumeration of all connected sets of k-1 edges, incorporates a labeled rooted tree data structure in the enumeration process to reduce the number of isomorphism tests required, and uses an array-based indexing scheme to simplify the subtree counting method. Results： The experiments on three representative undirected complex networks show that our algorithm is roughly an order of magnitude faster than existing subtree-centric approaches and base network-centric algorithm which does not use rooted tree, allowing for counting larger subtrees in larger networks than previously possible. We also show major differences between unicellular and multicellular organisms. In addition, our algorithm is applied to find network motifs based on pattern growth approach. Conclusions： A network-centric algorithm which allows for a This enables us to count larger motif in larger networks than faster counting of non-induced subtrees is proposed previously.

Distances Between Phylogenetic Trees: A Survey

Phylogenetic trees have been widely used in the study of evolutionary biology for representing the tree-like evolution of a collection of species. However, different data sets and different methods often lead to the construction of different phylogenetic trees for the same set of species. Therefore, comparing these trees to determine similarities or, equivalently, dissimilarities, becomes the fundamental issue. Typically, Tree Bisection and Reconnection（TBR）and Subtree Prune and Regraft（SPR） distances have been proposed to facilitate the comparison between different phylogenetic trees. In this paper, we give a survey on the aspects of computational complexity, fixed-parameter algorithms, and approximation algorithms for computing the TBR and SPR distances of phylogenetic trees.