Opposition-Based Memetic Algorithm and Hybrid Approach for Sorting Permutations by Reversals.

Sorting unsigned permutations by reversals is a difficult problem; indeed, it was proved to be NP -hard by Caprara ( 1997 ). Because of its high complexity, many approximation algorithms to compute the minimal reversal distance were proposed until reaching the nowadays best-known theoretical ratio of 1.375. In this article, two memetic algorithms to compute the reversal distance are proposed. The first one uses the technique of opposition-based learning leading to an opposition-based memetic algorithm; the second one improves the previous algorithm by applying the heuristic of two breakpoint elimination leading to a hybrid approach. Several experiments were performed with one-hundred randomly generated permutations, single benchmark permutations, and biological permutations. Results of the experiments showed that the proposed OBMA and Hybrid-OBMA algorithms achieve the best results for practical cases, that is, for permutations of length up to 120. Also, Hybrid-OBMA showed to improve the results of OBMA for permutations greater than or equal to 60. The applicability of our proposed algorithms was checked processing permutations based on biological data, in which case OBMA gave the best average results for all instances.

Micromechanics and poroelasticity of hydrated cellulose networks.

The micromechanics of cellulose hydrogels have been investigated using a new rheological experimental approach, combined with simulation using a poroelastic constitutive model. A series of mechanical compression steps at different strain rates were performed as a function of cellulose hydrogel thickness, combined with small amplitude oscillatory shear after each step to monitor the viscoelasticity of the sample. During compression, bacterial cellulose hydrogels behaved as anisotropic materials with near zero Poisson's ratio. The micromechanics of the hydrogels altered with each compression as water was squeezed out of the structure, and microstructural changes were strain rate-dependent, with increased densification of the cellulose network and increased cellulose fiber aggregation observed for slower compressive strain rates. A transversely isotropic poroelastic model was used to explain the observed micromechanical behavior, showing that the mechanical properties of cellulose networks in aqueous environments are mainly controlled by the rate of water movement within the structure.

Reconfigurable systems for sequence alignment and for general dynamic programming.

Reconfigurable systolic arrays can be adapted to efficiently resolve a wide spectrum of computational problems; parallelism is naturally explored in systolic arrays and reconfigurability allows for redefinition of the interconnections and operations even during run time (dynamically). We present a reconfigurable systolic architecture that can be applied for the efficient treatment of several dynamic programming methods for resolving well-known problems, such as global and local sequence alignment, approximate string matching and longest common subsequence. The dynamicity of the reconfigurability was found to be useful for practical applications in the construction of sequence alignments. A VHDL (VHSIC hardware description language) version of this new architecture was implemented on an APEX FPGA (Field programmable gate array). It would be several magnitudes faster than the software algorithm alternatives.