PIMS/CSC Research Seminar: Wayne Hayes

The alignment of genetic and protein sequences has taught us an enormous amount about biology, evolution, and disease. The alignment of biological networks has the potential to be equally enlightening, because if we can align a network of a well-studied species to a less well studied one, we can transfer biological information from one to the other, as well as to infer phylogenetic information among a set of species. However, while the wet-lab creation of genetic sequences is relatively cheap today, the creation of data sets for biological networks is enormously more expensive. Furthermore, while the computational problem of aligning genetic sequences of length n can essentially be solved in linear time, the alignment of networks is a generalization of the subgraph isomorphism problem and is thus NP-complete. Essentially, network alignment is the problem of finding the "best" way to overlay a smaller graph on top of a bigger one in the presence of noise. I will discuss these ideas as well as outline progress over the past decade or so.