Orientador: Zanoni Dias / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T22:45:38Z (GMT). No. of bitstreams: 1 Souza_MariaAngelicaLopesde_M.pdf: 2988201 bytes, checksum: 0742d490b058c7a3dae6fddd7314aba4 (MD5) Previous issue date: 2010 / Resumo: O alinhamento múltiplo dc sequências é uma tarefa de grande relevância cm Bioin-formática. Através dele é possível estudar eventos evolucionários c restrições estruturais ou funcionais, sejam de sequências de proteína, DNA ou RNA, tornando possível entender a estrutura, função c evolução dos genes que compõem um organismo. O objetivo do alinhamento múltiplo é a melhor representação do cenário dc evolução das sequencias ao longo do tempo, considerando a possibilidade dc ocorrerem diferentes eventos de mutação. Encontrar um alinhamento múltiplo dc sequencias ótimo é um problema NP-Difícil. Desta forma, diversas abordagens têm sido desenvolvidas no intuito de encontrar uma solução heurística que represente da melhor maneira possível o cenário dc evolução real, dentre elas está a abordagem progressiva. O alinhamento progressivo c uma das maneiras mais simples dc se realizar o alinhamento múltiplo, pois utiliza pouco tempo c memória computacional. Ele c realizado cm três etapas principais: determinar a distância entre as sequências que serão alinhadas, construir uma árvore guia a partir das distâncias c finalmente construir o alinhamento múltiplo. Este trabalho foi desenvolvido a partir do estudo de diferentes métodos para realizar cada etapa dc um alinhamento progressivo. Foram construídos 342 alinhadores resultantes da combinação dos métodos estudados. Os parâmetros dc entrada adequados para a maioria dos alinhadores foram determinados por estudos empíricos. Após a definição dos parâmetros adequados para cada tipo dc ahnhador, foram realizados testes com dois subconjuntos de referencia do BAliBASE. Com esses testes observamos que os melhores alinhadores foram aqueles que utilizam o agrupamento dc perfil para gerar o alinhamento múltiplo, com destaque paTa os que utilizam pontuação afim para penalizar buracos. Observamos também, que dentre os alinhadores dc agrupamento por consenso, os que utilizam função logarítmica, para penalizar buracos demonstraram melhores desempenhos / Abstract: The multiple sequence alignment is a relevant task in Bioinf'ormatics. Using this technique is possible to study evolutionary events and also structural or functional restrictions of protein, DNA, or RNA sequences. This study helps the understanding of the structure, function, and evolution of the genes that make up an organism. The multiple sequence alignment tries to achieve the best representation of a sequence evolution scenario, considering different mutation events occurrence. Finding an optimal multiple sequence alignment is a NP-Hard problem. Thus, several approaches have been developed in order to find an heuristic solution that represents the real evolution cenário, such as the progressive approach. The progressive alignment is a simple way to perform the multiple alignment, because its low memcny usage and computational time. It is performed in three main stages: (i) determining the distance between the sequences to be aligned, (ii) constructing a guide tree from the distances and finally (hi) building the multiple alignment guided by the tree. This work studied different methods for performing each step of progressive alignment and 342 aligners were built combining these methods. The input parameters suitable for most aligners were determined by empirical studies. After the parameters definition for each type of aligner, which where tested against two reference subsets of BAliBASE. The test results showed that the best aligners were those using the profile alignment to generate the multiple alignment, especially those using affine gap penalty function. In addition, this work shows that among the aligners of grouping by consensus, those that use the logarithmic gap penalty function presented better performance / Mestrado / Bioinformatica / Mestre em Ciência da Computação

No description available.

Made available in DSpace on 2015-04-11T14:02:59Z (GMT). No. of bitstreams: 1 Patricia Silva Peres.pdf: 506475 bytes, checksum: 40dfa72e28b5cca338c104148bd4ef06 (MD5) Previous issue date: 2006-02-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The simultaneous alignment of many DNA or protein sequences is one of the commonest tasks in computational molecular biology. Multiple alignments are important in many applications, such as, predicting the structure of new sequences, demonstrating the relationship between new sequences and existing families of sequences, inferring the evolutionary history of a family of sequences,finding the characteristic motifs (core blocks) between biological sequences, assembling fragments in DNA sequencing, and many others. Currently, the most popular strategy used for solving the multiple sequence alignment problem is the progressive alignment. Each step of this strategy might generate an error which is expected to be low for closely related sequences but increases as sequences diverge. Therefore, determining the order in which the sequences will be aligned is a key step in the progressive alignment strategy. Traditional approaches take into account, in each iteration of the progressive alignment, only the closest pair or groups of sequences to be aligned. Such strategy minimizes the error introduced in each step, but may not be the best option to minimize the final error. Based on that hypothesis, this work aims the study and the application of a global clustering technique to perform a previous analysis of all sequences in order to separate them into groups according to their similarities. These groups, then, guide the traditional progressive alignment, as an attempt to minimize the overall error introduced by the steps of the progressive alignment and improve the final result. To assess the reliability of this new strategy, three well-known methods were modified for the purpose of introducing the new sequence clustering stage. The accuracy of new versions of the methods was tested using three diferent reference collections. Besides, the modified methods were compared with their original versions. Results of the conducted experiments depict that the new versions of the methods with the global clustering stage really obtained better alignments than their original versions in the three reference collections and achieving improvement over the main methods found in literature, with an increase of only 3% on average in the running time. / O alinhamento simultâneo entre várias seqüências de DNA ou proteína é um dos principais problemas em biologia molecular computacional. Alinhamentos múltiplos são importantes em muitas aplicações, tais como, predição da estrutura de novas seqüências, demonstração do relacionamento entre novas seqüências e famílias de seqüências já existentes, inferência da história evolutiva de uma família de seqüências, descobrimento de padrões que sejam compartilhados entre seqüências, montagem de fragmentos de DNA, entre outras. Atualmente, a estratégia mais popular utilizada na resolução do problema do alinhamento múltiplo é o alinhamento progressivo. Cada etapa desta estratégia pode gerar uma taxa de erro que tenderá a ser baixa no caso de seqüências muito similares entre si, porêm tenderá a ser alta na medida em que as seqüências divergirem. Portanto, a determinação da ordem de alinhamento das seqüências constitui-se em um passo fundamental na estratégia de alinhamento progressivo. Estratégias tradicionais levam em consideração, a cada iteração do alinhamento progressivo, apenas o par ou grupo de seqüências mais próximo a ser alinhado. Tal estratégia minimiza a taxa de erro introduzida em cada etapa, porém pode não ser a melhor forma para minimizar a taxa de erro final. Baseado nesta hipótese, este trabalho tem por objetivo o estudo e aplicação de uma técnica de agrupamento global para executar uma análise prévia de todas as seqüências de forma a separálas em grupos de acordo com suas similaridades. Estes grupos, então, guiarão o alinhamento progressivo tradicional, numa tentativa de minimizar a taxa de erro global introduzida pelas etapas do alinhamento progressivo e melhorar o resultado final. Para avaliar a contabilidade desta nova estratégia, três métodos conhecidos foram modificados com o objetivo de agregar a nova etapa de agrupamento de seqüências. A acurácia das novas versões dos métodos foi testada utilizando três diferentes coleções de referências. Além disso, os métodos modificados foram comparadas com suas respectivas versões originais. Os resultados dos experimentos mostram que as novas versões dos métodos com a etapa de agrupamento global realmente obtiveram alinhamentos melhores do que suas versões originais nas três coleções de referência e alcançando melhorias sobre os principais métodos encontrados na literatura, com um aumento de apenas 3% em média no tempo de execução.

To be able to understand characteristics and purpose of biological sequences correctly, it is crucial to have a possibility to sort and compare them. Because of this need and to extend existing knowledge pool, numerous methods were proposed. Especially in field of multiple sequences alignment. Methods for multiple sequences alignment may provide various valuable information about sequences which failed to show enough similarity in pairwise alignment. According to this, several algorithms were implemented in various computer applications which provide a way to analyse huge sets of data. One of those, the progressive alignment algorithm, is implemented as a part of this thesis

The usefulness of digitized documents is directly related to the quality of the extracted text. Optical Character Recognition (OCR) has reached a point where well-formatted and clean machine- printed documents are easily recognizable by current commercial OCR products; however, older or degraded machine-printed documents present problems to OCR engines resulting in word error rates (WER) that severely limit either automated or manual use of the extracted text. Major archives of historical machine-printed documents are being assembled around the globe, requiring an accurate transcription of the text for the automated creation of descriptive metadata, full-text searching, and information extraction. Given document images to be transcribed, ensemble recognition methods with multiple sources of evidence from the original document image and information sources external to the document have been shown in this and related work to improve output. This research introduces new methods of evidence extraction, feature engineering, and evidence combination to correct errors from state-of-the-art OCR engines. This work also investigates the success and failure of ensemble methods in the OCR error correction task, as well as the conditions under which these ensemble recognition methods reduce the Word Error Rate (WER), improving the quality of the OCR transcription, showing that the average document word error rate can be reduced below the WER of a state-of-the-art commercial OCR system by between 7.4% and 28.6% depending on the test corpus and methods. This research on OCR error correction contributes within the larger field of ensemble methods as follows. Four unique corpora for OCR error correction are introduced: The Eisenhower Communiqués, a collection of typewritten documents from 1944 to 1945; The Nineteenth Century Mormon Articles Newspaper Index from 1831 to 1900; and two synthetic corpora based on the Enron (2001) and the Reuters (1997) datasets. The Reverse Dijkstra Heuristic is introduced as a novel admissible heuristic for the A* exact alignment algorithm. The impact of the heuristic is a dramatic reduction in the number of nodes processed during text alignment as compared to the baseline method. From the aligned text, the method developed here creates a lattice of competing hypotheses for word tokens. In contrast to much of the work in this field, the word token lattice is created from a character alignment, preserving split and merged tokens within the hypothesis columns of the lattice. This alignment method more explicitly identifies competing word hypotheses which may otherwise have been split apart by a word alignment. Lastly, this research explores, in order of increasing contribution to word error rate reduction: voting among hypotheses, decision lists based on an in-domain training set, ensemble recognition methods with novel feature sets, multiple binarizations of the same document image, and training on synthetic document images.