Tese (doutorado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2017. / Submitted by Raquel Almeida (raquel.df13@gmail.com) on 2018-04-09T17:54:10Z No. of bitstreams: 1 2017_DanielSundfeldLima.pdf: 12850930 bytes, checksum: 3333336c19d2551133d18cdbd0f7a240 (MD5) / Approved for entry into archive by Raquel Viana (raquelviana@bce.unb.br) on 2018-04-10T19:40:51Z (GMT) No. of bitstreams: 1 2017_DanielSundfeldLima.pdf: 12850930 bytes, checksum: 3333336c19d2551133d18cdbd0f7a240 (MD5) / Made available in DSpace on 2018-04-10T19:40:51Z (GMT). No. of bitstreams: 1 2017_DanielSundfeldLima.pdf: 12850930 bytes, checksum: 3333336c19d2551133d18cdbd0f7a240 (MD5) Previous issue date: 2018-04-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES). / O alinhamento múltiplo primário de sequências biológicas é um problema muito importante em Biologia Molecular, pois permite que sejam detectadas similaridades e diferenças entre um conjunto de sequências. Esse problema foi provado NP-Completo e, por essa razão, geralmente algoritmos heurísticos são usados para resolvê-lo. No entanto, a obtenção da solução ótima é bastante desejada e, por essa razão, existem alguns algoritmos exatos que solucionam esse problema para um número reduzido de sequências. As sequências de RNA, diferente do DNA, não possuem dupla-hélice e podem dobrar-se, pois seus nucleotídeos podem formar pares de bases. É conhecido na Biologia Molecular que a função dessa estrutura está ligada à sua conformação espacial, e não à composição de seus nucleotídeos. Obter a estrutura secundária (2D) de uma sequência de RNA também exige uma grande quantidade de recursos computacionais, até mesmo para um pequeno número de sequências. Desta forma, as arquiteturas de alto desempenho são muito importantes para a obtenção dos resultados em um tempo factível. A presente tese visa investigar os problemas do alinhamento múltiplo primário e do alinhamento em pares secundário, utilizando arquiteturas de alto desempenho para acelerar a obtenção de resultados. Para o alinhamento primário ótimo de múltiplas sequências, propusemos na presente Tese o PA-Star, uma estratégia multithreaded baseada no algoritmo A-Star que usa uma política sensível à localidade de atribuição de trabalho às threads. De modo a lidar com o alto uso de memória, nossa estratégia PA-Star usa tanto memória RAM como disco. Para o alinhamento estrutural (2D) de sequências de RNA, propusemos o Foldalign 2.5, que é uma estratégia multithreaded heurística baseada no algoritmo exato de Sankoff, capaz de obter o alinhamento estrutural de grandes sequências em tempo reduzido. Finalmente, propusemos o CUDA-Sankoff, que é capaz de obter o alinhamento estrutural ótimo entre duas sequências de RNA em GPU (Graphics Processing Unit). / The primary multiple sequence Alignment is a very important problem in Molecular Biology since it is able to detect similarities and differences in a set of sequences. This problem has been proven NP-Hard and, for this reason, heuristic algorithms are usually used to solve it. Nevertheless, obtaining the optimal solution is highly desirable and there are indeed some exact algorithms that solve this problem for a reduced number of sequences. The RNA sequences are different than the DNA, they do not have double helix, their nucleotides can form base pairs and the sequence can fold on itself. It is known in the Molecular Biology that, the function of the RNA is related to its spatial structure. Calculating the secondary structure of RNA sequences also demand a high amount of computational resources, even for a small number of sequences. The High Performance Computing (HPC) Platforms can be used in order to produce results faster. The current thesis aims to investigate the primary multiple sequence alignment and the secondary pairwise sequence alignment, using High Performance Architectures to accelerate and obtaining results in reasonable time. For the primary multiple sequence alignment, we propose the PA-Star, a multithreaded solution based on the A-Star algorithm using a locality sensitive hash to distribute the workload among the threads. Due to the high RAM memory usage required by the algorithm, our strategy can also uses disk. For the RNA structural alignment, we proposed the Foldalign 2.5, a multithreaded solution that uses heuristics to reduce the Sankoff Algorithm complexity, and can obtain the pairwise structural alignment of large sequences in reduced time. Finally, we proposed CUDASankoff, that obtains the optimal pairwise structural alignment for RNA sequences using a GPU (Graphics Processing Unit).

Orientador: Geraldo Francisco Donegá Zafalon / Banca: Angelo Pássaro / Banca: Adriano Mauro Cansian / Resumo: Recentemente, a bioinformática tornou-se um recurso imprescindível para a análise e interpretação da grande quantidade de informação biológica gerada pela biologia molecular e pelos sequenciadores de última geração. O processo de comparação dessas biossequências é o ponto de partida para o estudo da evolução e diferenciação dos organismos vivos, além de ser uma das tarefas mais importantes na biologia computacional. Neste trabalho apresenta-se uma abordagem baseada na heurística de Cadeias de Markov para otimização de um algoritmo de alinhamento múltiplo de sequências biológicas, proporcionando resultados com mais qualidade e sem o comprometimento do desempenho da ferramenta MUSCLE, escolhida para dar suporte ao trabalho. As cadeias de Markov foram escolhidas como técnica de otimização devido sua eficiente aplicabilidade em diversos problemas, sobretudo na biologia computacional, pois sua metodologia probabilística torna a aplicação computacionalmente viável, contornando os problemas NP-difícil e apresentando resultados significamente precisos / Abstract: Recently, bioinformatics has become an indispensable tool for analyzing and interpreting large amounts of information biological generated by molecular biology and the next-generation sequencers. The comparison process these sequences is the starting point for the study of evolution and differentiation of living organisms as well as being one of the most important tasks in computational biology. This work presents an approach based on Markov chains heuristics for optimization of a multiple alignment algorithm of biological sequences, provides improved quality results and without compromising the performance of MUSCLE tool chosen to support the work.. Markov chains were chosen as optimization technique due to its efficient applicability in various other problems, especially in computational biology, as its probabilistic methodology makes applying computationally feasible, bypassing the NP-hard problems and stating significantly accurate results / Mestre

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2016. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-05-06T16:17:35Z No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / Rejected by Raquel Viana(raquelviana@bce.unb.br), reason: A pedido do cliente. on 2016-05-12T17:27:55Z (GMT) / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-05-12T17:33:17Z No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-05-16T17:20:02Z (GMT) No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / Made available in DSpace on 2016-05-16T17:20:02Z (GMT). No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / A comparação de sequências biológicas é uma operação importante na Bioinformática, que é realizada frequentemente. Os algoritmos exatos para comparação de sequências obtêm o resultado ótimo calculando uma ou mais matrizes de programação dinâmica.Estes algoritmos têm complexidade de tempo O(mn), onde m e n são os tamanhos das sequências. Fickettpropôs um algoritmo que é capaz de reduzir a complexidade paraO(kn), onde k é a faixa decomputação e representa a quantidade de diagonais da matrizefetivamente calculadas. Nessa dissertação de mestrado, propomos e avaliamos oFickett-CUDAlign, uma estratégia paralela que divide a comparação de sequências emmúltiplas comparações de subsequências e calcula uma faixa de Fickett apropriada paracada comparação de sequência (bloco). Com estaabordagem, nós reduzimos potencialmenteo número de células calculadas, quando comparada ao Fickett, que usa uma únicafaixa para toda a comparação. Nossa estratégia multi-bloco ajustável foi programada emC/C++ e pthreadse foi integrada ao estágio 4 do CUDAlign, uma ferramenta do estadoda arte para comparações ótimas de sequências biológicas. O Fickett-CUDAlign foi usadopara comparar sequências reais de DNA cujo tamanho variou de 10KBP (Milhares dePares de Base) a 47MBP (Milhões de Pares de Base),alcançando um speedup de 59,60xna comparação 10MBP x 10MBP, quando comparado aoestágio 4 do CUDAlign. Nestecaso, o tempo de execução foi reduzido de 53,56 segundos para 0,90 segundo. ________________________________________________________________________________________________ ABSTRACT / Biological sequence comparison is an important task in Bioinformatics, which is frequently performed. The exact algorithms for sequence comparison obtain the optimal result by calculating one or more dynamic programming matrices. These algorithms have O(mn) time complexity, where m and n are the sizes of the sequences. Fickett proposed an algorithm which is able to reduce time complexity to O(kn), where k is the computation band and represents the amount of matrix diagonals actually calculated. In this MSc Dissertation, we propose and evaluate Fickett-CUDAlign, a parallel strategy that splits a pairwise sequence comparison in multiple comparisons of subsequences and calculates an appropriate Fickett band to each subsequence comparison (block). With this approach, we potentially reduce the number of cells calculated, when compared to Fickett, which uses a unique band to the whole comparison. Our adjustable multi-block strategy was programmed in C/C++ and pthreads and was integrated to the stage 4 of CUDAlign, a state-of-the-art tool for optimal biological sequence comparison. Fickett-CUDAlign was used to compare real DNA sequences whose sizes ranged from 10KBP (Thousands of Base Pairs) to 47MBP (Millions of Base Pairs), reaching a speedup of 59.60x in the 10MBP x 10MBP comparison, when compared to CUDAlign’s stage 4. In this case, the execution time was reduced from 53.56 seconds to 0.90 second.

Orientador: Luiz Francisco Zafalon / Coorientador: Fernando Antônio de Ávila / Coorientador: Oswaldo Durival Rossi Junior / Banca: Maurício de Alvarenga Mudadu / Banca: Luciano Menezes Ferreira / Banca: Hélio José Montassier / Banca: Marita Vedovelli Cardozo / Resumo: Tendo em vista a importância e o crescente interesse na produção de leite de búfala e seus derivados e da ocorrência de Staphylococcus coagulase negativa (SCN) como patógenos da mastite tanto em bovinos como em bubalinos. O presente estudo objetivou avaliar genes de virulência, a resistência a antimicrobianos, bem como metodologias para correta identificação destes SCN em ambiente de ordenha e no leite de bubalinos. Foram colhidas 320 amostras de leite de quartos mamários de 80 búfalas escolhidas aleatoriamente, 20 amostras de narinas e 20 amostras da boca dos bezerros bubalinos, 16 amostras das mãos dos ordenhadores e 64 amostras de insufladores das teteiras, coletadas durante a ordenha. Vinte e sete cepas de Staphylococcus coagulase negativa foram positivas para o gene eno, 10 para o gene ebps, 10 para o gene fnbA. Em relação aos genes relacionados com a produção de enterotoxinas, apenas uma cepa foi positiva para o gene sea, uma para o gene see e para os genes relacionados a resistência antimicrobiana, uma cepa foi positiva para o gene mecA. A identificação das espécies isoladas foi realizada utilizando-se a metodologia de MALDI-TOF MS e confirmada por iniciadores espécie-especifico desenhados neste estudo, exceto para S. agnetis o qual foi erroneamente identificado como S. hyiucs por espectofotometria de massa. Neste trabalho a identificação destas duas espécies foi confirmada por sequenciamento genômico de um isolado representativo. Foram observadas quatro amostras resis... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Due to the importance and the growing interest in buffalo milk production and its derivate and the concurrency of coagulase negative staphylococci as major mastitis pathogens both in cattle and in buffalo. This study aimed to search for virulence genes, antimicrobial resistance, and to evaluate methodologies for the identification of these microorganisms in samples of buffalo milk and from milking environment. For this, a total of 320 milk samples were collected from mammary quarters of 80 randomly selected buffaloes, 20 samples from nostrils and 20 samples from buffalo calves 'mouths, 16 samples from milking hands and 64 samples from liners were collected at the time of milking. Twenty-seven strains of coagulase negative staphylococci were positive for the eno gene, ten for ebpS gene, ten for the fnbA. Regarding genes related to enterotoxins production. Only one strain was positive for the sea and see gene and one for the mecA gene. The identification of the isolates was correctly done by MALDI-TOF MS and subsequently confirmed by species specific primers, except for S. agnetes that was wrongly identified as S. hyiucs. This identification was confirmed by genomic sequencing of a representative isolate from each species. There were four strains resistant to clindamycin, nine to vancomycin, one to chloramphenicol, seven to rifanmpicina, four to cefepime, seven to oxacillin, 17 to penicillin, 13 to erythromycin, 15 to cotrimoxazole and three to tetracycline. Furthermore, resistance to two or more antibiotics were observed in 21 isolates. The present study results may contribute to incidence prevention and control of mastitis in buffalo, caused by coagulase negative Staphylococcus. The main SCN species isolated were S. chromogenes, S. agnetis and S. epidermidis., the detection of genes related to adhesion and the production of enterotoxins m... (Complete abstract click electronic access below) / Doutor

Made available in DSpace on 2016-04-29T14:23:42Z (GMT). No. of bitstreams: 1 Aline Rodrigheri Ioste.pdf: 3892568 bytes, checksum: d4b25a166ea46de0a3b7edfbfeab6923 (MD5) Previous issue date: 2016-03-04 / The objective of this study is to deeply understand the techniques currently used in optimal alignment of DNA sequences, focused on the strengths and limitations of these methods. Analyzing the feasibility of creating a new logical approach able to ensure optimal results , taking into account existing problems in optimal alignment as: (i ) the numerous alignment possibilities of two sequences , ( ii ) the great need for space and memory the machines, ( ii ) processing time to compute the optimal data and (iv ) exponential growth. This study allowed the beginning of the creation of a new logical approach to the global optimum alignment, showing promising results in higher scores with less need for calculations where the mastery of these new techniques can lead to use search of excellent results in the global alignment optimal in large data bases / O objetivo deste estudo é entender profundamente as técnicas utilizadas atualmente no alinhamento ótimo de sequências de DNA e analisar a viabilidade da criação de uma nova abordagem lógica capaz de garantir o resultado ótimo, levando em consideração os problemas existentes no alinhamento ótimo como: (i) as inúmeras possibilidades de alinhamento de duas sequências, (ii) a grande necessidade de espaço e memória das máquinas, (ii) o tempo de processamento para computar os dados ótimos e (iv) seu crescimento exponencial. O presente estudo permitiu o início da criação de uma nova abordagem lógica para o alinhamento ótimo global, demonstrando resultados promissores de maiores pontuações com menos necessidades de cálculos, onde o domínio destas novas técnicas pode conduzir à utilização da busca de resultados ótimos no alinhamento global de sequências biológicas em grandes bases de dados

A origem dos novos genes é um processo importante para a evolução dos organismos, pois ela fornece fontes singulares para a inovação evolutiva. As abordagens que mostram como esses novos genes surgem e adquirem novas funções no curso da evolução são de fundamental importância, por exemplo, elas podem ajudar a correlacionar mutações com alterações metabólicas, fisiológicas e/ou morfológicas, indicando quais mutações podem ser importantes funcionalmente. Recentemente, uma nova abordagem, nomeada de filoestratigrafia, foi desenvolvida para estabelecer origem evolutiva dos genes. Neste método a emergência de novas sequências de um nó filogenético particular em uma linhagem ancestral-descente é inferida geralmente utilizando algoritmos de similaridade. No presente trabalho, nós fizemos uma pesquisa filoestratigráfica de dois bancos de dados de domínios proteicos, CATH e Pfam, para todas as entradas humanas descrevemos a origem dos domínios e arquiteturas humanas. Também realizamos uma nova abordagem para refinar os resultados por Male-PSI-BLAST, em um estudo de caso dos domínios príons e ADHs. A análise das duas bases de dados mostrou que existiram três períodos importantes de aparecimento de domínios proteicos humanos: a origem do organismo celular, Eucarioto e Euteleostomi, nos quais há um elevado número de surgimento de novos genes na linhagem ancestral-descente de humanos. Quando analisamos o aparecimento de arquiteturas, elas são evidentemente mais recentes que o aparecimento de domínios, embora, em seu conteúdo, possa haver domínios muito antigos misturados com domínios novos. Não notamos nenhuma tendência de acréscimo de novos domínios para arquiteturas que compreendem domínios antigos ou recentes. Para medir o grau de versatilidade de domínio, nós utilizamos a frequência ponderada de bigrama, uma combinação específica de dois domínios adjacentes. O teste de correlação de Spearman mostrou que existe uma baixa correlação negativa entre a idade de domínios e índices de versatilidade. Em um estudo de caso, demonstramos que é possível caracterizar descontinuidades evolutivas nos resultados de Male-PSI-BLAST entre domínios que surgiram a partir de outros. Pela primeira vez, a origem de todos os domínios e arquiteturas proteicas presentes nas bases de dados estudadas foi descrita, fornecendo um cenário evolutivo que pode ser mais explorado a partir das abordagens aqui desenvolvidas. / The origin of new genes is an important process for the evolution of organisms because they provide singular sources for evolutionary innovation. The approaches that show how these new genes arise and acquire new functions in the course of evolution are of fundamental importance: they can help to correlate mutations with metabolic, physiological, and morphological changes, indicating which mutations are likely to be functionally important. Recently, a new approach, named phylostratigraphy, was developed to establish the evolutionary origin of the genes. In this method the emergence of novel sequences at a particular phylogenetic node in a descendent-ancestor lineage is infer usually by using the similarity search algorithm. In the present work, we did a phylostratigraphical search of two protein domain databases, CATH and Pfam, for all human entries and depicted the origin of human domains and architectures. We also conducted a new approach to refine results by Male-PSI-BLAST in a case study of prions and ADH\'s domains. The analysis of two databases showed that there are three important periods of appearance of human gene domains: the origin of cellular organism, Eukaryote, and Euteleostomi appear to be important for production of new genes at the ancestor-descendent lineages that lead to the human species. However, when we analyze the appearance of architectures, they are by far more recent than the appearance of domains, although they might contain very ancient domains mixed with recent ones. We did not notice a bias of addition of new domains to architectures comprising either ancient or recent domains. To measure the degree of domain versatility, we used the weighted bigram frequency, where bigram is defined as a specific combination of two adjacent domains. The Spearman correlation test showed that there is a low negative correlation between the age of domains and versatility indexes. In the study of case, we have demonstrated that it is possible to characterize evolutionary ruptures in results of Male-PSI- BLAST between domains that emerged from others. For the first time the origin of all protein domains and architectures was depicted, providing an evolutionary scenario that can be further explored.

Tese (doutorado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2008. / Submitted by Jaqueline Oliveira (jaqueoliveiram@gmail.com) on 2008-12-04T18:50:12Z No. of bitstreams: 1 TESE_2008_JanMendoncaCorrea.pdf: 1697042 bytes, checksum: 1f33d862081703c73ca93cae5ea50d48 (MD5) / Approved for entry into archive by Georgia Fernandes(georgia@bce.unb.br) on 2009-02-12T17:40:49Z (GMT) No. of bitstreams: 1 TESE_2008_JanMendoncaCorrea.pdf: 1697042 bytes, checksum: 1f33d862081703c73ca93cae5ea50d48 (MD5) / Made available in DSpace on 2009-02-12T17:40:50Z (GMT). No. of bitstreams: 1 TESE_2008_JanMendoncaCorrea.pdf: 1697042 bytes, checksum: 1f33d862081703c73ca93cae5ea50d48 (MD5) / O alinhamento de seqüências biológicas é uma das operações mais básicas em bioinformática, tendo por objetivo determinar a similaridade entre as seqüências. A solução deste problema envolve geralmente a comparação de seqüências através de programação dinâmica. Este tipo de comparação gera resultados ótimos mas possui complexidade quadrática de tempo, justificando métodos para sua aceleração em hardware como o FPGA. Na presente tese foram projetadas arquiteturas wavefront em FPGA utilizando espaço linear para três diferentes algoritmos. O primeiro algoritmo foi o de Smith-Waterman. Ele foi implementado na forma de um vetor wavefront e foi utilizado na aceleração da fase inicial de um algoritmo de alinhamento. Esta arquitetura foi capaz de recuperar o maior escore e posição em espaço linear. Esta arquitetura foi sintetizada em FPGA e o melhor resultado da arquitetura foi 246,9 vezes mais rápido que em software, demonstrando a utilidade da arquitetura. A seguir, foi projetada uma arquitetura para a recuperação do escore ótimo do algoritmo de programação dinâmica DIALIGN também em espaço linear. Foram obtidos resultados até 383,41 vezes superiores ao programa em software. Para recuperar o alinhamento ótimo no DIALIGN é necessário espaço quadrático. Assim, foi projetada uma variante do DIALIGN capaz de recuperar o alinhamento de duas seqüências em espaço linear. Após a implementação em hardware, os resultados obtidos foram até 141,38 vezes mais rápido que a implementação em software. ______________________________________________________________________________________ ABSTRACT / The alignment of biological sequences is one of the more basic operations in bioinformatics. Its purpose is to find the similarity between sequences. The solution to this problem generally involves sequence comparison through dynamic programming. This kind of comparison yields optimal results but has quadratic time complexity thus justifying its hardware acceleration in FPGA. In this thesis, linear space wavefront architectures were designed in FPGA for three different algorithms. The first algorithm was Smith-Waterman. It was implemented in a wavefront array and utilized to accelerate the initial phase of a sequence alignment algorithm. This architecture was able to retrieve the largest score and its position in linear space. It was synthesized in FPGA and the best result was 246,9 times faster than software, showing the appropriateness of the architecture. Also, an architecture to retrieve the optimal DIALIGN score in linear space was designed. The results were up to 383,41 times better than software. The retrieval of the optimal alignment for DIALIGN needs quadratic space. Therefore, a variant for the DIALIGN dynamic programming algorithm was proposed to retrieve the alignment in linear space. This variant was implemented in hardware and the results were up to 141,38 times faster than the software implementation.

Made available in DSpace on 2016-06-02T20:36:39Z (GMT). No. of bitstreams: 1 4425.pdf: 4096750 bytes, checksum: d77921e33ac24b167ed701cea4759eb0 (MD5) Previous issue date: 2012-04-18 / Financiadora de Estudos e Projetos / Plant cell walls are composed of approximately 65% cellulose microfibrils and pectin. The latter is proteolytically degraded by the so-called pectinases enzymes (also known as pectinolytic enzymes). Pectinases may be either depolymerizing. They are produced by plants, filamentous fungi, bacteria, and yeast. Due to the wide commercial use of pectinase, one has testified a growing number of studies devoted to understand the activities of such enzymes. Bioinformatics tools were employed throughout this work in order to study fungal polygalacturonase (PG) under two aspects. Firstly, all stored fungal PG sequences in databases (2093) were analyzed in order to evaluate through searching for sequential motifs and phylogenetic studies the possibility to classifying the enzymes as either Endo- or Exo-PG. After excluding those with less than 70 amino acids, those that corresponded to the hypothetical protein , and those that were neither PG nor fungal PG, there were 957 sequences left. Those sequences were separated according to genus and species. For each group, multiple sequence alignments were made by using ClustalW software. The alignments were analyzed and the sequences displaying 100% identity were then expunged, thus resulting in a database of unique sequences of fungal PG. By means of the alignment, the study of structural motifs, and the construction of phylogenetic trees, one was able to classify all the sequences according to their mode of action in either Endo- or Ex-PG. Throughout the second part of our research, protein homology-modeling methods were employed while constructing a three-dimensional model of a L. gongylophorus fungal polygalacturonase, symbiont of leaf-cutting ant. The model was validated by PROCHECK, VERIFY 3D, and WHAT IF software. By analyzing the 3D model of the L. gongylophorus PG, a catalytic mechanism of the enzyme was outlined, which may take place by inverting the configuration of sugar anomeric carbon (substrate). / A parede celular de células de plantas é composta de aproximadamente 65% de rede de celulose e rede de pectato. Essa última é proteoliticamente degradada por enzimas chamadas pectinases ou enzimas pectinolíticas. As pectinases podem ser despolimerizantes ou desesterificantes e são produzidas por plantas, fungos filamentosos, bactérias e leveduras. Impulsionado pelas aplicações comerciais que pectinases representam, é crescente o estudo para o melhor entendimento sobre as atividades dessas enzimas. Ferramentas de bioinformática foram usadas neste trabalho para estudar poligalacturonases (PG) de fungos, sob dois aspectos. Na primeira parte do trabalho, todas as sequências de PG de fungos depositadas em bancos de dados (2093) foram analisadas e avaliadas quanto à possibilidade de classificação das enzimas em Endo- ou Exo-PG através de busca de motivos sequenciais e estudos filogenéticos. Após exclusão daquelas com menos de 70 aminoácidos, das que correspondiam a 'proteína hipotética' e ainda das que não eram PG ou mesmo não eram PG de fungos restaram 957 sequências. Essas sequências foram separadas por gênero e espécie e para cada grupo foram realizados alinhamentos múltiplos de sequências usando o programa ClustalW . Os alinhamentos foram analisados e as sequências com 100% de identidade foram retiradas, resultando em um conjunto de dados com 417 sequências únicas de PG de fungos. Através dos alinhamentos, do estudo de motivos estruturais e da construção de árvores filogenéticas foi possível classificar todas as sequências de acordo com seu modo de ação em Endo- ou Exo-PG. Na segunda parte do trabalho foi usado o método de modelagem por homologia na construção do modelo tridimensional de uma poligalacturonase do fungo L. gongylophorus, simbionte de formigas cortadeiras. O modelo foi validado com os programas PROCHECK, VERIFY 3D e WHAT IF. Através da análise do modelo 3D da PG do L. gongylophorus foi possível propor um mecanismo de ação da enzima, que deve ocorrer com inversão da configuração do carbono anomérico do açúcar (substrato).

Orientador: Geraldo Francisco Donegá Zafalon / Banca: André Carlos Ponce de Leon Ferreira de Carvalho / Banca: Rogéria Cristiane Gratão de Souza / Resumo: Com a crescente na quantidade de dados genômicos disponíveis, o alinhamento de sequências destaca-se como uma das tarefas relevantes no contexto da Bioinformática, cujos resultados são utilizados no auxílio às análises e posteriores inferências sobre esses dados. Assim, diversos algoritmos para alinhamento múltiplo de sequências baseados em diferentes heurísticas, como a de Algoritmos Genéticos, Otimização por Colônia de Formigas, Recozimento Simulado (Simulated Annealling), Busca Tabu, entre outros, foram propostos. No entanto, estudos apontam que com o uso de uma função objetivo mais adequada para aferir a qualidade do alinhamento produzido em cada caso específico, geralmente, produzem-se resultados com maior significância biológica. Além disso, o uso simultâneo de diferentes heurísticas para alinhamento múltiplo de sequências também tende a produzir melhores resultados, de modo que essa hibridização amenize as desvantagens de cada estratégia. No presente trabalho, implementou-se um escalonador automático de funções objetivo para selecionar o modelo de avaliação mais adequado para cada caso, com base na similaridade das sequências de entrada. Além disso, foi implementada uma fase de pós processamento com Otimização por Colônia de Formigas junto à MSA-GA, a fim de se refinar os alinhamentos produzidos pela ferramenta. Nos testes, pode-se verificar que o escalonador foi capaz de calcular de maneira adequada a similaridade dos conjuntos de entrada e, com isso, selecionar... / Abstract: Due the increasing of the genomic data available, the multiple sequence alignment became one of the most important tasks in Bioinformatics, whose results are used to help biologists in their analysis. Thus, many algorithms to perform multiple sequence alignment based on different heuristics have been proposed, as Genetic Algorithms, Ant Colony, Simulated Annealing, Tabu Search, among others. Nonetheless, studies show that the use of an objective function suited for each case, generally, results in alignments with more biological significance. Moreover the simultaneous use of different heuristics to perform multiple sequence alignment can produce better results, smoothing the disadvantages of each strategy. In the present work, it was developed an automatic scheduler of objective functions to select the evaluation model more suited for each case, based on the similarity of the input sequences. Moreover it was implemented into the MSA-GA tool a post-processing stage with Ant Colony, in order to refine the obtained alignments. In the tests, it can be noticed that the scheduler calculates satisfactorily the similarity of the sequence sets and selects the more suited objective function. Moreover, with the post-processing stage, it was possible to re- fine the alignments of the MSA-GA, producing better results in terms of biological significance / Mestre

Made available in DSpace on 2014-06-11T19:24:01Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-02-11Bitstream added on 2014-06-13T19:51:06Z : No. of bitstreams: 1 marucci_ea_me_sjrp.pdf: 2105093 bytes, checksum: 5b417abdc99cd4c7f9807768af1ab956 (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Devido a crescente quantidade de dados genômicos para comparação, a computação paralela está se tornando cada vez mais necessária para realizar uma das operaçoes mais importantes da bioinformática, o alinhamento múltiplo de sequências. Atualmente, muitas ferramentas computacionais são utilizadas para resolver alinhamentos e o uso da computação paralela está se tornando cada vez mais generalizado. Entretanto, embora diferentes algoritmos paralelos tenham sido desenvolvidos para suportar as pesquisas genômicas, muitos deles não consideram aspectos fundamentais da computação paralela. O MUSCLE [1] e uma ferramenta que realiza o alinhamento m ultiplo de sequências com um bom desempenho computacional e resultados biológicos signi cativamente precisos [2]. Embora os m etodos utilizados por ele apresentem diferentes versões paralelas propostas na literatura, apenas uma versão paralela do MUSCLE foi proposta [3]. Essa versão, entretanto, foi desenvolvida para sistemas de mem oria compartilhada. O desenvolvimento de uma versão paralela do MUSCLE para sistemas distribu dos e importante dado o grande uso desses sistemas em laboratórios de pesquisa genômica. Esta paralelização e o foco deste trabalho e ela foi realizada utilizando-se abordagens paralelas existentes e criando-se novas abordagens. Como resultado, diferentes estratégias paralelas foram propostas. Estas estratégias podem ser incorporadas a outras ferramentas de alinhamento que utilizam, em determinadas etapas, a mesma abordagem seq uencial. Em cada método paralelizado, considerou-se principalmente a e ciência, a escalabilidade e a capacidade de atender problemas reais da biologia. Os testes realizados mostram que, para cada etapa paralela, ao menos uma estratégia de nida atende bem todos esses crit erios. Al em deste trabalho realizar um paralelismo in edito, ao viabilizar a execução da ferramenta MUSCLE em... / Due to increasing amount of genetic data for comparison, parallel computing is becoming increasingly necessary to perform one of the most important operations in bioinformatics, the multiple sequence alignments. Nowadays, many software tools are used to solve sequence alignments and the use of parallel computing is becoming more and more widespread. However, although di erent parallel algorithms were developed to support genetic researches, many of them do not consider fundamental aspects of parallel computing. The MUSCLE [1] is a tool that performs multiple sequence alignments with good computational performance and biological results signi cantly precise [2]. Although the methods used by them have di erent parallel versions proposed in the literature, only one parallel version of the MUSCLE tool was proposed [3]. This version, however, was developed for shared memory systems. The development of a parallel MUSCLE tool for distributed systems is important given the wide use of such systems in laboratories of genomic researches. This parallelization is the aim of this work and it was done using existing parallel approaches and creating new approaches. Consequently, di erent parallel strategies have been proposed. These strategies can be incorporated into other alignment tools that use, in a given stage, the same sequential approach. In each parallel method, we considered mainly the e ciency, scalability and ability to meet real biological problems. The tests show that, for each parallel step, at least one de ned strategy meets all these criteria. In addition to the new MUSCLE parallelization, enabling it execute in a distributed systems, the results show that the de ned strategies have a better performance than the existing strategies.