Combinatorial Pattern Matching

An improved pattern matching algorithm for strings in terms of straight-line programs.- Episode matching.- Efficient algorithms for approximate string matching with swaps.- On the complexity of pattern matching for highly compressed two-dimensional texts.- Estimating the probability of approximate matches.- Space- and time-efficient decoding with canonical huffman trees.- On weak circular squares in binary words.- An easy case of sorting by reversals.- External inverse pattern matching.- Distributed generation of suffix arrays.- Direct construction of compact directed acyclic word graphs.- Approximation algorithms for the fixed-topology phylogenetic number problem.- A new algorithm for the ordered tree inclusion problem.- On incremental computation of transitive closure and greedy alignment.- Aligning coding DNA in the presence of frame-shift errors.- A filter method for the weighted local similarity search problem.- Trie-based data structures for sequence assembly.- Flexible identification of structural objects in nucleic acid sequences: Palindromes, mirror repeats, pseudoknots and triple helices.- Banishing bias from consensus sequences.- On the Nadeau-Taylor theory of conserved chromosome segments.- Iterative versus simultaneous multiple sequence alignment.- Modern comparative lexicostatistics.