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.

The SUCEST-FUN regulatory network database: Designing an energy grass

Modern sugarcane cultivars are complex hybrids resulting from crosses among several Saccharum species. Traditional breeding methods have been employed extensively in different countries over the past decades to develop varieties with increased sucrose yield and resistance to pests and diseases. Conventional variety improvement, however, may be limited by the narrow pool of suitable genes. Thus, molecular genetics is seen as a promising tool to assist in the process of developing improved varieties. The SUCEST-FUN Project (http://sucest-fun.org) aims to associate function with sugarcane genes using a variety of tools, in particular those that enable the study of the sugarcane transcriptome. An extensive analysis has been conducted to characterise, phenotypically, sugarcane genotypes with regard to their sucrose content, biomass and drought responses. Through the analysis of different cultivars, genes associated with sucrose content, yield, lignin and drought have been identified. Currently, tools are being developed to determine signalling and regulatory networks in grasses, and to sequence the sugarcane genome, as well as to identify sugarcane promoters. This is being implemented through the SUCEST-FUN (http://sucest-fun.org) and GRASSIUS databases (http://grassius.org), the cloning of sugarcane promoters, the identification of cis-regulatory elements (CRE) using Chromatin Immunoprecipitation-sequencing (ChIP-Seq) and the generation of a comprehensive Signal Transduction and Transcription gene catalogue (SUCAST Catalogue).