[pt] A família de algoritmos BLAST é a mais utilizada pelos biólogos para a busca de similaridade entre biosseqüências, e por esta razão, melhoras nestes algoritmos, em suas estruturas de dados ou em seus métodos de acesso à memória secundária são muito importantes para o avanço das descobertas biológicas. Nesta dissertação, foi estudada detalhadamente uma versão do programa BLAST, analisando as suas estruturas de dados e os algoritmos que as manipulam. Além disso, foram realizadas medições de desempenho com o intuito de identificar os possíveis gargalos de processamento dentro das fases de execução do BLAST. A partir das informações obtidas, técnicas de compactação de dados foram utilizadas como uma estratégia para redução de acesso à memória secundária com o objetivo de melhorar o desempenho para a execução do BLAST. Finalmente, foi gerada uma versão modificada do BLAST no ambiente Windows, na qual foi alterado diretamente o código do programa. Os resultados obtidos foram comparados com os resultados obtidos na execução do algoritmo original. / [en] The BLAST is the sequence comparison strategy mostly used in computational biology. Therefore, research on data structures, secondary memory access methods and on the algorithm itself, could bring important optimizations and consequently contributions to the area. In this work, we study a NCBI BLAST version by analyzing its data structures and algorithms for data manipulating. In addition, we collect performance data for identifying processing bottleneck in all the BLAST execution phases. Based on this analysis, data compress techniques were applied as a strategy for reducing number of secondary memory access operations. Finally, a modified version of BLAST was implemented in the Microsoft Windows environment, where the program was directly altered. Finally, an analysis was made over using the results of execution of original BLAST against modified BLAST.

[pt] Muitos experimentos científicos são elaborados como fluxos de tarefas computacionais, que podem ser implementados através do uso de linguagens de programação. Na área de bioinformática é muito comum o uso de scripts ad-hoc para construir fluxos de tarefas. Os Sistemas de Gerência de Workflow Científico (SGWC) surgiram como uma alternativa a estes scripts. Uma das funcionalidades desses sistemas que têm recebido bastante atenção pela comunidade científica é a captura automática de dados de proveniência. Estes permitem averiguar quais foram os recursos e parâmetros utilizados na geração dos resultados, dentre muitas outras informações indispensáveis para a validação e publicação de um experimento. Neste trabalho foram levantados alguns desafios na área de proveniência de dados em SGWCs, como por exemplo (i) a heterogeneidade de formas de representação dos dados nos diferentes sistemas, dificultando a compreensão e a interoperabilidade; (ii) o armazenamento de dados consumidos e produzidos e (iii) a reprodutibilidade de uma execução específica. Estes desafios motivaram a elaboração de um esquema conceitual de proveniência de dados para a representação de workflows. Foi implementada também uma extensão em um SGWC específico (BioSide) para incluir dados de proveniência e armazená-los utilizando o esquema conceitual proposto. Foram priorizados neste trabalho alguns requisitos comumente encontrados em workflows de Bioinformática. / [en] Many scientific experiments are designed as computational workflows, which can be implemented using traditional programming languages. In the Bioinformatics domain ad-hoc scripts are often used to build workflows. Scientific Workflow Management Systems (SWMS) have emerged as an alternative to those scripts. One particular SWMS feature that has received much attention by the scientific community is the automatic capture of provenance data. These allow users to track which resources and parameters were used to obtain the results, among many other required information to validate and publish an experiment. In the present work we have elicited some data provenance challenges in the SWMS context, such as (i) the heterogeneity of data representation schemes that hinders the understanding and interoperability; (ii) the storage of consumed and produced data and (iii) the reproducibility of a specific execution. These challenges have motivated the proposal of a data provenance conceptual scheme for workflow representation. We have implemented an extension of a particular SWMS system (Bioside) to include provenance data and store them using the proposed conceptual scheme. We have focused on some requirements commonly found in bioinformatics workflows.

Lo sviluppo delle tecnologie di sequenziamento ha portato alla nascita di strumenti in grado di produrre gigabasi di dati di sequenziamento in una singola corsa. Queste tecnologie, comunemente indicate come Next Generation Sequencing o NGS, producono grandi e complessi dataset la cui analisi comporta diversi problemi a livello bioinformatico. L'analisi di questo tipo di dati richiede la messa a punto di pipelines computazionali il cui sviluppo richiede un lavoro di scripting necessario per concatenare i softwares già esistenti. Questa tesi tratta l'aspetto metodologico dell'analisi di dati NGS ottenuti con tecnologia Illumina. In particolare in essa sono state sviluppate tre pipelines bioinformatiche applicate ai seguenti casi studio: 1) uno studio di espressione genica mediante RNA-seq in "Olea europaea" finalizzato all’indagine dei meccanismi molecolari alla base dell’acclimatazione al freddo in questa specie; 2) uno studio mediante RNA-seq finalizzato all’identificazione dei polimorfismi di sequenza nel trascrittoma di due razze bovine mirato a produrre un ampio catalogo di marcatori di tipo SNPs; 3) il sequenziamento, l’assemblaggio e l’annotazione del genoma di un ceppo di Lactobacillus plantarum che mostrava potenziali proprietà probiotiche. / The advance in sequencing technologies has led to the birth of sequencing platforms able to produce gigabases of sequencing data in a single run. These technologies commonly referred to as Next Generation Sequencing or NGS produce millions of short sequences called “reads” generating large and complex datasets that pose several challenges for Bioinformatics. The analysis of large omics dataset require the development of bioinformatics pipelines that are the organization of the bioinformatics tools in computational chains in which the output of one analysis is the input of the subsequent analysis. A work of scripting is needed to chain together a group of existing software tools.This thesis deals with the methodological aspect of the data analysis in NGS sequencing performed with the Illumina technology. In this thesis three bioinformatics pipelines were developed.to the following cases of study: 1) a global transcriptome profiling of “Oleaeuropeae” during cold acclimation, aimed to unravel the molecular mechanisms of cold acclimation in this species; 2) a SNPs profiling in the transcriptome of two cattle breeds aimed to produce an extensive catalogue of SNPs; 3) the genome sequencing, the assembly and annotation of the genome of a Lactobacillus plantarum strain showing probiotic properties.

[pt] Nos últimos anos surgiram novas tecnologias de sequenciamento de DNA conhecidas como NGS - Next-Generation Sequencing. Estas são responsáveis por tornar o processo de sequenciamento mais rápido e menos custoso, mas também trazem como resultado fragmentos de DNA muito pequenos, conhecidos como reads. A montagem do genoma a partir destes fragmentos é considerada um problema complexo devido à sua natureza combinatória e ao grande volume de reads produzidos. De maneira geral, os biólogos e bioinformatas escolhem o programa montador de sequências sem levar em consideração informações da eficiência computacional ou da qualidade biológica do resultado. Esta pesquisa tem como objetivo auxiliar aos usuários biólogos a avaliar a qualidade dos resultados da montagem. Primeiramente, foi projetada e desenvolvida uma metodologia para obter informações dos genes presentes na montagem, listando os genes que podem ser identificados, aqueles que têm o tamanho correto e a sequência de pares de bases correta. Em segundo lugar, foram realizados testes experimentais exaustivos envolvendo cinco dos principais montadores de genoma conhecidos na literatura os quais são baseados no uso de grafos de Bruijn e oito genomas de bactérias. Foram feitas comparações estatísticas do resultado usando as ferramentas QUAST e REAPR. Também foram obtidas informações qualitativas dos genes usando o algoritmo proposto e algumas métricas de eficiência. Em função dos resultados coletados, é feita uma análise comparativa que permite aos usuários conhecer melhor o comportamento das ferramentas consideradas nos testes. Por fim, foi desenvolvida uma ferramenta que recebe diferentes resultados de montagens de um mesmo genoma e produz um relatório qualitativo e quantitativo para o usuário interpretar os resultados de maneira integrada. / [en] New DNA sequencing technologies, known as NGS - Next-Generation Sequencing, are responsible for making the sequencing process more efficient. However, they generate a result with very small DNA fragments, known as reads. We consider the genome assembly from these fragments a complex problem due to its combinatorial nature and the large volume of reads produced. In general, biologists and bioinformatics experts choose the sequence assembler program with no regard to the computational efficiency or even the quality of the biological result information. This research aims to assist users in the interpretation of assembly results, including effectiveness and efficiency. In addition, this may sometimes increase the quality of the results obtained. Firstly, we propose an algorithm to obtain information about the genes present in the result assembly. We enumerate the identified genes, those that have the correct size and the correct base pair sequence. Next, exhaustive experimental tests involving five of the main genome assemblers in the literature which are based on the use of graphs of Bruijn and eight bacterial genomes data set were ran. We have performed statistical comparisons of results using QUAST and REAPR tools. We have also obtained qualitative information for the genes using the proposed algorithm and some computational efficiency metrics. Based on the collected results, we present a comparative analysis that allows users to understand further the behavior of the tools considered in the tests. Finally, we propose a tool that receives different assemblies of the same genome and produces a qualitative and quantitative report for the user, enabling the interpretation of the results in an integrated way.

[pt] Avanços tecnológicos recentes, tanto nos métodos de sequenciamento quanto nos algoritmos de montagem de fragmentos, têm facilitado a reconstrução de todo o DNA de espécies sem a necessidade de um genoma de referência. A montagem da cadeia completa envolve a leitura um grande volume de fragmentos do genoma (short reads), um desafio significativo em termos computacionais. Todos os principais algoritmos de montagem de fragmentos existentes têm como gargalo principal o alto consumo de memória principal. Consonante a isso, essa dissertação de mestrado visa estudar a implementação de um destes algoritmos, Velvet, que é amplamente usado e recomendado. A mesma possuiu um módulo, VelvetH que realiza um pré-processamento dos dados com o intuito de reduzir o consumo de memória principal. Após um estudo minucioso do código e alternativas de melhorias, foram feitas alterações pontuais e proposta uma solução com persistência de dados em memória secundária visando obter eficácia e robustez. / [en] Recent technological advances, both in assembly algorithms and in sequencing methods, have enabled the reconstruction of whole DNA even without a reference genome available. The assembly of the complete chain involves reading a large volume of genome fragments, called short-reads, which makes the problem a significant computational challenge. A major bottleneck for all existing fragmentassembly algorithms is the high consumption of RAM. This dissertation intends to study the implementation of one of these algorithms, called Velvet, which is widely used and recommended. The same possessed a module, VelvetH that performs a pre-processing data with the aim of reducing the consumption of main memory. After a thorough study of code improvements and alternatives, specific changes have been made and proposed a solution with data persistence in secondary memory in order to obtain effectiveness and robustness.

[pt] Projetos de genômica e biológica molecular estão gerando dados cujos volumes e complexidades jamais foram observados nesta área. Além disso, fontes de dados e de conhecimento são produzidas e utilizadas por grupos de pesquisa os quais utilizam terminologias diferentes (sinônimos, apelido e fórmulas), sintaxes diferentes (estrutura de arquivos e separadores) e semânticas diferentes (intra e interdisciplinares homônimos). O sucesso da pesquisa em biologia dependerá da correta representação e manipulação dos dados biológicos permitindo os cientistas criarem, gerenciarem, manipularem, integrarem e analisarem os dados de forma a gerar informação e conhecimento. Neste trabalho, estudamos os problemas para representação de dados biológicos apresentados nas principais linguagens de modelagem tradicionais. Em seguida, levantamos os requisitos para um novo modelo de dados conceitual para biologia molecular. Finalmente, propomos um novo modelo conceitual contendo construtores específicos para solucionar alguns dos problemas estudados. Além disso, formalizamos o modelo proposto usando lógica de primeira ordem e utilizamos esta descrição lógica para realizar inferências que auxiliem o trabalho do projetista de banco de dados durante a criação de um esquema de banco de dados. / [en] Genomic and molecular biology projects are generating knowledge data whose volume and complexity are unparalleled in this research area. In addition, data and knoweledge sources produced and used by research groups have terminological differences (synonyms, aliases and formulae), syntactic differences (file structure, separators and spelling) and semantic differences (intra- and interdisciplinary homonyms). In this context, data management techniques play a fundamental role for biological applications development because it offers adequate abstractions to desing, implement, access and manage data, in order to generate knowledge. In this work, we study the representation problems presentd in traditional languages. Following, we raise the main requiremants for a new conceptual data model specially conceived for molecular biology. Finally, we propose a new conceptual data model with special types of constructor tryng to solve some of the representation problems discurssed before. In addition, we formalize our proposed model using first-order logic and we use this logical description to infer some properties that may help database designer during the elaboration of database schema.

[pt] Os projetos para estudo de genomas partem de uma fase de sequenciamento onde são gerados em laboratório dados brutos, ou seja, sequências de DNA sem significado biológico. As sequências de DNA possuem códigos responsáveis pela produção de proteínas e RNAs, enquanto que as proteínas participam de todos os fenômenos biológicos, como a replicação celular, produção de energia, defesa imunológica, contração muscular, atividade neurológica e reprodução. As sequências de DNA, RNA e proteínas são chamadas nesta tese de biossequências. Porém, o grande desafio destes projetos consiste em analisar essas biossequências, e obter informações biologicamente relevantes. Durante a fase de análise, os pesquisadores usam diversas ferramentas, programas de computador, e um grande volume de informações armazenadas em fontes de dados de Biologia Molecular. O crescente volume e a distribuição das fontes de dados e a implementação de novos processos em Bioinformática facilitaram enormemente a fase de análise, porém criaram uma demanda por ferramentas e sistemas semi-automáticos para lidar com tal volume e complexidade. Neste cenário, esta tese aborda o uso de workflows para compor processos de Bioinformática, facilitando a fase de análise. Inicialmente apresenta uma ontologia modelando processos e dados comumente utilizados em Bioinformática. Esta ontologia foi derivada de um estudo cuidadoso, resumido na tese, das principais tarefas feitas pelos pesquisadores em Bioinformática. Em seguida, a tese propõe um framework para um sistema de gerência de análises em biossequências, composto por dois sub-sistemas. O primeiro é um sistema de gerência de workflows de Bioinformática, que auxilia os pesquisadores na definição, validação, otimização e execução de workflows necessários para se realizar as análises. O segundo é um sistema de gerência de dados em Bioinformática, que trata do armazenamento e da manipulação dos dados envolvidos nestas análises. O framework inclui um gerente de ontologias, armazenando ontologias para Bioinformática, nos moldes da apresentada anteriormente. Por fim, a tese descreve instanciações do framework para três tipos de ambiente de trabalho comumente encontrados e sugestivamente chamados de ambiente pessoal, ambiente de laboratório e ambiente de comunidade. Para cada um destes ambientes, a tese discute em detalhe os aspectos particulares da execução e otimização de workflows. / [en] Genome projects usually start with a sequencing phase, where experimental data, usually DNA sequences, is generated, without any biological interpretation. DNA sequences have codes which are responsible for the production of protein and RNA sequences, while protein sequences participate in all biological phenomena, such as cell replication, energy production, immunological defense, muscular contraction, neurological activity and reproduction. DNA, RNA and protein sequences are called biosequences in this thesis. The fundamental challenge researchers face lies exactly in analyzing these sequences to derive information that is biologically relevant. During the analysis phase, researchers use a variety of analysis programs and access large data sources holding Molecular Biology data. The growing number of Bioinformatics data sources and analysis programs indeed enormously facilitated the analysis phase. However, it creates a demand for systems that facilitate using such computational resources. Given this scenario, this thesis addresses the use of workflows to compose Bioinformatics analysis programs that access data sources, thereby facilitating the analysis phase. An ontology modeling the analysis program and data sources commonly used in Bioinformatics is first described. This ontology is derived from a careful study, also summarized in the thesis, of the computational resources researchers in Bioinformatics presently use. A framework for biosequence analysis management systems is next described. The system is divided into two major components. The first component is a Bioinformatics workflow management system that helps researchers define, validate, optimize and run workflows combining Bioinformatics analysis programs. The second component is a Bioinformatics data management system that helps researchers manage large volumes of Bioinformatics data. The framework includes an ontology manager that stores Bioinformatics ontologies, such as that previously described. Lastly, instantiations for the Bioinformatics workflow management system framework are described. The instantiations cover three types of working environments commonly found and suggestively called personal environment, laboratory environment and community environment. For each of these instantiations, aspects related to workflow optimization and execution are carefully discussed.

Nel corso dell’ultimo secolo, i programmi di miglioramento genetico hanno portato a notevoli progressi nelle razze bovine nonostante le conoscenze scarse o assenti relative ai geni coinvolti e alle loro funzioni. In questa tesi il genoma bovino è stato studiato con tecnologie massive, impiegando metodiche d’analisi sia tradizionali sia innovative per identificare i geni che controllano i fenotipi complessi e dare supporto al sistema allevatoriale. Nella prima parte del lavoro pannelli SNP a media densità sono stati utilizzati per l’individuazione di ”selection signature” condivise tra razze bovine da latte o da carne, identificando geni candidati specifici per l’attitudine produttiva, e di regioni associate ai fenotipi produttivi in razze da latte. L’associazione è stata effettuata sia con una regressione classica sia con un approccio “gene-centrico” innovativo. Regioni e geni associati significativamente ai fenotipi legati alla produzione lattea sono risultati essere razza specifici. Nella seconda parte, i dati dal sequenziamento dell’esoma e da pannelli SNP ad alta densità sono stati combinati per identificare mutazioni deleterie nella razza Frisona. Diversi approcci sono stati combinati per filtrare e ordinare le varianti genetiche. Alcuni geni che controllano meccanismi biologici di base, quali la fertilità e lo sviluppo, sono stati identificati come candidati ad essere deleteri. Per queste indagini sono stati utilizzati alcuni strumenti bioinformatici già disponibili e, quando necessario, sono stati sviluppati nuovi approcci e procedure. / In the last century, advanced breeding methods have increased the rate of genetic gain in cattle but, with a few exceptions, genes and molecular functions underlying phenotypic variation are still largely unknown. In this thesis, the bovine genome was studied with high-throughput technologies using established and innovative procedures to search for genes controlling complex traits and support bovine breeding. In the first part a medium density marker panel was used to detect selection signatures shared by dairy or by beef breeds, identify candidate genes for specific production aptitudes, and genomic regions associated to production traits in dairy cattle. Genome wide association was run using a classic regression and an innovative gene-centric method. Regions and genes significantly associated to milk traits were specific for each breed. In a second part, data from exome sequences and high-density marker panels were combined to identify deleterious mutations in Italian Holstein. Different approaches were combined to filter and prioritize genetic variants. A set of candidate deleterious genes were found, that control basic biological mechanisms such as development and fertility. State of the art bioinformatics tools were used in these investigations and, whenever necessary, new pipelines and approaches were developed.

[pt] Este trabalho consiste na criação de uma ferramenta provedora de dados para o BLAST, denominada BioProvider. Esta é usada para prover dados realizando um gerenciamento de buffer eficiente para o BLAST, controlando também o escalonamento dos processos do mesmo. A comunicação entre o BioProvider e os processos do BLAST, assim como o controle de concorrência e bloqueios, é feita por meio de um driver, que substitui as chamadas a funções de leitura e escrita de arquivos do banco de dados. Deste modo, o código do BLAST não precisa ser modificado para ser realizar a comunicação com o BioProvider e este pode ser usado para diferentes versões do BLAST. O desenvolvimento do BioProvider é a primeira etapa para a criação de uma solução aplicável também a outras ferramentas de Bioinformática. Por ser transparente aos programas, a ferramenta desenvolvida é facilmente extensível, podendo ser futuramente modificada para prover dados para outros aplicativos, usar outras estratégias de gerência de buffer ou prover dados armazenados em formatos diferentes dos lidos por processos clientes, convertendo-os em tempo de execução. O BioProvider foi testado com a versão recente do NCBI BLAST, obtendo consideráveis melhoras de desempenho, e seu funcionamento foi verificado também com a versão do WU-BLAST com código aberto. Foram realizadas análises de variações no algoritmo de gerenciamento de buffer e dos fatores que influenciam o desempenho dos processos BLAST. / [en] This work consists on the creation of a tool named BioProvider to provide data to BLAST. The tool provides the data using buffer management techniques that are efficient for BLAST and controls process scheduling. The communication between BioProvider and the BLAST processes, as well as the concurrency and blocking control, is done through a device driver that substitutes the read and write function calls to the database files. By this means, the application code can remain unchanged and BioProvider can be used with different versions of BLAST. The development of BioProvider was the first stage to the creation of a solution that can be applied as well to other Bioinformatics tools. Due to its transparency in the view of other applications, BioProvider can be easily extended in the future to provide data to other applications, to use other buffer management techniques or to provide data stored in different formats of those read by the client processes, converting the data in runtime. BioProvider has been tested with the most recent version of NCBI BLAST and considerable improvement has been verified. The tool has been shown to work as well with the open source version of WU-BLAST. Some variations on the buffer management algorithm were studied, as well as the different factors that influence the performance of BLAST processes.

Esta tese trata da aplicação de técnicas de estatística para a resolução de problemas encontrados na análise de dados provenientes da área de biologia molecular -- mais especificamente, dados gerados por estudos de expressão gênica obtidos pela contagem de transcritos, também chamados de perfis digitais de expressão. / This thesis is about the analysis of gene expression data produced by transcript counting methods, also known as digital gene profiles.