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.

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.

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.