Combinatorial Pattern Matching

A space efficient algorithm for finding the best non-overlapping alignment score.- The parameterized complexity of sequence alignment and consensus.- Computing all suboptimal alignments in linear space.- Approximation algorithms for multiple sequence alignment.- A context dependent method for comparing sequences.- Fast identification of approximately matching substrings.- Alignment of trees — An alternative to tree edit.- Parametric recomputing in alignment graphs.- A lossy data compression based on string matching: Preliminary analysis and suboptimal algorithms.- A text compression scheme that allows fast searching directly in the compressed file.- An alphabet-independent optimal parallel search for three dimensional pattern.- Unit route upper bound for string-matching on hypercube.- Computation of squares in a string.- Minimization of sequential transducers.- Shortest common superstrings for strings of random letters.- Maximal common subsequences and minimal common supersequences.- Dictionary-matching on unbounded alphabets: Uniform length dictionaries.- Proximity matching using fixed-queries trees.- Query primitives for tree-structured data.- Multiple matching of parameterized patterns.- Approximate string matching with don't care characters.- Matching with matrix norm minimization.- Approximate string matching and local similarity.- Polynomial-time algorithms for computing characteristic strings.- Recent methods for RNA modeling using stochastic context-free grammars.- Efficient bounds for oriented chromosome inversion distance.