Examination committee: Dr. Martin Farach-Colton(Chair), Dr. S. Muthu Muthukrishnan, Dr. Vladimir Pavlovic

Abstract:

In the era of proteomics, the analysis of high-throughput protein-protein interaction(PPI) data is becoming more and more important, providing a great oppotunity for understanding the cellular machinery in vivo, and as an important tool for drug target discovery. Currently many research efforts are centered on collecting PPI data, evaluating PPI data reliability, predicting PPIs in silico and mining information from PPI networks, such as inferring protein functions and discovering protein complexes. However, there have been few attempts to discover temporal relations in biomolecular pathways from PPI data. Here we model the biomolecular pathway as an interval graph where each interval corresponds to the life cycle of one protein in the pathway. We develop a tool XRONOS to compute the vertex ordering from the PPI graph, which shows temporal order of joining/leaving the pathway for proteins involved in the pathway. Since right now there is little biological data available to evaluate the temporal relation we obtain, we design two validation tests, one with minimum linear arrangement and the other with ordering computed from random graphs. We apply our approach to the ribosomal assembly pathway. The validation results show that the orderings computed by XRONOS for that pathway contain quite strong signals.