A utilização de redes complexas para a descriçãoi de diversos sistemas naturais e artificias,compreendidos nas mais diversas áreas do conhecimento humano, tem se mostrado uma abordagem poderosa para a redução da complexidade inerente a tais sistemas. Em muitos casos, tal complexidade resulta do número de componentes envolvidos e de suas intrincadas relações. Uma forma de reduzir a complexidade associada a tais sistemas, consiste em identificar e agrupar componentes que possuam características similares. Sendo assim, desenvolvemos nesta tese métodos de identificação de comunidades em redes complexas. Tais métodos se baseiam na ideia de que comunidades surgem quando grupos de vértices possuem um número mais elevado de conexões entre os vértices do mesmo grupo do que com vértices externos à este grupo. Além disso, utilizamos a função modularidade como função objetivo e como forma de avaliação e comparação dos resultados obtidos nesta tese com resultados previamente reportados na literatura. Uma vez estabelecido um método de identificação de comunidades, utilizamos a abordagem de redes complexas para a determinação de domínios estruturais de proteínas. Para tal, criamos redes de contato entre os aminoácidos de uma proteí?na buscando representar apenas as ligações relevantes do ponto de vista topológico. Por meio destas representações, aplicamos os métodos de identificação de comunidades desenvolvidos nesta tese, no intuito de identificar domínios estruturais de cadeias proteicas. Por fim, desenvolvemos um método específico para a identificação de domínios em proteínas com dois domínios sequencias, concluindo desta forma, os objetivos propostos nesta tese. / The use of complex networks for the representation of various natural and artificial sys- tems in the most diverse fields of human knowledge, has proven to be a powerful approach for the reduction of the complexity in the study of such systems. In many cases, this complexity emerges from the number of components of the system and from the intricate relationship between them. A reduction in this complexity is made possible by the iden- tification and grouping of the components of the system with similar characteristics. In this way, we developed in this thesis, methods for community identification in complex networks. Such methods are based on the notion that communities arise when groups of vertices are more densely connected with vertices of their same group, than with ver- tices belonging to other groups in the network. Moreover, the modularity function has been used as an objective function, and as a score for the evaluation and comparison of the results obtained in this thesis with the results reported in the literature of complex networks. Upon the establishment of a method for community detection, we used the framework of complex networks to the determination of structural protein domains. The- refore, we have created contact networks of amino acids of protein chains, focusing on the representation of only the most relevant interactions between them, from a topological point of view. We have applied to these networks the methods for community identi- fication developed in this thesis, aiming to identify the structural domains of proteins. Finally, we have developed a specific method for the identification of protein domains in protein chains with two sequential domains, concluding in this way, the objectives proposed in this thesis.

A utilização de redes complexas para a descriçãoi de diversos sistemas naturais e artificias,compreendidos nas mais diversas áreas do conhecimento humano, tem se mostrado uma abordagem poderosa para a redução da complexidade inerente a tais sistemas. Em muitos casos, tal complexidade resulta do número de componentes envolvidos e de suas intrincadas relações. Uma forma de reduzir a complexidade associada a tais sistemas, consiste em identificar e agrupar componentes que possuam características similares. Sendo assim, desenvolvemos nesta tese métodos de identificação de comunidades em redes complexas. Tais métodos se baseiam na ideia de que comunidades surgem quando grupos de vértices possuem um número mais elevado de conexões entre os vértices do mesmo grupo do que com vértices externos à este grupo. Além disso, utilizamos a função modularidade como função objetivo e como forma de avaliação e comparação dos resultados obtidos nesta tese com resultados previamente reportados na literatura. Uma vez estabelecido um método de identificação de comunidades, utilizamos a abordagem de redes complexas para a determinação de domínios estruturais de proteínas. Para tal, criamos redes de contato entre os aminoácidos de uma proteí?na buscando representar apenas as ligações relevantes do ponto de vista topológico. Por meio destas representações, aplicamos os métodos de identificação de comunidades desenvolvidos nesta tese, no intuito de identificar domínios estruturais de cadeias proteicas. Por fim, desenvolvemos um método específico para a identificação de domínios em proteínas com dois domínios sequencias, concluindo desta forma, os objetivos propostos nesta tese. / The use of complex networks for the representation of various natural and artificial sys- tems in the most diverse fields of human knowledge, has proven to be a powerful approach for the reduction of the complexity in the study of such systems. In many cases, this complexity emerges from the number of components of the system and from the intricate relationship between them. A reduction in this complexity is made possible by the iden- tification and grouping of the components of the system with similar characteristics. In this way, we developed in this thesis, methods for community identification in complex networks. Such methods are based on the notion that communities arise when groups of vertices are more densely connected with vertices of their same group, than with ver- tices belonging to other groups in the network. Moreover, the modularity function has been used as an objective function, and as a score for the evaluation and comparison of the results obtained in this thesis with the results reported in the literature of complex networks. Upon the establishment of a method for community detection, we used the framework of complex networks to the determination of structural protein domains. The- refore, we have created contact networks of amino acids of protein chains, focusing on the representation of only the most relevant interactions between them, from a topological point of view. We have applied to these networks the methods for community identi- fication developed in this thesis, aiming to identify the structural domains of proteins. Finally, we have developed a specific method for the identification of protein domains in protein chains with two sequential domains, concluding in this way, the objectives proposed in this thesis.

Orientadores: Eliane Martins, Fabiano Luis de Sousa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T18:05:18Z (GMT). No. of bitstreams: 1 Abreu_BrunoTeixeirade_M.pdf: 1214826 bytes, checksum: 85afe48e3c8196abe877dc2ea2efa102 (MD5) Previous issue date: 2006 / Resumo: O teste é uma atividade importante do processo de desenvolvimento de software, e automatizar a geração de dados de teste contribui para a redução dos esforços de tempo e recursos. Recentemente foi mostrado que os algoritmos evolutivos, tal como os Algoritmos Genéticos (AGs), são ferramentas valiosas para a geração de dados. Este trabalho avalia pela primeira vez o desempenho de um algoritmo evolutivo proposto recentemente, a Otimização Extrema Generalizada (em inglês, Generalized Extremal Optimization, GEO), na geração de dados de teste para cobrir um subconjunto de caminhos de um programa, com ou sem loops. Sete programas muito conhecidos e utilizados como benchmarks por outros autores foram escolhidos como estudos de caso, e o desempenho do GEO foi comparado com o de um AG e o Random-Test (RT). Uma aplicação real do Instituto Nacional de Pesquisas Espaciais (INPE) também foi testada para validar a pesquisa, e as comparações de desempenho incluíram uma variação do AG utilizado nos benchmarks. Para os benchmarks e a aplicação real, o uso do GEO exigiu muito menos esforço computacional para gerar os dados do que os AGs, e a cobertura média de caminhos obtida por ele foi muito semelhante à dos AGs. Além disso, o GEO também exigiu muito menos esforço computacional no ajuste interno de parâmetros do que os AGs. Estes resultados indicam que o GEO é uma opção muito atraente a ser utilizada na geração de dados de teste / Abstract: Software testing is an important activity of the software development process and automating test data generation contributes to reduce cost and time efforts. It has recently been shown that evolutionary algorithms, such as the Genetic Algorithms (GAs), are valuable tools for test data generation. This work assesses for the first time the performance of a recently proposed evolutionary algorithm, the Generalized Extremal Optimization (GEO), on generating test data to cover a subset of paths of a program, with or without loops. Seven well known benchmark programs were used as study cases, and the performance of GEO was compared to the one of a GA and Random-Test (RT). A real application from Instituto Nacional de Pesquisas Espaciais (INPE) was also tested in order to validate the research, and the performance comparisons included one variation of the GA used in the benchmarks. For the benchmark programs and the real application, using GEO required much less computational effort to generate test data than using the GAs, and GEO¿s average coverage was very similar to GA¿s. Besides this, it also required much less computational effort on internal parameter setting than the GAs. These results indicate that GEO is a very attractive option to be used for test data generation / Mestrado / Mestre em Ciência da Computação

Orientador: Eliane Martins / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-18T01:12:41Z (GMT). No. of bitstreams: 1 Buzzo_AndreVinicius_M.pdf: 3473272 bytes, checksum: e3da091fcaa16f3245465636a77cfad0 (MD5) Previous issue date: 2011 / Resumo: A geração automática de dados de teste pode ser abordada como um problema de otimização e algoritmos evolutivos se tornaram um foco de muita pesquisa nesta área. Recentemente um novo tipo de algoritmo evolutivo chamado GEO (GEO - Generalized Extremal Optimization) tem sido explorado em uma grande classe de problemas de otimização. Neste trabalho é apresentado o uso do algoritmo evolutivo GEO com codificação real - GEOreal - na geração de dados de teste. O desempenho deste algoritmo é comparado com diversos outros algoritmos e para melhor avaliar os resultados, duas funções objetivo - que mapeiam o problema de geração de dados em um problema de otimização - foram utilizadas. O algoritmo GEOreal combinado com a função objetivo Bueno e Jino obtiveram os melhores resultados nos problemas abordados. Um protótipo foi desenvolvido implementando todos os conceitos envolvidos neste trabalho e o seu desempenho foi comparado com outras ferramentas já disponíveis no mercado. Os resultados mostraram que este protótipo superou as ferramentas comparadas ao minimizar o tempo dispendido no esforço de gerar os dados de teste / Abstract: Automatic test data generation can be approached as an optimization problem and evolutionary algorithms have become a focus of much research in this area. Recently a new type of evolutionary algorithm called GEO (GEO - Generalized Extremal Optimization) has been explored in a large class of optimization problems. This paper presents the use of evolutionary algorithm with real coding GEO - GEOreal - in test data generation. The performance of this algorithm is compared with several other algorithms and to better compare the results two objective functions - that map the problem of generating data in an optimization problem - were used. The algorithm GEOreal combined with the function Bueno and Jino had the best results in the problems addressed. A prototype was developed implementing all the concepts involved in this work and its performance was compared with other tools already available. The results showed that this prototype was better than the compared tools when minimizing the time spent in the effort to test data generation / Mestrado / Ciência da Computação / Mestre em Ciência da Computação