As convulsões febris complexas durante a infância representam um fator de risco relevante para o desenvolvimento da epilepsia. Apesar desse fato, as alterações moleculares induzidas por essas crises febris, que tornam o cérebro susceptível ao processo de epileptogênese, ainda são pouco conhecidas. Nesse contexto, a utilização de modelos animais de crises febris induzidas por hipertermia (HS) permite o estudo das alterações moleculares a partir de uma análise temporal desse processo. Assim, neste trabalho foram investigadas as alterações temporais nos perfis de microRNAs e de expressão gênica em explantes da região CA3 hipocampal de ratos Wistar obtidas em quatro intervalos de tempo após o insulto hipertérmico no décimo primeiro dia pós-natal (P11). Os intervalos temporais foram selecionados para avaliar as fases aguda (P12), latente (P30 e P60) e crônica (P120). A análise transcriptômica consistiu na construção de redes de co-expressão gênica, permitindo a identificação de módulos de genes e sua relação com os grupos experimentais e intervalos de tempo selecionados. Os genes também foram caracterizados hierarquicamente, identificando-se genes que conferem robustez às redes de co-expressão gênica (hubs). Além disso, foram avaliados o perfil de expressão diferencial de microRNAs e feita a análise integrada da expressão de microRNAs e expressão gênica dos hubs. Os resultados deste trabalho mostraram que: i) o insulto hipertérmico leva a alterações importantes no desenvolvimento e funcionamento cerebral ii) essas alterações estão associadas a uma assinatura temporal, presumivelmente da epileptogênese à readaptação do cérebro frente ao insulto precipitante inicial; iii) isso envolve um mecanismo de regulação das redes de co-expressão gênica por microRNAs. Esses resultados sugerem que as alterações transcricionais desencadeadas pelo insulto febril podem levar à reprogramação neuronal e ao remodelamento da cromatina, tornando o cérebro susceptível ao processo epiléptico crônico. Como nas epilepsias humanas por insulto febril, o modelo em rato reflete um processo que vai da epileptogênese à cronificação na fase adulta. Como muitos dos casos de epilepsia por insulto febril são refratários a drogas anticonvulsivantes, o entendimento temporal dos mecanismos moleculares envolvidos nesse tipo de epilepsia é relevante para se identificar alvos terapêuticos e desenvolver drogas anti-epileptogênicas / Complex febrile seizures during childhood represent a relevant risk factor for the development of epilepsy. Despite this fact, the molecular alterations induced by febrile seizures that make the brain susceptible to the process of epileptogenesis are still poorly understood. In this context, the animal models of febrile seizures induced by hyperthermia (HS) allow the study of the molecular alterations from a temporal perspective. Thus, we investigated the temporal alterations in the profiles of gene expression and microRNAs in explants of the hippocampal CA3 region of Wistar rats, here obtained at four-time intervals after the hyperthermal insult on the eleventh postnatal day (P11). Time intervals were selected to evaluate the acute (P12), latent (P30 and P60) and chronic (P120) phases. Transcriptomic analysis consisted of constructing gene co-expression networks, allowing the identification of gene modules related to selected time intervals. Genes were also characterized hierarchically identifying those that control the robustness of gene co-expression networks (hubs). In addition, the differential expression profile of microRNA and the integrated analysis of microRNA expression and hub\'s gene expression were evaluated. The results of this work showed that: i) hyperthermic insults lead to important changes in cerebral development and functioning related to febrile seizures; ii) each time interval shows a transcriptomic signature, probably reflecting the process from epileptogenesis to brain readaptation after the initial precipitating insult; iii) this process involves a mechanism of regulation of gene co-expression networks by microRNAs. These results suggest that transcriptional changes triggered by febrile insults may lead to neuronal reprogramming and chromatin remodeling, making the brain susceptible to the chronic epileptic process. Human epilepsy triggered by febrile insults in childhood is related to resistance to antiepileptic drugs and no anti-epileptogenic drug was developed so far. Therefore, a better understanding of the temporal mechanisms involved in the development of chronic epilepsy is mandatory in order to discover new therapeutic targets and, eventually, anti-epileptogenic drugs

Leung Ka-Kit. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 129-131). / Abstracts in English and Chinese. / Abstract --- p.1 / Chapter CHAPTER 1. --- introduction --- p.14 / Chapter 1.1 --- Preamble --- p.14 / Chapter 1.2 --- Biological background --- p.14 / Chapter CHAPTER 2. --- previous related work --- p.18 / Chapter 2.1 --- Protein functionality analysis --- p.18 / Chapter 2.1.1 --- Analysis from primary structure --- p.18 / Chapter 2.1.2 --- Analysis from tertiary structure --- p.20 / Chapter 2.2 --- Secondary structure prediction --- p.21 / Chapter 2.3 --- Motivation - Challenges from protein complexity --- p.22 / Chapter CHAPTER 3. --- mathematical representations for protein properties and sequence alignment --- p.24 / Chapter 3.1 --- Secondary structure sequence model --- p.24 / Chapter 3.2 --- Substitution matrix --- p.26 / Chapter 3.3 --- Gap --- p.26 / Chapter 3.4 --- Similarity measurement --- p.27 / Chapter 3.5 --- Geometric Model for Protein --- p.28 / Chapter CHAPTER 4. --- overall system design --- p.30 / Chapter 4.1 --- System architecture and design --- p.30 / Chapter 4.2 --- System environment --- p.32 / Chapter 4.3 --- Experimental data --- p.32 / Chapter CHAPTER 5. --- adaptive dynamic programming (adp)- general global alignment consideration --- p.35 / Chapter 5.1 --- t-triangles cutting --- p.35 / Chapter 5.1.1 --- Theoretical time and memory requirements of ADP with z-triangles cutting --- p.43 / Chapter 5.1.1.1 --- Study of parameters affecting h in case 1 --- p.44 / Chapter 5.1.1.2 --- Study of parameters affecting h in case 2 --- p.45 / Chapter 5.1.2 --- Experimental results of ADP with z-triangles cutting --- p.46 / Chapter 5.2 --- Constructing the path matrix by expansion --- p.51 / Chapter 5.2.1 --- Time and memory requirements of EXPAND --- p.57 / Chapter 5.2.2 --- Experimental results and discussions --- p.58 / Chapter CHAPTER 6. --- adp - global alignment of sequences with consecutive repeated characters --- p.65 / Chapter 6.1 --- Estimation of similarity upper bound (Ba) --- p.65 / Chapter 6.1.1 --- Sequence composition (SC) consideration --- p.65 / Chapter 6.1.2 --- Implementation of SC --- p.67 / Chapter 6.1.3 --- Experimental results --- p.69 / Chapter 6.1.4 --- Overall trend of change of structures (OTCS) --- p.74 / Chapter 6.1.5 --- Uninformed search --- p.76 / Chapter 6.2 --- Short-cut --- p.80 / Chapter 6.2.1 --- Time and memory requirements --- p.86 / Chapter 6.2.2 --- Experimental results and discussions --- p.86 / Chapter CHAPTER 7. --- ga based topology discovery --- p.87 / Chapter 7.1 --- Chromosome encoding --- p.87 / Chapter 7.2 --- Non-sequential order penalty --- p.88 / Chapter 7.3 --- Fitness function --- p.88 / Chapter 7.4 --- Genetic operators --- p.88 / Chapter 7.4.1 --- Hop operator --- p.89 / Chapter 7.4.2 --- Inverse operator --- p.89 / Chapter 7.4.3 --- Shift operator --- p.90 / Chapter 7.4.4 --- Selection pressure --- p.90 / Chapter 7.5 --- Selection of progeny --- p.91 / Chapter 7.6 --- Implementation --- p.91 / Chapter 7.6.1 --- Size of population and generation --- p.91 / Chapter 7.6.2 --- Parallelization --- p.91 / Chapter 7.6.3 --- Crowding Handling --- p.92 / Chapter 7.6.4 --- Selection of progeny --- p.92 / Chapter 7.7 --- Results of alignment with GA exploration on topological order --- p.93 / Chapter CHAPTER 8. --- FILTERING OF FALSE POSITIVES --- p.103 / Chapter 8.1 --- Alignment Segments to Gap Ratio (ASGR) --- p.103 / Chapter 8.2 --- Tolerance --- p.104 / Chapter 8.3 --- Overall trend of change of structures (OTCS) --- p.104 / Chapter 8.4 --- Results and discussions --- p.105 / Chapter CHAPTER 9. --- SECONDARY STRUCTURE PREDICTION --- p.111 / Chapter 9.1 --- 3-STATE SECONDARY STRUCTURE PREDICTION IMPROVEMENT --- p.111 / Chapter 9.2 --- 8-state secondary structure prediction --- p.117 / Chapter 9.3 --- Iterative Subordinate Voting (IS V) --- p.117 / Chapter 9.4 --- ISV Results and discussion --- p.119 / Chapter CHAPTER 10. --- CONCLUSIONS --- p.123 / Chapter 10.1 --- Contributions --- p.123 / Chapter 10.2 --- Future Work --- p.126 / Chapter 10.2.1 --- Using database indexing --- p.126 / Chapter 10.2.2 --- 3-state secondary structure prediction improvement --- p.127 / appendix --- p.128 / Chapter ´Ø --- Interpretation on the dp一filter results --- p.128

Uma das tarefas mais básicas em bioinformática é a comparação de seqüências feita por algoritmos de alinhamento, que modelam as alterações evolutivas nas seqüências biológicas através de mutações como inserção, remoção e substituição de símbolos. Este trabalho trata de generalizações nos algoritmos de alinhamento que levam em consideração outras mutações conhecidas como rearranjos, mais especificamente, inversões, duplicações em tandem e duplicações por transposição. Alinhamento com inversões não tem um algoritmo polinomial conhecido e uma simplificação para o problema que considera somente inversões não sobrepostas foi proposta em 1992 por Schöniger e Waterman. Em 2003, dois trabalhos independentes propuseram algoritmos com tempo O(n^4) para alinhar duas seqüências com inversões não sobrepostas. Desenvolvemos dois algoritmos que resolvem este mesmo problema: um com tempo de execução O(n^3 logn) e outro que, sob algumas condições no sistema de pontuação, tem tempo de execução O(n^3), ambos em memória O(n^2). Em 1997, Benson propôs um modelo de alinhamento que reconhecesse as duplicações em tandem além das inserções, remoções e substituições. Ele propôs dois algoritmos exatos para alinhar duas seqüências com duplicações em tandem: um em tempo O(n^5) e memória O(n^2), e outro em tempo O(n^4) e memória O(n^3). Propomos um algoritmo para alinhar duas seqüências com duplicações em tandem em tempo O(n^3) e memória O(n^2). Propomos também um algoritmo para alinhar duas seqüências com transposons (um tipo mais geral que a duplicação em tandem), em tempo O(n^3) e memória O(n^2). / Sequence comparison done by alignment algorithms is one of the most fundamental tasks in bioinformatics. The evolutive mutations considered in these alignments are insertions, deletions and substitutions of nucleotides. This work treats of generalizations introduced in alignment algorithms in such a way that other mutations known as rearrangements are also considered, more specifically, we consider inversions, duplications in tandem and duplications by transpositions. Alignment with inversions does not have a known polynomial algorithm and a simplification to the problem that considers only non-overlapping inversions were proposed by Schöniger and Waterman in 1992. In 2003, two independent works proposed algorithms with O(n^4) time to align two sequences with non-overlapping inversions. We developed two algorithms to solve this problem: one in O(n^3 log n) time and other, considering some conditions in the scoring system, in O(n^3) time, both in O(n^2) memory. In 1997, Benson proposed a model of alignment that recognized tandem duplication, insertion, deletion and substitution. He proposed two exact algorithms to align two sequences with tandem duplication: one in O(n^5) time and O(n^2) memory, and other in O(n^4) time and O(n^3) memory. We propose one algorithm to align two sequences with tandem duplication in O(n^3) time and O(n^2) memory. We also propose one algorithm to align two sequences with transposons (a type of duplication more general than tandem duplication), in O(n^3) time and O(n^2) memory.

Leung Ka-Kit. / Thesis submitted in: November 2004. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 67-71). / Abstracts in English and Chinese. / Abstract / Chapter CHAPTER 1. --- INTRODUCTION --- p.1 / Chapter 1.1 --- Background of protein structures --- p.1 / Chapter 1.2 --- Background of protein-protein interaction (PPI) --- p.4 / Chapter 1.2.1 --- Quaternary structure and protein complex --- p.4 / Chapter 1.2.2 --- Previous related work --- p.4 / Chapter 1.2.3 --- The kinetic and thermodynamic formalism --- p.6 / Chapter CHAPTER 2. --- MATERIALS AND METHODS --- p.10 / Chapter 2.1 --- Amino acid composition representative power modeling --- p.10 / Chapter 2.1.1 --- Propensity level modeling --- p.10 / Chapter 2.1.2 --- Polar atoms visualization --- p.17 / Chapter 2.2 --- Rigid structure representative power modeling --- p.17 / Chapter 2.3 --- Electrostatic potential modeling --- p.17 / Chapter 2.3.1 --- Charge residence --- p.17 / Chapter 2.3.2 --- Minimum Ribbon (MR) --- p.19 / Chapter 2.4 --- Examination of interface --- p.23 / Chapter 2.5 --- Identification procedures of a binding site --- p.24 / Chapter 2.6 --- System requirements --- p.24 / Chapter CHAPTER 3. --- RESULTS AND DISCUSSIONS --- p.24 / Chapter 3.1 --- Polar atoms --- p.25 / Chapter 3.2 --- Minimum Ribbon (MR) --- p.27 / Chapter 3.3 --- "Charge complementarity, propensity level and rigid structure orientation" --- p.31 / Chapter 3.4 --- Identification of interacting site --- p.36 / Chapter CHAPTER 4. --- CONCLUSIONS --- p.64 / System requirements --- p.65 / Basic operation --- p.65 / Limitation --- p.66

Submitted by Fabíola Silva (fabiola.silva@famerp.br) on 2018-02-19T12:03:16Z No. of bitstreams: 1 thiagohenrique_tese.pdf: 1021380 bytes, checksum: c215716ce3befdfb390cce0309052b80 (MD5) / Made available in DSpace on 2018-02-19T12:03:16Z (GMT). No. of bitstreams: 1 thiagohenrique_tese.pdf: 1021380 bytes, checksum: c215716ce3befdfb390cce0309052b80 (MD5) Previous issue date: 2016-05-16 / Introduction: The total amount of scientific literature on cancer has grown rapidly in recent years. This makes it difficult, if not impossible, to manually retrieve relevant information on the mechanisms that govern the neoplastic process. Furthermore, cancer is a complex disease, and its. Heterogeneity is particularly evident in head and neck squamous cell carcinoma (HNSCC); one of the most common types of cancer worldwide. Objectives: The present study aimed: a) to identify genes/proteins related to HNSCC; b) to identify ligands that specifically target molecular biomarkers of interest; c) to evaluate computationally protein-ligand complexes and d) to evaluate the effect of ligands on gene expression and on carcinoma cell behavior. Methods: The search for potential markers related to HNSCC was performed by literature mining, following a flow chart that included selection of scientific articles in PubMed by MeSH terms, association of articles with genes/proteins through the gene2pubmed file, selection of genes in external data bases and manual curation steps. In order to identify potential ligands, proteins related to HNSCC and involved in inflammatory processes were used to perform molecular docking assays with known anti-inflammatory drugs. Finally, the role of piplartine, a substance extracted from the Piper longum with anti-inflammatory and antineoplastic effects, on proliferation, migration and gene expression was investigated in neoplastic cells. Results: The curated gene-to-publication assignment yielded a total of 1,370 genes related to HNSCC, with specificity of 74% and sensibility of 87%. The diversity of results allowed identifying new and mostly unexplored gene associations, revealing, for example, that processes linked to response to steroid hormone stimulus are significantly enriched with genes related to HNSCC. The results also showed that piplartine decreases viability and cell migration, and alters expression of genes involved in inflammatory responses. Conclusion: This approach allows the identification of genes related to HNSCC and is able to reveal new associations that deserve to be further studied. Piplartine, the compound selected for in vitro studies, interacts with molecular targets similar to known anti-inflammatory drugs, decreases proliferation and cell migration, and alter the expression of genes associated with HNSCC and inflammatory processes. / Introdução: A literatura científica sobre câncer tem crescido rapidamente nos últimos anos, o que torna difícil, se não impossível, a tarefa de recuperar e analisar manualmente as informações relevantes sobre os mecanismos que governam o processo neoplásico. Além disso, o câncer é uma doença complexa e sua heterogeneidade é particularmente evidente no câncer epidermoide de cabeça e pescoço (CECP), um dos tipos mais comuns de câncer em todo o mundo. Objetivos: Os objetivos do estudo foram (a) identificar genes/proteinas relacionados a CECP a partir de dados da literatura, (b) identificar ligantes que interajam eficiente e especificamente com alvos moleculares selecionados, (c) avaliar computacionalmente o complexo proteína/ligante e (d) avaliar a ação de ligantes na expressão gênica e no comportamento de células de carcinoma. Métodos: A busca de marcadores potenciais relacionados a CECP utilizou a mineração da literatura disponível publicamente, seguindo um fluxograma que incluiu seleção de artigos científicos no PubMed por termos MeSH, associação de artigos com genes/proteínas por meio do arquivo gene2pubmed, seleção de genes em bancos de dados externos e etapas de curação manual. As proteínas identificadas como sendo relacionadas a CECP que apresentaram envolvimento em processos inflamatórios foram submetidas a experimento de docking molecular para identificação de seus ligantes entre drogas disponíveis no mercado. Finalmente, o papel da piplartina, uma substância natural extraída da pimenta Piper longum com evidências de ação anti-inflamatória e antineoplásica, foi avaliado na proliferação, na migração e na expressão gênica de células neoplásicas. Resultados: Um total de 1370 genes relacionados a CECP foi identificado pela abordagem proposta, que mostrou especificidade de 74% e sensibilidade de 87%. A diversidade dos dados permitiu obter associações potenciais ainda não exploradas, revelando, por exemplo, que a resposta ao estímulo esteróide hormonal está significativamente enriquecida com genes relacionados a CECP. Os resultados também mostraram que a piplartina reduz a viabilidade e a migração celular e modifica o padrão de expressão de um painel de genes que atuam em processos inflamatórios. Conclusão: A abordagem empregada permite a identificação de genes relacionados à CECP e revela novas associações que merecem ser estudadas. O composto piplartina selecionado para estudos in vitro interage com alvos moleculares de forma semelhante à de medicamentos anti-inflamatórios conhecidos e é capaz de diminuir a proliferação e a migração celular e de alterar a expressão de genes relacionados à CECP e a processos inflamatórios.

Changes in the structure, content and morphology of chromosomes accumulate over evolutionary time and contribute to cell, developmental and organismal biology. The axolotl (Ambystoma mexicanum) is an important model for studying these changes because: 1) it provides important phylogenetic perspective for reconstructing the evolution of vertebrate genomes and amphibian karyotypes, 2) its genome has evolved to a large size (~10X larger than human) but has maintained gene orders, and 3) it possesses potentially young sex chromosomes that have not undergone extensive differentiation in the structure that is typical of many other vertebrate sex chromosomes (e.g. mammalian XY chromosomes and avian ZW chromosomes). Early chromosomal studies were performed through cytogenetics, but more recent methods involving next generation sequencing and comparative genomics can reveal new information. Due to the large size and inherent complexity of the axolotl genome, multiple approaches are needed to cultivate the genomic and molecular resources essential for expanding its utility in modern scientific inquiries. This dissertation describes our efforts to improve the genomic and molecular resources for the axolotl and other salamanders, with the aim of better understanding the events that have driven the evolution of vertebrate (and amphibian) chromosomes. First, I review our current state of knowledge with respect to genome and karyotype evolution in the amphibians, present a case for studying sex chromosome evolution in the axolotl, and discuss solutions for performing analyses of large vertebrate genomes. In the second chapter, I present a study that resulted in the optimization of methods for the capture and sequencing of individual chromosomes and demonstrate the utility of the approach in improving the existing Ambystoma linkage map and generating targeted assemblies of individual chromosomes. In the third chapter, I present a published work that focuses on using this approach to characterize the two smallest chromosomes and provides an initial characterization of the huge axolotl genome. In the fourth chapter, I present another study that details the development of a dense linkage map for a newt, Notophthalmus viridescens, and its use in comparative analyses, including the discovery of a specific chromosomal fusion event in Ambystoma at the site of a major effect quantitative trait locus for metamorphic timing. I then describe the characterization of the relatively undifferentiated axolotl sex chromosomes, identification of a tiny sex-specific (W-linked) region, and a strong candidate for the axolotl sex-determining gene. Finally, I provide a brief discussion that recapitulates the main findings of each study, their utility in current studies, and future research directions. The research in this dissertation has enriched this important model with genomic and molecular resources that enhance its use in modern scientific research. The information provided from evolutionary studies in axolotl chromosomes shed critical light on vertebrate genome and chromosome evolution, specifically among amphibians, an underrepresented vertebrate clade in genomics, and in homomorphic sex chromosomes, which have been largely unstudied in amphibians.

Soil and root microbial communities have been studied for decades, and the incorporation of high-throughput techniques and analysis has allowed the identification of endophytic/non-culturable organisms. This has helped characterize and establish the core microbiome of many model plant species which include underground and aboveground organs. Unfortunately, the information obtained from some of these model plants is not always transferable to other agronomic species. In this project, we decided to study the microbiome of the Nicotiana genus because of its importance in plant physiological and plant-microbe interactions studies. The data obtained was used as baseline information that allowed us to better understand the effect of microbial inoculums on the assembly of the microbiome of the plant. We analyzed 16s rRNA amplicons to survey the microbiome in different plant organs and rhizosphere from four different species. Bacterial strains evaluated were screened for a consistent reduction or improvement in plant growth. Four bacterial strains were tested and used as seed inoculum (Lf-Lysinobacillus fusisormis, Ms –Micrococcus sp., Bs–Bacillus sp., Bc–Bacillus cereus). Bs and Bc inoculants caused plant growth promotion, and in contrast Ms caused retarded growth, while Lf acted as a neutral or non-inducing phenotype strain. Data supported that microbial inoculum used as seed treatment caused systemic changes in the host plant microbiome. Functionality of the inoculum was studied and the response in plant growth was linked to hormonal changes (evaluated in the plant and in the bacterial strains). Gene expression analysis using a genome-scale approach revealed that genes that could possibly be involved in stress response are down-regulated for Bc and Bs treatments and up-regulated for Ms. Flexibility variability of the inoculum was also evaluated to have a better understanding of the main factors involved in the promotion or suppression of growth, and possibly its effect in following generations. In summary, the findings of this project support that the plant functional microbiome responds to exogenous stimulation from abiotic and biotic factors by adapting endogenous hormone responses.

Fibronectin is an important protein that is able to bind to other fibronectin molecules and to cell surface receptors. In doing so, the interactions fibronectin can perform is important for the processes of cell migration and tissue formation. Understanding the properties of fibronectin and fibril assembly is useful for areas such as wound healing, where fibronectin molecules are assembled to protect the tissue and to perform other tasks. Because of these reasons, it is important to understand how fibronectin is assembled and how its properties affect the fibril assembly, which in return affects the way the cell matrix operates. Previously published papers illustrate that the properties of fibronectin affect the mechanotransduction process, the cell conversion of mechanical stimulus to chemical, and this leads to various changes of the fibril assembly. However, the question that now comes to focus is what variables affect the fibril assembly? The two main variables that come into question is the substrate stiffness (ksub) (pN/nm) and the actin velocity (Vu) (nm/s). In order to test this hypothesis, several fibril assembly simulations were performed via MATLAB based upon the Weinberg-Mair-Lemmon Fibronectin Model. These simulations were performed by varying the parameters of substrate stiffness and actin velocity as well as fibril size, which affect the various measurements of the fibronectin, such as stretched length, relaxed length, etc. Through these various experiments, it was determined that the actin velocity and fibril size had the greatest impacts in affecting the fibronectin’s properties and its assembly.

Genomic search tools can provide valuable insights into the chemical structure, evolutionary origin and biochemical function of genetic material. A homology search algorithm compares a protein or nucleotide query sequence to each entry in a large sequence database and reports alignments with highly similar sequences. The exponential growth of public data banks such as GenBank has necessitated the development of fast, heuristic approaches to homology search. The versatile and popular blast algorithm, developed by researchers at the US National Center for Biotechnology Information (NCBI), uses a four-stage heuristic approach to efficiently search large collections for analogous sequences while retaining a high degree of accuracy. Despite an abundance of alternative approaches to homology search, blast remains the only method to offer fast, sensitive search of large genomic collections on modern desktop hardware. As a result, the tool has found widespread use with millions of queries posed each day. A significant investment of computing resources is required to process this large volume of genomic searches and a cluster of over 200 workstations is employed by the NCBI to handle queries posed through the organisation's website. As the growth of sequence databases continues to outpace improvements in modern hardware, blast searches are becoming slower each year and novel, faster methods for sequence comparison are required. In this thesis we propose new techniques for fast yet accurate homology search that result in significantly faster blast searches. First, we describe improvements to the final, gapped alignment stages where the query and sequences from the collection are aligned to provide a fine-grain measure of similarity. We describe three new methods for aligning sequences that roughly halve the time required to perform this computationally expensive stage. Next, we investigate improvements to the first stage of search, where short regions of similarity between a pair of sequences are identified. We propose a novel deterministic finite automaton data structure that is significantly smaller than the codeword lookup table employed by ncbi-blast, resulting in improved cache performance and faster search times. We also discuss fast methods for nucleotide sequence comparison. We describe novel approaches for processing sequences that are compressed using the byte packed format already utilised by blast, where four nucleotide bases from a strand of DNA are stored in a single byte. Rather than decompress sequences to perform pairwise comparisons, our innovations permit sequences to be processed in their compressed form, four bases at a time. Our techniques roughly halve average query evaluation times for nucleotide searches with no effect on the sensitivity of blast. Finally, we present a new scheme for managing the high degree of redundancy that is prevalent in genomic collections. Near-duplicate entries in sequence data banks are highly detrimental to retrieval performance, however existing methods for managing redundancy are both slow, requiring almost ten hours to process the GenBank database, and crude, because they simply purge highly-similar sequences to reduce the level of internal redundancy. We describe a new approach for identifying near-duplicate entries that is roughly six times faster than the most successful existing approaches, and a novel approach to managing redundancy that reduces collection size and search times but still provides accurate and comprehensive search results. Our improvements to blast have been integrated into our own version of the tool. We find that our innovations more than halve average search times for nucleotide and protein searches, and have no signifcant effect on search accuracy. Given the enormous popularity of blast, this represents a very significant advance in computational methods to aid life science research.

Although the tremendous catalytic power of enzymes is widely recognized, their exact mechanisms of action are still a source of debate. In order to elucidate the origin of their power, it is necessary to look at individual residues and atoms, and establish their contribution to ligand binding, activation, and reaction. Given the present limitations of experimental techniques, only computational tools allow for such detailed analysis. During my PhD studies I have applied a variety of computational methods, reviewed in Chapter 2, to the study of two enzymes: DfrB dihydrofolate reductase (DHFR) and methyltetrahydrofolate: corrinoid/iron-sulfur protein methyltransferase (MeTr). ¶ The DfrB enzyme has intrigued microbiologists since it was discovered thirty years ago, because of its simple structure, enzymatic inefficiency, and its insensitivity to trimethoprim. This bacterial enzyme shows neither structural nor sequence similarity with its chromosomal counterpart, despite both catalysing the reduction of dihydrofolate (DHF) using NADPH as a cofactor. As numerous attempts to obtain experimental structures of an enzyme ternary complex have been unsuccessful, I combined docking studies and molecular dynamics simulations to produce a reliable model of the reactive DfrB•DHF•NADPH complex. These results, combined with published empirical data, showed that multiple binding modes of the ligands are possible within DfrB. ¶ Comprehensive sequence and structural analysis provided further insight into the DfrB family. The presence of the dfrB genes within integrons and their level of sequence conservation suggest that they are old structures that had been diverging well before the introduction of trimethoprim. Each monomer of the tetrameric active enzyme presents an SH3-fold domain; this is a eukaryotic auxiliary domain never found before as the sole domain of a protein, let alone as the catalytic one. Overall, DfrB DHFR seems to be a poorly adapted catalyst, a ‘minimalistic’ enzyme that promotes the reaction by facilitating the approach of the ligands rather than by using specific catalytic residues. ¶ MeTr initiates the Wood-Ljungdahl pathway of anaerobic CO2 fixation. It catalyses the transfer of the N5-methyl group from N5-methyltetrahydrofolate (CH3THF) to the cobalt centre of a corrinoid/iron-sulfur protein. For the reaction to occur, the N5 position of CH3THF is expected to be activated by protonation. As experimental studies have led to conflicting suggestions, computational approaches were used to address the activation mechanism. ¶ Initially, I tested the accuracy of quantum mechanical (QM) methods to predict protonation positions and pKas of pterin, folate, and their analogues. Then, different protonation states of CH3THF and active-site aspartic residues were analysed. Fragment QM calculations suggested that the pKa of N5 in CH3THF is likely to increase upon protein binding. Further, ONIOM calculations which accounted for the complete protein structure indicated that active-site aspartic residues are likely to be protonated before the ligand. Finally, solvation and binding free energies of several protonated forms of CH3THF were compared using the thermodynamic integration approach. Taken together, these preliminary results suggest that further work with particular emphasis on the protonation state of active-site aspartic residues is needed in order to elucidate the protonation and activation mechanism of CH3THF within MeTr.