Ask Not What Stringology Can Do for You: Advances in Pattern Matching Driven by Computational Biology

Molecular biology has posed a number of fascinating and sometimes daunting computational problems, which came naturally expressed in its native language of character strings. Through the years, some such problems have found elegant and even useful solutions in response to the needs that originally motivated them. What is perhaps even more remarkable, several of the ideas inspired by computational molecular biology have found application in remote and diverse domains, so that it may be argued that molecular biology did more for computing than the latter did for it. As a modest tribute, this paper reviews a small sample of these cases drawing from the personal exposure of the author.

Keywords

Computational biology, design and analysis of algorithms, pattern matching, pattern discovery, motif, sequence alignment, waka, freakanomics, data analysis, data compression

Full Text (PDF format)

Published 1 January 2009