On molecules, strings, and coins: Some applications of string combinatorics in computational biology.

In this talk, I will discuss two problems from computational biology: (1) EST (expressed sequence tag) clustering and (2) identification of biomolecular samples from MS (mass spectrometry) data. The two problems above motivate string algorithmic and combinatoric problems such as the correct choice of string distance measure, the Money Changing Problem from number theory, and jumbled pattern matching, a type of non-standard string matching. In each case, I will briefly explain the biological problem setup, its mathematical counterpart, algorithmic solution or solutions, and, where applicable, implementations. 

 

In recent years, many new string problems have been introduced which are motivated by applications from molecular biology, but which are also of independent interest. In turn, string algorithms have often been applied successfully to molecular biology problems. Starting from the problems outlined above, the talk is designed to demonstrate this fruitful connection.

 

The talk should be accessible, at least in parts, both to computer scientists and to biologists.