An algorithm SACA-m is proposed to sort all suffixes of a read-only input string of n characters with alphabet size nO(1)in O(n) time and O(n1/2) workspace. It can be applied to sort suffixes of a general alphabet in O(n log n) time and O(n1/2) workspace. This algorithm can be revised to a succinct variant SACA-1 to reuse the space of suffix array for O(1) workspace while keeping O(n) time. The time and space performance of both algorithms are evaluated by experiments on realistic and artificial datasets. These new results give the best time and space complexities for sorting suffixes of big alphabets.

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.

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.

We present a new suffix array construction algorithm that aims to build, in external memory, the suffix array for an input string of length n measured in the magnitude of tens of Giga characters over a constant or integer alphabet. The core of this algorithm is adapted from the framework of the original internal memory SA-DS algorithm that samples fixed-size d-critical substrings. This new external-memory algorithm, called EM-SA-DS, uses novel cache data structures to construct a suffix array in a sequential scanning manner with good data spatial locality: data is read from or written to disk sequentially. On the assumed external-memory model with RAM capacity Ω (( nB ) 0.5 ), disk capacity O ( n ), and size of each I/O block B , all measured in log n -bit words, the I/O complexity of EM-SA-DS is O ( n / B ). This work provides a general cache-based solution that could be further exploited to develop external-memory solutions for other suffix-array-related problems, for example, computing the longest-common-prefix array, using a modern personal computer with a typical memory configuration of 4GB RAM and a single disk.

The Sort Transform (ST) can significantly speed up the block sorting phase of the Burrows-Wheeler Transform (BWT) by sorting the limited order contexts. However, the best result obtained so far for the inverse ST has a time complexity O ( N log k ) and a space complexity O ( N ), where N and k are the text size and the context order of the transform, respectively. In this article, we present a novel algorithm that can compute the inverse ST for any k -order contexts in an O ( N ) time and space complexity, a linear result independent of k . The main idea behind the design of this linear algorithm is a set of cycle properties of k -order contexts that we explore for this work. These newly discovered cycle properties allow us to quickly compute the Longest Common Prefix (LCP) between any pair of adjacent k -order contexts that may belong to two different cycles, which eventually leads to the proposed linear-time solution.

We present, in this paper, two efficient algorithms for linear time suffix array construction. These two algorithms achieve their linear time complexities, using the techniques of divide-and-conquer, and recursion. What distinguish the proposed algorithms from other linear time suffix array construction algorithms (SACAs) are the variable-length leftmost S-type (LMS) substrings and the fixed-length d-critical substrings sampled for problem reduction, and the simple algorithms for sorting these sampled substrings: the induced sorting algorithm for the variable-length LMS substrings and the radix sorting algorithm for the fixed-length d-critical substrings. The very simple sorting mechanisms render our algorithms an elegant design framework, and, in turn, the surprisingly succinct implementations. The fully functional sample implementations of our proposed algorithms require only around 100 lines of C code for each, which is only 1/10 of the implementation of the KA algorithm and comparable to that of the KS algorithm. The experimental results demonstrate that these two newly proposed algorithms yield the best time and space efficiencies among all the existing linear time SACAs.

We present a linear time and space suffix array (SA) construction algorithm called the SA-IS algorithm.The SA-IS algorithm is novel because of the LMS-substrings used for the problem reduction and the pure induced-sorting (specially coined for this algorithm)used to propagate the order of suffixes as well as that of LMS-substrings, which makes the algorithm almost purely relying on induced sorting at both its crucial steps.The pure induced-sorting renders the algorithm an elegant design and in turn a surprisingly compact implementation which consists of less than 100 lines of C code.The experimental results demonstrate that this newly proposed algorithm yields noticeably better time and space efficiencies than all the currently published linear time algorithms for SA construction.

Let S be an n-character string terminated with an unique smallest sentinel, its suffix array SA(S) is an array of pointers for all the suffixes in S sorted in the lexicographically ascending order. Specially, the Burrows-Wheeler transform for building efficient compression solutions can be quickly computed by fast suffix sorting based on suffix array construction algorithms (SACAs). The existing well-known practical linear SACAs are those two contemporarily reported in 2003 by Karkkainen and Sanders (KS) (J. Karkkaiinen and P. Sanders, 2003) and Ko and Aluru (KA) (P. Ko and S. Aluru, 2003).

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.

Summary form given only. The Schindler transform (ST) can speed up the block sorting phase of the Burrows-Wheeler transform (BWT) by limiting the context sorting to the first k (k E [0, N], where N is the length of the text) positions only. Under the ST's partial sorting scheme, if two rows share the exactly same k-order context, they may not be ordered alphabetically; instead, the relative order between them in the original matrix is preserved in the transformed matrix. A major tradeoff for the ST to achieve the speedup gain over the BWT is that the inverse ST appears to be more complicated than the inverse BWT. To deal with the existence of identical k-order contexts, Schindler suggested a hash based approach in which the text retrieval has to rely on the hash table based context lookup, which in turn has to rely on the complete retrieval of all the k-order contexts. An improved solution proposed by Yokoo uses no hash table; however, it still needs to restore all the k-order contexts, which clearly requires O(kN) for both the time and the space complexities. Recently, Nong and Zhang had proposed an auxiliary vector based framework, which is different from any possible k-order context retrieval based approaches formerly suggested by others, but similar to that used for the inverse BWT. This framework relies on two size-N vectors Tkand Ck(details are omitted due to space limit) to correctly retrieve the true immediate preceding character for a given character, which allows the original text to be recovered directly from the transformed text without statically restoring the complete fc-order contexts. As a consequence, this framework requires only O(N) space. However, its running time remains to be O(kN), for it has to visit each column of the fc-order context matrix to obtain Tkand Ck.Since Tkand Ckcan be deduced from the context switch vector D (the data structure indicating whether each pair of two neighbor rows in the context matrix are the same or not) in linear time, the more efficient the D can be calculated, the faster the ST can be inverted. If two k-order contexts are different, either their first halves are different already, or their second halves are different; furthermore, the second half of the k-order context matrix can be deduced from its first half due to the rotating scheme in ST. Based on this observation, we proposed a dynamic programming approach to quickly calculate D by doubling the steps to reach the fcth column in comparing the fc-order contexts. This "doubling technique" based algorithm requires only O(Nlogk) time to calculate D, thus resulting in an O(N log k) time complexity algorithm to invert ST. The space complexity of the algorithm remains to be O(N). This new algorithm can be used to build efficient compression solutions based on the ST.

As an important variant of the Burrows-WheelerTransform (BWT), the Sort Transform (ST) can speed up thetransformation by sorting only a portion of the matrix. However,because the currently known inverse ST algorithms need toretrieve the complete k-order contexts and use hash tables, theyare less efficient than the inverse BWT. In this paper, we proposethree fast and memory-efficient inverse ST algorithms. The firstalgorithm uses two auxiliary vectors to replace the hash tables.The algorithm achieves O(kN) time and space complexities for atext of N characters under the context order k. The second usestwo additional compact "alternate vectors" to further eliminatethe need to restore all the k-order contexts and achieve O(N)space complexity. And the third uses a "doubling technique" tofurther reduce the time complexity to O(N log2 k). The hallmarkof these three algorithms is that they can invert ST in a mannersimilar to inverting BWT in that they all make use of precalculatedauxiliary mapping vectors and require no hash tables.These unifying algorithms can also better explain the connectionbetween the BWT and the ST: their forward components can notonly be performed by the same algorithm framework, but theirrespective inverse components can also be efficiently conductedby the unifying algorithm framework proposed in the presentwork.

Summary form only given. This paper demonstrates how to successfully fit both the Burrows-Wheeler text (BWT) transform method and the Schindler transform (ST) method into a unified algorithm framework and how this can be used to reveal a strong connection between the ST and the BWT as well as that between the inverse ST and the inverse BWT

We present in this paper an efficient medium access control (MAC) protocol called iCSMA/CD for improving the efficiencies of optical wavelength division multiplexing (WDM) networks. The key idea behind the design of iCSMA/CD is similar to the well-known carrier sense multiple access with collision detection (CSMA/CD) MAC protocol for the Ethernet, in the sense that both use the CD technique to resolve contentions for the carrier. However, our proposed protocol is unique in that it exploits some look-ahead method for achieving better delay-throughput performance. Simulation experiments are conducted to evaluate the delay-throughput performance of a WDM ring network controlled by the proposed iCSMA/CD protocol and the results demonstrate the impressive advantages of iCSMA/CD

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.

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'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.