Algoritmos Evolutivos que utilizam modelos probabilísticos de distribuição dos valores das variáveis (para orientar o processo de busca da solução de problemas) são chamados Algoritmos de Estimação de Distribuição (AEDs). Esses algoritmos têm apresentado resultados relevantes para lidar com problemas relativamente complexos. O desempenho deles depende diretamente da qualidade dos modelos probabilísticos construídos que, por sua vez, dependem dos métodos de construção dos modelos. Os melhores modelos em geral são construídos por métodos computacionalmente complexos, resultando em AEDs que requerem tempo computacional alto, apesar de serem capazes de explorar menos pontos do espaço de busca para encontrar a solução de um problema. Este trabalho investiga modelos probabilísticos obtidos por algoritmos de reconstrução de filogenias, uma vez que alguns desses métodos podem produzir, de forma computacionalmente eficiente, modelos que representam bem as principais relações entre espécies (ou entre variáveis). Este trabalho propõe algumas estratégias para obter um melhor uso de modelos baseados em filogenia para o desenvolvimento de AEDs, dentre elas o emprego de um conjunto de filogenias em vez de apenas uma filogenia como modelo de correlação entre variáveis, a síntese das informações mais relevantes desse conjunto em uma estrutura de rede e a identificação de grupos de variáveis correlacionadas a partir de uma ou mais redes por meio de um algoritmo de detecção de comunidades. Utilizando esses avanços para a construção de modelos, foi desenvolvido uma nova técnica de busca, a Busca Exaustiva Composta, que possibilita encontrar a solução de problemas combinatórios de otimização de diferentes níveis de dificuldades. Além disso, foi proposta uma extensão do novo algoritmo para problemas multiobjetivos, que mostrou ser capaz de determinar a fronteira Pareto-ótima dos problemas combinatórios investigados. Por fim, o AED desenvolvido possibilitou obter um compromisso em termos de número de avaliações e tempo de computação, conseguindo resultados similares aos dos melhores algoritmos encontrados para cada um desses critérios de desempenho nos problemas testados. / Evolutionary Algorithms that use the distribution of values of variables as probabilistic models (to direct the search process of problem solving) are called Estimation of Distribution Algorithms (EDAs). These algorithms have presented relevant performance in handling relatively complex problems. The performance of such algorithms depends directly on the quality of probabilistic models constructed that, in turn, depend on the methods of model building. The best models are often constructed by computationally complex methods, resulting in AEDs that require high running time although they are able to explore less points in the search space to find the solution of a problem. This work investigates probabilistic models obtained by algorithms of phylogeny reconstruction since some of them can produce models in an efficient way representing the main relationships among species (or among variables). This work proposes some strategies for better use of phylogeny-based models in the development of EDAs, such as the employment of a set of phylogenies instead of only one phylogeny as a model of correlation among variables, the synthesis of the most relevant information from a set of phylogenies into a structure of network and the identification groups of correlated variables from one or more networks by an algorithm of community detection. Using those advances for model construction, a new search technique, called Composed Exhaustive Search, was developed in order to find solutions for combinatorial optimization problems with different levels of difficulty. In addition, an extension of the new algorithm for multi-objective problems was proposed, which was able to determine the Pareto-optimal front of the combinatorial problems investigated. Finally, the developed EDA makes possible to obtain a trade-off in terms of number of evaluations and running time, finding results that are similar to the ones achieved by the best algorithms found for each one of these performance criteria in the problems tested.

A Visualização Computacional trata de técnicas para representar e interagir graficamente com dados complexos, em geral de alta dimensionalidade. Dados de alta dimensionalidade são caracterizados por pontos representados em espaços vetoriais de alta dimensão, cada coordenada representando um atributo do vetor. Num grande número de aplicações da visualização multidimensional uma medida de similaridade existe entre esses vetores. Técnicas de projeção multidimensional podem ser utilizadas para posicionamento desses dados num plano de forma a facilitar a interpretação das relações de similaridade. Entretanto alguns problemas dessas técnicas comprometem a interpretação dos resultados obtidos. Este trabalho identifica esses problemas e propõe, uma técnica para posicionar os pontos no plano, através da formação de árvores filogenéticas a partir de relações de similaridade. Em geral árvores filogenéticas são utilizadas para codificação de relações de ancestralidade. Um algoritmo de geração e um algoritmo de traçado dessas árvores foram implementados no contexto do sistema PEx (Projection Explorer) e a solução é comparada com a funcionalidade das projeções na interpretação de dados multidimensionais em geral e, em particular, na representação de coleções de documentos, uma aplicação bastante estratégica da visualização computacional e da mineração visual de dados / Computational Visualization is concerned with graphical representation and exploration of complex data, usually bearing high dimensionality. Multidimensional data are characterized by points represented in vector spaces of many dimensions, each coordinate representing an attribute of the vector. In many applications a similarity measure can be found to highlight relationships of proximity between the vectors. In this environment projection techniques offer an alternative to ease interpretation coded by the similarity measures through proximity on the display. They do so by positioning the points on a bidimensional plane. Projection techniques are very useful to display and interact with data, but present some drawbacks that in some cases compromise the interpretation of certain features in data sets. This work discusses such problems and proposes, as an alternative to represent similarity relationships and to provide point placement on a plane, the use of phylogenetic trees, a representation typically employed to represent ancestrality relationships. An algorithm for generation and an algorithm for drawing such trees were implemented in a system called Projection Explorer. The approach is compared to that of multidimensional projections for multidimensional data in general and, in particular, for document data sets, an strategic application for multidimensional visualizations, since text can be represented and interpreted as multi-dimensional entities

A Visualização Computacional trata de técnicas para representar e interagir graficamente com dados complexos, em geral de alta dimensionalidade. Dados de alta dimensionalidade são caracterizados por pontos representados em espaços vetoriais de alta dimensão, cada coordenada representando um atributo do vetor. Num grande número de aplicações da visualização multidimensional uma medida de similaridade existe entre esses vetores. Técnicas de projeção multidimensional podem ser utilizadas para posicionamento desses dados num plano de forma a facilitar a interpretação das relações de similaridade. Entretanto alguns problemas dessas técnicas comprometem a interpretação dos resultados obtidos. Este trabalho identifica esses problemas e propõe, uma técnica para posicionar os pontos no plano, através da formação de árvores filogenéticas a partir de relações de similaridade. Em geral árvores filogenéticas são utilizadas para codificação de relações de ancestralidade. Um algoritmo de geração e um algoritmo de traçado dessas árvores foram implementados no contexto do sistema PEx (Projection Explorer) e a solução é comparada com a funcionalidade das projeções na interpretação de dados multidimensionais em geral e, em particular, na representação de coleções de documentos, uma aplicação bastante estratégica da visualização computacional e da mineração visual de dados / Computational Visualization is concerned with graphical representation and exploration of complex data, usually bearing high dimensionality. Multidimensional data are characterized by points represented in vector spaces of many dimensions, each coordinate representing an attribute of the vector. In many applications a similarity measure can be found to highlight relationships of proximity between the vectors. In this environment projection techniques offer an alternative to ease interpretation coded by the similarity measures through proximity on the display. They do so by positioning the points on a bidimensional plane. Projection techniques are very useful to display and interact with data, but present some drawbacks that in some cases compromise the interpretation of certain features in data sets. This work discusses such problems and proposes, as an alternative to represent similarity relationships and to provide point placement on a plane, the use of phylogenetic trees, a representation typically employed to represent ancestrality relationships. An algorithm for generation and an algorithm for drawing such trees were implemented in a system called Projection Explorer. The approach is compared to that of multidimensional projections for multidimensional data in general and, in particular, for document data sets, an strategic application for multidimensional visualizations, since text can be represented and interpreted as multi-dimensional entities

VIANA, Gerardo Valdíso Rodrigues. Técnicas para construção de árvores filogenéticas. 2007. 203 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2007. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-20T12:05:20Z No. of bitstreams: 1 2007_tese_gvrviana.pdf: 3571043 bytes, checksum: 34853f08d8a8ac37e7c9e07dcf25de25 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-25T11:50:34Z (GMT) No. of bitstreams: 1 2007_tese_gvrviana.pdf: 3571043 bytes, checksum: 34853f08d8a8ac37e7c9e07dcf25de25 (MD5) / Made available in DSpace on 2016-07-25T11:50:34Z (GMT). No. of bitstreams: 1 2007_tese_gvrviana.pdf: 3571043 bytes, checksum: 34853f08d8a8ac37e7c9e07dcf25de25 (MD5) Previous issue date: 2007 / Phylogenetic tree structures express similarities, ancestrality, and relationships between species or group of species, and are also known as evolutionary trees or phylogenies. Phylogenetic trees have leaves that represent species (taxons), and internal nodes that correspond to hypothetical ancestors of the species. In this thesis we rst present elements necessary to the comprehension of phylogenetic trees systematics, then ef cient algorithms to build them will be described. Molecular biology concepts, life evolution, and biological classi cation are important to the understanding of phylogenies. Phylogenetic information may provide important knowledge to biological research work, such as, organ transplantation from animals, and drug toxicologic tests performed in other species as a precise prediction to its application in human beings. To solve a phylogeny problem implies that a phylogenetic tree must be built from known data about a group of species, according to an optimization criterion. The approach to this problem involves two main steps: the rst refers to the discovery of perfect phylogenies, in the second step, information extracted from perfect phylogenies are used to infer more general ones. The techniques that are used in the second step take advantage of evolutionary hypothesis. The problem becomes NP-hard for a number of interesting hypothesis, what justify the use of inference methods based on heuristics, metaheuristics, and approximative algorithms. The description of an innovative technique based on local search with multiple start over a diversi ed neighborhood summarizes our contribution to solve the problem. Moreover, we used parallel programming in order to speed up the intensi cation stage of the search for the optimal solution. More precisely, we developed an ef cient algorithm to obtain approximate solutions for a phylogeny problem which infers an optimal phylogenetic tree from characteristics matrices of various species. The designed data structures and the binary data manipulation in some routines accelerate simulation and illustration of the experimentation tests. Well known instances have been used to compare the proposed algorithm results with those previously published. We hope that this work may arise researchers' interest to the topic and contribute to the Bioinformatics area. / Árvores filogenéticas são estruturas que expressam a similaridade, ancestralidade e relacionamentos entre as espécies ou grupo de espécies. Conhecidas como árvores evolucionárias ou simplesmente filogenias, as árvores filogenéticas possuem folhas que representam as espécies (táxons) e nós internos que correspondem aos seus ancestrais hipotéticos. Neste trabalho, além das informações necessárias para o entendimento de toda a sistemática filogenética, são apresentadas técnicas algorítmicas para construção destas árvores. Os conceitos básicos de biologia molecular, evolução da vida e classificação biológica, aqui descritos, permitem compreender o que é uma Filogenia e qual sua importância para a Biologia. As informações filogenéticas fornecem,por exemplo, subsídios importantes para decisões relativas aos transplantes de órgãos ou tecidos de outras espécies para o homem e para que testes de reação imunológica ou de toxicidade sejam feitos antes em outros sistemas biológicos similares ao ser humano. Resolver um Problema de Filogenia corresponde à construção de uma árvore filogenética a partir de dados conhecidos sobre as espécies em estudo, obedecendo a algum critério de otimização. A abordagem dada a esse problema envolve duas etapas, a primeira, referente aos casos em que as filogenias são perfeitas cujos procedimentos desenvolvidos serão utilizados na segunda etapa, quando deve ser criada uma técnica de inferência para a filogenia num caso geral. Essas técnicas consideram de forma peculiar as hipóteses sobre o processo de evolução. Para muitas hipóteses de interesse o problema se torna NP-Difícil, justificando-se o uso de métodos de inferência através de heurísticas, meta-heurísticas e algoritmos aproximativos. Nossa contribuição neste trabalho consiste em apresentar uma técnica de resolução desse problema baseada em buscas locais com partidas múltiplas em vizinhanças diversificadas. Foi utilizada a programação paralela para minimizar o tempo de execução no processo de intensificação da busca pela solução ótima do problema. Desta forma, desenvolvemos um algoritmo para obter soluções aproximadas para um Problema da Filogenia, no caso, para inferir, a partir de matrizes de características de várias espécies, uma árvore filogenética que mais se aproxima da história de sua evolução. Uma estrutura de dados escolhida adequadamente aliada à manipulação de dados em binário em algumas rotinas facilitaram a simulação e ilustração dos testes realizados. Instâncias com resultados conhecidos na literatura foram utilizadas para comprovar a performance do algoritmo. Esperamos com este trabalho despertar o interesse dos pesquisadores da área de Computação, consolidando, assim, o crescimento da Bioinformática.

Algoritmos Evolutivos que utilizam modelos probabilísticos de distribuição dos valores das variáveis (para orientar o processo de busca da solução de problemas) são chamados Algoritmos de Estimação de Distribuição (AEDs). Esses algoritmos têm apresentado resultados relevantes para lidar com problemas relativamente complexos. O desempenho deles depende diretamente da qualidade dos modelos probabilísticos construídos que, por sua vez, dependem dos métodos de construção dos modelos. Os melhores modelos em geral são construídos por métodos computacionalmente complexos, resultando em AEDs que requerem tempo computacional alto, apesar de serem capazes de explorar menos pontos do espaço de busca para encontrar a solução de um problema. Este trabalho investiga modelos probabilísticos obtidos por algoritmos de reconstrução de filogenias, uma vez que alguns desses métodos podem produzir, de forma computacionalmente eficiente, modelos que representam bem as principais relações entre espécies (ou entre variáveis). Este trabalho propõe algumas estratégias para obter um melhor uso de modelos baseados em filogenia para o desenvolvimento de AEDs, dentre elas o emprego de um conjunto de filogenias em vez de apenas uma filogenia como modelo de correlação entre variáveis, a síntese das informações mais relevantes desse conjunto em uma estrutura de rede e a identificação de grupos de variáveis correlacionadas a partir de uma ou mais redes por meio de um algoritmo de detecção de comunidades. Utilizando esses avanços para a construção de modelos, foi desenvolvido uma nova técnica de busca, a Busca Exaustiva Composta, que possibilita encontrar a solução de problemas combinatórios de otimização de diferentes níveis de dificuldades. Além disso, foi proposta uma extensão do novo algoritmo para problemas multiobjetivos, que mostrou ser capaz de determinar a fronteira Pareto-ótima dos problemas combinatórios investigados. Por fim, o AED desenvolvido possibilitou obter um compromisso em termos de número de avaliações e tempo de computação, conseguindo resultados similares aos dos melhores algoritmos encontrados para cada um desses critérios de desempenho nos problemas testados. / Evolutionary Algorithms that use the distribution of values of variables as probabilistic models (to direct the search process of problem solving) are called Estimation of Distribution Algorithms (EDAs). These algorithms have presented relevant performance in handling relatively complex problems. The performance of such algorithms depends directly on the quality of probabilistic models constructed that, in turn, depend on the methods of model building. The best models are often constructed by computationally complex methods, resulting in AEDs that require high running time although they are able to explore less points in the search space to find the solution of a problem. This work investigates probabilistic models obtained by algorithms of phylogeny reconstruction since some of them can produce models in an efficient way representing the main relationships among species (or among variables). This work proposes some strategies for better use of phylogeny-based models in the development of EDAs, such as the employment of a set of phylogenies instead of only one phylogeny as a model of correlation among variables, the synthesis of the most relevant information from a set of phylogenies into a structure of network and the identification groups of correlated variables from one or more networks by an algorithm of community detection. Using those advances for model construction, a new search technique, called Composed Exhaustive Search, was developed in order to find solutions for combinatorial optimization problems with different levels of difficulty. In addition, an extension of the new algorithm for multi-objective problems was proposed, which was able to determine the Pareto-optimal front of the combinatorial problems investigated. Finally, the developed EDA makes possible to obtain a trade-off in terms of number of evaluations and running time, finding results that are similar to the ones achieved by the best algorithms found for each one of these performance criteria in the problems tested.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-08-17T17:25:58Z No. of bitstreams: 1 FernandoOliveira.pdf: 2347086 bytes, checksum: 0b2d54b7d13b7467bee9db13f63100f5 (MD5) / Made available in DSpace on 2017-08-17T17:25:58Z (GMT). No. of bitstreams: 1 FernandoOliveira.pdf: 2347086 bytes, checksum: 0b2d54b7d13b7467bee9db13f63100f5 (MD5) Previous issue date: 2013-02-20 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Breast cancer is the second most common type of cancer in the world and difficult to diagnose. Distinguished Systems Aided Detection and Diagnosis Computer have been used to assist experts in the health field with an indication of suspicious areas of difficult perception to the human eye, thus aiding in the detection and diagnosis of cancer. This dissertation proposes a methodology for discrimination and classification of regions extracted from the breast mass and non-mass. The Digital Database for Screening Mammography (DDSM) is used in this work for the acquisition of mammograms, which are extracted from the regions of mass and non-mass. The Taxonomic Diversity Index (∆) and the Taxonomic Distinctness (∆*) are used to describe the texture of the regions of interest, originally applied in ecology. The calculation of those indices is based on phylogenetic trees, which applied in this work to describe patterns in regions of the images of the breast with two regions bounding approaches to texture analysis: circle with rings and internal with external masks. Suggested in this work to be applied in the description of patterns of regions in breast imaging approaches circle with rings and masks as internal and external boundaries regions for texture analysis. Support Vector Machine (SVM) is used to classify the regions in mass or non-mass. The proposed methodology provides successful results for the classification of masses and non-mass, reaching an average accuracy of 99.67%. / O câncer de mama é o segundo tipo de câncer mais frequente no mundo e de difícil diagnóstico. Distintos Sistemas de Detecção e Diagnóstico Auxiliados por Computador (Computer Aided Detection/Diagnosis) têm sido utilizados para auxiliar especialistas da área da saúde com a indicação de áreas suspeitas de difícil percepção ao olho humano, assim ajudando na detecção e diagnóstico de câncer. Este trabalho propõe uma metodologia de discriminação e classificação de regiões extraídas da mama em massa e não-massa. O banco de imagens Digital Database for Screening Mammography (DDSM) é usado neste trabalho para aquisição das mamografias, onde são extraído as regiões de massa e não-massa. Na descrição da textura da região de interesse são utilizados os Índices de Diversidade Taxonômica (∆) e Distinção Taxonômica (∆*), provenientes da ecologia. O cálculo destes índices é baseado nas árvores filogenéticas, sendo aplicados neste trabalho na descrição de padrões em regiões das imagens da mama com duas abordagens de regiões delimitadoras para análise da textura: círculo com anéis e máscaras internas com externas. Para classificação das regiões em massa e não-massa é utilizado o classificador Máquina de Vetores de Suporte (MVS). A metodologia apresenta resultados promissores para a classificação de massas e não-massas, alcançando uma acurácia média de 99,67%.

Made available in DSpace on 2015-05-14T12:14:09Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 3134384 bytes, checksum: 253c3fb1aaec508b89c44bcd7766a50c (MD5) Previous issue date: 2013-08-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this thesis, we investigate aspects of similarity between sequences of complete mitochondrial DNA. This line of study falls within the framework from the analysis of statistical properties of DNA sequences based on methods that seek to understand the information contained in these sequences a topic of renewed interest in the context of the so called Complex Systems. Previous approaches were used to obtain the frequencies of certain segments of nucleotides, regarded as the words of a given size, contained in sequences. These methods, inspired by studies devoted to the statistical properties of words distribution in linguistic and symbolical sequences, can be considered an alternative to techniques and algorithms for aligning sequences, and have been successful in the description of characteristics that allow to infer similarity and possible species grouping criteria, it means, biological afnity between DNA sequences. Previously, this methodology has been applied to evaluate the diferences between coding and nocoding DNA sequences and to extract linguistic aspects of these sequences by detecting keywords that describe relevant information embedded in the threads. In this dissertation, these studies are expanded in order to directly compare the contents of pairs of complete sequences of mitochondrial DNA, setting parameters that depend on the frequency distribution of sequences of words which highlight both the relevance of certain words as well as the possibility of grouping species estimating the distance between these words. Our results show that the best clusters between diferent species are obtained when we calculate the rate of agglomeration considering only frequencies of words. We have also observed that the larger the word size is, its greater clustering between sequences. The prospect of applying our results to analyze DNA sequences also belong to a single biological species, may be relevant in the construction of phylogenetic trees that are appropriate structures for understanding the evolutionary history of organisms. / Nesta dissertação, investigamos aspectos da similaridade entre sequências completas de DNA mitocondriais. Esta linha de estudo se insere no âmbito da análise de propriedades estatísticas de sequências de DNA baseadas em métodos que buscam entender a informação contida nessas sequências, tema de renovado interesse no contexto dos chamados Sistemas Complexos. Abordagens anteriores foram utilizadas para obtenção das frequências de determinados segmentos de nucleotídeos, considerados como palavras de um dado tamanho, contidos nas sequências. Tais métodos, inspirados em estudos dedicados às propriedades estatísticas de distribuição de palavras em textos linguísticos e sequências simbólicas, podem ser considerados uma alternativa às técnicas e algoritmos de alinhamento de sequências, e têm sido bem sucedidos na descrição de características que permitem inferir similaridade e possíveis critérios de agrupamentos de espécies, ou seja, afinidade biológica entre sequências de DNA. Anteriormente, esta metodologia foi aplicada para avaliar as diferenças entre sequências de DNA codificadas e não codificadas e para extrair aspectos linguísticos dessas sequências através da detecção de palavras-chaves que descrevem informações relevantes embutidas nas sequências. Nesta dissertação, ampliamos tais estudos, no sentido de comparar diretamente o conteúdo de pares de sequências completas de DNA mitocondriais, definindo parâmetros que dependem da distribuição de frequências de palavras das sequências que ressaltam tanto a relevância de determinadas palavras, bem como a possibilidade de agrupamentos de espécies estimando a distância entre essas sequências. Nossos resultados mostram que os melhores agrupamentos entre espécies distintas são obtidos quando calculamos a taxa de aglomeração levando em conta apenas as frequências das palavras. Notamos, também, que quanto maior o tamanho da palavra mais consistente é o agrupamento entre as sequências. A perspectiva de aplicação de nossos resultados, para analisar também sequências de DNA pertencentes a uma única espécie biológica, pode ser relevante na construção de árvores filogenéticas que são estruturas adequadas para se compreender a história evolucionária dos organismos.