A domain decomposition strategy for alignment of multiple biological sequences on multiprocessor platforms

Multiple Sequences Alignment (MSA) of biological sequences is a fundamental problem in computational biology due to its critical significance in wide ranging applications including haplotype reconstruction, sequence homology, phylogenetic analysis, and prediction of evolutionary origins. The MSA problem is considered NP-hard and known heuristics for the problem do not scale well with increasing numbers of sequences. On the other hand, with the advent of a new breed of fast sequencing techniques it is now possible to generate thousands of sequences very quickly. For rapid sequence analysis, it is therefore desirable to develop fast MSA algorithms that scale well with an increase in the dataset size. In this paper, we present a novel domain decomposition based technique to solve the MSA problem on multiprocessing platforms. The domain decomposition based technique, in addition to yielding better quality, gives enormous advantages in terms of execution time and memory requirements. The proposed strategy allows one to decrease the time complexity of any known heuristic of O(N)^x$O{\left(N\right)}^x$ complexity by a factor of O(1/p)^x$O{(1/p)}^x$, where N$N$ is the number of sequences, x$x$ depends on the underlying heuristic approach, and p$p$ is the number of processing nodes. In particular, we propose a highly scalable algorithm, Sample-Align-D, for aligning biological sequences using Muscle system as the underlying heuristic. The proposed algorithm has been implemented on a cluster of workstations using the MPI library. Experimental results for different problem sizes are analyzed in terms of quality of alignment, execution time and speed-up.     

Dynamic hybrid automatic repeat request (DHARQ) for WiMAX – Mobile multihop relay using adaptive power control

Wireless multihop network is currently attracting much attention as a new wireless broadband access technology due to numerous benefits. This work proposes a power control scheme for WiMAX multihop relay system. In contrast to existing power control and optimization approaches, our proposed method uses an adaptive Channel Quality Measurement for a relay station to reduce interferences to other mobile station (MS) or relay station (RS) within the same cell and hence increase the number of hops per link and consequently maximize the spatial reuse. The proposed power control is applied to a new dynamic HARQ algorithm for adaptive channel quality enhancement. Simulation results have indicated that the proposed approach achieves superior BER/PER performance enhancement in comparison to previous related works.     

Short-term and long-term memory analysis of learning using 2D and 3D educational contents

ABSTRACT

The effect of 2D and 3D educational content learning on memory has been studied using electroencephalography (EEG) brain signal. A hypothesis is set that the 3D materials are better than the 2D materials for learning and memory recall. To test the hypothesis, we proposed a classification system that will predict true or false recall for short-term memory (STM) and long-term memory (LTM) after learning by either 2D or 3D educational contents. For this purpose, EEG brain signals are recorded during learning and testing; the signals are then analysed in the time domain using different types of features in various frequency bands. The features are then fed into a support vector machine (SVM)-based classifier. The experimental results indicate that the learning and memory recall using 2D and 3D contents do not have significant differences for both the STM and the LTM.     

SimClus: an effective algorithm for clustering with a lower bound on similarity

Clustering algorithms generally accept a parameter k from the user, which determines the number of clusters sought. However, in many application domains, like document categorization, social network clustering, and frequent pattern summarization, the proper value of k is difficult to guess. An alternative clustering formulation that does not require k is to impose a lower bound on the similarity between an object and its corresponding cluster representative. Such a formulation chooses exactly one representative for every cluster and minimizes the representative count. It has many additional benefits. For instance, it supports overlapping clusters in a natural way. Moreover, for every cluster, it selects a representative object, which can be effectively used in summarization or semi-supervised classification task. In this work, we propose an algorithm, SimClus, for clustering with lower bound on similarity. It achieves a O(log n) approximation bound on the number of clusters, whereas for the best previous algorithm the bound can be as poor as O(n). Experiments on real and synthetic data sets show that our algorithm produces more than 40% fewer representative objects, yet offers the same or better clustering quality. We also propose a dynamic variant of the algorithm, which can be effectively used in an on-line setting.     

Optimum weight design of fiber composite plates in flexure based on a two level strategy

This paper offers a method for weight optimization of multilayer fiber composite plates under the action of lateral loadings. The objective is to design a fiber composite plate of minimum thickness which can sustain multiple static loadings applied normal to its surface without exhibiting failure based on Tsai-Hill criterion in any of its layers. In this investigation, fiber orientation angles are treated as discrete variables, which can vary only by pre-assigned increments, while thicknesses of layers are treated as continuous variables. The optimization procedure is based on a two stage strategy; in the first of which only the fiber orientation angles for the layers are treated as variables, and in the second, only the layer thicknesses. A powerful criterion based on a load factor has been defined to find the best angle for a new layer in the first stage, and the method of center points has been used for thickness optimization in the second stage. After any angle and thickness optimization has been done, a new layer is added to the thickness and the procedure is repeated for other new layers. The end of the two stage procedure is signaled whenever the thickness of the new layer in the optimization process approaches zero; meaning that no new layers would improve the set of layers already found. In this way at the end of the optimization procedure the plate thickness would be made of a minimum number of layers whose fibers are optimally oriented, and whose thicknesses are minimal. A poor choice of layers in the stack produce near zero thickness for the respective layer, and are thus deleted from the set. A repeat process is performed after each cycle, to modify layer angles in order to compensate for errors due to approximations involved. The priorities exercised in the choice of new layers for inclusion in the set and exclusion of all the un-necessary ones, allow an optimal state of stacking sequence to be achieved. Several examples are given to demonstrate the operation of the algorithm.     

Structural,magnetic and microwave absorption characteristics of BaCoxMnxTi2xFe12 − 4xO19

The effect of Mn⁺²Co⁺²Ti⁺⁴ substitution on microwave absorption has been studied for BaCo_xMn_xTi_2xFe_12 ? 4xO₁₉ ferrite–acrylic resin composites, where x varies from 0.3 to 0.5 in steps of 0.1, in frequency range from 12 to 20 GHz. X-ray diffraction (XRD), scanning electron microscope (SEM), vibrating sample magnetometer, and vector network analyzer were used to analyze the structures, electromagnetic and microwave absorption properties. The results showed that, the magnetoplumbite structures for all samples have been formed. Based on microwave measurement on reflectivity, BaCo_xMn_xTi_2xFe_12 ? 4xO₁₉ may be a good candidate for electromagnetic compatibility and other practical applications at high frequency.     

Designing a cellular manufacturing system considering decision style,skill and job security by NSGA-II and response surface methodology

Cell formation is a traditional problem in cellular manufacturing systems that concerns the allocation of parts, operators and machines to the cells. This paper presents a new mathematical programming model for cell formation in which operators’ personality and decision-making styles, skill in working with machines, and also job security are incorporated simultaneously. The model involves the following five objectives: (1) minimising costs of adding new machines to and removing machines from the cells at the beginning of each period, (2) minimising total cost of material handling, (3) maximising job security, (4) minimising inconsistency of operators’ decision styles in cells and (5) minimising cost of suitable skill. On account of the NP-hard nature of the proposed model, NSGA-II as a powerful meta-heuristic approach is used for solving large-sized problems. Furthermore, response surface methodology (RSM) is used for tuning the parameters. Lastly, MOPSO and two scalarization methods are employed for validation of the results obtained. To the best of our knowledge, this is the first study that presents a multi-objective mathematical model for cell formation problem considering operators’ personality and skill, addition and removal of machines and job security.