Currently, one of the main research problems in Structural Bioinformatics is associated to the study and prediction of the 3-D structure of proteins. The 1990’s GENOME projects resulted in a large increase in the number of protein sequences. However, the number of identified 3-D protein structures have not followed the same growth trend. The number of protein sequences is much higher than the number of known 3-D structures. Many computational methodologies, systems and algorithms have been proposed to address the protein structure prediction problem. However, the problem still remains challenging because of the complexity and high dimensionality of a protein conformational search space. This work presents a new computational strategy for the 3-D protein structure prediction problem. A first principle strategy which uses database information for the prediction of the 3-D structure of polypeptides was developed. The proposed technique manipulates structural information from the PDB in order to generate torsion angles intervals. Torsion angles intervals are used as input to a genetic algorithm with a local-search operator in order to search the protein conformational space and predict its 3-D structure. Results show that the 3-D structures obtained by the proposed method were topologically comparable to their correspondent experimental structure.

The focus of this thesis is to develop computational techniques for analysis of protein structures. We model protein structures as points in 3-dimensional space which in turn are modeled as weighted graphs. The problem of protein structure comparison is posed as a weighted graph matching problem and an algorithm motivated from the spectral graph matching techniques is developed. The thesis also proposes novel similarity measures by deriving kernel functions. These kernel functions allow the data to be mapped to a suitably defined Reproducing kernel Hilbert Space(RKHS), paving the way for efficient algorithms for protein structure classification. Protein structure comparison (structure alignment)is a classical method of determining overall similarity between two protein structures. This problem can be posed as the approximate weighted subgraph matching problem, which is a well known NP-Hard problem. Spectral graph matching techniques provide efficient heuristic solution for the weighted graph matching problem using eigenvectors of adjacency matrices of the graphs. We propose a novel and efficient algorithm for protein structure comparison using the notion of neighborhood preserving projections (NPP) motivated from spectral graph matching. Empirically, we demonstrate that comparing the NPPs of two protein structures gives the correct equivalences when the sizes of proteins being compared are roughly similar. Also, the resulting algorithm is 3 -20 times faster than the existing state of the art techniques. This algorithm was used for retrieval of protein structures from standard databases with accuracies comparable to the state of the art. A limitation of the above method is that it gives wrong results when the number of unmatched residues, also called insertions and deletions (indels), are very high. This problem was tackled by matching neighborhoods, rather than entire structures. For each pair of neighborhoods, we grow the neighborhood alignments to get alignments for entire structures. This results in a robust method that has outperformed the existing state of the art methods on standard benchmark datasets. This method was also implemented using MPI on a cluster for database search. Another important problem in computational biology is classification of protein structures into classes exhibiting high structural similarity. Many manual and semi-automatic structural classification databases exist. Kernel methods along with support vector machines (SVM) have proved to be a robust and principled tool for classification. We have proposed novel positive semidefinite kernel functions on protein structures based on spatial neighborhoods. The kernels were derived using a general technique called convolution kernel, and showed to be related to the spectral alignment score in a limiting case. These kernels have outperformed the existing tools when validated on a well known manual classification scheme called SCOP. The kernels were designed keeping the general problem of capturing structural similarity in mind, and have been successfully applied to problems in other domains, e.g. computer vision.

This thesis is an investigation of novel mono-ADP-ribosylating toxins. In the current data-rich era, making the leap from sequence data to knowledge is a task that requires an elegant bioinformatics toolset to pinpoint questions. A strategy to expand important protein-family knowledge is required, particularly in cases in which primary sequence identity is low but structural conservation is high. For example, the mono-ADP-ribosylating toxins fit these criteria and several approaches have been used to accelerate the discovery of new family members. A newly developed tactic for detecting remote members of this family -- in which fold recognition dominates -- reduces reliance on sequence similarity and advances us toward a true structure-based protein-family expansion methodology. Chelt, a cholera-like toxin from Vibrio cholerae, and Certhrax, an anthrax-like toxin from Bacillus cereus, are among six new bacterial protein toxins identified and characterized using in silico and cell-based techniques. Medically relevant toxins from Mycobacterium avium and Enterococcus faecalis were also uncovered. Agriculturally relevant toxins were found in Photorhabdus luminescens and Vibrio splendidus. Computer software was used to build models and analyze each new toxin to understand features including: structure, secretion, cell entry, activation, NAD+ substrate binding, intracellular target binding and the reaction mechanism. Yeast-based activity tests have since confirmed activity. Vibrio cholerae produces cholix – a potent protein toxin of particular interest that has diphthamide-specific ADP-ribosyltransferase activity against eukaryotic elongation factor 2. Here we present a 2.1Å apo X-ray structure as well as a 1.8Å X-ray structure of cholix in complex with its natural substrate, nicotinamide adenine dinucleotide (NAD+). Hallmark catalytic residues were substituted and analyzed both for NAD+ binding and ADP-ribosyltransferase activity using a fluorescence-based assay. These new toxins serve as a reference for ongoing inhibitor development for this important class of virulence factors. In addition to using toxins as targets for antivirulence compounds, they can be used to make vaccines and new cancer therapies. / Natural Sciences and Engineering Research Council (CGS-D), Canadian Institutes of Health Research, Cystic Fibrosis Canada, Human Frontier Science Program, Ontario government (OGSST), University of Guelph (Graduate Research Scholarship)

Currently, one of the main research problems in Structural Bioinformatics is associated to the study and prediction of the 3-D structure of proteins. The 1990’s GENOME projects resulted in a large increase in the number of protein sequences. However, the number of identified 3-D protein structures have not followed the same growth trend. The number of protein sequences is much higher than the number of known 3-D structures. Many computational methodologies, systems and algorithms have been proposed to address the protein structure prediction problem. However, the problem still remains challenging because of the complexity and high dimensionality of a protein conformational search space. This work presents a new computational strategy for the 3-D protein structure prediction problem. A first principle strategy which uses database information for the prediction of the 3-D structure of polypeptides was developed. The proposed technique manipulates structural information from the PDB in order to generate torsion angles intervals. Torsion angles intervals are used as input to a genetic algorithm with a local-search operator in order to search the protein conformational space and predict its 3-D structure. Results show that the 3-D structures obtained by the proposed method were topologically comparable to their correspondent experimental structure.

Currently, one of the main research problems in Structural Bioinformatics is associated to the study and prediction of the 3-D structure of proteins. The 1990’s GENOME projects resulted in a large increase in the number of protein sequences. However, the number of identified 3-D protein structures have not followed the same growth trend. The number of protein sequences is much higher than the number of known 3-D structures. Many computational methodologies, systems and algorithms have been proposed to address the protein structure prediction problem. However, the problem still remains challenging because of the complexity and high dimensionality of a protein conformational search space. This work presents a new computational strategy for the 3-D protein structure prediction problem. A first principle strategy which uses database information for the prediction of the 3-D structure of polypeptides was developed. The proposed technique manipulates structural information from the PDB in order to generate torsion angles intervals. Torsion angles intervals are used as input to a genetic algorithm with a local-search operator in order to search the protein conformational space and predict its 3-D structure. Results show that the 3-D structures obtained by the proposed method were topologically comparable to their correspondent experimental structure.

Comprendre comment les mutations impactent l’activité d’une protéine reste un défi dans le domaine des sciences protéiques. Les méthodes biochimiques traditionnellement utilisées pour résoudre ce type de questionnement sont très puissantes mais sont laborieuses à mettre en œuvre. Des approches bioinformatiques ont été développées à cet égard pour surmonter ces contraintes. Dans cette thèse, nous explorons l'utilisation d'approches bioinformatiques pour comprendre le lien entre mutations et changements d'activité. Notre modèle d'étude est une enzyme bactérienne, la sucrose phosphorylase de Bifidobacterium adolescentis (BaSP). Cette glycosyl-hydrolase de la famille 13 (GH13) suscite l’intérêt de l'industrie en raison de sa capacité à synthétiser des disaccharides et des glycoconjugués originaux. Son activité consiste à transférer un glucose d'un donneur, le saccharose, à un accepteur qui peut être un monosaccharide ou un aglycone hydroxylé. La réaction enzymatique se déroule selon un mécanisme dit « double déplacement avec rétention de configuration », ce qui nécessite la formation d'un intermédiaire covalent dit glucosyl-enzyme. Cependant, la possibilité de contrôler la régiosélectivité de ce transfert pour qu'il soit applicable au niveau industriel est un enjeumajeur. Cette thèse vise d’une part, à fournir une explication rationnelle quant aux modifications de la régiosélectivité de BaSP apportées par des mutations et d’autre part à proposer un canevas pour le contrôle de la régiosélectivité de couplage en vue de la synthèse de disaccharides pré-biotiques rares comme le kojibiose et le nigerose. Dans notre approche, nous avons émis l'hypothèse que les orientations préférées de l'accepteur dans le site catalytique après formation du glycosyl-enzyme déterminent la régiosélectivité de l'enzyme. Nous avons utilisé des approches computationnelles pour étudier l'impact des mutations sur la liaison de l'accepteur à l'intermédiaire covalent, le glucosylenzyme. À cette fin, nous avons construit des modèles à l’échelle atomique du glucosyl-enzyme pour un ensemble de variants de la BaSP pour lesquels des données expérimentales étaient disponibles. Pour y parvenir, nous avons paramétré le glucosyl-aspartyle en tant que nouveau résidu et les avons intégré dans des outils de modélisation tels que Modeller et Gromacs. Nous avons évalué la pertinence de ces paramètres et les avons ensuite appliqués à la vérification de notre hypothèse de travail par le biais d’expériences d'ancrage moléculaire. La méthodologie utilisée dans ce travail ouvre la perspective de l'utilisation d'approches bioinformatiques pour l'ingénierie de la régiosélectivité de la sucrose phosphorylase et plus généralement des glycosylhydrolases possédant un mécanisme similaire. À cet égard, un pipeline de modélisation moléculaire et d'amarrage de molécules accepteurs sur des intermédiaires covalents des enzymes de cette famille (ENZO pour Optimisation d’ENZyme) a été développé au cours de cette thèse. Son application à l’ingénierie d’autres variants de BaSP est en cours. / In this thesis, we explore the usage of computational approaches for understanding the link between mutations and changes in protein activity. Our study model is a bacterial sucrose phosphorylase enzyme from Bifidobacterium adolescentis (BaSP). This glycosyl hydrolase from family 13 (GH13) has been a focus in the industry due to its ability to synthesize original disaccharides and glycoconjugates. In fact, its activity is to transfer a glucose moiety from a donor sucrose to an acceptor which can be a monosaccharide or a hydroxylated aglycone. The enzymatic reaction proceeds by a double displacement with retention of configuration mechanism whereby a covalent glucosyl-enzyme intermediate is formed. However, it is at stake to control the regioselectivity of this transfer for it to be applicable at industrial level. This thesis aimed at providing a rational explanation for the observed impact of mutations on the regioselectivity of BaSP in view of controlling the synthesis of rare pre-biotic disaccharides like kojibiose and nigerose. We hypothesized that the preferred orientations of the acceptor determines the regioselectivity of the enzyme. In that respect, we used computational approaches to investigate the impact of mutations on the binding of the acceptor to the glucosyl-enzyme intermediate. The methodology used in this work opens the perspective of using computational approaches for engineering the regioselectivity of of glycosyl hydrolases with similar mechanism.

Proteins adopt three-dimensional structures which serve as a starting point to understand protein function and their evolutionary ancestry. It is unclear how proteins fold in vivo and how this process can be recreated in silico in order to predict protein structure from sequence. Contact maps are a possibility to describe whether two residues are in spatial proximity and structures can be derived from this simplified representation. Coevolution or supervised machine learning techniques can compute contact maps from sequence: however, these approaches only predict sparse subsets of the actual contact map. It is shown that the composition of these subsets substantially influences the achievable reconstruction quality because most information in a contact map is redundant. No strategy was proposed which identifies unique contacts for which no redundant backup exists. The StructureDistiller algorithm quantifies the structural relevance of individual contacts and identifies crucial contacts in protein structures. It is demonstrated that using this information the reconstruction performance on a sparse subset of a contact map is increased by 0.4 A, which constitutes a substantial performance gain. The set of the most relevant contacts in a map is also more resilient to false positively predicted contacts: up to 6% of false positives are compensated before reconstruction quality matches a naive selection of contacts without any false positive contacts. This information is invaluable for the training to new structure prediction methods and provides insights into how robustness and information content of contact maps can be improved. In literature, the relevance of two types of residues for in vivo folding has been described. Early folding residues initiate the folding process, whereas highly stable residues prevent spontaneous unfolding events. The structural relevance score proposed by this thesis is employed to characterize both types of residues. Early folding residues form pivotal secondary structure elements, but their structural relevance is average. In contrast, highly stable residues exhibit significantly increased structural relevance. This implies that residues crucial for the folding process are not relevant for structural integrity and vice versa. The position of early folding residues is preserved over the course of evolution as demonstrated for two ancient regions shared by all aminoacyl-tRNA synthetases. One arrangement of folding initiation sites resembles an ancient and widely distributed structural packing motif and captures how reverberations of the earliest periods of life can still be observed in contemporary protein structures.

L'objet de cette thèse de bioinformatique est de mieux comprendre l’ensemble des systèmes de régulation génique chez les bactéries. La disponibilité de centaines de génomes complets chez les bactéries ouvre la voie aux approches de génomique comparative et donc à l’étude de l’évolution des réseaux transcriptionnels bactériens. Dans un premier temps, nous avons implémenté et validé plusieurs méthodes de prédiction d’opérons sur base des génomes bactériens séquencés. Suite à cette étude, nous avons décidé d’utiliser un algorithme qui se base simplement sur un seuil sur la distance intergénique, à savoir la distance en paires de bases entre deux gènes adjacents. Notre évaluation sur base d’opérons annotés chez Escherichia coli et Bacillus subtilis nous permet de définir un seuil optimal de 55pb pour lequel nous obtenons respectivement 78 et 79% de précision. Deuxièmement, l’identification des motifs de régulation transcriptionnelle, tels les sites de liaison des facteurs de transcription, donne des indications de l’organisation de la régulation. Nous avons développé une méthode de recherche d’empreintes phylogénétiques qui consiste à découvrir des paires de mots espacés (dyades) statistiquement sur-représentées en amont de gènes orthologues bactériens. Notre méthode est particulièrement adaptée à la recherche de motifs chez les bactéries puisqu’elle profite d’une part des centaines de génomes bactériens séquencés et d’autre part les facteurs de transcription bactériens présentent des domaines Hélice-Tour-Hélice qui reconnaissent spécifiquement des dyades. Une évaluation systématique sur 368 gènes de E.coli a permis d’évaluer les performances de notre méthode et de tester l’influence de plus de 40 combinaisons de paramètres concernant le niveau taxonomique, l’inférence d’opérons, le filtrage des dyades spécifiques de E.coli, le choix des modèles de fond pour le calcul du score de significativité, et enfin un seuil sur ce score. L’analyse détaillée pour un cas d’étude, l’autorégulation du facteur de transcription LexA, a montré que notre approche permet d’étudier l’évolution des sites d’auto-régulation dans plusieurs branches taxonomiques des bactéries. Nous avons ensuite appliqué la détection d’empreintes phylogénétiques à chaque gène de E.coli, et utilisé les motifs détectés comme significatifs afin de prédire les gènes co-régulés. Au centre de cette dernière stratégie, est définie une matrice de scores de significativité pour chaque mot détecté par gène chez l’organisme de référence. Plusieurs métriques ont été définies pour la comparaison de paires de profils de scores de sorte que des paires de gènes ayant des motifs détectés significativement en commun peuvent être regroupées. Ainsi, l’ensemble des nos méthodes nous permet de reconstruire des réseaux de co-régulation uniquement à partir de séquences génomiques, et nous ouvre la voie à l’étude de l’organisation et de l’évolution de la régulation transcriptionnelle pour des génomes dont on ne connaît rien.<p><p>The purpose of my thesis is to study the evolution of regulation within bacterial genomes by using a cross-genomic comparative approach. Nowadays, numerous genomes have been sequenced facilitating in silico analysis in order to detect groups of functionally related genes and to predict the mechanism of their relative regulation. In this project, we combined prediction of operons and regulons in order to reconstruct the transcriptional regulatory network for a bacterial genome. We have implemented three methods in order to predict operons from a bacterial genome and evaluated them on hundreds of annotated operons of Escherichia coli and Bacillus subtilis. It turns out that a simple distance-based threshold method gives good results with about 80% of accuracy. The principle of this method is to classify pairs of adjacent genes as “within operon” or “transcription unit border”, respectively, by using a threshold on their intergenic distance: two adjacent genes are predicted to be within an operon if their intergenic distance is smaller than 55bp. In the second part of my thesis, I evaluated the performances of a phylogenetic footprinting approach based on the detection of over-represented spaced motifs. This method is particularly suitable for (but not restricted to) Bacteria, since such motifs are typically bound by factors containing a Helix-Turn-Helix domain. We evaluated footprint discovery in 368 E.coli K12 genes with annotated sites, under 40 different combinations of parameters (taxonomical level, background model, organism-specific filtering, operon inference, significance threshold). Motifs are assessed both at the level of correctness and significance. The footprint discovery method proposed here shows excellent results with E. coli and can readily be extended to predict cis-acting regulatory signals and propose testable hypotheses in bacterial genomes for which nothing is known about regulation. Moreover, the predictive power of the strategy, and its capability to track the evolutionary divergence of cis-regulatory motifs was illustrated with the example of LexA auto-regulation, for which our predictions are remarkably consistent with the binding sites characterized in different taxonomical groups. A next challenge was to identify groups of co-regulated genes (regulons), by regrouping genes with similar motifs, in order to address the challenging domain of the evolution of transcriptional regulatory networks. We tested different metrics to detect putative pairs of co-regulated genes. The comparison between predicted and annotated co-regulation networks shows a high positive predictive value, since a good fraction of the predicted associations correspond to annotated co-regulations, and a low sensitivity, which may be due to the consequence of highly connected transcription factors (global regulator). A regulon-per-regulon analysis indeed shows that the sensitivity is very weak for these transcription factors, but can be quite good for specific transcription factors. The originality of this global strategy is to be able to infer a potential network from the sole analysis of genome sequences, and without any prior knowledge about the regulation in the considered organism. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Abstract Most proteins carry out their functions through interactions with other molecules. Thus, proteins taking part in similar interactions are likely to carry out related functions. One way to determine whether two proteins do take part in similar interactions is by quantifying the likeness of their structures. This work focuses on the development of methods for the comparison of protein-protein and protein-ligand interactions, as well as their application to structure-based classification schemes. A method based on the MultiMer-align (or MM-align) program was developed and used to compare all known dimeric protein complexes. The results of the comparison demonstrates that the method improves over MM-align in a significant number of cases. The data was employed to classify the complexes, resulting in 1,761 different protein-protein interaction types. Through a statistical model, the number of existing protein-protein interaction types in nature was estimated at around 4,000. The model allowed the establishment of a relationship between the number of quaternary families (sequence-based groups of protein-protein complexes) and quaternary folds (structure-based groups). The interactions between proteins and small organic ligands were studied using sequence-independent methodologies. A new method was introduced to test three similarity metrics. The best of these metrics was subsequently employed, together with five other existing methodologies, to conduct an all-to-all comparison of all the known protein-FAD (Flavin-Adenine Dinucleotide) complexes. The results demonstrates that the new methodology captures the best the similarities between complexes in terms of protein-ligand contacts. Based on the all-to-all comparison, the protein-FAD complexes were subsequently separated into 237 groups. In the majority of cases, the classification divided the complexes according to their annotated function. Using a graph-based description of the FAD-binding sites, each group could be further characterized and uniquely described. The study demonstrates that the newly developed methods are superior to the existing ones. The results indicate that both the known protein-protein and the protein-FAD interactions can be classified into a reduced number of types and that in general terms these classifications are consistent with the proteins' functions. / Tiivistelmä Suurin osa proteiinien toiminnasta tapahtuu vuorovaikutuksessa muiden molekyylien kanssa. Proteiinit, jotka osallistuvat samanlaisiin vuorovaikutuksiin todennäköisesti toimivat samalla tavalla. Kahden proteiinin todennäköisyys esiintyä samanlaisissa vuorovaikutustilanteissa voidaan määrittää tutkimalla niiden rakenteellista samankaltaisuutta. Tämä väitöskirjatyö käsittelee proteiini-proteiini- ja proteiini-ligandi -vuorovaikutusten vertailuun käytettyjen menetelmien kehitystä, ja niiden soveltamista rakenteeseen perustuvissa luokittelujärjestelmissä. Tunnettuja dimeerisiä proteiinikomplekseja tutkittiin uudella MultiMer-align-ohjelmaan (MM-align) perustuvalla menetelmällä. Vertailun tulokset osoittavat, että uusi menetelmä suoriutui MM-alignia paremmin merkittävässä osassa tapauksista. Tuloksia käytettiin myös kompleksien luokitteluun, jonka tuloksena oli 1761 erilaista proteiinien välistä vuorovaikutustyyppiä. Luonnossa esiintyvien proteiinien välisten vuorovaikutusten määrän arvioitiin tilastollisen mallin avulla olevan noin 4000. Tilastollisen mallin avulla saatiin vertailtua sekä sekvenssin (”quaternary families”) sekä rakenteen (”quaternary folds”) mukaan ryhmiteltyjen proteiinikompleksien määriä. Proteiinien ja pienien orgaanisten ligandien välisiä vuorovaikutuksia tutkittiin sekvenssistä riippumattomilla menetelmillä. Uudella menetelmällä testattiin kolmea eri samankaltaisuutta mittaavaa metriikkaa. Näistä parasta käytettiin viiden muun tunnetun menetelmän kanssa vertailemaan kaikkia tunnettuja proteiini-FAD (Flavin-Adenine-Dinucleotide, flaviiniadeniinidinukleotidi) -komplekseja. Proteiini-ligandikontaktien osalta uusi menetelmä kuvasi kompleksien samankaltaisuutta muita menetelmiä paremmin. Vertailun tuloksia hyödyntäen proteiini-FAD-kompleksit luokiteltiin edelleen 237 ryhmään. Suurimmassa osassa tapauksista luokittelujärjestelmä oli onnistunut jakamaan kompleksit ryhmiin niiden toiminnallisuuden mukaisesti. Ryhmät voitiin määritellä yksikäsitteisesti kuvaamalla FAD:n sitoutumispaikka graafisesti. Väitöskirjatyö osoittaa, että siinä kehitetyt menetelmät ovat parempia kuin aikaisemmin käytetyt menetelmät. Tulokset osoittavat, että sekä proteiinien väliset että proteiini-FAD -vuorovaikutukset voidaan luokitella rajattuun määrään vuorovaikutustyyppejä ja yleisesti luokittelu on yhtenevä proteiinien toiminnan suhteen.

Les interactions ADN-protéine sont fondamentales dans de nombreux processus biologiques tels que la régulation des gènes et la réparation de l'ADN. Cette thèse est centrée sur l'analyse des propriétés physiques et dynamiques des interfaces ADN-protéine. À partir de l'étude de quatre complexes ADN-protéine, nous avons montré que l'interface ADN-protéine est dynamique et que les ponts salins et liaisons hydrogène se forment et se rompent dans une échelle de temps de l'ordre de la centaine de picosecondes. L'oscillation des chaînes latérales des résidus est dans certains cas capable de moduler la spécificité d'interaction. Nous avons ensuite développé un modèle de protéine gros grains dans le but de décomposer les interactions ADN-protéine en identifiant les facteurs qui modulent la stabilité et la conformation de l'ADN ainsi que les facteurs responsables de la spécificité de reconnaissance ADN-protéine. Notre modèle est adaptable, allant d'un simple volume mimant une protéine à une représentation plus complexe comportant des charges formelles sur les résidus polaires, ou des chaînes latérales à l'échelle atomique dans le cas de résidus clés ayant des comportements particuliers, tels que les cycles aromatiques qui s'intercalent entre les paires de base de l'acide nucléique / DNA-protein interactions are fundamental in many biological processes such as gene regulation and DNA repair. This thesis is focused on an analysis of the physical and dynamic properties of DNA-protein interfaces. In a study of four DNA-protein complexes, we have shown that DNA-protein interfaces are dynamic and that the salt bridges and hydrogen bonds break and reform over a time scale of hundreds of picoseconds. In certain cases, this oscillation of protein side chains is able to modulate interaction specificity. We have also developed a coarse-grain model of proteins in order to deconvolute the nature of protein-DNA interactions, identifying factors that modulate the stability and conformation of DNA and factors responsible for the protein-DNA recognition specificity. The design of our model can be changed from a simple volume mimicking the protein to a more complicated representation by the addition of formal charges on polar residues, or by adding atomic-scale side chains in the case of key residues with more precise behaviors, such as aromatic rings that intercalate between DNA base pairs