Determining protein sequence similarity is an important task for protein classification and homology detection, which is typically performed using sequence alignment algorithms. Fast and accurate alignment-free kernel based classifiers exist, that treat protein sequences as a “bag of words”. Kernels implicitly map the sequences to a high dimensional feature space, and can be thought of as an inner product between two vectors in that space. This allows an algorithm that can be expressed purely in terms of inner products to be ‘kernelised’, where the algorithm implicitly operates in the kernel’s feature space. A weighted string kernel, where the weighting is derived using probabilistic methods, is implemented using a binary data representation, and the results reported. Alternative forms of data representation, such as Ising and frequency forms, are implemented and the results discussed. These results are then used to inform the development of a variety of novel kernels for protein sequence comparison. Alternative forms of classifier are investigated, such as nearest neighbour, support vector machines, and multiple kernel learning. A kernelized Gaussian classifier is derived and tested, which is informative as it returns a score related to the probability of a sequence belonging to a particular classification. Support vector machines are tested with the introduced kernels, and the results compared to alternate classifiers. As similarity can be thought of as having different components, such as composition and position, multiple kernel learning is investigated with the novel kernels developed here. The results show that a support vector machine, using either single or multiple kernels, is the best classifier for remote protein homology detection out of all the classifiers tested in this thesis.

Cheap electronic storage and Internet bandwidth has increased the amount of online data. Large quantities of metadata are created to manage this wealth of information. Methods to organize and structure metadata has led to the development of ontologies - data that is organized to describe the relation between elements. The creation of large ontologies has brought forth the need for ontology management strategies. Ontology alignment and merging techniques are standard operations for ontology management. Accurate ontology alignment methods are typically semi-automatic, meaning they require periodic user input. This becomes infeasible on large ontologies and the accuracy and efficiency drops significantly when these algorithms are forced to align without human interaction. Bioinformatics, for example, has seen the influx of large ontologies, such as signal pathway sets with thousands of elements or protein-protein interaction (PPI) databases with hundreds of thousands of elements. This drives the need for a reliable method of large-scale ontology alignment. Many bioinformatics ontologies contain references to domain ontologies - manually curated ontologies describing additional, general information about the terms in the ontologies. For example, more than 2/3 of proteins in PPI data sets contain at least one annotation to the domain ontology the Gene Ontology. We use the domain ontology references as features to compute similarity between elements. However, there are few efficient ways to compute similarity from structured features. We present a novel, automatic method for aligning ontologies based on such domain ontology features. Specifically, we use simulated annealing to reduce the complexity of the domain ontologys structure by finding approximate relevant clusters of elements. An intermediate step performs hierarchical clustering based on the similarity between elements of the ontology. Then the mapping between clusters across aligning ontologies is built. The final step builds an alignment between matched clusters. To evaluate our methods, we perform an alignment between Human (Homo Sapiens) and Yeast (Saccharomyces cerevisiae) signal pathways provided by the Reactome database. The results were compared against reliable homology studies of proteins. The final mapping produces alignments that are significantly more accurate than the traditional ontology alignment methods, without any human involvement.

1D protein sequences, 2D contact maps and 3D structures are three different representational levels of detail for proteins. Predicting protein 3D structures from their 1D sequences remains one of the complex challenges of bioinformatics. The "Divide and Conquer" principle is applied in our research to handle this challenge, by dividing it into two separate yet dependent subproblems, using a Case-Based Reasoning (CBR) approach. Firstly, 2D contact maps are predicted from their 1D protein sequences; secondly, 3D protein structures are then predicted from their predicted 2D contact maps. We focus on the problem of identifying common substructural patterns of protein contact maps, which could potentially be used as building blocks for a bottom-up approach for protein structure prediction. We further demonstrate how to improve identifying these patterns by combining both protein sequence and structural information. We assess the consistency and the efficiency of identifying common substructural patterns by conducting statistical analyses on several subsets of the experimental results with different sequence and structural information. / Thesis (Master, Computing) -- Queen's University, 2009-04-23 22:01:04.528

Cheap electronic storage and Internet bandwidth has increased the amount of online data. Large quantities of metadata are created to manage this wealth of information. Methods to organize and structure metadata has led to the development of ontologies - data that is organized to describe the relation between elements. The creation of large ontologies has brought forth the need for ontology management strategies. Ontology alignment and merging techniques are standard operations for ontology management. Accurate ontology alignment methods are typically semi-automatic, meaning they require periodic user input. This becomes infeasible on large ontologies and the accuracy and efficiency drops significantly when these algorithms are forced to align without human interaction. Bioinformatics, for example, has seen the influx of large ontologies, such as signal pathway sets with thousands of elements or protein-protein interaction (PPI) databases with hundreds of thousands of elements. This drives the need for a reliable method of large-scale ontology alignment. Many bioinformatics ontologies contain references to domain ontologies - manually curated ontologies describing additional, general information about the terms in the ontologies. For example, more than 2/3 of proteins in PPI data sets contain at least one annotation to the domain ontology the Gene Ontology. We use the domain ontology references as features to compute similarity between elements. However, there are few efficient ways to compute similarity from structured features. We present a novel, automatic method for aligning ontologies based on such domain ontology features. Specifically, we use simulated annealing to reduce the complexity of the domain ontologys structure by finding approximate relevant clusters of elements. An intermediate step performs hierarchical clustering based on the similarity between elements of the ontology. Then the mapping between clusters across aligning ontologies is built. The final step builds an alignment between matched clusters. To evaluate our methods, we perform an alignment between Human (Homo Sapiens) and Yeast (Saccharomyces cerevisiae) signal pathways provided by the Reactome database. The results were compared against reliable homology studies of proteins. The final mapping produces alignments that are significantly more accurate than the traditional ontology alignment methods, without any human involvement.

Cheap electronic storage and Internet bandwidth has increased the amount of online data. Large quantities of metadata are created to manage this wealth of information. Methods to organize and structure metadata has led to the development of ontologies - data that is organized to describe the relation between elements. The creation of large ontologies has brought forth the need for ontology management strategies. Ontology alignment and merging techniques are standard operations for ontology management. Accurate ontology alignment methods are typically semi-automatic, meaning they require periodic user input. This becomes infeasible on large ontologies and the accuracy and efficiency drops significantly when these algorithms are forced to align without human interaction. Bioinformatics, for example, has seen the influx of large ontologies, such as signal pathway sets with thousands of elements or protein-protein interaction (PPI) databases with hundreds of thousands of elements. This drives the need for a reliable method of large-scale ontology alignment. Many bioinformatics ontologies contain references to domain ontologies - manually curated ontologies describing additional, general information about the terms in the ontologies. For example, more than 2/3 of proteins in PPI data sets contain at least one annotation to the domain ontology the Gene Ontology. We use the domain ontology references as features to compute similarity between elements. However, there are few efficient ways to compute similarity from structured features. We present a novel, automatic method for aligning ontologies based on such domain ontology features. Specifically, we use simulated annealing to reduce the complexity of the domain ontologys structure by finding approximate relevant clusters of elements. An intermediate step performs hierarchical clustering based on the similarity between elements of the ontology. Then the mapping between clusters across aligning ontologies is built. The final step builds an alignment between matched clusters. To evaluate our methods, we perform an alignment between Human (Homo Sapiens) and Yeast (Saccharomyces cerevisiae) signal pathways provided by the Reactome database. The results were compared against reliable homology studies of proteins. The final mapping produces alignments that are significantly more accurate than the traditional ontology alignment methods, without any human involvement. / Science, Faculty of / Computer Science, Department of / Graduate

Protein homology detection has played a central role in the understanding of evolution of protein structures, functions and interactions. Many of the developments in protein bioinformatics can be traced back to an initial step of homology detection. It is not surprising then, that extension of remote homology detection has gained a lot of attention in the recent past. The explosive growth of genome sequences and the slow pace of experimental techniques have thrust computational analyses into the limelight. It is not surprising to see that many of the traditional experimental areas such as gene expression analysis, recognition of function and recognition of 3-D structure have been attempted effectively by computational approaches. The idea behind homology-based bioinformatics work is the fact that the hereditary mechanisms ensure that the parent generation gives rise to a very similar offspring generation. Since biological functions of proteins of an organism are product of expression of its genetic material, it follows that the genes of an organism should show conservation from one generation to another (with very few mutations if parent and offspring generation have to be nearly identical) Thus, if it can be established that two proteins have descended from a common ancestor, then it can be inferred that the biological functions of the two proteins could be very similar. Thus, homology-based information transfer from one protein to another has become a commonly used procedure in protein bioinformatics. The ability to recognize homologs of a protein solely from amino acid sequences has seen a steady increase in the last two decades. However, currently, still there are a large number of proteins of known amino acid sequence and yet unknown function . Thus, a major goal of current computational work is to extend the limits of remote homology detection to enable the functional characterization of proteins of unknown function. Since proteins do not work in isolation in a cell, it has become essential to understand the in vivo context of the function of a protein. For this purpose, it is essential to have an understanding of all the molecules that interact with a particular protein. Thus, another major area of bioinformatics has been to integrate biological information with protein-protein interactions to enable a better understanding of the molecular processes. Such attempts have been made successfully for the interaction network of proteins within an organism. The extension of the interaction network analysis to a host-pathogen scenario can lead to useful insights into pathophysiology of diseases. The work done as part of the thesis explores both the ideas mentioned above, namely, the extension of limits of remote homology detection and prediction of protein-protein interactions between a pathogen and its host. Since the work can logically be divided into two different areas though there is a connection, the thesis is organized as two parts. The first part of the thesis (comprising Chapters 2, 3, 4 and 5) describes the development and application of remote homology detection tools for function/structure annotation. The second part of the thesis (comprising of Chapters 6, 7, 8 and 9) describes the development and application of a homology-based procedure for detection of host-pathogen protein-protein interactions. Chapter 1 provides a background and literature survey in the areas of homology detection and prediction of protein-protein interactions. It is argued that homology-based information transfer is currently an important tool in the prediction and recognition of protein structures, functions and interactions. The development of remote homology detection methods and its effect on function recognition has been highlighted. Recent work in the area of prediction of protein-protein interactions using homology to known interaction templates is described and it is implied to be a successful approach for prediction of protein-protein interactions on a genome scale. The importance of further improvements in remote homology detection (as done in the first part of the thesis), is emphasized for annotation of proteins in newly sequenced genomes. The importance of application of homology detection methods in predicting protein-protein interactions across host-pathogen organisms is also explored. Chapter 2 analyzes the performance of the PSI-BLAST, one of the well-known and very effective approaches for recognition of related proteins, for remote homology detection. The chapter describes in detail the working of the PSI-BLAST algorithm and focuses on three parameters that determine the time required for searching in a large database, and also provide a ceiling for the sensitivity of the search procedure. The parameters that have been analyzed are the window size for two-hit method, the threshold for extension of an initial hit to dynamic programming and the extent of dependence on the query as encompassed in the profile generation step. The procedure followed for the analysis is to consider a large database of known evolutionary relationships (SCOP database was chosen for the analysis), and use the PSI-BLAST program at different values of three parameters to find out the effect on sensitivity (defined as the normalized number of correct SCOP superfamily relationships found in a search), and the time required for completion of the search. For the demonstration of the effect on the query dependence, a multiple sequence alignment (MSA) of a SCOP family (generated from all family sequences using ClustalW), was used with multiple queries to derive profiles in PSI-BLAST runs. The increase in sensitivity and the increase in time required for completion of each search were then monitored. The effect of changing the two PSI-BLAST internal parameters of score threshold for extension of word hits and the window size for the two-hit method do not result in a significant increase in sensitivity. Since PSI-BLAST uses the amino acid residues present in the query sequence to derive the Position Specific Scoring Matrix (PSSM) parameters, there is a strong query dependence on the sensitivity of each PSSM. Using multiple PSSMs derived from a single MSA can thus help overcome the query dependence and increase the sensitivity. In this Chapter such an approach, named as MulPSSM, has been demonstrated to have higher sensitivity than single profiles approach, (by up to two times more) in a benchmark dataset of 100 randomly chosen SCOP folds. Strategies to optimize sensitivity and the time required in searching MulPSSM have been explored and it is found that use of a non-redundant set of queries to generate MulPSSM can reduce the time required for each search while not affecting the sensitivity by a large degree. The application of the MulPSSM approach in function annotation of proteins in completely sequenced genomes was explored by searching genomic sequences in a MulPSSM database of Pfam families. The association of function to proteins has been assessed when both single profile per family database and MulPSSM database of families were used. It is found that in a comprehensive list of 291 genomes of Prokaryotes, 44 genomes of Eukaryotes and 40 genomes of Archea, that on an average MulPSSM is able to identify evolutionary relationships for 10% more proteins in a genome than single profiles-based approach. Such an enhancement in the recognition of evolutionary relationships, which has an implication in obtaining clues to functions, can help in more efficient exploration of newly sequenced genomes. Identification of evolutionary relationships involving some of the proteins of M. tuberculosis and M. leprae has been possible due to the use of multiple profiles search approach which is discussed in this chapter. The examples of annotations provided in the chapter include enzymes that are involved in glyco lipids synthesis which are vital for the survival of the pathogens inside the host and such annotations can help in expanding our knowledge of these processes. Chapter 3 describes the development and assessment of a sensitive remote homology detection method. The sensitivity of remote homology detection methods has been steadily increasing in the past decade and profile analysis has become a mainstay of such efforts. The profile is a probabilistic model of substitutions allowed at each position in a sequence family, and hence captures the essential features of a family. Alignment of two such profiles is thus considered to provide a more sensitive and accurate method than the alignment of two sequences. The performance of HMMs (Hidden Markov Models) has been shown to be higher than PSSMs (Position Specific Scoring Matrix). Thus, a profile-profile alignment using HMMs can in principle give the best possible sensitivity in remote homology detection. Many investigators have incorporated residue conservation and secondary structure information to align two HMMs, and such additional information has been demonstrated to provide better sensitivity in remote homology detection (for instance in the HHSearch program). The work presented in Chapter 3, extends the idea of incorporating additional information such as explicit hydrophobicity information, along with conservation and predicted secondary structure over a window of Multiple Sequence Alignment (MSA) columns in aligning HMMs. The new algorithm is named AlignHUSH (Alignment of HMMs Using Secondary structure and Hydrophobicity). The HMMs used in the work are derived from structural alignments using HMMER program and are taken from the publicly available superfamily database which provides HMMs for all the SCOP families. The HMMs are modified into two-state HMMs by collapsing the ‘insert’ and ‘delete’ states into a ‘non-match’ state in the AlignHUSH algorithm. The two state HMMs enables the use of dynamic programming methods and keeps intact the position-specific gap penalties. The two state HMMs can be more readily extended to alignment of PSSMs. The incorporation of secondary structure information is made using secondary structure predictions made using PSIPRED program. The hydrophobicity information is calculated using the Kyte Doolittle hydrophobicity values. The alignment is generated by scoring each position using the values present in a window of residues. The assessment of alignment accuracy is done by comparison to manually curated alignments present in the BaliBASE database. A detailed description of the optimization steps followed for obtaining the values for each score contribution (conservation, secondary structure and hydrophobicity) is provided. The assessment revealed that a high weightage to conservation score (18.0) and low weightage to the secondary structure score (1.5) and hydrophobicity (1.0) is optimal. The use of residue windows in alignment has been shown to dramatically increase the sensitivity (around 30% on a small dataset comprising 10% of total SCOP domains). The sensitivity of AlignHUSH algorithm in comparison to other HMM-HMM alignment methods HHSearch and PRC in an all-against-all comparison of SCOP 1.69 database demonstrates that AlignHUSH has better sensitivity than both HHSearch and PRC (approximately by 10% and 5% respectively). The alignment accuracy calculated as the ratio of correctly aligned residues and all alignment positions in BaliBASE alignments reveals that AlignHUSH algorithm provides an accuracy comparable or marginally higher than both HHSearch and PRC (25% for AlignHUSH and roughly 17% for both HHSearch and PRC). A few examples of structural relationships between SCOP families belonging to different folds and/or classes are presented in the chapter to illustrate the strength of AlignHUSH in detecting very remote relationships. Chapter 4 describes a database of evolutionary relationships identified between Pfam families. The grouping of Pfam families is important for obtaining better understanding on evolutionary relationships and in obtaining clues to functions of proteins in families of yet unknown function. Much effort has been taken by various investigators in bringing many proteins in the sequence databases within homology modeling distance with a protein of known structure. Structural genomics initiatives spend considerable effort in achieving this goal. The results from such experiments suggest that in many cases after the structure has been solved using X-ray crystallography or NMR methods, the protein is seen to have structural similarity to a protein of already known structure. Thus, an inability to detect such remote relationships severely impairs the efficiency of structural genomics initiatives. The development of the SUPFAM method was made earlier in the group to enable detection of distant relationships between Pfam families. In SUPFAM approach, relationships are detected by mapping the Pfam families to SCOP families. Further, using the implicit or explicit evolutionary relationship information present in the SCOP database relationships between Pfam families are detected. The work presented in this chapter is an improvement of previous development using the significantly more sensitive AlignHUSH method to uncover more relationships. The new database follows a procedure slightly different than the older SUPFAM database and hence is called SUPFAM+. The relative improvement brought by SUPFAM+ has been discussed in detail in the chapter. The methodology followed for the analysis is to first generate SUPFAM database by recognition of relationships between Pfam families and SCOP families using PSI BLAST / RPS BLAST. For the generation of SUPFAM+ database, recognition of relationships between Pfam families and SCOP families is done using AlignHUSH. The criteria are kept stringent at this stage to minimize the rate of false positives. In cases of a Pfam family mapping to two or more SCOP superfamilies, a semi-automated decision tree is used to assign the Pfam family to a single SCOP superfamily. Some of the Pfam families which remain without a mapping to a SCOP family are mapped indirectly to a SCOP family by identifying relationships between such Pfam families and other Pfam families which are already mapped to a SCOP family. In the final step, the Pfam families still without a SCOP family mapping are mapped onto one another to form ‘Potential New Superfamilies’ (PNSF), which are excellent targets for structural genomics since none of the proteins in such PNSFs have a recognizable homologue of known structure. The clustering of Pfam families into Superfamilies belonging to SCOP 1.69 version, were then queried to check if a structure has been solved for these Pfam families subsequent to the release of the SCOP 1.69 database. The latest SCOP database reveals that for close to 87 Pfam families a structure was solved which is at best related at a SCOP superfamily level with a family present in SCOP 1.69. An analysis of the mappings provided by SUPFAM+ database reveals that the mappings are correct in 85% of the cases at the SCOP superfamily level. An in-depth analysis revealed that among the rest of the cases, only one can be adjudged as an incorrect mapping. Many of the inconsistent mappings were found to be due to the absence of the SCOP fold in the SCOP 1.69 release, although interestingly the mapping provided by SUPFAM+ database shows structural similarity to the actual fold for the Pfam family found subsequently. A straightforward comparison with a similar database (Pfam Clans database) reveals that the SUPFAM+ database could suggest four times more pairwise relationships between Pfam families than the Pfam Clans database. Thus, since the structural mappings provided in the SUPFAM+ database are very accurate the relationships found in the database could help in function annotation of uncharacterized protein families (explored in Chapter 5). The accuracy of mapping would be similar for the PNSFs, and hence these clusters can be excellent targets for structural genomics initiatives. The classification of families based on sequence/structural similarities can also be useful for function annotation of families of uncharacterized proteins, and such an idea is explored in the next chapter. Chapter 5 describes the attempts made to obtain clues to the structure and/or function of the DUF (Domain of Unknown Function) families present in the Pfam database. Currently, the DUF families populate around 21% of the Pfam database (2260 out of 10340). Thus, although homologues for each of the proteins in these families can be recognized in sequence databases, the homology does not provide obvious insight into the function of these proteins. The annotation of such difficult targets is a major goal of computational biologists in the post-genomic era. The development of a sensitive profile-profile alignment method as part of this thesis, gives an excellent opportunity to increase the number of annotations for proteins, especially in the DUF families, since a profile for these families exists in the Pfam database. The method followed for the analysis is similar to the SUPFAM+ development, and involved generation of Pfam profiles compatible with the AlignHUSH method. For the analysis presented in the chapter, relationships found between DUF families and SCOP families were analyzed. In benchmarks using the AlignHUSH method, it was found that a Z score of 5.0 gives a 10% error rate, and a Z score of 7.5 gives an error rate of 1%, and hence a minimum Z score cutoff of 7.5 was used in the analysis. A very high Z score in AlignHUSH is usually seen in cases, when sequence identity is also high, so a maximum Z score cutoff of 12.0 was used to find DUF families which are difficult to annotate using other profile based methods (such as PSI-BLAST). For some of the DUF families, subsequent structure determination of one of the proteins had been reported in literature, and these cases were used to assess the accuracy of structural annotation using AlignHUSH. In other cases, fold recognition was done using the PHYRE method to ensure that the structure mappings are corroborated by fold recognition. In all cases studied, the alignment of the DUF family with the SCOP family was generated and queried for conservation of active site residues reported for each homologous SCOP family in the CSA (Catalytic Site Atlas) database. The assessment on 8 DUF families for which structure was solved subsequent to the SCOP release used in the analysis, reveals that in all cases, the correct structure was identified using the AlignHUSH procedure. In the eight cases of validated structure annotation, the conservation of active site residues was seen pointing to the effectiveness of AlignHUSH and its use in function annotation. The 27 cases in which a structure for any one of the proteins in the DUF family is not known, the fold recognition attempts suggest that in all cases, the results from fold recognition corroborate the suggestion made by AlignHUSH. The alignments of each of the DUF families with the suggested homologous SCOP family reveals that in many cases the active site residues are not conserved or are substituted by different residues. An in-depth analysis of some cases reveals that the non-conservation of residues occurs between two SCOP families in the same SCOP superfamily. Thus, although structure annotation can be reliably provided for all the DUF families studied, the exact biochemical function could be detected only for those cases in which active site conservation is seen even among distantly related families (such as two SCOP families in the same SCOP superfamily). The development and application of methods for remote homology detection has been made successfully and it has been demonstrated in the first part of the thesis that there is scope for extending the limits of remote homology detection. The use of sequence derived information in aligning profiles makes the procedure generally applicable and has been applied successfully for the case of structure/function recognition in the DUF families. In the next part of the thesis, a method for prediction of protein-protein interactions between a host and pathogen organism and its application to three groups of pathogens is presented. Chapter 6 describes the development of a procedure for prediction of protein-protein interactions (PPI) between a pathogen and its host organism. In the past, prediction of PPI has been attempted for proteins of a given organism. This was often approached by identifying proteins of the organism of interest that are homologous to two interacting proteins of another organism. A study of conservation of interactions as a function of sequence identity has been made in the past by various groups, which reveal that homologues sharing a sequence identity greater than about 30% interact in similar way. This fact can be used, along with a high quality database of protein-protein interactions to predict interactions between proteins of same organism. The work done in this thesis is one of the first attempts at extending the idea to the prediction of interactions between two different organisms. Homology of proteins from a pathogen and its host to proteins which are known to interact with each other would suggest that the proteins from pathogen and host can interact. The feasibility of such an interaction to occur under in vivo conditions need to be addressed for biologically meaningful predictions. These issues have been dealt with in this part of the thesis. One of the main steps in the procedure for the prediction of PPI is identification of homologues of pathogen and host proteins to interacting proteins listed in PPI databases. Two template PPI databases have been used in this work. One of the databases is the DIP database which provides a list of interactions based on genome-scale yeast-two-hybrid data or small scale experiments. The other database used is the iPfam database which provides interaction templates (Pfam families) based on protein complexes of known structure present in Protein Data Bank (PDB). Thus, the two databases are both comprehensive and are of high quality. The search for homologues in the DIP database was made using PSI-BLAST with stringent cutoffs for various parameters to minimize false positives. The search in iPfam database is done using RPS-BLAST and MulPSSM using stringent cutoffs. The cutoffs for the searches were fixed based on an assessment of conservation of putative interacting residues in the host and pathogen proteins as compared to the protein complexes of known structure. The predictions made are analyzed manually to assess the importance to the pathogenesis of the disease under consideration. In this chapter, in order to obtain an idea about robustness of this approach, PPI prediction was made for the phage-bacteria system and the herpes virus – human system which have been experimentally studied extensively and hence opportunities exist to compare the “predictions” with experimental results. The prediction of phage – bacteria interactions suggests that the gross biological features of the pathogenesis have been captured in the predictions. The GO (Gene Ontology) based annotations for the bacterial proteins predicted to interact suggests that the predictions involve proteins participating in DNA replication and protein synthesis. Many of the known interactions such as between the lambda phage repressor and RecA protein of bacteria were also ‘predicted’ in the analysis. A few novel interactions were predicted. For example interaction between a tail component protein and a protein of unknown function, YeeJ in E.coli has been predicted. The prediction of interactions between Herpes Virus 8 and human host and its comparison to a set of experimentally verified interactions reported in literature suggested that close to 50% of the known interactions were ‘predicted’ by the procedure followed. A few novel cases of interaction between the viral proteins and the p53 protein have also been made which might help in understanding the tumorigenesis of the viral disease. A comparison between the procedure followed in this thesis and the results from another genome-scale method (proposed by Andrej Sali and coworkers) suggests that although the proteins involved in predicted interactions from two methods may differ, the functions of the proteins concerned suggested by GO annotations are highly correlated (greater than 98%). In the next few chapters, the prediction of interactions for different host-pathogen systems is described. In the Chapter 7, the prediction of PPI between a Eukaryotic malarial pathogen, P.falciparum and its human host is described. The malarial parasite was chosen because of the extensive work reported in the literature on this pathogen in the recent years. Also, the gene expression patterns in the pathogen are highly correlated to the human tissue types with each stage of the pathogen occurring in a distinct tissue type. Thus, the biological context of the PPI can be explicitly assessed, which makes this example a well suited case for the procedure described in the Chapter 6 of this thesis. The pathogen is important from a medical perspective since there has been a recent emergence of P.falciparum induced malaria which is unresponsive to conventional drugs. Thus, studies of this parasite have gained an importance in the post genomic era. The difficulty in identifying homologues of many of the P.falciparum proteins makes this a challenging case study. Prediction of PPI between the malarial parasite and the human proteins has been approached in the same way as described in Chapter 6, with the cutoffs in homology searches kept stringent. However, in this case effective use of available additional biological data has been possible. The tissue specific expression information for human proteins has been obtained from the Atlas of Human transcriptome, and the NCBI GEO database. The pathogen stage-specific expression data has been obtained from multiple genome-scale experiments reported in the literature. The subcellular localization of both human and pathogen proteins has been predicted and hence this information is given low weightage in subsequent analysis. The prediction of PPI between malarial parasite and human, resulted in a total of more than 30,000 interactions which were compatible in an in vivo condition according to the expression data. Further reduction in the set of predicted interactions was made by incorporating the subcellular localization predictions (reduced to around 2000 interactions). Manual analysis of each of these interactions taking aid from literature on malarial parasites reveals that many of the known PPI are also ‘predicted’ in the analysis such as the interaction between SSP2 protein of P.falciparum and human ICAMs. For many proteins known to be important for pathogenesis, such as the RESA antigen, novel interactions were predicted that could help in better understanding of the pathogen. For some of the novel predicted interactions, such as that between the parasite Plasmepsin and human Spectrin, there exists circumstantial experimental evidence of interaction. Among many other novel interactions, the procedure used could predict interactions for 441 ‘hypothetical proteins’ of unknown function coded in the genome of the pathogen. The comprehensive list of predictions made using the procedure and an exploration of its biological significance can lead to novel hypothesis regarding the parthenogenesis of malaria and hence the work presented in this chapter can be helpful for further experimental exploration of the pathogen. The success of the procedure in predicting known interactions as well as novel interactions in a Eukaryotic pathogen suggests that the procedure developed is generally applicable. However it must be pointed out that in many cases of host-pathogen systems, such extensive expression and localization data may not be available, which makes the analysis difficult due to the large number of interactions predicted. One of such difficult cases is the interactions between Mycobacterial species and human host which is described in the next chapter. Chapter 8 describes the prediction of PPI between human and M.tuberculosis as well as three pathogens closely related to M.tuberculosis. Each of the pathogens has seen to re-emerge due to drug resistance and other causes. M.tuberculosis is becoming a global problem due to the limited number of drugs available to treat TB, which is susceptible to resistance. M.leprae has also shown signs of emergence of drug resistance, whereas C.diptheriae another pathogen studied in this chapter is seen as an emerging pathogen in Eastern Europe and in Indian subcontinent. Nocardial infections have also seen a rise due to the prevalence of AIDS which leads to susceptibility to the Nocardia infections. Thus, there is a need to understand further the pathogens in this important family, in order to better direct drug development. An important area for such endeavors is the mapping of the PPI between the pathogens and the human host. The procedure developed as part of the thesis can be used to predict such interactions. The procedure for prediction of interactions is the same as followed in Chapter 6 and involves identifications of homologues for the pathogen and host proteins among the proteins listed in the two template datasets DIP and iPfam using PSI-BLAST and RPS-BLAST (MulPSSM). In addition to the homology to the proteins involved in PPI, information / prediction on subcellular localization is used to assess biological significance of the interaction. An experimentally derived dataset of exported proteins in the M.tuberculosis was used to supplement the predictions from PSORTb database that provides subcellular localization for bacterial proteins. In order to minimize the number of predictions explored manually and to maximize the biological relevance of predicted interactions,, the predictions were made only for proteins present on the membrane of the pathogen or which are exported into the host. Prediction of interactions between human proteins and the proteins of four pathogens studied revealed that, some of the interactions which were known from earlier experiments were “predicted” by the present procedure. For example, the M.leprae exported Serine protease is known to interact with Ras-like proteins in the human host, and this interaction was ‘predicted’. Among other predicted interactions, several novel interactions have been suggested for proteins important for pathogenesis such as the MPT70 protein of M.tuberculosis which has been predicted to interact with TGFβ associated proteins which could play an important role in the pathogenesis of the disease. Some of the human proteins are known to play important role in pathogenesis, especially the toll-like receptors. A C.diphtheriae protein Mycosin, has been predicted to interact with the toll-like receptors raising the possibility that the Mycosins may play an important role in pathogenesis. Several hypothetical proteins of unknown function in the pathogens have been predicted to interact with human proteins. A few of such cases from M.tuberculosis have been described in the thesis and these proteins are predicted to interact with proteins involved in post-transnational modification in the human host. The prediction of novel interactions along with known interactions in four bacterial species thus points to the fact that the procedure can be used for almost any host-pathogen pair. In the next chapter, the application of the method to three other bacterial species belonging to the Enterobacteriaciae family is presented. Chapter 9 describes the analysis performed on the predicted interactions between human and three pathogens in the Enterobact

Significant advancements in genome sequencing techniques and other high-throughput initiatives have resulted in the availability of complete sequences of genomes of a large number of organisms, which provide an opportunity to study detailed biological information encoded therein. Identification of functional roles of proteins can aid in comprehension of various cellular activities in an organism, which is traditionally achieved using techniques pertaining to the field of molecular biology, protein chemistry and macromolecular crystallography. The established experimental methods for protein structure and function determination, although accurate and resourceful, are laborious and time consuming. Computational analyses of sequences of gene products and exploration of evolutionary relationships can give clues on protein structure and/or function with reasonable accuracy which can be used to direct experimental studies on proteins of interest, effectively. Moreover, with growing volumes of data, there has been a growing disparity in the number of well-characterized and uncharacterized proteins, further necessitating the use of computational methods for investigating evolutionary and structure-function relationships. The remarkable progress made in the development of computational techniques (Chapter 1) has immensely contributed to the state-of-the-art biological sequence analysis and recognition of protein structure and function in a reliable manner. These methods have largely influenced the exploration of protein sequence-structure-function space. One of the relevant applications of computational approaches is in the understanding of functional make-up of human pathogens, their complex interplay with the host and implications in pathogenesis. In this thesis, sensitive profile-based search procedures have been utilized to address various aspects in the context of three pathogens- Mycobacterium tuberculosis, Plasmodium falciparum and Trypanosoma brucei, which are causative agents of potentially life- threatening diseases. The existing drugs approved for the diseases, although of immense value in controlling the disease, have several shortcomings, the most important of them being the emergence of drug resistance that render the current treatment regimens futile. Thus, the identification of practicable targets and new drugs or new combination therapies become an important necessity. Analyses on structural and functional repertoire of proteins encoded in the pathogenic genomes can provide means for rational identification of therapeutic intervention strategies. This thesis begins with the computational analyses of proteins encoded in M. tuberculosis genome. M. tuberculosis is a primary aetiological agent of tuberculosis in humans, and is o responsible for an estimated 1.5 million deaths every year. The complete genome of the pathogen was sequenced and made available more than a decade ago, which has been valuable in determination of functional roles of its gene products. Yet, functions of many M. tuberculosis proteins remain unknown. Computational prediction of protein function is an on- going process based on ever growing information made available in public databases as well as the introduction of powerful homology recognition techniques. Hence, a continuous refinement is essential to make the most of the sequence data, ensuring its accuracy and relevance. With the use of multiple sequence and structural profile-based search procedures, an enhanced structural and functional characterization of M. tuberculosis proteins, totalling to 95% of the genome was achieved (Chapter 2). Following are the key findings. o Domain definitions were obtained for a total of 3566 of 4018 proteins. Amino acid residue coverage of >70% was achieved for 2295 proteins which constitute more than half of the proteome. o Domain assignments were newly identified for 244 proteins with domain-unassigned regions. Structure prediction for these proteins corroborated all the remote homologyrelationships recognized using profile-based methods, enhancing the reliability of the predictions. o Comparison on domain compositions of proteins between M. tuberculosis and human host, revealed presence of pathogen-specific domains that are not homologous to proteins in human. Such proteins in M. tuberculosis are mainly virulence factors involved in host-pathogen interactions such as immune-dominance and aiding entry and survival in human host macrophages, hence forming attractive targets for drug discovery. o Putative structural and functional information for proteins with no recognizable domains were inferred by means of fold recognition and an iterative profile-based search against sequence database. o Attributing putative structures and functions to 955 conserved hypothetical proteins in M. tuberculosis, 137 of which are reportedly essential to the pathogen, provide a basis to re-investigate their involvement in pathogenesis and survival in the host. Proteins with no detectable homologues were recognized as M. tuberculosis H37Rv-specific, which can serve as promising drug targets. An attempt was made to identify porin-like proteins in M. tuberculosis, considering MspA porin from M. smegmatis as a template. The difficulty in recognition of putative porins in M. tuberculosis is indicative of novel outer membrane channel proteins, not characterized yet, or high representation of ion-channels, symporters and transporters to compensate for the functional role of porins. In addition, MspA-like proteins were not readily recognized in other slow-growing mycobacterial pathogens that are known to infect human host, apart from M. tuberculosis. This indicates probable acquisition of physiological adaptations, i.e. absence of porins, to confer drug-resistance, in the course of their co-evolution with human hosts. Evolutionary relationships recognized between sequence (Pfam) and structural (SCOP) families aided in association of potential structures and/or functions for 55 uncharacterized Pfam domains recognized in M. tuberculosis. Such associations deliver useful insights into the structure and function of a protein housing the uncharacterized domain. The functional inferences drawn for M. tuberculosis proteins based on the predictions can provide valuable basis for experimental endeavours in understanding mechanisms of pathogenesis and can significantly impact anti-tubercular drug discovery programmes. An interesting outcome benefitted from the exercise of exploring relationships between Pfam and SCOP families, was the identification of evolutionary relationship between a Pfam domain of unknown function DUF2652 and class III nucleotidyl cyclases. A detailed investigation was undertaken to assess this relationship (Chapter 3). Nucleotidyl cyclases synthesize cyclic nucleotides which are critical second messengers in signalling pathways. The DUF2652 family predominantly comprises of bacterial proteins belonging to three lineages- Actinobacteria, Bacteroidetes and Proteobacteria. Thus, recognition of evolutionary relationship between these bacterial proteins and nucleotide cyclases is of particular interest due to the indispensability of cyclic nucleotides in regulation of varied biological activities in bacteria. Use of fold recognition program suggested presence of nucleotide cyclase-characteristic topological motif (βααββαβ) in all the members of the DUF2652 family. Detailed analyses on structural and functional features of the uncharacterized set of bacterial proteins corresponding to 50 bacterial genomes, using profile- based alignments, revealed presence of key features typical of nucleotidyl cyclases, including metal-binding aspartates, substrate-specifying residues and transition-state stabilizing residues. Depending on the features, 20 proteins of Actinobacteria lineage, predominantly mycobacteria, of unknown structure and function were identified as putative nucleotide cyclases, 23 proteins of Bacteroidetes lineage were associated with guanylyl cyclases, while 8 uncharacterized proteins of Proteobacteria were recognized as nucleotide cyclase-like proteins (7 adenylyl and one guanylyl cyclase). Sequence similarity-based clustering of the predicted nucleotide cyclase-like proteins with established nucleotide cyclases indicated the apparent evolutionarily distinctness of the subfamily of class III nucleotidyl cyclases predicted. Furthermore, analysis of evolutionarily conserved gene clusters of the predicted nucleotide cyclase-like proteins indicated functional associations that support the predictions on their participation in cellular signalling events. The inferences made can be experimentally investigated further to ascertain the involvement of the uncharacterized bacterial proteins in signalling pathways, which can help in understanding the pathobiology of pathogenic species of interest. The next objective was the recognition of biologically relevant protein-protein interactions across M. tuberculosis and human host (Chapter 4). M. tuberculosis is well known for its ability to successfully co-evolve with human host in terms of establishing infection, survival and persistence. The current knowledge on the mechanisms of host invasion, immune evasion and persistence in the host environment can be attributed, and is limited, to the experimental studies pursued by numerous groups. Chapter 4 presents an approach for computational identification of biologically feasible protein-protein interactions across M. tuberculosis and human host. The approach utilizes crystal structures of intra-organism protein-protein complexes which are transient in nature. Identification of homologues of host and pathogen proteins in the database of known protein-protein interactions, formed the initial step, followed by identification of conserved interfacial patch and integration of information on tissue-specific expression of human proteins and subcellular localization of human and M. tuberculosis proteins. In addition, appropriate filters were used to extract biologically feasible host-pathogen protein-protein interactions. This resulted in recognition of 386 interactions potentially mediated by 59 M. tuberculosis proteins and 90 human proteins. A predominance of host-pathogen interactions (193 protein-protein interactions) brought about by M. tuberculosis proteins participating in cell wall processes, was observed, which is in concurrence with the experimental studies on immuno-modulatory activities brought about by such proteins. These set of mycobacterial proteins were predicted to interact with diverse set of host proteins such as those involved in ubiquitin conjugation pathways, metabolic pathways, signalling pathways, regulation of cell proliferation, transport, apoptosis and autophagy. The predictions have the potential to complement experimental observations at the molecular level. Details on couple of interesting cases are presented in the chapter, one of which is the probable mechanism of immune evasion adopted by M. tuberculosis to inhibit lysozyme activity in macrophages, and second is the mechanism of nutrient uptake from host. The set of M. tuberculosis proteins predicted to mediate interactions with host proteins have the potential to warrant an experimental follow-up on probable mechanisms of pathogenesis and also serve as attractive targets for chemotherapeutic interventions. proteins known to participate in P. falciparum metabolism. Pathway holes, where evidence on metabolic step exists but the catalysing enzyme is not known, have also been addressed in the study, several of which have been suggested to play an important role in growth and development of the parasite during its intra-erythrocytic stages in human host. A subsequent objective was the recognition P. falciparum proteins potentially capable of remodelling erythrocytes to suit their niche (Chapter 7). Exploitative mechanisms are brought about by the parasite to remodel erythrocytes for growth and survival during intra-erythrocytic stages of its life-cycle, the understanding of which is limited to experimental studies. To achieve physicochemically viable protein-protein interactions potentially mediated by proteins of human erythrocytes and P. falciparum proteins, a structure-influenced protocol, similar to the one demonstrated in Chapter 4, was employed. Information on subcellular localization and protein expression is crucial especially for parasites like P. falciparum, which reside in One of the major shortcomings with current treatment regimen for tuberculosis is the emergence of multidrug (MDR) and extensively drug-resistant (XDR) strains that render first-line and second-line drug treatments futile. This entails a need to explore target space in M. tuberculosis as well as explore the potential of existing drugs for repurposing against tuberculosis. A drug repurposing strategy i.e. exploring within-target-family selectivity of small molecules, has been implemented (Chapter 5) to contribute towards time and cost-saving anti-tubercular drug development efforts. With the use of profile-based search procedures, evolutionary relationships between targets (other than proteins of M. tuberculosis) of FDA-approved drugs and M. tuberculosis proteins were investigated. A key filter to exclude drugs capable of acting on human proteins substantially reduced the chances of obtaining anti-targets. Thus, total of 130 FDA-approved drugs were recognized that can be repurposed against 78 M. tuberculosis proteins, belonging to the functional categories- intermediary metabolism and respiration, information pathways, cell wall and cell processes and lipid metabolism. The catalogue of structure and function of M. tuberculosis proteins and their involvement in host-pathogen protein-protein interactions compiled from chapters 2 and 4 served as a guiding tool to explore the functional importance of targets identified. Many of the potential targets identified have been experimentally shown to be essential for growth and survival of the pathogen earlier, thus gaining importance in terms of pharmaceutical relevance. Polypharmacological drugs or drugs capable of acting of multiple targets were also identified (92 drugs) in the study. These drugs have the potential to stand tolerance against development of drug resistance in the pathogen. Comparative sequence and structure-based analysis of M. tuberculosis proteins homologous to known targets yielded credible inferences on putative binding sites of FDA-approved drugs in potential targets. Instances where information on binding sites could not be readily inferred from known targets, potentially druggable sites have been predicted. Comparison with earlier experimental studies that report anti-tubercular potential of several approved drugs enhanced the credibility of 74 of 130 FDA-approved drugs that can be readily prioritized for clinical studies. An additional exercise was pursued to identify prospective anti-tubercular agents by means of structural comparison between ChEMBL compounds and 130 FDA-approved drugs. Only those compounds were retained that showed considerably high structural similarity with approved drugs. Such compounds with minor changes in terms of physicochemical properties provide a basis for exploration of compounds that may exhibit higher affinities to bind to M. tuberculosis targets. The set of approved drugs recognized as repurpose-able candidates against tuberculosis, in concert with the structurally similar compounds, can significantly impact anti-tubercular drug development and drug discovery. The next part of the thesis focuses on Plasmodium falciparum, an obligate intracellular protozoan parasite responsible for malaria. The parasite genome features unusual characteristics including abundance of low complexity regions and pronounced sequence divergence that render protein structure and function recognition difficult. The parasite also manifests remarkable plasticity in its metabolic organization throughout its developmental stages in two hosts-human and mosquito; thus obtaining an exhaustive list of metabolic proteins in the parasite gains importance. Considering the utility of multiple sensitive profile-based search approaches in enhanced annotation of M. tuberculosis genome, a similar exercise was employed to recognize potential metabolic proteins in P. falciparum (Chapter 6). A total of 172 metabolic proteins were identified as participants of 78 metabolic pathways, over and above 609heterogeneous environmental conditions at different stages in their lifecycle. Inclusion of such data aided in extraction of 208 biologically relevant protein-protein interactions potentially mediated by 59 P. falciparum proteins and 30 erythrocyte proteins. Host-parasite protein-protein interactions were predicted pertaining to several major strategies spanning intra-erythrocytic stages in P. falciparum pathogenesis including- gaining entry into the host erythrocytes (category: RBC invasion, protease), redirecting parasitic proteins to erythrocyte membrane (category: protein traffic), modulating erythrocyte machinery (category: rosette formation, putative adhesin, chaperone, kinase), evading immunity (category: immune evasion) and eventually egress (category: merozoite egress) to infect other uninfected erythrocytes. Elaborate means to analyse and evaluate the functional viability of a predicted interaction in terms of geometrical packing at the interfacial region, electrostatic complementarity of the interacting surfaces and interaction energies is also demonstrated. The protein-protein interactions, thus predicted between human erythrocytes and P. falciparum, have the potential to provide a useful basis in understanding probable mechanisms of pathogenesis, and indeed in pinning down attractive targets for antimalarial drug discovery. The emergence of drug resistance against all known antimalarial agents, currently in use, necessitates discovery and development of either new antimalarial agents or unexplored combination of drugs that may not only reduce mortality and morbidity of malaria, but also reduce the risk of resistance to antimalarial drugs. In an attempt to contribute towards the same, Chapter 8 explores the established concept of within-target-family selectivity of small molecules to recognize antimalarial potential of the approved drugs. Eighty six FDA-approved drugs, predominantly constituted by antibacterial agents, were identified as feasible candidates for repurposing against 90 P. falciparum proteins. Most of the potential parasite targets identified are known to participate in housekeeping machinery, protein biosynthesis, metabolic pathways and cell growth and differentiation, and thus are pharmaceutically relevant. During intra-erythrocytic growth of P. falciparum, the parasite resides within the erythrocyte, within a protective encasing, known as parasitophorous vacuole. Hence a drug, intended to target a parasite protein residing in an organelle, must be sufficiently hydrophilic or hydrophobic to be able to permeate cell membranes and reach its site of activity. On the basis of lipophilicity of the drugs, a physical property determined experimentally, 57 of 86 FDA-approved drugs were recognized as feasible candidates for use against P. falciparum during the course of blood-stages of infection, which can be prioritized for antimalarial drug development programmes. The final section of the thesis focuses on the protozoan parasite Trypanosoma brucei, a causative agent of African sleeping sickness (Chapter 9). This disease is endemic to sub-Saharan regions of Africa. Despite the availability of completely sequenced genome of T. brucei, structure and function for about 50% of the proteins encoded in the genome remain unknown. Absence of prophylactic chemotherapy and vaccine, compounded with emergence of drug-resistance renders anti-trypanosomal drug discovery challenging. Thus, considering the utility of frameworks established in earlier chapters for recognition of protein structure, function and drug-targets, similar steps were undertaken to understand functional repertoire of the parasite and use drug repurposing methods to accelerate anti-trypanosomal drug discovery efforts. Structures and functions were reliably recognized for 70% of the gene products (5894) encoded in T. brucei genome, with the use of multiple profile-based search procedures, coupled with information on presence of transmembrane domains and signal peptide cleavage sites. Consequently, a total of 282 uncharacterized T. brucei proteins could be newly coined as potential metabolic proteins. Integration of information on stage-specific expression profiles with Trypanosoma-specific and T-.brucei-specific proteins identified in the study, aided in pinning down potential attractive targets. Additionally, exploration of evolutionary relationships between targets of FDA-approved drugs and T. brucei proteins, 68 FDA-approved drugs were predicted as repurpose-able candidates against 42 potential T. brucei targets which primarily include proteins involved in regulatory processes and metabolism. Several targets predicted are reportedly essential in assisting the parasite to switch between differentiation forms (bloodstream and procyclic) in the course of its lifecycle. These targets are of high therapeutic relevance, hence the corresponding drug-target associations provide a useful resource for experimental endeavours. In summary, this thesis presents computational analyses on three pathogenic genomes in terms of enhancing the understanding of functional repertoire of the pathogens, addressing metabolic pathway holes, exploring probable mechanisms of pathogenesis brought about by potential host-pathogen protein-protein interactions, and identifying feasible FDA-approved drug candidates to repurpose against the pathogens. The studies are pursued primarily by taking advantage of powerful homology-detection techniques and the ever-growing biological information made available in public databases. Indeed, the inferences drawn for the three pathogenic genomes serve an excellent resource for an experimental follow-up. The set of protocols presented in the thesis are highly generic in nature, as demonstrated for three pathogens, and can be utilized for genome-wide analyses on many other pathogens of interest. The supplemental data associated with the chapters is provided in a compact disc attached with this thesis.

For three decades, the ongoing HIV pandemic has taken the lives of tens of millions of people. Still, more tens of millions are fighting this incurable disease today. Current failures in combating this global problem are caused mainly by the virus's extreme ability of mutation, its very effective molecular shield which repels the immune system's attacks, and its immense variability. A breakthrough, achieved relatively recently, is the discovery of the so-called broadly neutralizing antibodies against HIV-1, which carry a very efficient and broad neutralizing response. So far, it's not known how to elucidate the production of these antibodies in the infected hosts to quell or altogether eliminate the virus. This work deals with experimental results, which led to both in vivo and in vitro proof-of-concept of the so-called protein mimetics, the ability to imitate viral surface epitopes, and therefore stimulate an efficient immune response carried by targeted broadly neutralizing antibodies. This effect is mediated by recombinant binding proteins, based on the Myomedin scaffold. This work describes the selection and characterization of these binding proteins mimicking the epitopes of one of the most effective broadly neutralizing antibodies, 10E8. It shows that the binding affinities of selected...