Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Comparative and Evolutionary Analysis of Cellular Pathways

Manikandan Narayanan

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2007-141
December 5, 2007

http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-141.pdf

Various pathways maintain the structure, function and health of a cell, and intricate molecular mechanisms underlie these cellular pathways. Inquiring how such mechanisms could have evolved is a basic question in evolutionary biology with wide-ranging implications for predicting and altering cellular phenotypes. This dissertation presents our work on the computational analysis of genome-level data (on biomolecular sequences and interactions) available for many organisms to study the conservation and evolution of cellular pathways. We study conservation of pathways in the context of comparative analysis of protein interaction networks. We specifically present a method based on a graph-matching algorithm to detect conserved pathways between two protein networks. Our algorithm is provably efficient unlike the search heuristics used in previous methods, and is novel in the broader field of graph-matching as well. We apply the method to compare the yeast network with the human, fruit fly and nematode worm networks, evaluate the detected conserved pathways using known yeast protein complexes, and demonstrate applications to function prediction. We study evolution of pathways in the context of phylogenetic analysis of bacterial and archaeal pathways. We specifically present a tractable probabilistic model for pathway evolution that makes the assumptions about pathway evolution explicit, in contrast to the few past studies that use discrete pathway similarity based models. We then apply the model to estimate the phylogeny along which a pathway such as citric acid cycle or chemotaxis evolved from its unknown ancestral forms to extant forms. We interpret the estimated phylogenies of such pathways involved in essential metabolisms or stress responses using known species phylogenies and published cellular phenotypes.

Advisor: Richard M. Karp


BibTeX citation:

@phdthesis{Narayanan:EECS-2007-141,
    Author = {Narayanan, Manikandan},
    Title = {Comparative and Evolutionary Analysis of Cellular Pathways},
    School = {EECS Department, University of California, Berkeley},
    Year = {2007},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-141.html},
    Number = {UCB/EECS-2007-141},
    Abstract = {Various pathways maintain the structure, function and health of a cell, and intricate molecular mechanisms underlie these cellular pathways. Inquiring how such mechanisms could have evolved is a basic question in evolutionary biology with wide-ranging implications
for predicting and altering cellular phenotypes. This dissertation presents our work on the computational analysis of genome-level data (on biomolecular sequences and interactions) available for many organisms to study the conservation and evolution of cellular pathways.

We study conservation of pathways in the context of comparative analysis of protein interaction networks. We specifically present a method based on a graph-matching algorithm to detect conserved pathways between two protein networks. Our algorithm is provably efficient unlike the search heuristics used in previous methods, and is novel in the broader field of graph-matching as well. We apply the method to compare the yeast network with the human, fruit fly and nematode worm networks, evaluate the detected conserved pathways using known yeast protein complexes, and demonstrate applications to function prediction.

We study evolution of pathways in the context of phylogenetic analysis of bacterial and archaeal pathways. We specifically present a tractable probabilistic model for pathway evolution that makes the assumptions about pathway evolution explicit, in contrast to the few past studies that use discrete pathway similarity based models. We then apply the model to estimate the phylogeny along which a pathway such as citric acid cycle or chemotaxis
evolved from its unknown ancestral forms to extant forms. We interpret the estimated phylogenies of such pathways involved in essential metabolisms or stress responses using
known species phylogenies and published cellular phenotypes.}
}

EndNote citation:

%0 Thesis
%A Narayanan, Manikandan
%T Comparative and Evolutionary Analysis of Cellular Pathways
%I EECS Department, University of California, Berkeley
%D 2007
%8 December 5
%@ UCB/EECS-2007-141
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-141.html
%F Narayanan:EECS-2007-141