Enzyme Function Assignment in Metabolic Pathways and Interacting Partner Prediction in Two Component Signaling Systems Using Conserved and Co-varying Amino Acid Residues

A biological pathway involves multiple proteins that work together or serially to perform important biological functions in cells. Determining the presence and absence of biological pathways in a genome is one of the most important genome analysis tasks, thus the identification of proteins which have biochemical functions related to biological pathways and how these proteins interact is of critical importance.;This thesis proposes two new computational methods for biological pathway reconstruction using (1) conserved regions among proteins in the same functional category and (2) co-evolving amino acid residue pairs between interacting partners.;The first of these problems involves the detection of enzymes, genes involved in pathways, and their functions in a whole genome. This method utilized a clustering technique based on the graph theory and the profile Hidden Markov Modeling using common shared regions (CSR) extracted from proteins in the same cluster. Amino acid residues in the CSR were further analyzed to highlight important residues using the Aggregated Related Column Scoring scheme (ARCS), a method that uses aggregation of mutual information at residue pairs.;The second problem addresses the detection of partnering proteins in two-component signaling pathways that consist of histidine kinases and response regulators. I developed a new algorithm, TCS Interacting Pair Predictor (TCSpp), to predict interacting pairs among all possible combinations of sensor histidine kinases and response regulators in a specific bacterial two-component system (TCS). This algorithm used an information- and graph-theoretic approach to identify co-evolving amino acid residue pairs in interacting HK and RR partners. Then co-evolving residues were further screened using a maximum bipartite graph matching technique. The co-evolving amino acid pairs were used to build machine learning predictors.;These two methods have been fully implemented and applied to provide web-based services, ComPath and TCSppWWW, to the bioinformatics community. The design concept and the workflow of the analysis tasks also are briefly described.