Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2006. / Submitted by Luana Patrícia de Oliveira Porto (luana_porto_23@hotmail.com) on 2009-09-29T22:25:03Z No. of bitstreams: 1 2006_HedersonPereiraSantos.pdf: 829940 bytes, checksum: 2a5c9eb3eec94eeac21dfc0bcdb86756 (MD5) / Approved for entry into archive by Luanna Maia(luanna@bce.unb.br) on 2009-10-02T15:12:08Z (GMT) No. of bitstreams: 1 2006_HedersonPereiraSantos.pdf: 829940 bytes, checksum: 2a5c9eb3eec94eeac21dfc0bcdb86756 (MD5) / Made available in DSpace on 2009-10-02T15:12:08Z (GMT). No. of bitstreams: 1 2006_HedersonPereiraSantos.pdf: 829940 bytes, checksum: 2a5c9eb3eec94eeac21dfc0bcdb86756 (MD5) Previous issue date: 2006-12-14 / Biologia Computacional é uma área da Ciência da Computação que tem por objetivo o estudo e aplicação de técnicas e ferramentas computacionais aos problemas da Biologia Molecular. Dentre os problemas pesquisados, encontra-se o de evolução molecular, onde são estudados métodos para comparar seqüências de espécies distintas, baseados em eventos mutacionais. Estes métodos geram medidas de distância, que podem ser empregadas para verificar o relacionamento em termos evolutivos entre dois organismos. Uma técnica de computar distância é comparar blocos, formados por um ou mais genes, de genomas de dois organismos. O nosso trabalho pertence à área de Rearranjo de Genomas que, de forma genérica, visa resolver o problema combinatorial de encontrar uma seqüência mínima de eventos de rearranjo (mutações) que transformam um genoma em outro. Estudamos um evento de rearranjo específico – transposição, que move uma porção de genes de um local para outro dentro do mesmo cromossomo. Este evento gera o problema da ordenação por transposições, que consiste em computar e encontrar a menor seqüência de transposições que transformam um genoma em outro. Neste trabalho propusemos dois algoritmos de aproximação baseados no formalismo algébrico de Dias e Meidanis para o problema de ordenação por transposições. Implementamos estes algoritmos utilizando a linguagem Java e comparamos os resultados obtidos com outros encontrados na literatura. Este trabalho visa contribuir para encontrar a complexidade do problema de ordenação por transposições que ainda não é conhecida. _________________________________________________________________________________________ ABSTRACT / Computational Biology is an area that aims to study and to apply techniques and computational tools to problems of molecular biology. One of these problems is molecular evolution, in which methods are proposed for comparing sequences of distinct species, based on mutational events. These methods generate distance measures that could be employed to verify the evolutionary relationship between two organisms. A technique to compute distance is to compare blocks, composed by one ore more genes, of the genomes of two organisms. This work belongs to the field of genome rearrangement, that has the objective to solve the combinatorial problem of finding a minimum sequence of rearrangement events that transform a genome into another. We studied a particular rearrangement event - transposition, that moves a portion of genes from a local to another inside one chromosome. This event generates the problem of sorting by transpositions, that consists in computing and finding the minimum sequence of transpositions that transform a genome into another. In this work, we proposed two approximation algorithms based on the algebraic formalism of Dias and Meidanis to solve the problem of sorting by transpositions. We implemented these algorithms using the Java language, and compared the results obtained with the results of other algorithms found in the literature. This work aims to contribute to find the complexity of this problem still unknown.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Mecânica, 2007. / Submitted by Kathryn Cardim Araujo (kathryn.cardim@gmail.com) on 2009-11-27T13:35:11Z No. of bitstreams: 1 2007_AnnaPauladeSousaParenteRodrigues.PDF: 3031715 bytes, checksum: 258343a10631bc1ac04d15de5d6f8273 (MD5) / Approved for entry into archive by Joanita Pereira(joanita) on 2009-11-27T16:20:57Z (GMT) No. of bitstreams: 1 2007_AnnaPauladeSousaParenteRodrigues.PDF: 3031715 bytes, checksum: 258343a10631bc1ac04d15de5d6f8273 (MD5) / Made available in DSpace on 2009-11-27T16:20:57Z (GMT). No. of bitstreams: 1 2007_AnnaPauladeSousaParenteRodrigues.PDF: 3031715 bytes, checksum: 258343a10631bc1ac04d15de5d6f8273 (MD5) Previous issue date: 2007 / O rotor é o componente do sistema hidrocinético cujas características de configuração são de suma importância, pois influencia diretamente no rendimento global do sistema. Dessa maneira, a determinação da geometria de pá que melhor se adapta as condições de funcionamento impostas, aumentando a potência gerada, é um importante fator a ser otimizado na turbina hidrocinética (THC). Para que a otimização se torne mais eficiente, é necessário realizar a implementação de um modelo matemático capaz de descrever o comportamento da THC. No presente trabalho utilizou-se o MATLAB 7.0 na plataforma Windows XP. Tal algoritmo é baseado na definição de parâmetros operacionais e dimensionais, os quais permitem o tratamento de dados de ensaios de desempenho, assim como a proposição de uma linha de desenvolvimento tecnológico do projeto hidrodinâmico do rotor. Um modelo simplificado do escoamento na THC possibilita uma avaliação sistemática do efeito da geometria da máquina, considerando o efeito de um difusor no incremento da potência gerada. Algoritmos genéticos foram utilizados para a otimização da geometria das pás, isto é, a melhor combinação dos ângulos dos bordos de ataque e de fuga, além da dimensão da corda de cada perfil. Simulações numéricas foram realizadas, através do código comercial ANSYS-CFX 11, a fim de se validar toda a metodologia matemática e de otimização. Comprovando a capacidade do modelo matemático de descrever o comportamento da THC, além da viabilidade do uso de algoritmos genéticos para sua otimização. _________________________________________________________________________________ ABSTRACT / The rotor is the part of the hydrokinetic system whose configuration characteristics are essential due to its influence on the global efficiency of the system. The definition of the blade runner that adapts to the imposed working conditions, increasing the power, is an important factor to be optimized in a hydrokinetic turbine (HKT). In order to make the optimization more efficient, a mathematical model capable of describing the HT behavior has to be implemented. In this work the MATLAB 7.0 in the Windows XP platform was used. The algorithm is based on the definition of operational and dimensional parameters that enable the treatment of performance test data and the proposition of a technological development line of the hydrodynamic project of the rotor. A simplified flowing model in the HKT enables a systemic evaluation of the geometric effect of the machine, considering the effect of a diffuser on the increase of the generated power. Genetic algorithms were applied for blade geometry optimization in order to obtain the best combination of the angles of leading and trailing edges besides the dimensions of the ropes of each profile. Numerical simulations were conducted using the commercial code ANSYS-CFX 11 to validate the mathematical methodology and the optimization. The results indicate that the applied model describes properly the HKT behavior and that the genetic algorithm optimized the hydrokinetic system of the rotor.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Civil e Ambiental, 2007. / Submitted by Diogo Trindade Fóis (diogo_fois@hotmail.com) on 2009-12-11T13:03:54Z No. of bitstreams: 1 2007_CarolinadeLimaNeves.PDF: 1219008 bytes, checksum: 698a907e6bbcaf1e42fdfa65f017abb6 (MD5) / Approved for entry into archive by Daniel Ribeiro(daniel@bce.unb.br) on 2009-12-11T22:32:12Z (GMT) No. of bitstreams: 1 2007_CarolinadeLimaNeves.PDF: 1219008 bytes, checksum: 698a907e6bbcaf1e42fdfa65f017abb6 (MD5) / Made available in DSpace on 2009-12-11T22:32:12Z (GMT). No. of bitstreams: 1 2007_CarolinadeLimaNeves.PDF: 1219008 bytes, checksum: 698a907e6bbcaf1e42fdfa65f017abb6 (MD5) Previous issue date: 2007-09-18 / A preocupação com o uso racional da água e com o controle de perdas nas redes de distribuição de água aumentou os esforços para o desenvolvimento de ferramentas que auxiliassem na operação desses sistemas. Por isso, o conhecimento do comportamento da rede em diversas condições tornou-se atraente para as empresas de saneamento. Os modelos de simulação hidráulica permitem que o desempenho da rede seja previsto possibilitando a adoção de medidas de controle mais eficazes. Entretanto, com o passar do tempo, as tubulações que compõem a rede vão alterando suas características originais de resistência hidráulica pelo envelhecimento mudando assim os parâmetros de projeto. Como alguns parâmetros são de difícil medição em campo uma alternativa que tem sido muito usada é a calibração dessas variáveis a partir da comparação de valores de pressão e/ou vazão medidos em campo e aqueles calculadas pelos simuladores, a partir de parâmetros obtidos por alguma técnica de otimização. Neste trabalho foi desenvolvido um algoritmo de calibração utilizando problema inverso, simulador hidráulico de escoamento de água em regime permanente e algoritmos genéticos como técnica de otimização. O programa foi testado utilizando diferentes valores para os parâmetros de entrada com o objetivo de avaliar a interferência desses valores na eficiência do algoritmo proposto. Os resultados obtidos neste trabalho apontaram que o algoritmo proposto conduz a bons valores de vazão, entretanto, não se conseguiu obter uma solução única para as resistências na calibração em regime permanente. A calibração pelo controle simultâneo de pressão e vazão, testado em alguns casos neste trabalho, indicou que é mais eficiente que a calibração por controle apenas da pressão. _________________________________________________________________________________ ABSTRACT / The concern on rational water use and on losses control in the water distribution networks increased the efforts for the development of tools to assist the operation of these systems. Therefore, the knowledge of the network behavior in different conditions became attractive for the water industry. Hydraulic simulation models allows prediction of distribution network performance making possible the adoption of more efficient control measures. However, with time, the network pipes have their original resistance characteristics modified by ageing changing the project parameters. Due to the difficulty to measure such parameters in the field, an alternative that has been used is the calibration of these variables from the comparison of pressure or outflow values measured in field and those calculated by the mathematical simulators, from parameters obtained by some optimization technique. In this work a calibration algorithm using inverse problem, a steady-state hydraulic simulator and genetic algorithm optimization technique was developed. The program was tested using different input parameter values aiming to evaluate the interferences of these parameter values in the efficiency of the algorithm. The results obtained in this work show that good flow values can be obtained, however, a unique solution for the values of resistance was not obtained in the calibration process in steady state flow. The calibration using simultaneous control of pressure and flow, tested in a few cases in this work indicated that this procedure is more efficient than the calibration using only pressure control.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2009. / Submitted by Elna Araújo (elna@bce.unb.br) on 2010-04-01T20:50:35Z No. of bitstreams: 1 2009_MaisaNettoLeidemer.pdf: 1790802 bytes, checksum: 102a7b5f90bae15f2bb2c2f8de9bca2f (MD5) / Approved for entry into archive by Lucila Saraiva(lucilasaraiva1@gmail.com) on 2010-04-15T00:49:29Z (GMT) No. of bitstreams: 1 2009_MaisaNettoLeidemer.pdf: 1790802 bytes, checksum: 102a7b5f90bae15f2bb2c2f8de9bca2f (MD5) / Made available in DSpace on 2010-04-15T00:49:29Z (GMT). No. of bitstreams: 1 2009_MaisaNettoLeidemer.pdf: 1790802 bytes, checksum: 102a7b5f90bae15f2bb2c2f8de9bca2f (MD5) Previous issue date: 2009-03 / Problemas de otimização multiobjetivo na presença de incertezas são muito frequentes na engenharia. A fabricação de dispositivos, como os circuitos de RF/microondas, muitas vezes são afetadas por incertezas associadas aos componentes de fabricação. Desta forma, é desejável uma metodologia de projeto robusto que considere estas incertezas durante o processo de otimização. Esta dissertação propõe tal metodologia de projeto robusto a partir dos conceitos de otimização multiobjetivo evolucionária e análise de sensibilidade. A Transformada Unscented é utilizada para análise da sensibilidade e como ferramenta no algoritmo de otimização robusta. O projeto robusto é definido em três etapas: a caracterização da incerteza associada ao problema, a definição dos parâmetros sensíveis de projeto e a otimização robusta. A metodologia proposta é testada em funções analíticas e é realizado o projeto robusto de um amplificador de potência classe E, que opera na faixa de UHF. _________________________________________________________________________________________ ABSTRACT / Multi-objective optimization problems in the presence of uncertainties occur very often in engineering. The manufacture of devices, for example RF/microwaves circuits, is surrounded by uncertainties associated to the manufacturing components. So it’s desirable to establish a method that renders a robust design in which uncertainties are considered during the optimization process. This dissertation presents this method utilizing the concepts of evolutionary multiobjective optimization and sensitivity analysis. The Unscented Transformation is used in the sensitivity analysis and as an auxiliary tool of robust optimization algorithm. The robust design is a three-part project: the characterization of the uncertainties associated with the problem, the identification of the sensitivity parameters and the robust optimization. The method presented is tested in analytical functions and the robust project of a class-E power amplifier operating in UHF band is elaborated.

Tese (doutorado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2008. / Submitted by Thaíza da Silva Santos (thaiza28@hotmail.com) on 2011-02-12T18:19:36Z No. of bitstreams: 1 2008_MariaJosePDantas.pdf: 1493172 bytes, checksum: 18a925483554ae5d93882b6cbc6e8893 (MD5) / Approved for entry into archive by Daniel Ribeiro(daniel@bce.unb.br) on 2011-02-14T23:16:54Z (GMT) No. of bitstreams: 1 2008_MariaJosePDantas.pdf: 1493172 bytes, checksum: 18a925483554ae5d93882b6cbc6e8893 (MD5) / Made available in DSpace on 2011-02-14T23:16:54Z (GMT). No. of bitstreams: 1 2008_MariaJosePDantas.pdf: 1493172 bytes, checksum: 18a925483554ae5d93882b6cbc6e8893 (MD5) / Este trabalho discute a aplicação de metodologias evolucionárias ao projeto de filtros de RF/microondas demandados nos sistemas eletrônicos atuais. A recente tendência por operações em múltiplas bandas de freqüências dos sistemas de comunicações móveis impõe especificações cada vez mais rigorosas para os circuitos de microondas, tais como tamanho reduzido e operações multi-bandas, que são características difíceis de serem obtidas por métodos convencionais. Propõe-se aqui um método de síntese automática de circuitos analógicos de duas portas, usando algoritmo evolucionário híbrido (memético), capaz de atender às necessidades das aplicações modernas. O algoritmo proposto aplica conhecimento especialista para definir um esquema de representação variável bidimensional utilizando matriz posicional e operadores genéticos 2D adequados, para impor um conjunto moderado de restrições estruturais às soluções candidatas sem, contudo, perder a flexibilidade para gerar topologias inovadoras. A combinação de um algoritmo evolucionário bi-objetivo (para evoluir topologias) com processos de busca local utilizando a técnica Simulated Annealing em locais estratégicos do ciclo evolucionário (para melhorar os parâmetros) potencializam o algoritmo, e permitem um balanceamento entre a otimização da topologia e dos parâmetros, que ocorrem simultaneamente. Os resultados mostram que a aplicação do método evolucionário proposto é capaz de gerar, com pequenas populações, poucas gerações, circuitos de duas portas de tamanhos reduzidos e estruturados, em conformidade com as especificações. São sintetizados vários filtros cujos projetos apresentam considerável grau de dificuldade, tais como filtros passafaixa assimétricos, filtros rejeita-faixa, filtros de duas faixas de passagem e filtros de banda larga. _________________________________________________________________________________ ABSTRACT / This work discusses the use of evolutionary methodologies in the project of RF/Microwave Filters demanded in the current electronic systems. The recent trend of multi-frequency bands operations in wireless communication systems along with the explosion in wireless portable devices are imposing more stringent requirements such as size reduction, and multi-band operations for the microwave circuits, which are difficult characteristics to be obtained by conventional methodologies. Here, the method proposed is of an automated synthesis of two-port analogical circuits, using hybrid evolutionary (memetic) algorithm, capable of attending the needs of modern applications. The proposed algorithm applies expert knowledge to define a bidimensional representation scheme of variable size using a positional matrix and suitable genetic 2D operators, for imposing a set of moderate constraints on the structure of the candidate solutions, without, however, losing the flexibility to generate innovating topologies. The combination of an bi-objective evolutionary algorithm (to evolve topologies) and a processes of local search using Simulated Annealing technique in strategic locals of evolutionary cycle (to improve the parameters) strives for the maximum potential of the algorithm, and allows the balance between topology and parameters optimization, which occurs simultaneously. The results show that the proposed evolutionary method application is capable of generating, with small populations, few generations, two-port circuits of reduced and structured sizes, according to the specifications. Several filters are synthesized which projects present a considerable difficulty degree, such as asymmetric bandpass filters, stopband filters, dualband bandpass filters, and wideband filters.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Estatística, 2010. / Submitted by Jaqueline Ferreira de Souza (jaquefs.braz@gmail.com) on 2011-02-22T15:09:28Z No. of bitstreams: 1 2010_FredericoLaradeSouza.pdf: 447130 bytes, checksum: 90cb6581cfce9e00b4ef65d2a68b5fcb (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2011-02-23T10:32:52Z (GMT) No. of bitstreams: 1 2010_FredericoLaradeSouza.pdf: 447130 bytes, checksum: 90cb6581cfce9e00b4ef65d2a68b5fcb (MD5) / Made available in DSpace on 2011-02-23T10:32:52Z (GMT). No. of bitstreams: 1 2010_FredericoLaradeSouza.pdf: 447130 bytes, checksum: 90cb6581cfce9e00b4ef65d2a68b5fcb (MD5) / Neste trabalho estudamos propriedades da mistura finita de duas componentes extremais da mesma classe e utilizamos o algoritmo EM como método de estimação dos parâmetros das misturas. Primeiro calculamos as medidas como média, mediana, variância e moda de cada mistura, em seguida provamos a identificabilidade da classe de distribuição Weibull e Gumbel, pelo mesmo método já utilizado para provar a identificabilidade da classe Fréchet. Descrevemos o algoritmo EM com método de estimação do parâmetros das misturas e finalmente para testar o algoritmo com os modelos descritos, com simulações estimamos os parâmetros das misturas e calculamos o erro quadrático médio para as estimativas dos parâmetros de forma das misturas. _____________________________________________________________________________ ABSTRACT / We study properties of finite mixture of two extremal components of the same class and use the EM algorithm as a method to estimate the parameters of the mixtures. First we calculate the measures as mean, median, variance and mode of each mix- ture, then we prove the identifiability of the class of Weibull and Gumbel distribution using the same method already used to prove the identifiability of the class of Frechet distributions. Describe the EM algorithm as a method of parameter estimation of mixtures and finally to test the algorithm with the models described, with simulations we estimate the parameters of mixtures and calculate the mean square error for the estimated shape parameter of the mixtures.

Dissertação (mestrado)-Universidade de Brasília, Departamento de Estatística, 2011. / Submitted by Shayane Marques Zica (marquacizh@uol.com.br) on 2011-11-10T10:06:51Z No. of bitstreams: 1 2011_RaucelioCoelhoCardochValdes.pdf: 1068729 bytes, checksum: a4f97eab9ad84ac93f0764f8bfe382d2 (MD5) / Approved for entry into archive by Elzi Bittencourt(elzi@bce.unb.br) on 2011-12-07T14:13:26Z (GMT) No. of bitstreams: 1 2011_RaucelioCoelhoCardochValdes.pdf: 1068729 bytes, checksum: a4f97eab9ad84ac93f0764f8bfe382d2 (MD5) / Made available in DSpace on 2011-12-07T14:13:26Z (GMT). No. of bitstreams: 1 2011_RaucelioCoelhoCardochValdes.pdf: 1068729 bytes, checksum: a4f97eab9ad84ac93f0764f8bfe382d2 (MD5) / Misturas de finitas de densidades de variáveis aleatórias _-estáveis é uma alternativa de modelagem para dados multimodais com origem em subpopulações que apresentam assimetria e caudas pesadas. Na família das variáveis aleatórias _-estáveis os únicos membros com densidade em forma fechada simples são as Normais, Cauchy e Lévy1 2 . Entretanto, sua função característica é bem conhecida e envolve quatro parâmetros. Neste trabalho, foram aplicados dois métodos de estimação dos parâmetros de uma mistura finita de densidades _-estáveis. O primeiro método é o Estimador via Função Característica (EFC) que minimiza a distância entre a função característica teórica e a função característica empírica, quando as componentes são Normais, Cauchy e _-estáveis simétricas. O segundo método é uma adaptação do algoritmo EM (Expectation-Maximization), devido ao cálculo numérico das densidades _-estáveis simétricas. Ilustrações numéricas dos resultados com dados reais e simulados também são apresentados. _______________________________________________________________________________ ABSTRACT / Finite mixtures of _-stable random variables` densities is an alternative model for multimodal data stemming from subpopulations with skewed and heavy-tailed distributions. Regarding the family of _-stable random variables, the only members with simple closed-form density are the Normal, Cauchy and Lévy1 2 distributions. However, its characteristic function is well-known, and encompasses four parameters. In this study, two methods of parameter estimation of a finite mixture of _- stable densities have been applied. The first method is the Characteristic Function Estimator (CFE), which minimizes the distance between the theoretical characteristic function and the empirical characteristic function whenever there are Normal, Cauchy and symmetric _-stable components. The second method consists of an adaptation of the Expectation-Maximization (EM) algorithm, due to numerical calculations of symmetric _-stable densities. Numerical illustrations of results, consisting of real and simulated data, are presented in this study as well.

No description available.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Estatística, 2103. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2013-08-13T15:56:24Z No. of bitstreams: 1 2013_ThaysaGuimaraesSouza.pdf: 1450329 bytes, checksum: 5e412eeaded3f9f11a6aa716cd0de9ab (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-08-19T15:10:23Z (GMT) No. of bitstreams: 1 2013_ThaysaGuimaraesSouza.pdf: 1450329 bytes, checksum: 5e412eeaded3f9f11a6aa716cd0de9ab (MD5) / Made available in DSpace on 2013-08-19T15:10:23Z (GMT). No. of bitstreams: 1 2013_ThaysaGuimaraesSouza.pdf: 1450329 bytes, checksum: 5e412eeaded3f9f11a6aa716cd0de9ab (MD5) / Este trabalho busca revisar e comparar numericamente diferentes metodologias de análise de dados longitudinais com estrutura assintótica. Especificamente, são estudados testes de ausência de efeito simples com base nos trabalhos de Wang (2004), von Borries (2008) e Zhang (2008). As curvas de poder desses testes são construídas para diferentes cenários de simulação e a partir disso, constata-se que o teste de Zhang (2008) apresenta resultados superiores, mesmo nos casos em que os testes de von Borries (2008) e Wang (2004) eram tidos como adequados. Como conseqüência, esses testes são adaptados ao algoritmo de agrupamento PPCLUSTEL e utilizados na análise de dados de microarranjo, eletroencefalografia e eletromiografia. Os softwares SAS e Gnuplot são adotados na obtenção dos resultados. ______________________________________________________________________________ ABSTRACT / This work looks at different methodologies for analyzing longitudinal data with asymptotic structure. The studies focus specically on tests of no simple e ect based on the works of Wang (2004), von Borries (2008) and Zhang (2008). The power curves of these tests are then built for di erent simulation scenarios and from these curves it can be seen that Zhang's (2008) tests presents superior results, even in the cases where von Borries's (2008) and Wang's (2004) tests were considered adequate. Therefore, these tests are adapted to the clustering algorithms PPCLUSTEL and used in the analysis of microarray, electroencephalography and electromyography data. SAS and Gnuplot software were adopted for obtaining the results.

Dissertação (Mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação Mestrado em Informática, 2013. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2014-04-16T13:34:05Z No. of bitstreams: 1 2013_LuizAugustoGarciaSilva.pdf: 810446 bytes, checksum: 291c6f45324fb72ea0a2f50ea0f10dc2 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2014-04-16T14:54:51Z (GMT) No. of bitstreams: 1 2013_LuizAugustoGarciaSilva.pdf: 810446 bytes, checksum: 291c6f45324fb72ea0a2f50ea0f10dc2 (MD5) / Made available in DSpace on 2014-04-16T14:54:51Z (GMT). No. of bitstreams: 1 2013_LuizAugustoGarciaSilva.pdf: 810446 bytes, checksum: 291c6f45324fb72ea0a2f50ea0f10dc2 (MD5) / Em Biologia Computacional, eventos mutacionais afetando grandes porções de um genoma são estudados na área de Rearranjo de Genomas. Particularmente, a transposição é um evento mutacional que troca de posição dois blocos contíguos de genes em um cromossomo. Este evento gera o problema da distância de transposição (PDT), que consiste em encontrar o número mínimo de transposições necessárias para transformar um cromossomo em outro. Recentemente, foi mostrado que o PDT é NP-difícil. Na literatura, muitos algoritmos foram propostos para resolver este problema, seguindo abordagens diferentes. Neste trabalho, utilizaremos o formalismo algébrico proposto por Meidanis e Dias, para a modelagem de cromossomos e transposições, e resultados clássicos de Grupos de Permutações para propor um algoritmo de aproximação com razão 2 para o problema da distância de transposição. Embora existam algoritmos com razão de aproximação melhores, a contribuição do presente trabalho é teórica, pois propõe uma solução para o problema da distância de transposição utilizando apenas resultados conhecidos de Teoria de Grupos de Permuta- ções, desvinculada do formalismo clássico Bafna e Pevzner. É importante notar que nosso algoritmo simula, de forma natural, a solução baseada em grafo de ciclos de Bafna e Pevzner. Nossa solução poderá ser automatizada em parte, e acreditamos que indica caminhos novos, que possibilitarão tanto diminuir a razão de aproximação quanto obter uma outra prova usando resultados de Grupos de Permutações para mostrar que o problema da distância de transposição é NP-difícil. O algoritmo proposto foi implementado na linguagem de programação Java. Utilizamos um sistema de álgebra computacional, chamado GAP, para computar operações envolvendo permutações. O algoritmo foi auditado na ferramenta GRAAu, o que permitiu a comparação de todas as distâncias de transposições dadas por nosso algoritmo, para todas as permutações de tamanho 2 até 11, com os valores exatos. Os resultados dessa auditoria foram comparados com outros encontrados na literatura. ______________________________________________________________________________ ABSTRACT / In computational biology, mutational events a ecting large portions of a genome are studied in genome rearrangements. Particularly, transposition is a mutational event that changes two contiguous blocks of genes inside a single chromosome. This event generates the problem of transposition distance, which is to nd the minimum number of transpositions transforming a chromosome into another. Recently, this problem was proved to be NP-hard. In the literature many algorithms were proposed to solve this problem, taking into account di erent approaches. In the present work, we will use the algebraic formalism for chromosome modeling and transpositions proposed by Meidanis and Dias, and classic results of Permutation Groups to suggest a 2-approximation algorithm for the transposition distance problem. Although there are better approximation algorithms, the contribution of this work is the proposition of a solution to the transposition distance problem using only known results of Permutation Groups Theory, dissociated from the classic formalism proposed by Bafna and Pevzner. It is worth noting that our algorithm simulates, in a natural way, the solution based on Bafna and Pevzner's cycle graph. Our solution can be automated in part, and we believe that it indicates new ways that enable to decrease the approximation ratio and to achieve another proof, using results of Permutation Groups, to show that the problem of transposition distance is NP-hard. The proposed algorithm was implemented using Java programming language. We have used a computer algebra system, called GAP, to compute operations involving permutations. The algorithm was also audited in GRAAu tool, which allowed the comparison of all transposition distances given by our algorithm, for all permutations of size 2 to 11, with the exact values. The results of this audit were compared with others found in the literature.