Flight over Bristol

Bristol Algorithms Days 2010
Feasibility Workshop

15 - 16 February 2010

  •    •    •  

Strings, Points, Braids and Genes

Alexander Tiskin

The longest common subsequence (LCS) problem is a classical problem in computer science. The semi-local LCS problem is a generalisation of the LCS problem, arising naturally in the context of string comparison. Apart from playing an important role in string algorithms, this problem turns out to have surprising connections with computational geometry, algebra, graph theory, as well as applications in computational molecular biology. The talk gives a survey of recent results that expose these connections. We conclude that semi-local string comparison is a fascinating problem and a powerful algorithmic technique, which unifies and improves on a number of previous approaches.


  The University of Bristol   EPSRC