On the structure and evolution of protein interaction networks

The study of protein interactions from the networks point of view has yielded new insights into systems biology [Bar03, MA03, RSM+02, WS98]. In particular, "network motifs" become apparent as a useful and systematic tool for describing and exploring networks [BP06, MKFV06, MSOI+02, SOMMA02, SV06]. Finding motifs has involved either exact counting (e.g. [MSOI+02]) or subgraph sampling (e.g. [BP06, KIMA04a, MZW05]). In this thesis we develop an algorithm to count all instances of a particular subgraph, which can be used to query whether a given subgraph is a significant motif. This method can be used to perform exact counting of network motifs faster and with less memory than previous methods, and can also be combined with subgraph sampling to find larger motifs than ever before -- we have found motifs with up to 15 nodes and explored subgraphs up to 20 nodes. Unlike previous methods, this method can also be used to explore motif clustering and can be combined with network alignment techniques [FNS+06, KSK+03]. We also present new methods of estimating parameters for models of biological network growth, and present a new model based on these parameters and underlying binding domains. Finally, we propose an experiment to explore the effect of the whole genome duplication [KBL04] on the protein-protein interaction network of S. cerevisiae, allowing us to distinguish between cases of subfunctionalization and neofunctionalization.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2006

Author dc:creator

• Grochow, Joshua A

Advisor dc:contributor.advisor

• Manolis Kellis.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/42053

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/42053