Querying biological databases
======================================================================

Biological databases are structurally very simple, often available as 
flat text files, but encode complex information.
Here, I will talk about two problems related to querying of biological 
data. 

In the first case, our database is a graph of interacting proteins, and 
we ask if a pathway (a small graph) in a model species (EX: yeast, 
mouse) is conserved in a different species by looking for isomorphic 
subgraphs in another species (EX: human). We present some algorithms to 
do these queries when the query subgraph has a simple structure (tree, 
or bounded tree-width graph).

In the second case, the database is large string. However, each symbol 
has a mass (a real number) associated with it. We would like to query 
the database for a string s. However, s is unknown, and is given as a 
collection of masses, each of which is the mass of the prefix or suffix 
of s.

Both problems are relevant to modern biology, and we will show this with 
some collaborations across campus.