String Algorithmics

Costas S. Iliopoulos and Thierry Lecroq, editors

King's College London Publications, 2004.

String Algorithmics


In recent years there has been an unprecedented need for algorithms on strings. This is due to the increasing need for fast and innovative algorithms that can help researchers from other scientific areas conduct research more efficiently. Computational biology, computerized music analysis and web searching are some of the research areas that constantly provide new problems on strings or require more efficient algorithms for known problems. In addition, many theoretical problems from Computer Science are closely related to well-known problems on strings. This volume aims to provide some new methods and solutions for a subset of all these problems.

The organization of the book allows the reader to either obtain a broad overview or detailed knowledge of some of the main topics in string algorithmics. Each chapter of the book has been written by leading researchers in this field. In a nutshell, the topics covered in this book are the following:

  • String Algorithms for Music Analysis
  • Algorithmic toolkits for Sequence Alignment
  • Search and extraction of regularities such as tandem repeats, motifs, etc
  • The relationship between strings and the four colour problem as well as the maximum common embedded subtree problem for ordered subtrees
  • Applications of string techniques to data compression

Table of contents

Editorial Preface
Costas Iliopoulos and Thierry Lecroq

String Matching Techniques for Music Analysis
Raphaël Clifford, Tim Crawford, Costas Iliopoulos and Dave Meredith

Re-Use Dynamic Programming for Sequence Alignment: An Algorithmic Toolkit
Maxime Crochemore, Gad M. Landau, Baruch Schieber and Michal Ziv-Ukelson

Stringology and the Four Colour Problem of Planar Maps
Alan Gibbons and Paul Sant

Evolutive Tandem Repeats: A Survey
Richard Groult, Martine Léonard and Laurent Mouchard

Computing the Regularities in Biological Weighted Sequences
Costas Iliopoulos, Katerina Perdikuri and Hui Zhang

Different Applications of the Factor Oracle: An Overview
Thierry Lecroq and Arnaud Lefebvre

On the Maximum Common Embedded Subtree Problem for Ordered Trees
Antoni Lozano and Gabriel Valente

New Upper Bounds on Various String Manipulation Problems
Christos Makris, Yannis Panagis, Katerina Perdikuri, Spyros Sioutas, Evangelos Theodoridis, Athanasios Tsakalidis, Kostas Tsichlas and Raffaella Campaner

A Comparative Study of Bases for Motif Inference
Nadia Pisanti, Maxime Crochemore, Roberto Grossi and Marie-France Sagot

Generalized and Weighted Strings: Repetitions and Pattern Matching
Michal Vorácek, Borivoj Melichar and Manolis Christodoulakis

Thierry Lecroq Home Page
Thierry Lecroq Home Page
Thierry Lecroq