STACRP: a secure trusted auction oriented clustering based routing protocol for MANET

In mobile ad hoc network?(MANET) nodes have a tendency to drop others’ packet to conserve its own energy. If most of the nodes in a network start to behave in this way, either a portion of the network would be isolated or total network functionality would be hampered. This behavior is known as selfishness. Therefore, selfishness mitigation and enforcing cooperation between nodes is very important to increase the availability of nodes and overall throughput and to achieve the robustness of the network. Both credit and reputation based mechanisms are used to attract nodes to forward others’ packets. In light of this, we propose a game theoretic routing model, Secure Trusted Auction oriented Clustering based Routing Protocol (STACRP), to provide trusted framework for MANET. Two auction mechanisms procurement and Dutch are used to determine the forwarding cost-per-hop for intermediate nodes. Our model is lightweight in terms of computational and communication requirements, yet powerful in terms of flexibility in managing trust between nodes of heterogeneous deployments. It manages trust locally with minimal overhead in terms of extra messages. STACRP organizes the network into 1-hop disjoint clusters and elects the most qualified and trustworthy nodes as Clusterhead. The trust is quantified with carefully chosen parameters having deep impact on network functionality. The trust model is analyzed using Markov chain and is proven as continuous time Markov chain. The security analysis of the model is analyzed to guarantee that the proposed approach achieves a secure reliable routing solution for MANETs. The proposed model have been evaluated with a set of simulations that show STACRP detects selfish nodes and enforces cooperation between nodes and achieves better throughput and packet delivery ratio with lees routing overhead compare to AODV.     

On an ensemble algorithm for clustering cancer patient data

Background

The TNM staging system is based on three anatomic prognostic factors: Tumor, Lymph Node and Metastasis. However, cancer is no longer considered an anatomic disease. Therefore, the TNM should be expanded to accommodate new prognostic factors in order to increase the accuracy of estimating cancer patient outcome. The ensemble algorithm for clustering cancer data (EACCD) by Chen et al. reflects an effort to expand the TNM without changing its basic definitions. Though results on using EACCD have been reported, there has been no study on the analysis of the algorithm. In this report, we examine various aspects of EACCD using a large breast cancer patient dataset. We compared the output of EACCD with the corresponding survival curves, investigated the effect of different settings in EACCD, and compared EACCD with alternative clustering approaches.

Results

Using the basic T and N definitions, EACCD generated a dendrogram that shows a graphic relationship among the survival curves of the breast cancer patients. The dendrograms from EACCD are robust for large values of m (the number of runs in the learning step). When m is large, the dendrograms depend on the linkage functions.The statistical tests, however, employed in the learning step have minimal effect on the dendrogram for large m. In addition, if omitting the step for learning dissimilarity in EACCD, the resulting approaches can have a degraded performance. Furthermore, clustering only based on prognostic factors could generate misleading dendrograms, and direct use of partitioning techniques could lead to misleading assignments to clusters.

Conclusions

When only the Partitioning Around Medoids (PAM) algorithm is involved in the step of learning dissimilarity, large values of m are required to obtain robust dendrograms, and for a large m EACCD can effectively cluster cancer patient data.

     

An improved algorithm for clustering gene expression data

MOTIVATION: Recent advancements in microarray technology allows simultaneous monitoring of the expression levels of a large number of genes over different time points. Clustering is an important tool for analyzing such microarray data, typical properties of which are its inherent uncertainty, noise and imprecision. In this article, a two-stage clustering algorithm, which employs a recently proposed variable string length genetic scheme and a multiobjective genetic clustering algorithm, is proposed. It is based on the novel concept of points having significant membership to multiple classes. An iterated version of the well-known Fuzzy C-Means is also utilized for clustering. RESULTS: The significant superiority of the proposed two-stage clustering algorithm as compared to the average linkage method, Self Organizing Map (SOM) and a recently developed weighted Chinese restaurant-based clustering method (CRC), widely used methods for clustering gene expression data, is established on a variety of artificial and publicly available real life data sets. The biological relevance of the clustering solutions are also analyzed.     

Predicting protein-ligand binding sites based on an improved geometric algorithm

Knowledge of protein-ligand binding sites is very important for structure-based drug designs. To get information on the binding site of a targeted protein with its ligand in a timely way, many scientists tried to resort to computational methods. Although several methods have been released in the past few years, their accuracy needs to be improved. In this study, based on the combination of incremental convex hull, traditional geometric algorithm, and solvent accessible surface of proteins, we developed a novel approach for predicting the protein-ligand binding sites. Using PDBbind database as a benchmark dataset and comparing the new approach with the existing methods such as POCKET, Q-SiteFinder, MOE-SiteFinder, and PASS, we found that the new method has the highest accuracy for the Top 2 and Top 3 predictions. Furthermore, our approach can not only successfully predict the protein-ligand binding sites but also provide more detailed information for the interactions between proteins and ligands. It is anticipated that the new method may become a useful tool for drug development, or at least play a complementary role to the other existing methods in this area.     

A multiple kernel density clustering algorithm for incomplete datasets in bioinformatics

Background

While there are a large number of bioinformatics datasets for clustering, many of them are incomplete, i.e., missing attribute values in some data samples needed by clustering algorithms. A variety of clustering algorithms have been proposed in the past years, but they usually are limited to cluster on the complete dataset. Besides, conventional clustering algorithms cannot obtain a trade-off between accuracy and efficiency of the clustering process since many essential parameters are determined by the human user’s experience.

Results

The paper proposes a Multiple Kernel Density Clustering algorithm for Incomplete datasets called MKDCI. The MKDCI algorithm consists of recovering missing attribute values of input data samples, learning an optimally combined kernel for clustering the input dataset, reducing dimensionality with the optimal kernel based on multiple basis kernels, detecting cluster centroids with the Isolation Forests method, assigning clusters with arbitrary shape and visualizing the results.

Conclusions

Extensive experiments on several well-known clustering datasets in bioinformatics field demonstrate the effectiveness of the proposed MKDCI algorithm. Compared with existing density clustering algorithms and parameter-free clustering algorithms, the proposed MKDCI algorithm tends to automatically produce clusters of better quality on the incomplete dataset in bioinformatics.

     

Forest species diversity mapping based on clustering algorithm

该研究基于机载激光雷达(LiDAR)和高光谱数据, 从森林物种叶片的生理化学源头探寻生化特征与光谱特征的内在关联, 探讨生化多样性、光谱多样性与物种多样性之间的响应机制, 选择最优植被指数并结合最优结构参数, 通过聚类方法构建森林物种多样性遥感估算模型, 在古田山自然保护区开展森林乔木物种多样性监测。研究结果表明: (1)从16种叶片生化组分中, 筛选出叶绿素a、叶绿素b、类胡萝卜素、叶片含水量、比叶面积、纤维素、木质素、氮、磷和碳可通过偏最小二乘法用叶片光谱有效模拟(R² = 0.60-0.79, p < 0.01), 并选择有效的植被指数: 转换型吸收反射指数/优化型土壤调整指数(TCARI/OSAVI)、类胡萝卜素反射指数(CRI)、水波段指数(WBI)、比值植被指数(RVI)、生理反射指数(PRI)和冠层叶绿素浓度指数(CCCI)表征相应的最优生化组分; (2)基于机载LiDAR数据利用结合形态学冠层控制的分水岭算法获得高精度单木分离结果(R ² = 0.77, RMSE = 16.48), 同时采用逐步回归方法从常用的森林结构参数中选取树高和偏度作为最优结构参数(R ² = 0.32, p < 0.01); (3)基于6个最优植被指数和2个最优结构参数, 以20 m × 20 m为窗口通过自适应模糊C均值方法进行聚类, 实现了研究区森林乔木物种丰富度(Richness, R ²= 0.56, RMSE = 1.81)和多样性指数Shannon-Wiener (R ² = 0.83, RMSE = 0.22)与Simpson (R ² = 0.85, RMSE = 0.09)的成图。该研究在冠层尺度上获取了与物种多样性相关的生化、光谱和结构参数, 将单木个体作为最小单元, 利用聚类算法直接估算物种类别差异, 无需判定具体的树种属性, 是利用遥感数据进行区域尺度森林物种多样性监测与成图的实践, 可为亚热带地区常绿阔叶林的物种多样性监测提供借鉴。     

利用聚类算法监测森林乔木物种多样性

该研究基于机载激光雷达(LiDAR)和高光谱数据, 从森林物种叶片的生理化学源头探寻生化特征与光谱特征的内在关联, 探讨生化多样性、光谱多样性与物种多样性之间的响应机制, 选择最优植被指数并结合最优结构参数, 通过聚类方法构建森林物种多样性遥感估算模型, 在古田山自然保护区开展森林乔木物种多样性监测。研究结果表明: (1)从16种叶片生化组分中, 筛选出叶绿素a、叶绿素b、类胡萝卜素、叶片含水量、比叶面积、纤维素、木质素、氮、磷和碳可通过偏最小二乘法用叶片光谱有效模拟(R² = 0.60-0.79, p < 0.01), 并选择有效的植被指数: 转换型吸收反射指数/优化型土壤调整指数(TCARI/OSAVI)、类胡萝卜素反射指数(CRI)、水波段指数(WBI)、比值植被指数(RVI)、生理反射指数(PRI)和冠层叶绿素浓度指数(CCCI)表征相应的最优生化组分; (2)基于机载LiDAR数据利用结合形态学冠层控制的分水岭算法获得高精度单木分离结果(R ² = 0.77, RMSE = 16.48), 同时采用逐步回归方法从常用的森林结构参数中选取树高和偏度作为最优结构参数(R ² = 0.32, p < 0.01); (3)基于6个最优植被指数和2个最优结构参数, 以20 m × 20 m为窗口通过自适应模糊C均值方法进行聚类, 实现了研究区森林乔木物种丰富度(Richness, R ²= 0.56, RMSE = 1.81)和多样性指数Shannon-Wiener (R ² = 0.83, RMSE = 0.22)与Simpson (R ² = 0.85, RMSE = 0.09)的成图。该研究在冠层尺度上获取了与物种多样性相关的生化、光谱和结构参数, 将单木个体作为最小单元, 利用聚类算法直接估算物种类别差异, 无需判定具体的树种属性, 是利用遥感数据进行区域尺度森林物种多样性监测与成图的实践, 可为亚热带地区常绿阔叶林的物种多样性监测提供借鉴。     

Traffic-aware routing protocol for wireless sensor networks

In wireless sensor networks, when a sensor node detects events in the surrounding environment, the sensing period for learning detailed information is likely to be short. However, the short sensing cycle increases the data traffic of the sensor nodes in a routing path. Since the high traffic load causes a data queue overflow in the sensor nodes, important information about urgent events could be lost. In addition, since the battery energy of the sensor nodes is quickly exhausted, the entire lifetime of wireless sensor networks would be shortened. In this paper, to address these problem issues, a new routing protocol is proposed based on a lightweight genetic algorithm. In the proposed method, the sensor nodes are aware of the data traffic rate to monitor the network congestion. In addition, the fitness function is designed from both the average and the standard deviation of the traffic rates of sensor nodes. Based on dominant gene sets in a genetic algorithm, the proposed method selects suitable data forwarding sensor nodes to avoid heavy traffic congestion. In experiments, the proposed method demonstrates efficient data transmission due to much less queue overflow and supports fair data transmission for all sensor nodes. From the results, it is evident that the proposed method not only enhances the reliability of data transmission but also distributes the energy consumption across wireless sensor networks.     

TBC: A clustering algorithm based on prokaryotic taxonomy

High-throughput DNA sequencing technologies have revolutionized the study of microbial ecology. Massive sequencing of PCR amplicons of the 16S rRNA gene has been widely used to understand the microbial community structure of a variety of environmental samples. The resulting sequencing reads are clustered into operational taxonomic units that are then used to calculate various statistical indices that represent the degree of species diversity in a given sample. Several algorithms have been developed to perform this task, but they tend to produce different outcomes. Herein, we propose a novel sequence clustering algorithm, namely Taxonomy-Based Clustering (TBC). This algorithm incorporates the basic concept of prokaryotic taxonomy in which only comparisons to the type strain are made and used to form species while omitting full-scale multiple sequence alignment. The clustering quality of the proposed method was compared with those of MOTHUR, BLASTClust, ESPRIT-Tree, CD-HIT, and UCLUST. A comprehensive comparison using three different experimental datasets produced by pyrosequencing demonstrated that the clustering obtained using TBC is comparable to those obtained using MOTHUR and ESPRIT-Tree and is computationally efficient. The program was written in JAVA and is available from .     

FastJoin, an improved neighbor-joining algorithm

Reconstructing the evolutionary history of a set of species is an elementary problem in biology, and methods for solving this problem are evaluated based on two characteristics: accuracy and efficiency. Neighbor-joining reconstructs phylogenetic trees by iteratively picking a pair of nodes to merge as a new node until only one node remains; due to its good accuracy and speed, it has been embraced by the phylogeny research community. With the advent of large amounts of data, improved fast and precise methods for reconstructing evolutionary trees have become necessary. We improved the neighbor-joining algorithm by iteratively picking two pairs of nodes and merging as two new nodes, until only one node remains. We found that another pair of true neighbors could be chosen to merge as a new node besides the pair of true neighbors chosen by the criterion of the neighbor-joining method, in each iteration of the clustering procedure for the purely additive tree. These new neighbors will be selected by another iteration of the neighbor-joining method, so that they provide an improved neighbor-joining algorithm, by iteratively picking two pairs of nodes to merge as two new nodes until only one node remains, constructing the same phylogenetic tree as the neighbor-joining algorithm for the same input data. By combining the improved neighbor-joining algorithm with styles upper bound computation optimization of RapidNJ and external storage of ERapidNJ methods, a new method of reconstructing phylogenetic trees, FastJoin, was proposed. Experiments with sets of data showed that this new neighbor-joining algorithm yields a significant speed-up compared to classic neighbor-joining, showing empirically that FastJoin is superior to almost all other neighbor-joining implementations.     

Genetic algorithm based two-mode clustering of metabolomics data

Metabolomics and other omics tools are generally characterized by large data sets with many variables obtained under different environmental conditions. Clustering methods and more specifically two-mode clustering methods are excellent tools for analyzing this type of data. Two-mode clustering methods allow for analysis of the behavior of subsets of metabolites under different experimental conditions. In addition, the results are easily visualized. In this paper we introduce a two-mode clustering method based on a genetic algorithm that uses a criterion that searches for homogeneous clusters. Furthermore we introduce a cluster stability criterion to validate the clusters and we provide an extended knee plot to select the optimal number of clusters in both experimental and metabolite modes. The genetic algorithm-based two-mode clustering gave biological relevant results when it was applied to two real life metabolomics data sets. It was, for instance, able to identify a catabolic pathway for growth on several of the carbon sources. Electronic supplementary material The online version of this article (doi:) contains supplementary material, which is available to authorized users. J. A. Hageman and R. A. van den Berg contributed equally to this paper.     

An improved micropropagation protocol for teak

An improved micropropagation protocol has been developed for teak (Tectona grandis). Nodal explants placed on MS medium supplemented with 22.2 M benzylaminopurine and then serially transferred to fresh medium after 12, 24, 48 and 72 h gave maximum culture establishment (76.8%). Establishment was reduced when explants were retained in the initial culture medium longer than 12 h. Explants collected in May showed maximum (76.8%) response. Placement of the explants on MS medium supplemented with 22.2 M benzylaminopurine and 0.57 M indole-3-acetic acid resulted in the maximum average number of shoots. In vitro raised micro shoots were rooted ex vitro by dipping in indole-3-butyric acid (9.8 mM) for 2 min followed by planting in polyethylene pots containing a soil:vermiculite (1:1 v/v) mixture. This treatment resulted in 77.9% survival of the plantlets. They were weaned in a glasshouse and finally moved to an agro-net shade house.     

An improved localization algorithm based on genetic algorithm in wireless sensor networks

Wireless sensor network (WSN) are widely used in many applications. A WSN is a wireless decentralized structure network comprised of nodes, which autonomously set up a network. The node localization that is to be aware of position of the node in the network is an essential part of many sensor network operations and applications. The existing localization algorithms can be classified into two categories: range-based and range-free. The range-based localization algorithm has requirements on hardware, thus is expensive to be implemented in practice. The range-free localization algorithm reduces the hardware cost. Because of the hardware limitations of WSN devices, solutions in range-free localization are being pursued as a cost-effective alternative to more expensive range-based approaches. However, these techniques usually have higher localization error compared to the range-based algorithms. DV-Hop is a typical range-free localization algorithm utilizing hop-distance estimation. In this paper, we propose an improved DV-Hop algorithm based on genetic algorithm. Simulation results show that our proposed algorithm improves the localization accuracy compared with previous algorithms.     

Purification of plasmid DNA by an improved electrophoretic protocol

Plasmid DNA from Escherichia coli was isolated by electroelution carried out in an agarose gel that contains an incorporated dialysis membrane. As the relative mobility of circular plasmid DNA to linear chromosomal DNA increases when the agarose concentration is decreased, we were able to purify plasmids of up to 50 kbp in 0.3% agarose gel in Tris acetate buffer yielding 10-60 g DNA ml bacterial culture.