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 Matemática, 2014 / Submitted by Ana Cristina Barbosa da Silva (annabds@hotmail.com) on 2014-12-05T11:31:19Z No. of bitstreams: 1 2014_MarcusViniciusPereira.pdf: 1495143 bytes, checksum: 847eb280919f4cd43cfea39b1e5ac3ce (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2014-12-05T14:32:22Z (GMT) No. of bitstreams: 1 2014_MarcusViniciusPereira.pdf: 1495143 bytes, checksum: 847eb280919f4cd43cfea39b1e5ac3ce (MD5) / Made available in DSpace on 2014-12-05T14:32:22Z (GMT). No. of bitstreams: 1 2014_MarcusViniciusPereira.pdf: 1495143 bytes, checksum: 847eb280919f4cd43cfea39b1e5ac3ce (MD5) / O objetivo deste texto é realizar um estudo sobre sequências numéricas mostrando exemplos de sequências não comumente estudadas no ensino médio inclusive as decorrentes da solução de determinados problemas. Abordamos também as relações de recorrência, apresentando alguns resultados sobre a resolução de tais recorrências e sugerindo atividades de investigação matemática em sala de aula. _________________________________________________________________________________ ABSTRACT / The aim of this paper is to conduct a study on numerical sequences showing ex-amples of sequences unusually studied in high school including those resulting from the solution of certain problems. We also analyze the recurrence relations, present some re-sults about solving such recurrences and suggest mathematical research activities in the classroom.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2009. / Submitted by Allan Wanick Motta (allan_wanick@hotmail.com) on 2010-07-16T19:38:07Z No. of bitstreams: 1 2009_LidiaAraujoMiranda.pdf: 5472186 bytes, checksum: 3bc128515fab954a95e110f39e6c356c (MD5) / Approved for entry into archive by Lucila Saraiva(lucilasaraiva1@gmail.com) on 2010-07-19T14:24:14Z (GMT) No. of bitstreams: 1 2009_LidiaAraujoMiranda.pdf: 5472186 bytes, checksum: 3bc128515fab954a95e110f39e6c356c (MD5) / Made available in DSpace on 2010-07-19T14:24:14Z (GMT). No. of bitstreams: 1 2009_LidiaAraujoMiranda.pdf: 5472186 bytes, checksum: 3bc128515fab954a95e110f39e6c356c (MD5) Previous issue date: 2009 / O Alinhamento Múltiplo de Sequências genéticas (AMS) é executado milhares de vezes ao dia por cientistas, a fim de identificar regiões de semelhança entre três ou mais sequências. Os alinhamentos múltiplos assim obtidos são usados na resolução de problemas complexos, como a determinação do histórico evolutivo das espécies. Por se tratar de um problema NP-completo, geralmente são utilizadas soluções heurísticas para a sua resolução. Dentre soluções adotadas, destaca-se o Algoritmo Genético (AG), que é um método iterativo não-determinístico, baseado nos princípios da Evolução das Espécies de Darwin. Apesar de apresentar soluções boas para o AMS, os algoritmos genéticos demandam um alto poder de processamento, que se traduz em um alto tempo de execução. Por essa razão, algumas estratégias paralelas foram propostas na literatura para acelerar a obtenção de alinhamentos múltiplos com AGs, geralmente utilizando a estratégia da ilha como base de paralelização. A presente dissertação de mestrado propõe e avalia uma estratégia paralela que utiliza Algoritmo Genético para o Alinhamento Múltiplo de Sequências, inspirada no modelo Multi-ilha. De maneira diferente das abordagens para AMS existentes na literatura, a estratégia proposta utiliza 3 Super Ilhas, onde cada Super Ilha implementa um modelo tradicional de ilhas. Os resultados obtidos com bases reais de proteínas mostram que a estratégia proposta é capaz de encontrar alinhamentos múltiplos de melhor qualidade em menor tempo, quando comparada com a estratégia de ilha tradicional. _______________________________________________________________________________ ABSTRACT / The Multiple Sequence Alignment (MSA) between genetic sequences is exhaustively done by scientists trying to identify matching regions within three or more sequences. The resulting multiple alignments are used in complex problems like the one of establishing genetic relationships between biological sequences. The MSA has been shown to be an NP-complete problem, therefore heuristic solutions are usually used to solve it. One of the solutions that has shown good results for MSA is the Genetic Algorithm (GA), a non deterministic iterative method, based on Charles Darwin's theory of evolution. Though presenting good results, the GA demands high amount of computing power, taking usually a lot of time to be executed. To speed up the sequential algorithms execution, parallel algorithms were proposed in the literature, most of them using the island strategy of parallelization. This masters dissertation proposes and evaluates a parallel strategy that uses Genetic Algorithms to the Multiple Sequence Alignment based on the Multi-island parallelization strategy. Di erently from other MSA strategies, the proposed strategy creates three Super Islands and each one executes a GA parallelized by the island strategy. The results were obtained with real protein banks and revealed that the proposed strategy is capable of nding better multiple alignments in a smaller amount of time, when compared to the conventional island strategy.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2011. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2012-02-27T16:19:33Z No. of bitstreams: 1 2011_EdansFlaviusOliveiraSandes.pdf: 1562566 bytes, checksum: 676058b28872648ff52973f27bc2f19c (MD5) / Approved for entry into archive by Patrícia Nunes da Silva(patricia@bce.unb.br) on 2012-02-27T20:57:53Z (GMT) No. of bitstreams: 1 2011_EdansFlaviusOliveiraSandes.pdf: 1562566 bytes, checksum: 676058b28872648ff52973f27bc2f19c (MD5) / Made available in DSpace on 2012-02-27T20:57:53Z (GMT). No. of bitstreams: 1 2011_EdansFlaviusOliveiraSandes.pdf: 1562566 bytes, checksum: 676058b28872648ff52973f27bc2f19c (MD5) / A comparação de sequências biológicas é uma operação muito importante na Bioinformática. Embora existam métodos exatos para comparação de sequências, estes métodos usualmente são preteridos por causa da complexidade quadrática de tempo e espaço. De forma a acelerar estes métodos, muitos algoritmos em GPU foram propostos na literatura. Entretanto, todas estas propostas restringem o tamanho da sequência de busca de forma que a comparação de sequências genômicas muito longas não é possível. Neste trabalho, nós propomos e avaliamos o CUDAlign, um algoritmo em GPU capaz de comparar sequências biológicas longas com o método exato de Smith-Waterman com o modelo affine gap. O CUDAlign foi implementado em CUDA e testado em duas placas de vídeo, separadamente. Para sequências reais com tamanho entre 1 MBP (milhões de pares de bases) e 47 MBP, um desempenho aproximadamente constante em GCUPS (Bilhões de células atualizadas por segundo) foi obtida, mostrando o potencial de escalabilidade da nossa abordagem. Além disso, o CUDAlign foi capaz de comparar o cromossomo 21 humano e o cromossomo 22 do chimpanzé. Esta operação levou aproximadamente 18 horas na GeForce GTX 285, resultando em um desempenho de 23.87 GCUPS, valor muito próximo do desempenho máximo previsto (23.93 GCUPS). Até onde sabemos, esta foi a primeira vez que cromossomos grandes como esses foram comparados com um método exato. ______________________________________________________________________________ ABSTRACT / Biological sequence comparison is a very important operation in Bioinformatics. Even though there do exist exact methods to compare biological sequences, these methods are not often employed due to their quadratic time and space complexity. In order to accelerate these methods, many GPU algorithms were proposed in the literature. Nevertheless, all of them restrict the size of the query sequence in such a way that Megabase genome comparison is prevented. In this work, we propose and evaluate CUDAlign, a GPU algorithm that is able to compare Megabase biological sequences with an exact Smith-Waterman affine gap variant. CUDAlign was implemented in CUDA and tested in two GPU boards, separately. For real sequences whose size range from 1 MBP (Megabase Pairs) to 47 MBP, a close to uniform GCUPS (Giga Cells Updates per Second) was obtained, showing the potential scalability of our approach. Also, CUDAlign was able to compare the human chromosome 21 and the chimpanzee chromosome 22. This operation took approximately 18 hours on GeForce GTX 285, resulting in a performance of 23.87 GCUPS, very close to the maximum predicted performance (23.93 GCUPS). As far as we know, this is the first time such huge chromosomes are compared with an exact method.

Submitted by Chaylane Marques (chaylane.marques@ufpe.br) on 2015-03-13T18:44:16Z No. of bitstreams: 2 Dissert. Camila Tenorio França PPGCB.pdf: 5895108 bytes, checksum: daba019b5bd4acf2d9d72976ba7c959f (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-13T18:44:16Z (GMT). No. of bitstreams: 2 Dissert. Camila Tenorio França PPGCB.pdf: 5895108 bytes, checksum: daba019b5bd4acf2d9d72976ba7c959f (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012-08-08 / CAPES / Yersinia pestis é o agente causador da peste, doença primária de roedores transmitida por pulgas, que pode afetar o homem e outros mamíferos. A subtipagem molecular das cepas de Y. pestis tem sido dificultada pela grande similaridade genética entre os isolados. A análise dos locos CRISPR (Clustered Regularly Interspaced Short Palindromic Repeats) trouxe avanços em estudos filogenéticos e tipagem de cepas de Y. pestis dos numerosos focos dos diversos países. O objetivo deste trabalho foi avaliar a diversidade intraespecífica em cepas brasileiras de Y. pestis através do estudo dos locos CRISPR. As três sequências CRISPR (YPa, YPb e YPc) reconhecidas da Y. pestis foram amplificadas nas 98 cepas analisadas, originadas de diferentes fontes, focos e momentos epidemiológicos. Os amplicons obtidos por PCR foram analisados em gel de agarose e sequenciados. O loco YPa se mostrou o mais polimórfico, apresentando seis alelos de 449 a 630 pares de base (pb), seguido pelo YPb, com quatro alelos de 271 a 392 pb. O loco YPc, monomórfico, apresentou apenas um alelo de 331 pb em toda as cepas. Foi observado que as repetições diretas (DRA) são compostas de 28 pb, separadas por sequências espaçadoras únicas de 32 ou 33 pb em todos os locos. Dos 137 espaçadores já conhecidos 18 foram encontrados nas cepas analisadas e, adicionalmente, 19 novos espaçadores foram observados, 15 no loco YPa e quatro no loco YPb. A análise da distribuição dos espaçadores definiu 20 perfis genotípicos, refletindo a diversidade intraespecífica das cepas brasileiras, e evidenciou uma correlação entre a presença de alguns conjuntos de sequências espaçadoras e os focos de origem das cepas. A maioria dos perfis é exclusiva de uma cepa de um foco, e alguns são dispersos em vários focos e períodos. As incorporações/perdas de motivos observadas nos locos YPa e YPb sugerem que estes estão ativos e a ausência de alterações no loco YPc sugere inatividade. Em conclusão, a análise dos locos CRISPR revelou heterogeneidade e identificou características genéticas exclusivas nas cepas brasileiras que podem ser atribuídas à microevolução da bactéria após sua introdução no país.

Submitted by Pedro Barros (pedro.silvabarros@ufpe.br) on 2018-07-26T20:23:30Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Amanda Jôse Dantas da Silva.pdf: 3478100 bytes, checksum: 6410bdc099df7153ba4a5b669bb91340 (MD5) / Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-08-02T21:27:56Z (GMT) No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Amanda Jôse Dantas da Silva.pdf: 3478100 bytes, checksum: 6410bdc099df7153ba4a5b669bb91340 (MD5) / Made available in DSpace on 2018-08-02T21:27:56Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DISSERTAÇÃO Amanda Jôse Dantas da Silva.pdf: 3478100 bytes, checksum: 6410bdc099df7153ba4a5b669bb91340 (MD5) Previous issue date: 2017-04-25 / Esta dissertação tem como objetivo geral compreender, a partir de uma perspectiva dialógica de base bakhtiniana, as ações didáticas de uma docente do 4º ano do Ensino Fundamental e os possíveis diálogos travados por ela no uso de sequências de atividades para o ensino de produção textual, propostas pelo Instituto Qualidade no Ensino (IQE). Buscamos ainda observar, no cotidiano escolar, a utilização de dois artefatos didáticos do IQE no ensino da produção textual; refletir sobre as ações responsivas realizadas pela docente ao didatizá-los e construir o seu projeto didático autoral para o ensino de produção textual; bem como, identificar as concepções de língua e de ensino da escrita que norteiem a elaboração das sequências de atividades do Instituto e a prática pedagógica da professora participante. Para dar conta desses objetivos e melhor empreendermos as análises, recorremos a uma abordagem qualitativa, de natureza descritiva, interpretativista e documental. Para tal, utilizamosdistintos procedimentos e instrumentos para a geração dos fenômenos discursivos: observação de uma turma do 4º ano do Ensino Fundamental, em uma escola municipal do Estado de Pernambuco em que o IQE atuava, no ano de 2015; entrevista semiestruturada com a professora e com a coordenadora responsável pelo programa no munícipio; e notas de observação de campo. Para fundamentarmos nossas reflexões, trouxemos para o debate, conceitos teórico-metodológicos sobre sequências didáticas da Escola de Genebra ([2001] 2004; [1997] 2004; [1996] 2004; 2015; 2016); e sobre produção textual, com base em Geraldi ([1984] 2003, [1991] 2003, 2010), e em outras vozes conceituais, sob um viés dialógico e interacionista, como Soares (2001), Bonini (2002), Azevedo e Tardelli ([1997] 2004), Menegassi (2011), Leite (2012), entre outras. A partir das discussões geradas por esses aportes teóricos, como resultado do estudo, verificamos que apesar das sequências assumirem uma concepção de ensino e de escrita mais próxima do limiar interacionista, prevendo inclusive estratégias de escrita que direcionem a uma relação interlocutiva, a professora não se limitou meramente a repetir o que ‘orientavam’ as prescrições de uso (MATÊNCIO, 1998). Em favor do seu projeto didático autoral (BUNZEN, 2009) para o ensino textual, ela demonstrou uma atitude mais semelhante ao sujeito ativo bakhtiniano. Contudo, por meio das concordâncias, das ampliações ou das discordâncias sobre o discurso alheio, representado no protagonismo docente, notamos que a ação didática sedimenta práticas que transitam entre as noções interacionistas e o subjetivismo idealista - o que acaba por tecer o seu discurso didático com os fios tanto da inovação quanto do retorno a práticas tradicionais de ensino da escrita. / Esta disertación tiene como objetivo general comprender, a partir de una concepción dialógica de base bakhtiniana, las acciones didácticas de una maestra del 4º año de la Enseñanza Primaria y sus posibles conversaciones con las secuencias de actividades para enseñar la producción textual, propuestas por el Instituto Qualidade no Ensino (IQE). Hemos intentado, aún, observar, en el diario escolar, la utilización de dos instrumentos didácticos del IQE en la enseñanza de la escrita; reflexionar acerca de las acciones responsivas puestas por la educadora al utilizarlos en la clase y construir su proyecto didáctico autoral para la educación de la escrita; así también, identificar las concepciones de lengua y de enseñanza del texto que sirven de fundamento para la elaboración y la práctica pedagógica de la profesora participante. Para ejecutar estos objetivos y abrir la comprensión acerca de los análisis, hemos recogido a una visión cualitativa, de origen descriptiva, interpretativista y documental. Para llevar a cabo la investigación, hemos empleado distintos mecanismos y estrategías para la generación de los fenómenos discursivos: observación de un grupo del 4 º año de la enseñanza Primaria, en una Escuela de una ciudad de Pernambuco, donde el IQE ha actuado en 2015; entrevista semiestructurada con la maestra y con la coordinadora de la Secretaria de Educación local, responsable por el programa; y apuntes sobre las observaciones de la práctica. Para basarnos las reflexiones, hemos traído a la discusión, conceptos teóricos y metodológicos sobre secuencias didácticas de la Escuela de Ginebra ([2001] 2004; [1997] 2004; [1996] 2004; 2015; 2016); y sobre producción textual, fundamentándonos en Geraldi ([1984] 2003, [1991] 2003, 2010), y en otras voces conceptuales, desde un punto de vista dialógico e interaccionista, como Soares (2001), Bonini (2002), Azevedo y Tardelli ([1997] 2004), Menegassi (2011), Leite (2012), entre otras. Por medio de estas discusiones teóricas, como resultado del estudio, hemos percibido que a pesar de las secuencias suministraren una concepción de enseñanza y de producción de texto más cercana del pensamiento interaccionista, incluyendo estrategias de escritura que partan de un eje dialógico, la educadora no se ha limitado a repetir lo que decían las prescripciones del uso de los materiales (MATÊNCIO, 1998). En búsqueda de su proyecto didáctico autoral (BUNZEN, 2009) para la enseñanza del texto, ella nos ha demostrado una actitud semejante al sujeto bakhtiniano. Sin embargo, por medio de los acuerdos, de las ampliaciones o de los desaciertos acerca del discurso ajeno, representado por el protagonismo pedagógico, hemos observado que la acción didáctica mezclaprácticas que se mueven entre las nociones interaccionistasy el ‘subjetivismo idealista’ – lo que acaba por tejer su discurso educativo con hilos de la innovación y del regreso a las metodologías tradicionales de la enseñanza del texto.

Made available in DSpace on 2014-06-12T15:02:48Z (GMT). No. of bitstreams: 2 arquivo2079_1.pdf: 1542093 bytes, checksum: 5ba006fe6225bec7d678f8e2525b50f3 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Fundação de Amparo à Ciência e Tecnologia do Estado de Pernambuco / O gênero Phaseolus apresenta grande importância econômica no mundo, principalmente por ser uma das principais fonte de proteínas para alimentação humana. Estudos cariotípicos no gênero têm acompanhado os avanços das técnicas citogenéticas em plantas, desde análises convencionais até estudos comparativos de mapas citogenéticos construídos através da hibridização in situ fluorescente (FISH). Cromossomos artificiais de bactérias (BACs) foram utilizados como sondas em FISH na comparação entre os mapas de P. vulgaris (2n = 22), principal representante de gênero, e P. lunatus (2n = 22), uma espécie filogeneticamente próxima, revelando uma total conservação de sintenia e apenas três quebras de colinearidade. Visando estender os conhecimentos acerca da evolução do gênero, o presente estudo utilizou esses mesmos marcadores em FISH para evidenciar os principais eventos cromossômicos ocorridos entre P. vulgaris e P. microcarpus (2n = 22), uma espécie selvagem e distante filogeneticamente. Análises de bandeamento CMA/DAPI e localização de sítios de DNAr 5S e 45S e da sequência telomérica também foram realizadas. O estudo revelou que, apesar da distância filogenética entre as duas espécies, houve uma forte conservação de sintenia entre os homeólogos e apenas quatro quebras de colinearidade. Apenas eventos de inversão cromossômica foram propostos, justificando sua estabilidade numérica. Além disso, foram evidenciados padrões distintos de hibridização entre sequências repetitivas para uma mesma região cromossômica. Os resultados demonstraram que em Phaseolus a evolução cromossômica parece estar relacionada a eventos de rearranjo raros e de pouca complexidade, confirmando sua aparente estabilidade cariotípica postulada em estudos convencionais

Submitted by BRUNO CHIODEROLI GREGIO null (brunogregio@hotmail.com) on 2017-05-30T23:45:02Z No. of bitstreams: 1 dissertação-versão-final.pdf: 1021988 bytes, checksum: c0924e4811037991cd26568ddd59ae7a (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-05-31T18:33:45Z (GMT) No. of bitstreams: 1 gregio_bc_me_sjrp.pdf: 1021988 bytes, checksum: c0924e4811037991cd26568ddd59ae7a (MD5) / Made available in DSpace on 2017-05-31T18:33:45Z (GMT). No. of bitstreams: 1 gregio_bc_me_sjrp.pdf: 1021988 bytes, checksum: c0924e4811037991cd26568ddd59ae7a (MD5) Previous issue date: 2017-04-28 / Este trabalho apresenta uma proposta para o estudo de sequências de números reais, sobretudo no ensino médio. A partir da definição de uma sequência, estudamos os casos particulares das progressões aritméticas e geométricas. Como sabemos, é praxe os livros didáticos encerrarem o assunto sobre sequências por aqui, porém neste trabalho avançamos os estudos apresentando a noção de limite de uma sequência e os principais resultados sobre sequências convergentes. Tendo compreendido que cada número real pode ser obtido como o limite de uma sequência de Cauchy de números racionais, apresentamos as famosas constantes matemáticas e, π e φ, além dos números da forma √ a, como o limite de certas sequências de Cauchy de números racionais. / This work presents a proposal for the study on sequences of real numbers, especially in high school. From the de nition of a sequence, we study the particular cases of arithmetic and geometric progressions. As we know, it is usual for textbooks to terminate the subject of sequences here, but in this work we have advanced the studies presenting the notion of limit of a sequence and the main results on convergent sequences. Having understood that each real number can be obtained as the limit of a Cauchy sequence of rational numbers, we introduce the famous mathematical constants e, π and ϕ, beyond the numbers of the form √a, as the limit of certain Cauchy sequences of rational numbers.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2007. / Submitted by Rosane Cossich Furtado (rosanecossich@gmail.com) on 2010-01-04T21:40:52Z No. of bitstreams: 1 2007_FabioViniciusPintoSilva.pdf: 1375531 bytes, checksum: 2272e318dce7e1284d2d2eb04367db52 (MD5) / Approved for entry into archive by Carolina Campos(carolinacamposmaia@gmail.com) on 2010-01-05T17:08:01Z (GMT) No. of bitstreams: 1 2007_FabioViniciusPintoSilva.pdf: 1375531 bytes, checksum: 2272e318dce7e1284d2d2eb04367db52 (MD5) / Made available in DSpace on 2010-01-05T17:08:01Z (GMT). No. of bitstreams: 1 2007_FabioViniciusPintoSilva.pdf: 1375531 bytes, checksum: 2272e318dce7e1284d2d2eb04367db52 (MD5) Previous issue date: 2007-09-17 / Encontrar e visualizar semelhanças entre seqüências de DNA permite aprofundar o conhecimento sobre genomas de organismos em Biologia Molecular. Com o número de seqüências disponíveis para consulta em alguns bancos de dados crescendo exponencialmente, surge um desafio para a ciência da computação. É o de construir sistemas de informática com desempenho suficiente para permitir comparar seqüências genômicas em tempo hábil para a pesquisa e com um custo viável. Freqüentemente são usadas soluções heurísticas, devido ao grande tempo computacional necessário para o uso de soluções exatas. Soluções exatas atualmente apresentam complexidade de tempo quadrática em computadores convencionais, dificultando seu uso prático para seqüências de comprimento como as de aplicações reais. O principal objetivo deste trabalho é viabilizar o uso de algoritmos exatos para comparação de seqüências genômicas, acelerando a obtenção de seus resultados. É proposto um arranjo sistólico de elementos de processamento em hardware reconfigurável. Assim, é explorado o paralelismo potencial do algoritmo de programação dinâmica de Smith-Waterman, reduzindo sua complexidade de tempo de quadrática para linear. É proposta uma solução para minimizar o problema de gargalo de comunicação, esperado por uma implementação "ingênua" da solução. Além do sistema proposto, a prototipação realizada em FPGA é descrita, incluindo uma análise do desempenho obtido. _______________________________________________________________________________ ABSTRACT / To find and to visualize similarities between DNA sequences allow to deepen the knowledgement on genomas of organisms in Molecular Biology. With the number of available sequences for consultation in some data bases growing exponentially , a challenge for the computer science appears. It is to construct computing systems with enough performance to allow to compare genomics sequences in skillful time for the research and at a viable cost. Frequently heuristical solutions are used, due to the great computational time necessary to the use of exact solutions. Exact solutions currently presents quadratic time complexity in conventionals computers, making difficult its practical use for sequences of length as of real applications. The main objective of this work is to make possible the use of exact algorithms for comparison of genomics sequences, by speeding up the attainment of its results. A systolic arrangement of elements of processing in reconfigurable hardware is proposed. This way, the potential parallelism of the algorithm of dynamic programming of Smith-Waterman is explored, reducing its time complexity from quadratic to linear. Is also proposed a solution to minimize the problem of communication bottleneck, waited in a “naive” implementation. Besides the proposed system, the prototipation made in FPGA is described, including an analysis of the performance gotten.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Não informado / Neste trabalho, apresentamos uma análise sobre sequências numéricas dando ênfase a aplicações de conceitos como convergência, limitação e monotonicidade no ensino das progress~oes aritm etica e geom etrica, contextualizando com alguns temas do ensino m edio, a saber, fun c~oes, geometria e matem atica nanceira. Apresentamos propostas did aticas para abordagem em sala de aula das progress~oes relacionando com alguns problemas cl assicos da matem atica como por exemplo, o Paradoxo de Zen~ao. / São Cristóvão, SE