O problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic structure of costs. This quadratic structure models interaction effects between pairs of edges. Linear and quadratic costs are added up to constitute the total cost of the spanning tree, which must be minimized. When these interactions are restricted to adjacent edges, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). AQMST and QMST are NP-hard problems that model several problems of transport and distribution networks design. In general, AQMST arises as a more suitable model for real problems. Although, in literature, linear and quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider these costs separately. In this sense, Multiobjective Optimization provides a more realistic model for QMST and AQMST. A review of the state-of-the-art, so far, was not able to find papers regarding these problems under a biobjective point of view. Thus, the objective of this Thesis is the development of exact and heuristic algorithms for the Biobjective Adjacent Only Quadratic Spanning Tree Problem (bi-AQST). In order to do so, as theoretical foundation, other NP-hard problems directly related to bi-AQST are discussed: the QMST and AQMST problems. Bracktracking and branch-and-bound exact algorithms are proposed to the target problem of this investigation. The heuristic algorithms developed are: Pareto Local Search, Tabu Search with ejection chain, Transgenetic Algorithm, NSGA-II and a hybridization of the two last-mentioned proposals called NSTA. The proposed algorithms are compared to each other through performance analysis regarding computational experiments with instances adapted from the QMST literature. With regard to exact algorithms, the analysis considers, in particular, the execution time. In case of the heuristic algorithms, besides execution time, the quality of the generated approximation sets is evaluated. Quality indicators are used to assess such information. Appropriate statistical tools are used to measure the performance of exact and heuristic algorithms. Considering the set of instances adopted as well as the criteria of execution time and quality of the generated approximation set, the experiments showed that the Tabu Search with ejection chain approach obtained the best results and the transgenetic algorithm ranked second. The PLS algorithm obtained good quality solutions, but at a very high computational time compared to the other (meta)heuristics, getting the third place. NSTA and NSGA-II algorithms got the last positions

Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo

The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature

Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Análise da Expressão de APE1 após Estresse Oxidativo Induzido em Células Proficientes e Deficientes na Via de Reparo por Excisão de Nucleotídeos

Riboflavin is a vitamin very important in aerobic organisms, as a precursor of many coenzymes involved in the electron transporter chain. However, after photosensitization of riboflavin with UV or visible light, it generates reactive oxygen species (ROS), which can oxidize the DNA. The repair of oxidative lesions on DNA occurs through the base excision repair pathway (BER), where APE1 endonuclease plays a central role. On the other hand, the nucleotide excision repair pathway (NER) repairs helix-distorting lesions. Recently, it was described the participation of NERproteins in the repair of oxidative damage and in stimulation of repair function fromAPE1. The aim of this research was to evaluate the cytotoxic effects of photosensitized riboflavin (RF*) in cells proficient and deficient in NER, correlating with APE1 expression. For this propose, the cells were treated with RF* and it was performed the cell viability assay, extraction of whole proteins, cells fractionation, immunoblotting, indirect immunofluorescence and analysis of polymorphisms of BER gens. The results evidenced that cells deficient in XPA and CSB proteins were more sensitive to RF*. However, XPC-deficient cells presented similar resistance to MRC5- SV cells, which is proficient in NER. These results indicate that XPA and CSB proteins have an important role on repair of oxidative lesions induced by RF*. Additionally, it was evidenced that single nucleotide polymorphisms (SNPs) in BER enzymes may influence in sensitivity of NER-deficient cell lines. Concerning the APE1 expression, the results showed that expression of this protein after treatment with RF* only changed in XPC-deficient cells. Though, it was observed that APE1 is recruited and is bound to chromatin in MRC5-SV and XPA cells after treatment with RF*. The results also showed the induction of DNA damage after treatment with RF*, through the analysis of-H2AX, since the treatment promoted an increase of endogenous levels of this phosphorylated protein, which acts signaling double strand-break on DNA. On the other hand, in XPC-deficient cells, regardless of resistance of RF*, the endogenous levels of APE1 are extremely reduced when compared with other cell lines and APE1 is not bound to chromatin after treatment with RF*. These results conclude that RF* was able to induce cell death in NERdeficient cells, where XPA and CSB cells were more sensitive when compared with MRC5-SV and XPC-deficient cells. This last result is potentially very interesting, since XPC-deficient cell line presents low levels of APE1. Additionally, the results evidenced that APE1 protein can be involved in the repair of oxidative damage induced by RF*, because APE1 is recruited and bound strongly to chromatin after treatment.

A mineração artesanal e de pequena escala em pegmatitos e cerâmica no município de Parelhas, região do Seridó/Rio Grande do Norte

The working conditions, occupational health, occupational illness and workers quality of life, usually referring to the artisanal activities and the workers with a poor professional support. Because this reality is still present in locals without good infrastructure of social and economic attention, there is a need for a broad knowledge of problems related to the productive processes that include features of unsanitary and unhealthy. Despite the intense process of industrialization promoted by globalization and the growth of developing nations like Brazil, the activities of artisanal and small-scale mining are still suffering from the marginalization of their production processes and their workers. This dissertation deals with the description of mineral-based activities (MBA), especially the activities related to production processes of extraction and processing of red pottery and minerals in pegmatites in Parelhas city, Seridó, Rio Grande do Norte, which are conducted by small mining companies or artisanal miners. The study of the work process was based on direct observation, photographic documentation, ergonomics, health and occupational safety analysis, interviews and structured questionnaire with workers of the two activities. The results indicate the need for improvement in both workplaces (red pottery and pegmatites), adaptation of workers to safety standards specific to the workplace, more attention and care related to ergonomics and occupational safety, greater importance to economic and social relations among performed activities, workers and firms of mineral branch and better and greater integration of social policies, supported by different sectors of society with the intention of transforming the current social, cultural, labor and education situation

Análise da expressão de APE1 após estresse oxidativo induzido em células proficientes e deficientes na via de reparo por excisão de nucleotídeos.

Riboflavin is a vitamin very important in aerobic organisms, as a precursor of many coenzymes involved in the electron transporter chain. However, after photosensitization of riboflavin with UV or visible light, it generates reactive oxygen species (ROS), which can oxidize the DNA. The repair of oxidative lesions on DNA occurs through the base excision repair pathway (BER), where APE1 endonuclease plays a central role. On the other hand, the nucleotide excision repair pathway (NER) repairs helix-distorting lesions. Recently, it was described the participation of NERproteins in the repair of oxidative damage and in stimulation of repair function fromAPE1. The aim of this research was to evaluate the cytotoxic effects of photosensitized riboflavin (RF*) in cells proficient and deficient in NER, correlating with APE1 expression. For this propose, the cells were treated with RF* and it was performed the cell viability assay, extraction of whole proteins, cells fractionation, immunoblotting, indirect immunofluorescence and analysis of polymorphisms of BER gens. The results evidenced that cells deficient in XPA and CSB proteins were more sensitive to RF*. However, XPC-deficient cells presented similar resistance to MRC5- SV cells, which is proficient in NER. These results indicate that XPA and CSB proteins have an important role on repair of oxidative lesions induced by RF*. Additionally, it was evidenced that single nucleotide polymorphisms (SNPs) in BER enzymes may influence in sensitivity of NER-deficient cell lines. Concerning the APE1 expression, the results showed that expression of this protein after treatment with RF* only changed in XPC-deficient cells. Though, it was observed that APE1 is recruited and is bound to chromatin in MRC5-SV and XPA cells after treatment with RF*. The results also showed the induction of DNA damage after treatment with RF*, through the analysis of-H2AX, since the treatment promoted an increase of endogenous levels of this phosphorylated protein, which acts signaling double strand-break on DNA. On the other hand, in XPC-deficient cells, regardless of resistance of RF*, the endogenous levels of APE1 are extremely reduced when compared with other cell lines and APE1 is not bound to chromatin after treatment with RF*. These results conclude that RF* was able to induce cell death in NERdeficient cells, where XPA and CSB cells were more sensitive when compared with MRC5-SV and XPC-deficient cells. This last result is potentially very interesting, since XPC-deficient cell line presents low levels of APE1. Additionally, the results evidenced that APE1 protein can be involved in the repair of oxidative damage induced by RF*, because APE1 is recruited and bound strongly to chromatin after treatment.