A growing number of measures of sequence similarity is being based on some underlying notion of relative compressibility. Within this paradigm, similar sequences are expected to share a large number of common substrings, or subsequences, or more complex patterns or motifs, and so on. The computational complexity of such measures varies, and it increases with the complexion of the patterns taken into account. At the low end of the spectrum, most measures based on the bags of shared substrings are typically afforded in linear time. This performance is no longer achievable as soon as some degree of distortion is accepted. In this paper, measures of sequence similarity are introduced and studied in which patterns in a pair are considered similar if they coincide up to a preset number of mismatches, that is, within a bounded Hamming distance. It is shown here that for some such measures bounds are achievable that are slightly better than O(n2). Preliminary experiments demonstrate the potential applicability to phylogeny and classification of similarity measures that are rougher than previously adopted ones.

Approaches to image compression and indexing based on extensions to 2D of some of the Lempel-Ziv incremental parsing techniques have been proposed in the recent past. In these approaches, an image is decomposed into a number of patches, consisting each of a square or rectangular solid block. This paper proposes image compression techniques based on patches that are not necessarily solid blocks, but are affected instead by a controlled number of undetermined or don't care pixels. Such patches are chosen from a set of candidate motifs that are extracted in turn from the image 2D motif basis, the latter consisting of a compact set of patterns that result from the autocorrelation of the image with itself. As is expected, it is found that limited indeterminacy can be traded for higher compression at the expense of negligible loss. Preliminary experiments show that this technique yields higher compression than other popular techniques such as GZIP, BZIP and JPEG.

Measures of sequence similarity based on some underlying notion of relative compressibility are becoming increasingly of interest in connection with massive tasks of textfile classification such as, notably, in document classification and molecular taxonomy on a genomic scale. Sequences that are similar can be expected to share a large number of common substrings, whence some successful measures in this class have been based on the substring composition of the input sequences. Among the corresponding methods, one finds suitable extensions of the bag-of-words together with more explicit resorts to data compression techniques such as LZ77. The approach presented in this paper explores the potential of LZW - the variant of LZ78 proposed by Welch -- as well as of some of its lossy variants, in this context. Whereas LZW has a faster and simpler implementation than LZ77, the vocabulary underlying LZW is significantly smaller than that of LZ77. In addition, recently introduced "gapped" variants of LZW are considered that are equally straightforward to implement but allow for a controlled number of don't cares to be introduced in the substrings that constitute the dictionary used in compression. This study assesses the robustness of compressibility based measures of similarity under these faster yet inherently more dispersive paradigms built around LZW.

The discovery of motifs in biosequences is frequently torn between the rigidity of the model on one hand and the abundance of candidates on the other hand. In particular, motifs that include wild cards or "don't cares" escalate exponentially with their number, and this gets only worse if a don't care is allowed to stretch up to some prescribed maximum length. In this paper, a notion of extensible motif in a sequence is introduced and studied, which tightly combines the structure of the motif pattern, as described by its syntactic specification, with the statistical measure of its occurrence count. It is shown that a combination of appropriate saturation conditions and the monotonicity of probabilistic scores over regions of constant frequency afford us significant parsimony in the generation and testing of candidate overrepresented motifs. A suite of software programs called Varun is described, implementing the discovery of extensible motifs of the type considered. The merits of the method are then documented by results obtained in a variety of experiments primarily targeting protein sequence families. Of equal importance seems the fact that the sets of all surprising motifs returned in each experiment are extracted faster and come in much more manageable sizes than would be obtained in the absence of saturation constraints.

The quantitative underpinning of the information contents of biosequences represents an elusive goal and yet also an obvious prerequisite to the quantitative modeling and study of biological function and evolution. Previous studies have consistently exposed a tenacious lack of compressibility on behalf of biosequences. This leaves the question open as to what distinguishes them from random strings, the latter being clearly unpalatable to the living cell. This paper assesses the randomness of biosequences in terms on newly introduced parameters that relate to the vocabulary of their (suitably constrained) subsequences rather than their substrings. Results from experiments show the potential of the method in distinguishing a protein sequence from its random reshuffling, as well as in tasks of classification and clustering.

Saturated patterns with don't care like those emerged in biosequence motif discovery have proven a valuable notion also in the design of lossless and lossy compression of sequence data. In independent endeavors, the peculiarities inherent to the compression of tables have been examined, leading to compression schemata advantageously hinged on a prudent rearrangement of columns. The present paper introduces off-line table compression by textual substitution in which the patterns used in compression are chosen among models or templates that capture recurrent record subfields. A model record is to be interpreted here as a sequence of intermixed solid and don't care characters that obeys, in addition, some conditions of saturation: most notably, it must be not possible to replace a don't care in the model by a solid character without having to forfeit some of its occurrences in the table. Saturation is expected to save on the size of the codebook at the outset, and hence to improve compression. It also induces some clustering of the records in the table, which may present independent interest. Results from preliminary experiments show the savings and potential for classification brought about by this method in connection with a table of specimens collected in a context of biodiversity studies.

The increasing throughput of sequencing raises growing needs for methods of sequence analysis and comparison on a genomic scale, notably, in connection with phylogenetic tree reconstruction. Such needs are hardly fulfilled by the more traditional measures of sequence similarity and distance, like string edit and gene rearrangement, due to a mixture of epistemological and computational problems. Alternative measures, based on the subword composition of sequences, have emerged in recent years and proved to be both fast and effective in a variety of tested cases. The common denominator of such measures is an underlying information theoretic notion of relative compressibility. Their viability depends critically on computational cost. The present paper describes as a paradigm the extension and efficient implementation of one of the methods in this class. The method is based on the comparison of the frequencies of all subwords in the two input sequences, where frequencies are suitably adjusted to take into account the statistical background.

The synergies among biology, computing and other formal disciplines continue to produce a unique blend of domain-specific and methodological advances that is shaping the very fabrics of the new scientific method. Among the many examples of this phenomenon, the one offered by the unrelenting growth of bioinformatics and computational biology is unique in that nowhere else is the native lexicon of a natural science more directly conducive to digital representation and manipulation. The research articles contained in this Supplement originate from posters presented at the Tenth Annual International Conference on Research in Computational Molecular Biology (RECOMB 2006), which was held in Venice, Italy, on April 2–5, 2006. The RECOMB conference series was started in 1997 by Sorin Istrail, Pavel Pevzner and Michael Waterman. The previous meetings were held in Santa Fe, NM (USA); New York, NY (USA); Lyon, France; Tokyo, Japan; Montreal, Canada; Washington, DC (USA); Berlin, Germany; San Diego, CA (USA); and Boston, MA (USA). RECOMB 2006 was hosted by University of Padova in the Venice Convention Center at Cinema Palace, Venice Lido, Italy. The Tenth Edition of RECOMB was special in several ways. For one, the Program Committee, consisting of 38 specialists of the highest distinction in the field, included all past Committee and Conference Chairs as well as the Members of the Steering Committee. The Committee selected 40 papers out of the received submissions of well over 200. Some of the accepted papers were further expanded and refereed in order to appear in the special issue traditionally devoted to the Conference. For the Tenth Edition, however, in view of the high quality of the contributions submitted for poster presentation, it was felt that another Special Issue, devoted to expanded and duly refereed versions of poster submissions was also warranted. Thus, the present Supplement constitutes one more innovation brought about by the Tenth Anniversary of RECOMB. The eight enclosed papers emerged at the outset of a rigid selection and review and represent a vivid snapshot of work mature enough to be reported within vibrant frameworks still in the making. We hope that they will start one more tradition for RECOMB. This Issue was made possible thanks to the effort of many, in particular, the special task force set up for handling posters, which consisted of Luca Bortolussi (University of Udine, Italy), Giovanni Ciriello (University of Padova, Italy), Matteo Comin (University of Padova, Italy), Claudio Garrutti (University of Padova, Italy), Giosue Lo Bosco (University of Palermo, Italy), Sabrina Mantaci (University of Palermo, Italy) Cinzia Pizzi (University of Padova, Italy, and Helsinki, Finland), Simone Scalabrin (University of Udine, Italy), and Nicola Vitacolonna (University of Udine, Italy). We are also grateful to the external reviewers, the members of the Steering Committee and other colleagues who helped in the process. Finally, we express our thanks to the institutions and corporations who provided financial support for the conference: Broad Institute of MIT and Harvard, USA; College of Computing, Georgia Tech., USA; Department of Energy, USA; Department of Information Engineering, University of Padova, Italy; IBM Corporation, USA; ISMB, International Society for Computational Biology; AICA, Italian Association for Informatics and Automatic Computation; National Science Foundation, USA; University of Padova, Italy.

Summary form only given. In this paper, various lossless and lossy adaptations and extensions of that paradigm are developed and tested, for the most part susceptible to simple linear time implementation. This is in contrast to the existing lossy variants of the Ziv-Lempel family of encoders, which have been traditionally built around the iterated quest for the best match within an assigned fidelity, thereby resulting in algorithms that are inherently superlinear and not easy to implement and analyze. Whereas a thorough analytical treatment of the proposed method seems hard, the basic algorithm and its main variants show good performance and latitude of practical applicability.

Lossy variants of the Ziv-Lempel family of encoders are built traditionally around the iterated quest for best matches within an assigned fidelity. Most of the resulting algorithms are inherently superlinear and not easy to implement and analyze. On the other hand, it is well known that any lossy scheme of low computational complexity must have the drawback that it cannot yield the minimal distortion which can be achieved by the optimal data compression algorithm specifically tailored for that case. This paper concentrates on parses of guaranteed low time performance, in which phrases are all distinct and generated mechanically by self-correlations of the source set forth by the parsing process. The goal of the paper is to describe the basic algorithm and some of its variants, show their good performance and latitude of practical applicability, and possibly stimulate in-depth analytical treatment, which is made particularly hard by the fact that the underlying processes are not stationary.

We consider gapped variants of classical data compression paradigms (Ziv, J. and Lempel, A.,1977, 1978; Welch, T.A., 1984). In the original algorithm, phrases are identified and stored in a dictionary on-the-fly as the text-file is scanned. The entries in the dictionary are then matched against the incoming string, thereby determining the next codeword, and this gives the method an inherently linear-time implementation. In our variants, the phrases used in compression are selected among suitably chosen strings of intermittently solid and wild characters produced by the autocorrelation of the source-string, in a way that still preserves linearity of time. At the receiver, gaps can be filled back exactly, interpolated, or left blank, so that lossless, as well as lossy, implementations are possible. However, the focus of the paper is on lossy variants.

Summary form only given. We present lossy off-line data compression techniques by textual substitution in which the patterns used in compression are chosen among the extensible motifs that are found to recur in the textstring with a minimum pre-specified frequency. A motif is to be interpreted here as a sequence of intermixed solid and don't care characters that obeys, in addition, some conditions of saturations: most notably, it must be not possible to eliminate some don't cares in the pattern without having to forfeit some of its occurrences. Motif discovery and motif-driven parses of various kinds have been previously introduced and used in Apostolico et al. (2004) and Apostolico et al. (2003). Whereas the motifs considered in those studies are "rigid", here we assume that each sequence of gaps present in a motif comes endowed with some individually prescribed degree of elasticity, whereby a same pattern may be stretched to fit segments of the source that match at all the solid characters but are otherwise of different lengths. This is expected to save on the size of the codebook, and hence to improve compression.

We present variants of classical data compression paradigms by Ziv, Lempel, and Welch in which the phrases used in compression are selected among suitably chosen motifs, defined here as strings of intermittently solid and wild characters that recur more or less frequently in the source textstring. This notion emerged primarily in the analysis of biological sequences and molecules. Whereas the number of motifs in a sequence or family may be exponential in the size of the input, a linear-sized basis of irredundant motifs may be defined such that any other motif can be obtained by the union of a suitable subset from the basis. Previous study has exposed the advantages of using irredundant motifs in lossy as well as lossless offline compression. In the present paper, we examine adaptations and extensions of classical incremental ZL and ZLW paradigms. First, hybrid schemata are proposed along these lines, in which motifs may be discovered and selected off-line, while the parse and encoding is still conducted on-line. The performances thus obtained improve on the one hand over previous off-line implementations of motif-based compression, and on the other, over the traditionally best implementations of ZLW. On the basis of this, both lossy and lossless motif-based schemata are introduced and tested that follow more closely the ZL and ZLW paradigms.

Data compression techniques hinged on the notion of a motif are presented, interpreted here as a string of intermittently solid and wild characters that recurs more or less frequently in an input sequence or family of sequences. Correspondingly, motif discovery techniques and tools have been devised. This task is made difficult by the circumstance that the number of motifs identifiable in general in a sequence can be exponential in the size of that sequence. A significant gain in the direction of reducing the number of motifs is achieved through the introduction of irredundant motifs, which in intuitive terms are a combination of other motif occurrences. The number of abundant motifs in a sequence is at worst linear in the sequence. It is shown that irredundant motifs can be usefully exploited in lossy compression methods based on textual substitution and suitable for signals as well as text. Preliminary experiments with these fungible strategies at the crossroads of lossless and lossy data compression show performances that improve over popular methods by more than 20% in lossy and 10% in lossless implementations.

The problem of characterizing and detecting recurrent sequence patterns such as substrings or motifs and related associations or rules is variously pursued in order to compress data, unveil structure, infer succinct descriptions, extract and classify features, etc. In Molecular Biology, exceptionally frequent or rare words in bio-sequences have been implicated in various facets of biological function and structure. The discovery, particularly on a massive scale, of such patterns poses interesting methodological and algorithmic problems, and often exposes scenarios in which tables and synopses grow faster and bigger than the raw sequences they are meant to encapsulate. In previous study, the ability to succinctly compute, store, and display unusual substrings has been linked to a subtle interplay between the combinatorics of the subwords of a word and local monotonicities of some scores used to measure the departure from expectation. In this paper, we carry out an extensive analysis of such monotonicities for a broader variety of scores. This supports the construction of data structures and algorithms capable of performing global detection of unusual substrings in time and space linear in the subject sequences, under various probabilistic models.

In a passage by J.L. Borges on the "exactitude of Science," a fictitious author describes an Empire in which the art of Cartography "logro tal perfeccion que el mapa de una sola Provincia ocupaba toda la Ciudad, y el mapa del Imperio toda una Provincia." With time, these huge maps wouldn't be enough, and the Colleges of the Cartographers erected a map of the Empire that equalled in width the Empire itself... This paper concerns itself with increasing cases of pattern discovery and data mining in which synopses, indices and relationships thereof seem to grow faster and bigger than the phenomena they were meant to encapsulate. The paper then reviews specific examples of algorithmic and combinatorial constructs that proved capable of alleviating such paradoxes in the author's recent work experience.

We follow one of the simplest possible steepest descent paradigms. This consists of performing repeated stages in each one of which we identify a substring of the current version of the text yielding the maximum compression, and then replace all those occurrences except one with a pair of pointers to the untouched occurrence. This is somewhat dual with respect to the bottom up vocabulary buildup scheme considered by Rubin. This simple scheme already poses some interesting algorithmic problems. In terms of performance, the method does outperform current Lempel-Ziv implementations in most of cases. Here we show that, on biological sequences, it beats all other generic compression methods and approaches the performance of methods specifically built around some peculiar regularities of DNA sequences, such as tandem repeats and palindromes, that are neither distinguished nor treated selectively here. The most interesting performances, however, are obtained in the compression of entire groups of genetic sequences forming families with similar characteristics. This is becoming a standard and useful way to group sequences in a growing number of important specialized databases. On such inputs, the approach presented here yields scores that are not only better than those of any other method, but also improve increasingly with increasing input size. This is to be attributed to a certain ability to capture distant relationships among the sequences in a family.

Statistical modeling of sequences is a central paradigm of machine learning that finds multiple uses in computational molecular biology and many other domains. The probabilistic automata typically built in these contexts are subtended by uniform, fixed-memory Markov models. In practice, such automata tend to be unnecessarily bulky and computationally imposing both during their synthesis and use. In [8], much more compact, tree-shaped variants of probabilistic automata are built which assume an underlying Markov process of variable memory length. In [3, 4], these variants, called Probabilistic Suffix Trees (PSTs) were successfully applied to learning and prediction of protein families. The process of learning the automaton from a given training set S of sequences requires &THgr; (Ln2) worst-case time, where n is the total length of the sequences in S and L is the length of a longest substring of S to be considered for a candidate state in the automaton. Once the automaton is built, predicting the likelihood of a query sequence of m characters may cost time &THgr; (m2) in the worst case. The main contribution of this paper is to introduce automata equivalent to PSTs but having the following properties: learning the automaton takes O (n) time. prediction of a string of m symbols by the automaton takes O (m) time. Along the way, the paper presents an evolving learning sheme, and addresses notions of empirical probability and related efficient computation,possibly a by-product of more general interest.

Greedy off-line textual substitution refers to the following approach to compression or structural inference. Given a long text string x, a substring W is identified such that replacing all instances of W in X except one by a suitable pair of pointers yields the highest possible contraction of X; the process is then repeated on the contracted text string until substrings capable of producing contractions can no longer be found. This paper examines computational issues arising in the implementation of this paradigm and describes some applications and experiments.

The identification of strings that are, by some measure, redundant or rare in the context of larger sequences is an implicit goal of any data compression method. In the straightforward approach to searching for unusual substrings, the words (up to a certain length) are enumerated more or less exhaustively and individually checked in terms of observed and expected frequencies, variances, and scores of discrepancy and significance thereof. As is well known, clever methods are available to compute and organize the counts of occurrences of all substrings of a given string. The corresponding tables take up the tree-like structure of a special kind of digital search index or trie. We show here that under several accepted measures of deviation from expected frequency, the candidate over- or under-represented words are restricted to the O(n) words that end at internal nodes of a compact suffix tree, as opposed to the /spl Theta/(n/sup 2/) possible substrings. This surprising fact is a consequence of properties in the form that if a word that ends in the middle of an arc is, say, over-represented, then its extension to the nearest node of the tree is even more so. Based on this, we design global linear detectors of favoured and unfavored words for our probabilistic framework, and display the results of some preliminary that apply our constructions to the analysis of genomic sequences.

Greedy off-line textual substitution refers to the following steepest descent approach to compression or structural inference. Given a long text string x, a substring w is identified such that replacing all instances of w in x except one by a suitable pair of pointers yields the highest possible contraction of x; the process is then repeated on the contracted text string, until substrings capable of producing contractions can no longer be found. This paper examines the computational issues and performance resulting from implementations of this paradigm in preliminary applications and experiments. Apart from intrinsic interest, these methods may find use in the compression of massively disseminated data, and lend themselves to efficient parallel implementation, perhaps on dedicated architectures.

An optimal $O(\log \log n)$-time concurrent-read concurrent-write parallel algorithm for detecting all squares in a string is presented. A tight lower bound shows that over general alphabets, this is the fastest possible optimal algorithm. When p processors are available, the bounds become $\Theta \lceil {({{n\log n)} p}\rceil + \log \log _{\lceil {1 + {p / n}} \rceil } 2p} )$. The algorithm uses an optimal parallel string-matching algorithm together with periodicity properties to locate the squares within the input string.

Describes our experience with a newly-established international partnership between the Software Engineering Research Center (SERC), a university-based National Science Foundation (NSF) sponsored industrial research organization in the United States and an Italian industry-university team based in Padua, Italy.>

This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string: 1. An O(log n) time, n-processor algorithm over general alphabets. In the case of constant size alphabets the algorithm requires only nlog n processors, and thus achieves an optimalspeedup. 2. An O(log log n) time, n log nloglog n-processor algorithm over general alphabets. This is the fastest possible time with the number of processors used. These new results improve on the known parallel palindrome detection algorithms by using smaller auxiliary space and either by making fewer operations or by achieving a faster running time.

An extension of the disjoint set union problem is considered, where the extra primitive backtrack $(i)$ can undo the last i unions not yet undone. Let n be the total number of elements in all the sets. A data structure is presented that supports each union and find in $O({{\log n} / {\log \log n}})$ worst-case time and each backtrack$(i)$ in $O(1)$ worst-case time, irrespective of i. The total space required by the data structure is $O(n)$. A byproduct of this construction is a partially persistent data structure for the standard set union problem, capable of supporting union, find, and find-in-the-past operations, each in $O({{\log n} / {\log \log n}})$ worst-case time. All these upper bounds are tight for the class of separable-pointer algorithms as well as in the cell probe model of computation.

The string editing problem for input strings x and y consists of transforming x into y by performing a series of weighted edit operations on x of overall minimum cost. An edit operation on x can be the deletion of a symbol from x, the insertion of a symbol in x or the substitution of a symbol of x with another symbol. This problem has a well-known $O(|x||y|)$ time-sequential solution. Efficient PRAM parallel algorithms for the string editing problem are given. If $m = \min (|x|,|y|)$ and $n = \max (|x|,|y|)$, then the CREW bound is $O(\log m \log n)$ time with $O({{mn} / {\log m}})$ processors. The CROW bound is $O(\log n(\log \log m)^{2})$ time with $O(mn/ \log \log m)$ processors. In all algorithms, space is $O(mn)$.

Families of Fibonacci codes and Fibonacci representations are defined. Their main attributes are robustness, manifesting itself by the local containment of errors; and simple encoding and decoding. The main application explored is the transmission of binary strings in which the length is in an unknown range, using robust Fibonacci representations instead of the conventional error-sensitive logarithmic ramp representation. Though the former is asymptotically longer than the latter, the former is actually shorter for very large initial segments of integers.

Based on the Boyer–Moore–Galil approach, a new algorithm is proposed which requires a number of character comparisons bounded by 2n, regardless of the number of occurrences of the pattern in the textstring. Preprocessing is only slightly more involved and still requires a time linear in the pattern size.

One-and two-dimensional pattern matching oriented systolic array processors are presented that support, respectively, the detection of all repetitions in a string x and the statistics of all substrings of x with and without overlap. The time is linear in the length of x in both applications, whereas the number of processors is linear and quadratic, respectively.