Skip to main content Skip to navigation

Royal Society Funds Research in Parallel Algorithms and Algorithms on Strings

The Royal Society has awarded a prestigious Leverhulme Trust Senior Research Fellowship to Dr Alexander Tiskin, who is a member of the Algorithms and Computational Complexity Research Group and of the Centre for Discrete Mathematics and its Applications (DIMAP). The project will run for one year starting in October 2009, and will concentrate on two research areas: parallel algorithms, and algorithms on strings.

Parallel algorithms are a fundamental concept in modern computing. The number of processing units in a computer may vary from two to several thousand. Efficient coordination of individual units is a serious challenge, both in theory and in practice. Parallel algorithms have numerous applications in computational science and processing of massive datasets on parallel computers, processor clusters and multicore processors.

Strings (or sequences) of characters are one of the most fundamental data structures. Classical problems on strings include exact pattern matching, string comparison, and approximate pattern matching. String algorithms have numerous applications in different areas of science and technology, from simple text editors to sophisticated data mining and telecommunications. A particularly rich source of applications is computational molecular biology, where the role of strings is played by nucleotide sequences in a DNA molecule.

The Algorithms and Computational Complexity Research Group has contributed to the study of parallel algorithms and algorithms on strings for several decades. The current project, funded by Royal Society, will build on this expertise and on the strengths of Warwick's Centre for Discrete Mathematics and Its Applications (DIMAP). The research by Dr Tiskin will study the communication and synchronisation efficiency of parallel algorithms, and advanced methods of approximate comparison and matching in strings.