Combinatorial pattern matching

This work covers a range of advanced algorithms and techniques relevant to computational biology and string processing. It revisits chaining algorithms for multiple genome alignment and explores two-dimensional pattern matching, including rotations. The text presents an improved algorithm for comparing minisatellites and discusses optimal spaced seeds for hidden Markov models, particularly in homologous coding regions. It details fast and lightweight methods for constructing and checking suffix arrays, as well as distributed and paged suffix trees for handling large genetic databases. The analysis includes tree edit distance algorithms and a polynomial distance-based method for reconstructing single copy tandem duplication trees. It also addresses average-optimal multiple approximate string matching and introduces a new class of Burrows-Wheeler compression algorithms. Additionally, the work covers haplotype inference by pure parsimony and presents a simpler approximation algorithm for sorting by transpositions. Other topics include efficient data structures for sorting signed permutations, linear-time construction of suffix arrays, and tuning string matching for large pattern sets. The text examines sparse LCS common substring alignment and the alignment of multiple alignments. It also provides an effective algorithm for peptide de novo sequencing from MS/MS spectra and discusses pattern discovery in RNA secondary structures