Graph algorithms for biological systems analysis
The post-genomic era has witnessed an explosion in the quality, quantity and variety of biological data-sequence, structure, and networks. However, when building computational models on these data, some abstractions recur often. In particular, graph-based computational models are a powerful, flexible and efficient way of modeling many biological systems. Graph models are used in systems biology where the goal is to understand relationships among biological entities, and in structural bioinformatics where a graph is used to represent the amino acid (or atom) interaction relationships in a protein or the secondary structure base-pairing relationships in RNA. For many of these problems, we can develop algorithms that explore the fact that certain key parameters have complexity dependent on the treewidth of the system, which is typically very small for a variety of biological systems. When treewidth is large, we can still use spectral methods to find biologically sound solutions in an efficient manner.
