Algorithms for classification and prediction of protein structure and function

The subject of this thesis is predicting the function of a protein.; Many aspects of protein function are determined by its shape, or the structure. This thesis discusses methods for converting sets of local predictions concerning the structure of a protein chain to an overall prediction of the structure.; One approach was to define a similarity function for chains of "local predictions" and to use this function to rank the prepositions that the input protein belongs to a particular fold from the most likely to the least likely. This is called fold classification. We show how to use information that is not local from the point of view of a protein chain, namely, which loops are closed, to improve the quality of classification. In the process, a weakness in the previous evaluation method was discovered and a better method proposed and tested.; The second approach is to start with predictions of secondary structures, strands and helices, and a predictor of propensity of beta-strands to form pairs, and to obtain the overall prediction of the pairing of strands. We discuss global optimization problems that this task can pose, their hardness and approximation algorithms. We also test several algorithms on biological data and find improvement in respect to a previous method.; Other aspects of protein function are determined by their place in the networks of cellular interactions. We study the cycles in the transcription regulatory network of Saccharomyces cerevisiae, we find the graph-theoretic properties of these cycles, and we characterize the place of these cycles in the regulatory mechanism of the cell in terms of hierarchy. We also establish which life conditions are associated with the cycles and we conjecture the reasons.