[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.

[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.

[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.

[pt] A maioria dos laboratórios não conta com um sistema informatizado para gestão dos procedimentos pertinentes a cada caso. A administração e controle das amostras é feito manualmente, através de diversas fichas que são preenchidas desde o colhimento do material biológico, no hospital, até a identificação final da bactéria no laboratório. Dessa forma, a organização das informações fica limitada, uma vez que, estando as informações escritas à mão e guardadas em livros, é quase impossível a extração de conhecimento útil que possa servir não só no apoio à decisão, como também, na formulação de simples estatísticas. Esta dissertação teve dois objetivos principais. O desenvolvimento de um sistema Web, intitulado BCIWeb (Bacterial Classification and Identification for Web), que fosse capaz de auxiliar na identificação bacteriológica e prover a tecnologia necessária para a administração e controle de amostras clínicas oriundas de hospitais. E a descoberta de conhecimento na base de dados do sistema, através da mineração de dados utilizando os métodos de Mapas Auto-Organizáveis (SOM: Self-Organizing Maps) e Redes Multilayer Perceptrons (MLP) para classificação e identificação de bactérias. A partir do desenvolvimento desta ferramenta amigável, no estudo de caso, os dados históricos do LDCIC (Laboratório de Difteria e Corinebactérias de Importância Clínica) do Departamento de Biologia da UERJ foram inseridos no sistema. Os métodos inteligentes propostos para classificação e identificação de bactérias foram analisados e apresentaram resultados promissores na área. / [en] Most laboratories do not have a computerized system for management procedures. The administration and control of the samples are made manualy through many forms of data sheets which are filled from the beginning, when the samples of biological materials are gathered at the hospital, up to the final identification at the laboratory. In this context, the organization of the information become very limited, while the information writting by hands and stored in books, its almost impossible to extract useful knowledge, which could help not only supporting decisions but also in the formulations of simples statistics. This thesis had two objectives. The development of a web system called BCIWeb (Bacterial Classifiation and Identification for Web) that could assist in bacterial identification and provide the technology necessary for the administration and control of clinical specimen coming from the hospitals and the discovery of knowledge in database system, through data mining methods using SOM (Self Organizing Maps) and Multilayer Perceptron Neural Networks (MLP) for classification and identificatin of bactéria. From the development of this friendly tool, in the case study, the historical data from LDCIC (Laboratório de Difteria e Corinebactérias de Importância Clínica) of UERJ Biology Department were entered into the system. The proposed intelligent methods for classification and identification of bacteria were analysed and showed promising results.