Doctor of Philosophy(PhD) / In this thesis, we consider Markov models for matched sequences. De¯ne fij(t) = P(X(t) = i; Y (t) = jjX(0) = Y (0)); where fij is the joint probability that, for a given site, the ¯rst and second sequences have the values i and j at a given site, given that they were the same at time 0. This can generalized to several sequences. The sequences (taxa) are then arranged in an evolutionary tree (phylogenetic tree) depicting how taxa diverge from their common ancestors. We develop tests and estimation methods for the parameters of di®erent models. Standard phylogenetic methods assume stationarity, homogeneity and reversibility for the Markov processes, and often impose further restrictions on the parameters. The parameters in these cases are estimated using many popular packages, including PHYLIP and PAUP*. We describe a new and more general method for calculating the joint probability distribution under stationary and homogeneous models for the more general models with some weakening of the stationarity and homogeneity assumptions. We describe the method for a two edged tree and then extend it to the case for a K tipped tree. We discuss the case of a ¯ve edged tree for a set of bacterial sequences for which stationarity and homogeneity are not present. This data set is very similar to that of Galtier and Gouy (1995), and the search for methods appropriate for its analysis has provided the raison d'etre for this work. The extension we propose is to allow non-stationarity, so that from the root of the tree we permit di®erent Markov processes to operate along different descendant lineages; furthermore, we permit non-homogeneous Markov processes to operate across the tree. We obtain methods that

<p>Methods using oligonucleotide probes are powerful tools for the analysis of nucleic acids. During recent years, many such methods have been developed that enable the simultaneous interrogation of multiple qualities of a sample. Many of these multiplexing techniques share common limitations. This thesis discusses new developments to overcome the problems of multiplex amplification of genomic sequences and design of sets of oligonucleotide probes for multiplex genetic analyses.</p><p>A novel molecular technique, termed the selector method, is described. This method allows circularization of an arbitrary selection of restriction fragments from genomic DNA, and the subsequent amplification of these circular products in parallel using common primers. The utility of the method is demonstrated by a 96-plex amplification experiment. Furthermore, the PieceMaker software for selection of restriction enzymes and restriction fragments is described. These two developments allow the selective amplification of subsets of genomes for further analyses.</p><p>A software tool for the design of sequence-tagged oligonucleotide probes is presented. The ProbeMaker software is a framework for design of sets of probes composed of separate functional elements, and uses an extension mechanism to incorporate support for new probe types as needed. An approach to a unified system for oligonucleotide design is also presented. This system will serve to decrease development times for new oligonucleotide design applications by allowing extensive code reuse.</p>

A lot of things happen to proteins when Escherichia coli cells enter stationary phase, such as protein amount, post-translational modifications, conformation changes, and component of protein complex. Proteomics, which study the whole component of proteins, can be used to study the products of the genome and the physiology of Escherichia coli cells at different conditions. By comparing proteome from different growth phases, such as exponential and stationary phase, a lot of proteins with changes can be identified at the same time, which provides a pilot for further studies of mechanism. Current global proteomic studies have identified about 27% of the annotated proteins of E. coli, most of which are predicted to be abundance proteins. Subproteomics, the study of specific subsets of the proteome, can be used to study specific functional classes of proteins and low abundance proteins. In this dissertation, using non-denatured anion exchange column with 2D SDS-PAGE and tandem mass spectrometry, difference of E. coli cells between exponential and stationary phase were studied for whole soluble proteome. Also, using heparin column and mass spectrometry with tandem mass spectrometry, heparin-binding proteins were identified and analyzed for exponential growth and stationary phases. To manage and display the data generated by proteomics, a web-based database has been constructed for experiments in E. coli proteomics (EEP), which includes NonDeLC, Heparome, AIX/2D PAGE and other proteomic studies.

Methods using oligonucleotide probes are powerful tools for the analysis of nucleic acids. During recent years, many such methods have been developed that enable the simultaneous interrogation of multiple qualities of a sample. Many of these multiplexing techniques share common limitations. This thesis discusses new developments to overcome the problems of multiplex amplification of genomic sequences and design of sets of oligonucleotide probes for multiplex genetic analyses. A novel molecular technique, termed the selector method, is described. This method allows circularization of an arbitrary selection of restriction fragments from genomic DNA, and the subsequent amplification of these circular products in parallel using common primers. The utility of the method is demonstrated by a 96-plex amplification experiment. Furthermore, the PieceMaker software for selection of restriction enzymes and restriction fragments is described. These two developments allow the selective amplification of subsets of genomes for further analyses. A software tool for the design of sequence-tagged oligonucleotide probes is presented. The ProbeMaker software is a framework for design of sets of probes composed of separate functional elements, and uses an extension mechanism to incorporate support for new probe types as needed. An approach to a unified system for oligonucleotide design is also presented. This system will serve to decrease development times for new oligonucleotide design applications by allowing extensive code reuse.

In this thesis, nutrient signalling in yeast is used as a model to study several features of gene regulation, such as combinatorial gene regulation, the role of motif context and chromatin modifications. The nutrient signalling system in yeast consists of several pathways that transmit signals about the availability of key nutrients, and regulate the transcription of a large part of the genome. Some of the signalling pathways are also conserved in other eukaryotic species where they are implicated in processes such as aging and in human disease.   Combinatorial gene regulation is examined in papers I and II. In paper I, the role of Mig1, Mig2 and Mig3 is studied. To elucidate how the three proteins contribute to the control of gene expression, we used microarrays to study the expression of all yeast genes in the wild type and in all seven possible combinations of mig1, mig2 and mig3 deletions. In paper II, a similar strategy is used to investigate Gis1 and Rph1, two related transcription factors. Our results reveal that Rph1 is involved in nutrient signalling together with Gis1, and we find that both the activities and the target specificities of Gis1 and Rph1 depend on the growth phase.   Paper III describes ContextFinder, a program for identifying constraints on sequence motif locations and orientations. ContextFinder was used to analyse over 300 cases of motifs that are enriched in experimentally selected groups of yeast promoters. Our results suggest that motif context frequently is important for stable DNA binding and/or regulatory activity of transcription factors.   In paper IV, we investigated how gene expression changes resulting from nitrogen starvation are accompanied by chromatin modifications. Activation of gene expression is concentrated to specific genomic regions. It is associated with nucleosome depletion (in both promoters and coding regions) and increased levels of H3K9ac (but not H4K5ac).

Background: In P. falciparum a similarity between the transit peptides of apicoplast and mitochondrial proteins in the context of net positive charge has previously been observed in few proteins. Existing P. falciparum protein localization prediction tools were leveraged in this study to study this similarity in larger sets of these proteins. Results: The online public-domain malarial repository PlasmoDB was utilized as the source of apicoplast and mitochondrial protein sequences for the similarity study of the two types of transit peptides. It was found that many of the 551 apicoplast-targeted proteins (NEAT proteins) of PlasmoDB may have been wrongly annotated to localize to the apicoplast, as some of these proteins lacked annotations for signal peptides, while others also had annotations for localization to the mitochondrion (NEMT proteins). Also around 50 NEAT proteins could contain signal anchors instead of signal peptides in their N-termini, something that could have an impact on the current theory that explains localization to the apicoplast [1]. The P. falciparum localization prediction tools were then used to study the similarity in net positive charge between the transit peptides of NEAT and NEMT proteins. It was found that NEAT protein prediction tools like PlasmoAP and PATS could be made to recognize NEMT proteins as NEAT proteins, while the NEMT predicting tool PlasMit could be made to recognize a significant number of NEAT proteins as NEMT. Based on these results a conjecture was proposed that a single technique may be sufficient to predict both apicoplast and mitochondrial transit peptides. An implementation in PERL called TargetPf was implemented to test this conjecture (using PlasmoAP rules), and it reported a total of 408 NEAT proteins and 1504 NEMT proteins. This number of predicted NEMT proteins (1504) was significantly higher than the annotated 258 NEMT proteins of plasmoDB, but more in line with the 1200 predictions of the tool PlasMit. Conclusions: Some possible ambiguities in the PlasmoDB annotations related to NEAT protein localization were identified in this study. It was also found that existing P. falciparum localization prediction tools can be made to detect transit peptides for which they have not been trained or built for.

Proteins combine in various ways to execute different essential functions. Cellular processes are enormously complex and it is a great challenge to explain the underlying organization. Various methods have been applied in attempt to reveal the organization of the cell. Gene expression analysis uses the mRNA levels in the cell to predict which proteins are present in the cell simultaneously. This method is useful but also known to sometimes fail. Proteins that are known to be functionally related do not always show a significant correlation in gene expression. This fact might be explained by the dynamic organization of the proteome. Proteins can have diverse functions and might interact with some proteins only during a few time points, which would probably not result in significant correlation in their gene expression. In this work we tried to address this problem by combining gene expression data with data for physical interactions between proteins. We used a method for modular decomposition introduced by Gagneur et al. (2004) that aims to reveal the logical organization in protein-protein networks. We extended the interpretation of the modular decomposition to localize the dynamics in the protein organization. We found evidence that protein-interactions supported by gene expression data are very likely to be related in function and thus can be used to predict function for unknown proteins. We also identified negative correlation in gene expression as an overlooked area. Several hypotheses were generated using combination of these methods. Some could be verified by the literature and others might shed light on new pathways after additional experimental testing.

The number of experimentally determined protein structures in the protein data bank (PDB) is continuously increasing. The common features like; cellular location, function, topology, primary structure, secondary structure, tertiary structure, domains or fold are used to classify them. Therefore, there are various methods available for classification of proteins. In this work we are attempting an additional method for making appropriate classification, i.e. solvent energy. Solvation is one of the most important properties of macromolecules and biological membranes by which they remain stabilized in different environments. The energy required for solvation can be measured in term of solvent energy. Proteins from similar environments are investigated for similar solvent energy. That is, the solvent energy can be used as a measure to analyze and classify proteins. In this project solvent energy of proteins present in the Protein Data Bank (PDB) was calculated by using Jones’ algorithm. The proteins were classified into two classes; transmembrane and globular. The results of statistical analysis showed that the values of solvent energy obtained for two main classes (globular and transmebrane) were from different sets of populations. Thus, by adopting classification based on solvent energy will definitely help for prediction of cellular placement.

The topic of gene regulation is a major research area in the bioinformatics community. In this thesis prior knowledge from Gene Ontology in the form of templates is integrated into the fitness function of an evolutionary algorithm to predict gene regulatory networks. The resulting multi-objective fitness functions are then tested with MAPK network data taken from KEGG to evaluate their respective performances. The results are presented and analyzed. However, a clear tendency cannot be observed. The results are nevertheless promising and can provide motivation for further research in that direction. Therefore different ideas and approaches are suggested for future work.

State-of-the-art methods for topology of α-helical membrane proteins are based on the use of time-consuming multiple sequence alignments obtained from PSI-BLAST or other sources. Here, we examine if it is possible to use the consensus of topology prediction methods that are based on single sequences to obtain a similar accuracy as the more accurate multiple sequence-based methods. Here, we show that TOPCONS-single performs better than any of the other topology prediction methods tested here, but ~6% worse than the best method that is utilizing multiple sequence alignments. AVAILABILITY AND IMPLEMENTATION: TOPCONS-single is available as a web server from http://single.topcons.net/ and is also included for local installation from the web site. In addition, consensus-based topology predictions for the entire international protein index (IPI) is available from the web server and will be updated at regular intervals.