New experiments are revealing interactions between many molecules, such as proteins, in present-day bacterial and animal cells. These interactions have evolved over time, resulting in the networks of interactions we see today. Often, however, we are interested in what such a network looked like in the past in a now-extinct ancestral species. This project will develop new algorithms for recovering lost, ancient biological networks from present-day networks. To do this, we view the reconstruction problem as a network design task where the designed network is subjected to random modifications according to a model of network evolution. We then seek to design an ancestral network that is likely to have evolved into the observed, present-day networks. The developed techniques will be applied to find precursor networks of a single network at various points in time and to find the common ancestor network of several extant organisms. In concert with the reconstruction task, we will create more realistic computational models of network evolution by efficiently searching a large space of possible evolutionary models. Our examination of recovered ancient networks will advance our understanding of how biological interactions evolve and how that evolution has shaped the function of the cell. The application of the algorithms to retrieve the history of social networks will also be explored.
The project further aims to excite undergraduate and high school students about a career in science by expanding a successful summer internship program in bioinformatics. The program will host additional interns to conduct research on systems biology, genomics, and other topics at the interface of computer science and molecular biology. We will also create improved online resources to connect undergraduates interested in bioinformatics research with faculty mentors. The research on ancestral network reconstruction will be incorporated into several undergraduate and graduate bioinformatics and algorithms courses.
