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.

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.

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.

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