Efficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design

The design of a network is a solution to several engineering and science problems. Several network design problems are known to be NP-hard, and population-based metaheuristics like evolutionary algorithms (EAs) have been largely investigated for such problems. Such optimization methods simultaneously generate a large number of potential solutions to investigate the search space in breadth and, consequently, to avoid local optima. Obtaining a potential solution usually involves the construction and maintenance of several spanning trees, or more generally, spanning forests. To efficiently explore the search space, special data structures have been developed to provide operations that manipulate a set of spanning trees (population). For a tree with n nodes, the most efficient data structures available in the literature require time O(n) to generate a new spanning tree that modifies an existing one and to store the new solution. We propose a new data structure, called node-depth-degree representation (NDDR), and we demonstrate that using this encoding, generating a new spanning forest requires average time O(root n). Experiments with an EA based on NDDR applied to large-scale instances of the degree-constrained minimum spanning tree problem have shown that the implementation adds small constants and lower order terms to the theoretical bound.

Therapeutic DNA Vaccine Encoding Peptide P10 against Experimental Paracoccidioidomycosis

Paracoccidioidomycosis (PCM), caused by Paracoccidioides brasiliensis, is the most prevalent invasive fungal disease in South America. Systemic mycoses are the 10th most common cause of death among infectious diseases in Brazil and PCM is responsible for more than 50% of deaths due to fungal infections. PCM is typically treated with sulfonamides, amphotericin B or azoles, although complete eradication of the fungus may not occur and relapsing disease is frequently reported. A 15-mer peptide from the major diagnostic antigen gp43, named P10, can induce a strong T-CD4+ helper-1 immune response in mice. The TEPITOPE algorithm and experimental data have confirmed that most HLA-DR molecules can present P10, which suggests that P10 is a candidate antigen for a PCM vaccine. In the current work, the therapeutic efficacy of plasmid immunization with P10 and/or IL-12 inserts was tested in murine models of PCM. When given prior to or after infection with P. brasiliensis virulent Pb 18 isolate, plasmid-vaccination with P10 and/or IL-12 inserts successfully reduced the fungal burden in lungs of infected mice. In fact, intramuscular administration of a combination of plasmids expressing P10 and IL-12 given weekly for one month, followed by single injections every month for 3 months restored normal lung architecture and eradicated the fungus in mice that were infected one month prior to treatment. The data indicate that immunization with these plasmids is a powerful procedure for prevention and treatment of experimental PCM, with the perspective of being also effective in human patients.