Submitted by Aline Batista (alinehb.ufpel@gmail.com) on 2018-04-18T14:49:00Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Augusto_Schmidt.pdf: 1380825 bytes, checksum: 43661cd55f67f8a90201f1208716e6c9 (MD5) / Approved for entry into archive by Aline Batista (alinehb.ufpel@gmail.com) on 2018-04-19T14:43:09Z (GMT) No. of bitstreams: 2 Dissertacao_Augusto_Schmidt.pdf: 1380825 bytes, checksum: 43661cd55f67f8a90201f1208716e6c9 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-04-19T14:43:17Z (GMT). No. of bitstreams: 2 Dissertacao_Augusto_Schmidt.pdf: 1380825 bytes, checksum: 43661cd55f67f8a90201f1208716e6c9 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-07-18 / Sem bolsa / Motivos não são entidades aleatórias encontradas em cadeias de DNA, podendo ser definidos como um fenômeno não único dentro de uma sequência genética. Os motivos, além de ter padrões recorrentes nas sequências analisadas, também possuem uma função biológica. Os algoritmos evolutivos são amplamente utilizados para encontrar soluções para otimização e padrões de pesquisa na área de ciência da computação. Encontrar motivos em sequências de genes é um dos problemas mais importantes na bioinformática e pertence à classe NP-Difícil. Portanto, é plausível investigar a hibridação de ferramentas consolidadas, mas limitadas em seu desempenho, em combinação com técnicas de algoritmos evolutivos. Este trabalho tem a premissa de mostrar uma pesquisa das principais técnicas e conceitos de algoritmos evolutivos utilizados na descoberta de padrões (motivos) na em moléculas e também um estudo aprofundado dos principais algoritmos de bioinformática que são utilizados para esta função em recentes anos por pesquisadores. Entende-se que tais técnicas em combinação, podem obter resultados interessantes para pesquisa em bioinformática. Assim, propondo uma arquitetura otimizada para descoberta de motivos em moléculas de regiões promotoras da bactéria. Usando tanto algoritmos evolutivos, como algoritmos de bioinformática e técnicas de refinação de seus principais dados fornecidos pelos algoritmos utilizados. Assim, formando uma arquitetura com melhor desempenho devido à hibridização de ferramentas consolidadas para buscar padrões em expressões genéticas. / Motifs are not random entities found in DNA strands, and can be defined as a nonunique phenomenon within a genetic sequence. Motifs, besides having recurrent patterns in the analyzed sequences, also have a biological function. Evolutionary algorithms are widely used to find solutions for optimization and research standards in the area of computer science. Finding motifs in gene sequences is one of the most important problems in bioinformatics and belongs to the NP-Difficult class. Therefore, it is plausible to investigate the hybridization of consolidated but limited tools in their performance, in combination with evolutionary algorithm techniques. This work has the premise of showing a research of the main techniques and concepts of evolutionary algorithms used in the discovery of patterns in molecules and also an in depth study of the main bioinformatics algorithms that have been used for this function in recent years by researchers. It is understood that such techniques in combination may yield interesting results for research in bioinformatics. Thus, proposing an architecture optimized for the discovery of motifs in molecules of promoter regions of the bacterium. Using both evolutionary algorithms, bioinformatics algorithms and refining techniques of its main data provided by the algorithms used. Thus, forming an architecture with better performance due to the hybridization of consolidated tools to look for patterns in genetic expressions.

Les facteurs de transcription sont des protéines spécialisées qui jouent un rôle important dans différents processus biologiques tel que la différenciation, le cycle cellulaire et la tumorigenèse. Ils régulent la transcription des gènes en se fixant sur des séquences d’ADN spécifiques (éléments cis-régulateurs). L’identification de ces éléments est une étape cruciale dans la compréhension des réseaux de régulation des gènes. Avec l’avènement des technologies de séquençage à haut débit, l’identification de tout les éléments fonctionnels dans les génomes, incluant gènes et éléments cis-régulateurs a connu une avancée considérable. Alors qu’on est arrivé à estimer le nombre de gènes chez différentes espèces, l’information sur les éléments qui contrôlent et orchestrent la régulation de ces gènes est encore mal définie. Grace aux techniques de ChIP-chip et de ChIP-séquençage il est possible d’identifier toutes les régions du génome qui sont liées par un facteur de transcription d’intérêt. Plusieurs approches computationnelles ont été développées pour prédire les sites fixés par les facteurs de transcription. Ces approches sont classées en deux catégories principales: les algorithmes énumératifs et probabilistes. Toutefois, plusieurs études ont montré que ces approches génèrent des taux élevés de faux négatifs et de faux positifs ce qui rend difficile l’interprétation des résultats et par conséquent leur validation expérimentale. Dans cette thèse, nous avons ciblé deux objectifs. Le premier objectif a été de développer une nouvelle approche pour la découverte des sites de fixation des facteurs de transcription à l’ADN (SAMD-ChIP) adaptée aux données de ChIP-chip et de ChIP-séquençage. Notre approche implémente un algorithme hybride qui combine les deux stratégies énumérative et probabiliste, afin d’exploiter les performances de chacune d’entre elles. Notre approche a montré ses performances, comparée aux outils de découvertes de motifs existants sur des jeux de données simulées et des jeux de données de ChIP-chip et de ChIP-séquençage. SAMD-ChIP présente aussi l’avantage d’exploiter les propriétés de distributions des sites liés par les facteurs de transcription autour du centre des régions liées afin de limiter la prédiction aux motifs qui sont enrichis dans une fenêtre de longueur fixe autour du centre de ces régions. Les facteurs de transcription agissent rarement seuls. Ils forment souvent des complexes pour interagir avec l’ADN pour réguler leurs gènes cibles. Ces interactions impliquent des facteurs de transcription dont les sites de fixation à l’ADN sont localisés proches les uns des autres ou bien médier par des boucles de chromatine. Notre deuxième objectif a été d’exploiter la proximité spatiale des sites liés par les facteurs de transcription dans les régions de ChIP-chip et de ChIP-séquençage pour développer une approche pour la prédiction des motifs composites (motifs composés par deux sites et séparés par un espacement de taille fixe). Nous avons testé ce module pour prédire la co-localisation entre les deux demi-sites ERE qui forment le site ERE, lié par le récepteur des œstrogènes ERα. Ce module a été incorporé à notre outil de découverte de motifs SAMD-ChIP. / Transcription factors (TF) play important roles in various biological processes such as differentiation, cell cycle progression and tumorigenesis. They regulate gene expression by binding to specific DNA sequences (TFBS). Identifying these cis-regulatory elements is a crucial step to understand gene regulatory networks. Technological developments have enhanced DNA sequencing at genomic scale. On the basis of the resulting sequences, computational biologists now attempt to localize the most important functional regions, starting with genes, but also importantly the whole genome characterization of transcription factor binding sites and allow the development of several computational DNA motif discovery tools. Although these various tools are widely used and have been successful at discovering novel motifs, they are not adapted to ChIP-chip and ChIP-sequencing data. The main drawback of these approaches is that most of the predicted motifs represent artifacts due to an inefficient assessment of their enrichment. This thesis is about transcription factor proteins and statistical analysis of their binding sites in ChIP-chip and ChIP-sequencing data. The first objective was to develop a new do novo DNA motif discovery tool adapted to ChIP-chip and ChIP-sequencing data. SAMD-ChIP combines enumerative and stochastic strategies to predict enriched motifs in the vicinity of the ChIP peak summits. Our approach is an automated pipeline that includes motif discovery, motif clustering, motif optimization and finally motif identification using transcription factor (TF) databases. SAMD-ChIP outperforms state-of-the-art motif discovery tools in term of the number of predicted motifs and the prediction of rare and degenerate motifs. In particular, SAMD-ChIP efficiently identifies gapped motifs such as inverted or direct repeats bound by nuclear receptors and composite motifs resulting from the association of different single TF binding sites. The underlying assumption of the second objective is that in regulatory regions, binding sites of interacting transcription factors co-occur more often than expected by chance in the vicinity of the ChIP-peak summits. We proposed an approach to predict transcription factor binding sites co-localization based on the prediction of single motifs by do novo motif discovery tools or by using TFBS models from TF data bases.