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.

Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.

Tree height integrated into pantropical forest biomass estimates

Aboveground tropical tree biomass and carbon storage estimates commonly ignore tree height (H). We estimate the effect of incorporating H on tropics-wide forest biomass estimates in 327 plots across four continents using 42 656 H and diameter measurements and harvested trees from 20 sites to answer the following questions: 1. What is the best H-model form and geographic unit to include in biomass models to minimise site-level uncertainty in estimates of destructive biomass? 2. To what extent does including H estimates derived in (1) reduce uncertainty in biomass estimates across all 327 plots? 3. What effect does accounting for H have on plot- and continental-scale forest biomass estimates? The mean relative error in biomass estimates of destructively harvested trees when including H (mean 0.06), was half that when excluding H (mean 0.13). Power- and Weibull-H models provided the greatest reduction in uncertainty, with regional Weibull-H models preferred because they reduce uncertainty in smaller-diameter classes (< 40 cm D) that store about one-third of biomass per hectare in most forests. Propagating the relationships from destructively harvested tree biomass to each of the 327 plots from across the tropics shows that including H reduces errors from 41.8 Mg ha(-1) (range 6.6 to 112.4) to 8.0 Mg ha(-1) (-2.5 to 23.0).

Genetic characterization of fig tree mutants with molecular markers

The fig (Ficus carica L.) is a fruit tree of great world importance and, therefore, the genetic improvement becomes an important field of research for better crops, being necessary to gather information on this species, mainly regarding its genetic variability so that appropriate propagation projects and management are made. The improvement programs of fig trees using conventional procedures in order to obtain new cultivars are rare in many countries, such as Brazil, especially due to the little genetic variability and to the difficulties in obtaining plants from gamete fusion once the wasp Blastophaga psenes, responsible for the natural pollinating, is not found in Brazil. In this way, the mutagenic genetic improvement becomes a solution of it. For this reason, in an experiment conducted earlier, fig plants formed by cuttings treated with gamma ray were selected based on their agronomic characteristics of interest. We determined the genetic variability in these fig tree selections, using RAPD and AFLP molecular markers, comparing them to each other and to the Roxo-de-Valinhos, used as the standard. For the reactions of DNA amplification, 140 RAPD primers and 12 primer combinations for AFLP analysis were used. The selections did not differ genetically between themselves and between them and the Roxo-de-Valinhos cultivar. Techniques that can detect polymorphism between treatments, such as DNA sequencing, must be tested. The phenotypic variation of plants may be due to epigenetic variation, necessitating the use of techniques with methylation-sensitive restriction enzymes.

PHENOLOGY AND FRUIT TRAITS OF ARCHONTOPHOENIX CUNNINGHAMIANA, AN INVASIVE PALM TREE IN THE ATLANTIC FOREST OF BRAZIL

The Australian palm Archontophoenix cunninghamiana was introduced into Brazil as an ornamental species, and became a dangerous invader of remnant Atlantic forest patches, demanding urgent management actions that require careful planning. Its fruits are greatly appreciated by generalist birds and its sudden eradication could be as harmful as its permanence in the native community. Our hypothesis was that A. cunninghamiana phenology and fruit traits would have facilitated the invasion process. Hence the aim of the study was to characterize the reproductive phenology of the palm by registering flowering and fruiting events, estimating fruit production, and evaluating fruit nutritional levels. Phenological observations were carried out over 12 months and analyzed statistically. Fruit traits and production were estimated. Pulp nutritional levels were determined by analyzing proteins, lipids, and carbohydrates. Results showed constant flowering and fruiting throughout the year with a weak reproductive seasonality. On average, 3651 fruits were produced per bunch mainly in the summer. Fruit analysis revealed low nutrient contents, especially of proteins and lipids compared with other Brazilian native palm species. We concluded that the abundant fruit production all year round, and fruit attractivity mainly due to size and color, :may act positively on the reproductive performance and effective dispersion of A. cunninghamiana. As a management procedure which would add quality to frugivore food resources we suggest the replacement of A. cunninghamiana by the native palm Euterpe edulis, especially in gardens and parks near to Atlantic forest fragments.

CONTEXT TREE SELECTION AND LINGUISTIC RHYTHM RETRIEVAL FROM WRITTEN TEXTS

The starting point of this article is the question "How to retrieve fingerprints of rhythm in written texts?" We address this problem in the case of Brazilian and European Portuguese. These two dialects of Modern Portuguese share the same lexicon and most of the sentences they produce are superficially identical. Yet they are conjectured, on linguistic grounds, to implement different rhythms. We show that this linguistic question can be formulated as a problem of model selection in the class of variable length Markov chains. To carry on this approach, we compare texts from European and Brazilian Portuguese. These texts are previously encoded according to some basic rhythmic features of the sentences which can be automatically retrieved. This is an entirely new approach from the linguistic point of view. Our statistical contribution is the introduction of the smallest maximizer criterion which is a constant free procedure for model selection. As a by-product, this provides a solution for the problem of optimal choice of the penalty constant when using the BIC to select a variable length Markov chain. Besides proving the consistency of the smallest maximizer criterion when the sample size diverges, we also make a simulation study comparing our approach with both the standard BIC selection and the Peres-Shields order estimation. Applied to the linguistic sample constituted for our case study, the smallest maximizer criterion assigns different context-tree models to the two dialects of Portuguese. The features of the selected models are compatible with current conjectures discussed in the linguistic literature.

A survey of evolutionary algorithms for decision-tree induction

This paper presents a survey of evolutionary algorithms that are designed for decision-tree induction. In this context, most of the paper focuses on approaches that evolve decision trees as an alternate heuristics to the traditional top-down divide-and-conquer approach. Additionally, we present some alternative methods that make use of evolutionary algorithms to improve particular components of decision-tree classifiers. The paper's original contributions are the following. First, it provides an up-to-date overview that is fully focused on evolutionary algorithms and decision trees and does not concentrate on any specific evolutionary approach. Second, it provides a taxonomy, which addresses works that evolve decision trees and works that design decision-tree components by the use of evolutionary algorithms. Finally, a number of references are provided that describe applications of evolutionary algorithms for decision-tree induction in different domains. At the end of this paper, we address some important issues and open questions that can be the subject of future research.

Two new species of marsupial tree-frogs genus Gastrotheca Fitzinger, 1843 (Anura, Hemiphractidae) from the Brazilian Atlantic Forest

Two new species of Gastrotheca are described from northeastern Minas Gerais and southern Bahia, in the Atlantic Forest of Brazil. Data on morphology, calls, mitochondrial, and nuclear DNA are provided. Allied to G. fissipes and G. megacephala, the new taxa provide evidence for a higher diversity of species of Gastrotheca than previously thought at the Atlantic Forest. The data also suggest that G. pulchra, another Atlantic Forest taxon, is more closely related to non-Atlantic Forest species than to the remaining analyzed Brazilian Gastrotheca species. This implies that the Gastrotheca at the Brazilian coastal forests have at least two independent origins.

Automatic design of decision-tree induction algorithms tailored to flexible-receptor docking data

Background: This paper addresses the prediction of the free energy of binding of a drug candidate with enzyme InhA associated with Mycobacterium tuberculosis. This problem is found within rational drug design, where interactions between drug candidates and target proteins are verified through molecular docking simulations. In this application, it is important not only to correctly predict the free energy of binding, but also to provide a comprehensible model that could be validated by a domain specialist. Decision-tree induction algorithms have been successfully used in drug-design related applications, specially considering that decision trees are simple to understand, interpret, and validate. There are several decision-tree induction algorithms available for general-use, but each one has a bias that makes it more suitable for a particular data distribution. In this article, we propose and investigate the automatic design of decision-tree induction algorithms tailored to particular drug-enzyme binding data sets. We investigate the performance of our new method for evaluating binding conformations of different drug candidates to InhA, and we analyze our findings with respect to decision tree accuracy, comprehensibility, and biological relevance. Results: The empirical analysis indicates that our method is capable of automatically generating decision-tree induction algorithms that significantly outperform the traditional C4.5 algorithm with respect to both accuracy and comprehensibility. In addition, we provide the biological interpretation of the rules generated by our approach, reinforcing the importance of comprehensible predictive models in this particular bioinformatics application. Conclusions: We conclude that automatically designing a decision-tree algorithm tailored to molecular docking data is a promising alternative for the prediction of the free energy from the binding of a drug candidate with a flexible-receptor.

Detection of isometric, dsRNA-containing viral particles in Colletotrichum gloeosporioides isolated from cashew tree

Fungi are disease-causing agents in plants and affect crops of economic importance. One control method is to induce resistance in the host by using biological control with hypovirulent phytopathogenic fungi. Here, we report the detection of a mycovirus in a strain of Colletotrichum gloeosporioides causing anthracnose of cashew tree. The strain C. gloeosporioides URM 4903 was isolated from a cashew tree (Anacardium occidentale) in Igarassu, PE, Brazil. After nucleic acid extraction and electrophoresis, the band corresponding to a possible double-stranded RNA (dsRNA) was purified by cellulose column chromatography. Nine extrachromosomal bands were obtained. Enzymatic digestion with DNAse I and Nuclease S1 had no effect on these bands, indicating their dsRNA nature. Transmission electron microscopic examination of extracts from this strain showed the presence of isometric particles (30-35 nm in diameter). These data strongly suggest the infection of this C. gloeosporioides strain by a dsRNA mycovirus. Once the hypovirulence of this strain is confirmed, the strain may be used for the biological control of cashew anthracnose.

Mating system parameters at hierarchical levels of fruits, individuals and populations in the Brazilian insect-pollinated tropical tree, Tabebuia roseo-alba (Bignoniaceae)

For many tree species, mating system analyses have indicated potential variations in the selfing rate and paternity correlation among fruits within individuals, among individuals within populations, among populations, and from one flowering event to another. In this study, we used eight microsatellite markers to investigate mating systems at two hierarchical levels (fruits within individuals and individuals within populations) for the insect pollinated Neotropical tree Tabebuia roseo-alba. We found that T. roseo-alba has a mixed mating system with predominantly outcrossed mating. The outcrossing rates at the population level were similar across two T. roseo-alba populations; however, the rates varied considerably among individuals within populations. The correlated paternity results at different hierarchical levels showed that there is a high probability of shared paternal parentage when comparing seeds within fruits and among fruits within plants and full-sibs occur in much higher proportion within fruits than among fruits. Significant levels of fixation index were found in both populations and biparental inbreeding is believed to be the main cause of the observed inbreeding. The number of pollen donors contributing to mating was low. Furthermore, open-pollinated seeds varied according to relatedness, including half-sibs, full-sibs, self-sibs and self- half-sibs. In both populations, the effective population size within a family (seed-tree and its offspring) was lower than expected for panmictic populations. Thus, seeds for ex situ conservation genetics, progeny tests and reforestation must be collected from a large number of seed-trees to guarantee an adequate effective population in the sample.

Classification and regression tree (CART) model to predict pulmonary tuberculosis in hospitalized patients

Background: Tuberculosis (TB) remains a public health issue worldwide. The lack of specific clinical symptoms to diagnose TB makes the correct decision to admit patients to respiratory isolation a difficult task for the clinician. Isolation of patients without the disease is common and increases health costs. Decision models for the diagnosis of TB in patients attending hospitals can increase the quality of care and decrease costs, without the risk of hospital transmission. We present a predictive model for predicting pulmonary TB in hospitalized patients in a high prevalence area in order to contribute to a more rational use of isolation rooms without increasing the risk of transmission. Methods: Cross sectional study of patients admitted to CFFH from March 2003 to December 2004. A classification and regression tree (CART) model was generated and validated. The area under the ROC curve (AUC), sensitivity, specificity, positive and negative predictive values were used to evaluate the performance of model. Validation of the model was performed with a different sample of patients admitted to the same hospital from January to December 2005. Results: We studied 290 patients admitted with clinical suspicion of TB. Diagnosis was confirmed in 26.5% of them. Pulmonary TB was present in 83.7% of the patients with TB (62.3% with positive sputum smear) and HIV/AIDS was present in 56.9% of patients. The validated CART model showed sensitivity, specificity, positive predictive value and negative predictive value of 60.00%, 76.16%, 33.33%, and 90.55%, respectively. The AUC was 79.70%. Conclusions: The CART model developed for these hospitalized patients with clinical suspicion of TB had fair to good predictive performance for pulmonary TB. The most important variable for prediction of TB diagnosis was chest radiograph results. Prospective validation is still necessary, but our model offer an alternative for decision making in whether to isolate patients with clinical suspicion of TB in tertiary health facilities in countries with limited resources.

Responses of transplanted native tree species to invasive alien grass removals in an abandoned cattle pasture in the Lacandon region, Mexico

We tested the early performance of 16 native early-, mid-, and late-successional tree species in response to four intensities of grass removal in an abandoned cattle pasture dominated by the introduced, invasive African grass, Cynodon plectostachyus, within the Lacandon rainforest region, southeast Mexico. The increase in grass removals significantly improved the performance of many species, especially of early-and mid-successional species, while performance of late-successional species was relatively poor and did not differ significantly among treatments. Good site preparation and at least one additional grass removal four months after seedling transplant were found to be essential; additional grass removals led to improved significantly performance of saplings in most cases. In order to evaluate the potential of transplanting tree seedlings successfully in abandoned tropical pastures, we developed a "planting risk index", combining field performance measurements and plantation cost estimations. Our results showed a great potential for establishing restoration plantings with many early-and mid-successional species. Although planting risk of late-successional species was considered high, certain species showed some possibilities of acclimation after 18 months and should be considered in future plantation arrangements in view of their long-term contributions to biodiversity maintenance and also to human welfare through delivery of ecosystem services. Conducting a planting risk analysis can help avoid failure of restoration strategies involving simultaneous planting of early-, mid-, and late-successional tree species. This in turn will improve cost-effectiveness of initial interventions in large-scale, long-term restoration programs.

Biological invasions and the acoustic niche: the effect of bullfrog calls on the acoustic signals of white-banded tree frogs

Invasive species are known to affect native species in a variety of ways, but the effect of acoustic invaders has not been examined previously. We simulated an invasion of the acoustic niche by exposing calling native male white-banded tree frogs (Hypsiboas albomarginatus) to recorded invasive American bullfrog (Lithobates catesbeianus) calls. In response, tree frogs immediately shifted calls to significantly higher frequencies. In the post-stimulus period, they continued to use higher frequencies while also decreasing signal duration. Acoustic signals are the primary basis of mate selection in many anurans, suggesting that such changes could negatively affect the reproductive success of native species. The effects of bullfrog vocalizations on acoustic communities are expected to be especially severe due to their broad frequency band, which masks the calls of multiple species simultaneously.

Leaves of Lolium multiflorum 'Lema' and tropical tree species as biomonitors of polycyclic aromatic hydrocarbons

This study extends the current knowledge regarding the use of plants for the passive accumulation of anthropogenic PAHs that are present in the atmospheric total suspended particles (TSP) in the tropics and sub-tropics. It is of major relevance because the anthropic emissions of TSP containing PAHs are significant in these regions, but their monitoring is still scarce. We compared the biomonitor efficiency of Lolium multiflorum 'Lema' and tropical tree species (Tibouchina pukka and Psidium guajava 'Paluma') that were growing in an intensely TSP-polluted site in Cubatao (SE Brazil), and established the species with the highest potential for alternative monitoring of PAHs. PAHs present in the TSP indicated that the region is impacted by various emission sources. L. multiflorum showed a greater efficiency for the accumulation of PAH compounds on their leaves than the tropical trees. The linear regression between the logBCF and logKoa revealed that L. multiflorum is an efficient biomonitor of the profile of light and heavy PAHs present in the particulate phase of the atmosphere during dry weather and mild temperatures. The grass should be used only for indicating the PAHs with higher molecular weight in warmer and wetter periods. (C) 2012 Elsevier Inc. All rights reserved.