The network coding enhances performance in network communications and distributed storage by increasing throughput and robustness while reducing latency. Batched sparse (BATS) codes are a class of capacity-achieving network codes, but their practical applications are hindered by their structure, computational intensity, and power demands of finite field (FF) operations. Most literature focuses on algorithmic-level techniques to improve the coding efficiency. Optimization with an algorithm/hardware co-designing approach has long been neglected. Leveraging the unique structure of BATS codes, we first present cyclic-shift BATS (CS-BATS), a hardware-friendly variant. Next, we propose a simple but effective bounded-value (BV) generator, to reduce the size of a finite field multiplier by up to 70%. Finally, we report on a scalable and resource-efficient field-programmable gate array (FPGA)-based network coding accelerator that achieves a throughput of 27 Gb/s, a speedup of more than 300 over software.

Gene regulatory network (GRN), which refers to the complex interactions with time delays between TFs and other genes, plays an important role in the working of the cell. Therefore inferring the GRN is crucial to studying diseases related to malfunctioning of the cell. Even with high-throughput technology, time series expression data is still limited compared to the network size, which poses significant challenge to inferring large GRN. Since GRNs are known to be modular, or hierarchically modular, we propose to exploit this by first inferring an initial GRN using CLINDE, then decomposing it into possibly overlapping subnetworks, then re-learning the subnetworks using either CLINDE or DD-lasso, and lastly merging the subnetworks. We have performed extensive experiments on synthetic data to test this strategy on both modular and hierarchically modular networks with 500 and 1000 genes, using either a long time series or several short time series. Results show that the strategy does improve GRN inference with statistical significance. Also, the algorithm is robust to different variance and slight deviation of Gaussianity for the error terms.

Classification on pseudoknots existence is a challenging and meaningful problem in Bioinformatics. As predicting RNA secondary structures with pseudoknots is NP-complete problem while predicting pseudoknot-free structures can be done in O(n3) time, if a preliminary pseudoknots existence classification of RNA sequence can be done before the prediction, the classification result can enhance the efficiency of RNA secondary structure prediction. In this paper, a classification of the existence of pseudoknots in an RNA sequence is presented. A set of features have been chosen by partial sequence content and thousands of RNA sequences with validated structures are used to train the classifier. Using a validated testing dataset, this classification method is shown to achieve a very good performance that the best result get 87% accuracy in 10-fold cross validation and around 75% accuracy in testing data. Moreover it may reveal how partial sequence content can affect the formation of pseudoknots.

BACKGROUND: Inferring gene regulatory network (GRN) has been an important topic in Bioinformatics. Many computational methods infer the GRN from high-throughput expression data. Due to the presence of time delays in the regulatory relationships, High-Order Dynamic Bayesian Network (HO-DBN) is a good model of GRN. However, previous GRN inference methods assume causal sufficiency, i.e. no unobserved common cause. This assumption is convenient but unrealistic, because it is possible that relevant factors have not even been conceived of and therefore un-measured. Therefore an inference method that also handles hidden common cause(s) is highly desirable. Also, previous methods for discovering hidden common causes either do not handle multi-step time delays or restrict that the parents of hidden common causes are not observed genes. RESULTS: We have developed a discrete HO-DBN learning algorithm that can infer also hidden common cause(s) from discrete time series expression data, with some assumptions on the conditional distribution, but is less restrictive than previous methods. We assume that each hidden variable has only observed variables as children and parents, with at least two children and possibly no parents. We also make the simplifying assumption that children of hidden variable(s) are not linked to each other. Moreover, our proposed algorithm can also utilize multiple short time series (not necessarily of the same length), as long time series are difficult to obtain. CONCLUSIONS: We have performed extensive experiments using synthetic data on GRNs of size up to 100, with up to 10 hidden nodes. Experiment results show that our proposed algorithm can recover the causal GRNs adequately given the incomplete data. Using the limited real expression data and small subnetworks of the YEASTRACT network, we have also demonstrated the potential of our algorithm on real data, though more time series expression data is needed.

Inferring gene regulatory network (GRN) from the microarray expression data is an important problem in Bioinformatics, because knowing the GRN is an essential first step in understanding the inner workings of the cell and the related diseases. Time delays exist in the regulatory effects from one gene to another due to the time needed for transcription, translation, and to accumulate a sufficient number of needed proteins. Also, it is known that the delays are important for oscillatory phenomenon. Therefore, it is crucial to develop a causal gene network model, preferably as a function of time. In this paper, we propose an algorithm CLINDE to infer causal directed links in GRN with time delays and regulatory effects in the links from time-series microarray gene expression data. It is one of the most comprehensive in terms of features compared to the state-of-the-art discrete gene network models. We have tested CLINDE on synthetic data, the in vivo IRMA (On and Off) datasets and the [1] yeast expression data validated using KEGG pathways. Results show that CLINDE can effectively recover the links, the time delays and the regulatory effects in the synthetic data, and outperforms other algorithms in the IRMA in vivo datasets.

RNAs are functionally important in many biological processes. Predicting secondary structures of RNAs can help understanding 3D structures and functions of RNAs. However, RNA secondary structure prediction with pseudoknots is NP-complete. Predicting whether the RNAs contain pseudoknots in advance can save computation time as secondary structure prediction without pseudoknots is much faster. In this paper, we use k-mer occurrences as attributes to predict whether the RNAs have pseudoknots in the secondary structure. The results show two classifiers can predict 90% of the instance correctly.

The free energy (evaluation) models used in RNA secondary structure prediction are one of the most important reasons that makes the prediction a challenging computational problem in Bioinformatics. These models are the key factor determining the accuracy of the prediction algorithms. Previously we have developed a method called GAknot that has obtained good performance on predicting RNA secondary structures with pseudoknots. In this paper, we propose a new free energy model. We first select a number of RNA sequences from a database which contains known RNA secondary structures as a training dataset for learning this new model. From the training dataset, we then extract base pairs patterns in subsequences of pairs of k-mers from the stems of each sequence in the training data and use the patterns to formulate penalty factors. We modify the energy model by adding these penalty factors. Combined with the new modified energy model, the prediction performance of GAknot has been improved significantly. GAknot with the new modified energy model is shown to be the best method in comparison with two state-of-the-art algorithms using a commonly used testing dataset. The penalty factors of the new energy model and dataset can be downloaded at http://appsrv.cse.cuhk.edu.hk/~kktong/NewModel.

Non-coding RNAs are RNA molecules that do not translate into proteins. These RNAs are functional important in many biological processes. Their biological functions are highly related to their interaction partners. RNA-RNA interactions are one of the possibilities. It is desired to use computational methods to study and predict the interaction partners of non-coding RNAs. Most recent programs for RNA-RNA interaction prediction programs are based on Turner Energy Model. Some papers show that the free energy of RNA-structures is lower than random sequences but it is not statistically significant. It shows that we may need to modify the energy model for different RNA structures applications. In this paper, we first study the RNA-RNA interaction pattern using experimental validated RNA-RNA interaction data, which are extracted from sRNATarBase. We study the sRNA-mRNA interaction data and extract some features of the RNA-RNA interaction patterns. Then we combine these features about interaction sites into the Turner Energy Model. We develop a genetic algorithm based program RIPGA to solve the RNA-RNA interaction prediction problem. We use genetic algorithm because the RNA-RNA interaction prediction is NP-hard and we are interested to find out good suboptimal solutions. We use an sRNA-mRNA interaction dataset to evaluate the performance of the modified energy model and compare the results with two state-of-the-art programs. The comparison of the original model and the modified model shows that the modified energy model has better performance in both sensitivity and positive predictive value (PPV). Comparing RIPGA with state-of-the-art programs, RIPGA have better sensitivity and comparable positive predictive value.

Predicting RNA secondary structure is a significant challenge in Bioinformatics especially including pseudoknots. There are so many researches proposed that pseudoknots have their own biological functions inside human body, so it is important to predict this kind of RNA secondary structures. There are several methods to predict RNA secondary structure, and the most common one is using minimum free energy. However, finding the minimum free energy to predict secondary structure with pseudoknots has been proven to be an NP-complete problem, so there are many heuristic approaches trying to solve this kind of problems. In this paper, we propose GAknot, a computational method using genetic algorithm (GA), to predict RNA secondary structure with pseudoknots. GAknot first generates a set of maximal stems, and then it tries to generate several individuals by different combinations of stems. After halting condition is reached, GAknot will output the best solution as the output of predicted secondary structure. By using two commonly used validation data sets, GAknot is shown to be a better prediction method in terms of accuracy and speed comparing to several competitive prediction methods. Source code and datasets can be downloaded.

Nonlinear integrals (NIs) are useful integration tools. It can get a set of virtual values by projecting original data onto a virtual space for classification purpose using NIs. The classical NIs implement projection along a line with respect to the features. But, in many cases, the linear projection cannot achieve good performance for classification or regression due to the limitation of the integrand. The linear function used for the integrand is just a special type of function with respect to the features. In this paper, we propose a nonlinear integrals with polynomial kernel (NIPK). A polynomial function with respect to the features is used as the integrand of NIs. It enables the projection to be along different types of curves to the virtual space so that the virtual values gotten by NIs can be better regularized and have higher separation power for classification. We use genetic algorithm to learn the fuzzy measures so that a larger solution space can be searched. To test the capability of the NIPK, we apply it to classification on several benchmark datasets and a bioinformatics project. Experiments show that there is evident improvement on performance for the NIPK compared to classical NIs. © 2011 Wiley Periodicals, Inc.

A new nonlinear multiregression model based on a pair of extreme nonlinear integrals, upper and lower nonlinear integrals with respect to signed fuzzy measure, is established in this paper. A data set with the predictive features and the relevant objective feature is required for estimating the regression coefficients. Owing to the nonadditivity of the model, a multiobjective optimization using genetic algorithm is adopted to search for the optimized solution in the regression problem. Applying such a nonlinear multiregression model, an interval prediction for the value of the objective feature can be made once a new observation of predictive features is available. We apply our model on synthetic data and weather problem. The results testify the performance of the multiregression based on upper and lower nonlinear integrals. © 2012 Wiley Periodicals, Inc.

Identifying the unknown transcription factor binding sites (TFBSs) is a fundamental and important component for understanding gene regulation as well as life mechanisms. The corresponding de novo motif discovery problem in bioinformatics is formulated as pattern discovery from strings, where challenges come from both modeling and optimization, because the short TFBSs are weak signals in massive and noisy experimental data. While genetic algorithms have been widely applied to the problem, recent memetic algorithms (MAs) employing local operators demonstrate the superiority in both effectiveness and efficiency. In this paper, we propose and study various MA components including local operators and models for motif discovery, through the newly established MA framework. The demonstrated optimization and modeling capabilities are analyzed in-depth on real datasets and their noisy versions. Selected optimal MAs show significantly improved performance over state-of-the-art methods in extensive tests including the blind test on the eukaryotic benchmark. This paper serves as the first systematic study of MAs on de novo motif discovery, where important issues are highlighted in the analyses of MA design. The comprehensive component categorization and the MA framework provide a useful platform for future MA developments, especially on the newly emerging chromatin immunoprecipitation followed by sequencing data.

Discovering new drugs for emerging diseases has been a challenging task. There are numerous drug design techniques including fragment-based and diversity-oriented methods but their accuracies and efficiencies are low. By incorporating visualisation, biomedical experts can interact with the process to produce drug-like ligands more efficiently. The paper presents an interactive drug design algorithm which generates lead candidates against a protein. A set of drug candidates, created by an in house fragment-based method and docked on the target protein, are visualised in the virtual reality settings. Biomedical experts can investigate and select some of the ligands for further processing, aided with distance and bonding information. It also assists the user to drag and rotate the ligand to the binding site they find suitable. The algorithm runs iteratively and improves the quality of lead candidates every step. The paper compares the quality of resulting ligands between interactive and automatic approaches.

MOTIVATION: The bindings between transcription factors (TFs) and transcription factor binding sites (TFBSs) are fundamental protein-DNA interactions in transcriptional regulation. Extensive efforts have been made to better understand the protein-DNA interactions. Recent mining on exact TF-TFBS-associated sequence patterns (rules) has shown great potentials and achieved very promising results. However, exact rules cannot handle variations in real data, resulting in limited informative rules. In this article, we generalize the exact rules to approximate ones for both TFs and TFBSs, which are essential for biological variations. RESULTS: A progressive approach is proposed to address the approximation to alleviate the computational requirements. Firstly, similar TFBSs are grouped from the available TF-TFBS data (TRANSFAC database). Secondly, approximate and highly conserved binding cores are discovered from TF sequences corresponding to each TFBS group. A customized algorithm is developed for the specific objective. We discover the approximate TF-TFBS rules by associating the grouped TFBS consensuses and TF cores. The rules discovered are evaluated by matching (verifying with) the actual protein-DNA binding pairs from Protein Data Bank (PDB) 3D structures. The approximate results exhibit many more verified rules and up to 300% better verification ratios than the exact ones. The customized algorithm achieves over 73% better verification ratios than traditional methods. Approximate rules (64-79%) are shown statistically significant. Detailed variation analysis and conservation verification on NCBI records demonstrate that the approximate rules reveal both the flexible and specific protein-DNA interactions accurately. The approximate TF-TFBS rules discovered show great generalized capability of exploring more informative binding rules.

Extraction of meaningful information from large experimental data sets is a key element in bioinformatics research. One of the challenges is to identify genomic markers in Hepatitis B Virus (HBV) that are associated with HCC (liver cancer) development by comparing the complete genomic sequences of HBV among patients with HCC and those without HCC. In this study, a data mining framework, which includes molecular evolution analysis, clustering, feature selection, classifier learning, and classification, is introduced. Our research group has collected HBV DNA sequences, either genotype B or C, from over 200 patients specifically for this project. In the molecular evolution analysis and clustering, three subgroups have been identified in genotype C and a clustering method has been developed to separate the subgroups. In the feature selection process, potential markers are selected based on Information Gain for further classifier learning. Then, meaningful rules are learned by our algorithm called the Rule Learning, which is based on Evolutionary Algorithm. Also, a new classification method by Nonlinear Integral has been developed. Good performance of this method comes from the use of the fuzzy measure and the relevant nonlinear integral. The nonadditivity of the fuzzy measure reflects the importance of the feature attributes as well as their interactions. These two classifiers give explicit information on the importance of the individual mutated sites and their interactions toward the classification (potential causes of liver cancer in our case). A thorough comparison study of these two methods with existing methods is detailed. For genotype B, genotype C subgroups C1, C2, and C3, important mutation markers (sites) have been found, respectively. These two classification methods have been applied to classify never-seen-before examples for validation. The results show that the classification methods have more than 70 percent accuracy and 80 percent sensitivity for most data sets, which are considered high as an initial scanning method for liver cancer diagnosis.

DNA motif discovery is an important problem for deciphering gene regulation. Motifs usually contain gaps (spaced) and are more complex than contiguously conserved (monad) patterns. Existing algorithms mostly address monad motifs, and methods for spaced motifs impose various constraints on gaps, which may affect the discovery of complex motifs. In this paper, we propose Genetic Algorithm (GA) for Spaced Motifs Elicitation on Nucleotides (GASMEN), which searches from a wide range of possible widths (4-25) and relaxes substantial constraints. GASMEN employs submotif indexing to partition the search space into smaller sub-space for GA to easier reach optimality. Multiple-motif control is employed and probabilistic refinements are proposed to improve motif quality respectively. The preliminary results on real spaced motifs demonstrate that GASMEN is promising to find more accurate motifs and optimal widths, compared with the state-of-the-art method, SPACE. GASMEN is also capable of finding monad motifs, outperforming both Weeder and SPACE on most of the 8 real datasets.

Motif discovery is an important Bioinformatics problem for deciphering gene regulation. Numerous sequence-based approaches have been proposed employing human specialist motif models (evaluation functions), but performance is so unsatisfactory on benchmarks that the underlying information seems to have already been exploited and have doomed. However, we have found that even a simple modified representation still achieves considerably high performance on a challenging benchmark, implying potential for sequence-based motif discovery. Thus we raise the problem of learning motif evaluation functions. We employ Genetic programming (GP) which has the potential to evolve human competitive models. We take advantage of the terminal set containing specialist-model-like components and have tried three fitness functions. Results exhibit both great challenges and potentials. No models learnt can perform universally well on the challenging benchmark, where one reason may be the data appropriateness for sequence-based motif discovery. However, when applied on different widely-tested datasets, the same models achieve comparable performance to existing approaches based on specialist models. The study calls for further novel GP to learn different levels of effective evaluation models from strict to loose ones on exploiting sequence information for motif discovery, namely quantitative functions, cardinal rankings, and learning feasibility classifications.

Finding Transcription Factor Binding Sites, i.e., motif discovery, is crucial for understanding the gene regulatory relationship. Motifs are weakly conserved and motif discovery is an NP-hard problem. We propose a new approach called Cluster Refinement Algorithm for Motif Discovery (CRMD). CRMD employs a flexible statistical motif model allowing a variable number of motifs and motif instances. CRMD first uses a novel entropy-based clustering to find complete and good starting candidate motifs from the DNA sequences. CRMD then employs an effective greedy refinement to search for optimal motifs from the candidate motifs. The refinement is fast, and it changes the number of motif instances based on the adaptive thresholds. The performance of CRMD is further enhanced if the problem has one occurrence of motif instance per sequence. Using an appropriate similarity test of motifs, CRMD is also able to find multiple motifs. CRMD has been tested extensively on synthetic and real data sets. The experimental results verify that CRMD usually outperforms four other state-of-the-art algorithms in terms of the qualities of the solutions with competitive computing time. It finds a good balance between finding true motif instances and screening false motif instances, and is robust on problems of various levels of difficulty.

BACKGROUND: Identification of transcription factor binding sites (TFBSs) is a central problem in Bioinformatics on gene regulation. de novo motif discovery serves as a promising way to predict and better understand TFBSs for biological verifications. Real TFBSs of a motif may vary in their widths and their conservation degrees within a certain range. Deciding a single motif width by existing models may be biased and misleading. Additionally, multiple, possibly overlapping, candidate motifs are desired and necessary for biological verification in practice. However, current techniques either prohibit overlapping TFBSs or lack explicit control of different motifs. RESULTS: We propose a new generalized model to tackle the motif widths by considering and evaluating a width range of interest simultaneously, which should better address the width uncertainty. Moreover, a meta-convergence framework for genetic algorithms (GAs), is proposed to provide multiple overlapping optimal motifs simultaneously in an effective and flexible way. Users can easily specify the difference amongst expected motif kinds via similarity test. Incorporating Genetic Algorithm with Local Filtering (GALF) for searching, the new GALF-G (G for generalized) algorithm is proposed based on the generalized model and meta-convergence framework. CONCLUSION: GALF-G was tested extensively on over 970 synthetic, real and benchmark datasets, and is usually better than the state-of-the-art methods. The range model shows an increase in sensitivity compared with the single-width ones, while providing competitive precisions on the E. coli benchmark. Effectiveness can be maintained even using a very small population, exhibiting very competitive efficiency. In discovering multiple overlapping motifs in a real liver-specific dataset, GALF-G outperforms MEME by up to 73% in overall F-scores. GALF-G also helps to discover an additional motif which has probably not been annotated in the dataset. http://www.cse.cuhk.edu.hk/%7Etmchan/GALFG/

The problem of Transcription Factor Binding Sites identification or motif discovery is to identify the motif binding sites in the cis-regulatory regions of DNA sequences. The biological experiments are expensive and the problem is NP-hard computationally. We have proposed Estimation of Distribution Algorithm for Motif Discovery (EDAMD). We use Bayesian analysis to derive the fitness function to measure the posterior probability of a set of motif instances, which can be used to handle a variable number of motif instances in the sequences. EDAMD adopts a Gaussian distribution to model the distribution of the sets of motif instances, which is capable of capturing the bivariate correlation among the positions of motif instances. When a new Position Frequency Matrix (PFM) is generated from the Gaussian distribution, a new set of motif instances is identified based on the PFM via the Greedy Refinement operation. At the end of a generation, the Gaussian distribution is updated with the sets of motif instances. Since Greedy Refinement assumes a single motif instance on a sequence, a Post Processing operation based on the fitness function is used to find more motif instances after the evolution. The experiments have verified that EDAMD is comparable to or better than GAME and GALF on the real problems tested in this paper.

As an aggregation tool in information fusion and data mining, the Choquet integral is generalized to allow the involved set function being fuzzy-valued. A calculation formula of such a Choquet integral is developed when the universal set is finite, such as the set of attributes in a database.

MOTIVATION: Identification of transcription factor binding sites (TFBSs) plays an important role in deciphering the mechanisms of gene regulation. Recently, GAME, a Genetic Algorithm (GA)-based approach with iterative post-processing, has shown superior performance in TFBS identification. However, the basic GA in GAME is not elaborately designed, and may be trapped in local optima in real problems. The feature operators are only applied in the post-processing, but the final performance heavily depends on the GA output. Hence, both effectiveness and efficiency of the overall algorithm can be improved by introducing more advanced representations and novel operators in the GA, as well as designing the post-processing in an adaptive way. RESULTS: We propose a novel framework GALF-P, consisting of Genetic Algorithm with Local Filtering (GALF) and adaptive post-processing techniques (-P), to achieve both effectiveness and efficiency for TFBS identification. GALF combines the position-led and consensus-led representations used separately in current GAs and employs a novel local filtering operator to get rid of false positives within an individual efficiently during the evolutionary process in the GA. Pre-selection is used to maintain diversity and avoid local optima. Post-processing with adaptive adding and removing is developed to handle general cases with arbitrary numbers of instances per sequence. GALF-P shows superior performance to GAME, MEME, BioProspector and BioOptimizer on synthetic datasets with difficult scenarios and real test datasets. GALF-P is also more robust and reliable when further compared with GAME, the current state-of-the-art approach. AVAILABILITY: http://www.cse.cuhk.edu.hk/~tmchan/GALFP/.

In genetic programming (GP), evolving tree nodes separately would reduce the huge solution space. However, tree nodes are highly interdependent with respect to their fitness. In this paper, we propose a new GP framework, namely, instruction-matrix (IM)-based GP (IMGP), to handle their interactions. IMGP maintains an IM to evolve tree nodes and subtrees separately. IMGP extracts program trees from an IM and updates the IM with the information of the extracted program trees. As the IM actually keeps most of the information of the schemata of GP and evolves the schemata directly, IMGP is effective and efficient. Our experimental results on benchmark problems have verified that IMGP is not only better than those of canonical GP in terms of the qualities of the solutions and the number of program evaluations, but they are also better than some of the related GP algorithms. IMGP can also be used to evolve programs for classification problems. The classifiers obtained have higher classification accuracies than four other GP classification algorithms on four benchmark classification problems. The testing errors are also comparable to or better than those obtained with well-known classifiers. Furthermore, an extended version, called condition matrix for rule learning, has been used successfully to handle multiclass classification problems.

Identification of Transcription Factor Binding Site (TFBS) motifs in multiple DNA upstream sequences is important in understanding the mechanism of gene regulation. This identification problem is challenging because such motifs are usually weakly conserved due to evolutionary variation. Exhaustive search is intractable for finding long motifs because the combinatorial growth of the search space is exponential, thus heuristic methods are preferred. In this paper, we propose the Genetic Algorithm with Local Filtering (GALF) to address the problem, which combines and utilizes both position-led and consensus-led representations in present GA approaches. While position-led representation provides flexibility to move around the search space, it is likely to contain some "false positive" sites within an individual. This problem can be overcome by our local filtering operator, which employs consensus-led representation, while it needs less computation than alignments used in conventional consensus-led approaches. Thus both efficiency and accuracy can be achieved. The experimental results on real biological data show that our method can identify TFBSs more accurately and efficiently than other methods including GA-based ones, and is able to deal with relaxed motif widths with superior correctness.

The advances in kernel-based learning necessitate the study on solving a large-scale non-sparse positive definite linear system. To provide a deterministic approach, recent researches focus on designing fast matrixvector multiplication techniques coupled with a conjugate gradient method. Instead of using the conjugate gradient method, our paper proposes to use a domain decomposition approach in solving such a linear system. Its convergence property and speed can be understood within von Neumann’s alternating projection framework. We will report significant and consistent improvements in convergence speed over the conjugate gradient method when the approach is applied to recent machine learning problems. 1.

Experimental results show that parallel programs can be evolved more easily than sequential programs in genetic parallel programming (GPP). GPP is a novel genetic programming paradigm which evolves parallel program solutions. With the rapid development of lookup-table-based (LUT-based) field programmable gate arrays (FPGAs), traditional circuit design and optimization techniques cannot fully exploit the LUTs in LUT-based FPGAs. Based on the GPP paradigm, we have developed a combinational logic circuit learning system, called GPP logic circuit synthesizer (GPPLCS), in which a multilogic-unit processor is used to evaluate LUT circuits. To show the effectiveness of the GPPLCS, we have performed a series of experiments to evolve combinational logic circuits with two- and four-input LUTs. In this paper, we present eleven multi-output Boolean problems and their evolved circuits. The results show that the GPPLCS can evolve more compact four-input LUT circuits than the well-known LUT-based FPGA synthesis algorithms.

This correspondence introduces a multidrug cancer chemotherapy model to simulate the possible response of the tumor cells under drug administration. We formulate the model as an optimal control problem. The algorithm in this correspondence optimizes the multidrug cancer chemotherapy schedule. The objective is to minimize the tumor size under a set of constraints. We combine the adaptive elitist genetic algorithm with a local search algorithm called iterative dynamic programming (IDP) to form a new memetic algorithm (MA-IDP) for solving the problem. MA-IDP has been shown to be very efficient in solving the multidrug scheduling optimization problem.

Based on the theoretical guidance and existing recommendations for designing efficient genetic representations, we investigate a novel genetic representation — a splicing/decomposable (S/D) binary encoding in this paper. The S/D binary representation can be spliced and decomposed to describe potential solutions of the problem with different precisions by different number of uniform-salient building blocks (BBs). According to the characteristics of the S/D binary representation, genetic and evolutionary algorithms (GEAs) can be applied from the high scaled to the low scaled BBs sequentially to avoid genetic drift and improve GEAs’ performance. Our theoretical and empirical investigations reveal that the S/D binary representation is more proper than other existing binary encodings for GEAs searching.

Genetic Parallel Programming (GPP) is a novel Genetic Programming paradigm. Based on the GPP paradigm and a local search operator - FlowMap, a logic circuit synthesizing system integrating GPP and FlowMap, a Hybridized GPP based Logic Circuit Synthesizer (HGPPLCS) is developed. To show the effectiveness of the proposed HGPPLCS, six combinational logic circuit problems are used for evaluations. Each problem is run for 50 times. Experimental results show that both the lookup table counts and the propagation gate delays of the circuits collected are better than those obtained by conventional design or evolved by GPP alone. For example, in a 6-bit one counter experiment, we obtained combinational digital circuits with 8 four-input lookup tables in 2 gate level on average. It utilizes 2 lookup tables and 3 gate levels less than circuits evolved by GPP alone.

In this paper, we introduce a new genetic representation --- a splicing/decomposable (S/D) binary encoding, which was proposed based on some theoretical guidance and existing recommendations for designing efficient genetic representations. Our theoretical and empirical investigations reveal that the S/D binary representation is more proper than other existing binary encodings for searching of genetic algorithms (GAs). Moreover, we define a new genotypic distance on the S/D binary space, which is equivalent to the Euclidean distance on the real-valued space during GAs convergence. Based on the new genotypic distance, GAs can reliably and predictably solve problems of bounded complexity and the methods depended on the Euclidean distance for solving different kinds of optimization problems can be directly used on the S/D binary space.

Most genetic programming paradigms are population-based and require huge amount of memory. In this paper, we review the instruction matrix based genetic programming which maintains all program components in a instruction matrix (IM) instead of manipulating a population of programs. A genetic program is extracted from the matrix just before it is being evaluated. After each evaluation, the fitness of the genetic program is propagated to its corresponding cells in the matrix. Then, we extend the instruction matrix to the condition matrix (CM) for generating rule base from datasets. CM keeps some of characteristics of IM and incorporates the information about rule learning. In the evolving process, we adopt an elitist idea to keep the better rules alive to the end. We consider that genetic selection maybe lead to the huge size of rule set, so the reduct theory borrowed from rough sets is used to cut the volume of rules and keep the same fitness as the original rule set. In experiments, we compare the performance of condition matrix for rule learning (CMRL) with other traditional algorithms. Results are presented in detail and the competitive advantage and drawbacks of CMRL are discussed

Kernel-based regularized learning seeks a model in a hypothesis space by minimizing the empirical error and the model's complexity. Based on the representer theorem, the solution consists of a linear combination of translates of a kernel. This paper investigates a generalized form of representer theorem for kernel-based learning. After mapping predefined features and translates of a kernel simultaneously onto a hypothesis space by a specific way of constructing kernels, we proposed a new algorithm by utilizing a generalized regularizer which leaves part of the space unregularized. Using a squared-loss function in calculating the empirical error, a simple convex solution is obtained which combines predefined features with translates of the kernel. Empirical evaluations have confirmed the effectiveness of the algorithm for supervised learning tasks.

This paper presents a novel Genetic Parallel Programming (GPP) paradigm for evolving parallel programs running on a Multi-Arithmetic-Logic-Unit (Multi-ALU) Processor (MAP). The MAP is a Multiple Instruction-streams, Multiple Data-streams (MIMD), general-purpose register machine that can be implemented on modern Very Large-Scale Integrated Circuits (VLSIs) in order to evaluate genetic programs at high speed. For human programmers, writing parallel programs is more difficult than writing sequential programs. However, experimental results show that GPP evolves parallel programs with less computational effort than that of their sequential counterparts. It creates a new approach to evolving a feasible problem solution in parallel program form and then serializes it into a sequential program if required. The effectiveness and efficiency of GPP are investigated using a suite of 14 well-studied benchmark problems. Experimental results show that GPP speeds up evolution substantially.

This paper proposes a new memetic algorithm (MA) to solve the multi-drug chemotherapy optimization problem. The new MA combines GA with a local search algorithm called iterative dynamic programming (IDP). A multi-drug chemotherapy model is introduced to simulate the possible response of the tumor cells under drugs administration. Optimization of the multiple chemotherapeutic agents' administration schedules is based on this tumor model. We formulate the optimization problem as an optimal control problem (OCP) with a set of dynamic equations. The objective is to design efficient schedules which minimize the tumor size under a set of constraints. Our new MA has been shown to be very efficient on solving our multi-drug model.

A novel linear genetic programming (LGP) paradigm called genetic parallel programming (GPP) has been proposed to evolve parallel programs based on a multi-ALU processor. It is found that GPP can evolve parallel programs for data classification problems. In this paper, five binary-class UCI machine learning repository databases are used to test the effectiveness of the proposed GPP-classifier. The main advantages of employing GPP for data classification are: 1) speeding up evolutionary process by parallel hardware fitness evaluation; and 2) discovering parallel algorithms automatically. Experimental results show that the GPP-classifier evolves simple classification programs with good generalization performance. The accuracies of these evolved classifiers are comparable to other existing classification algorithms.

We investigate the sample weighting effect on genetic parallel programming (GPP). GPP evolves parallel programs to solve the training samples in a training set. Usually, the samples are captured directly from a real-world system. The distribution of samples in a training set can be extremely biased. Standard GPP assigns equal weights to all samples. It slows down evolution because crowded regions of samples dominate the fitness evaluation causing premature convergence. We present 4 sample weighting (SW) methods, i.e. equal SW, class-equal SW, static SW (SSW) and dynamic SW (DSW). We evaluate the 4 methods on 7 training sets (3 Boolean functions and 4 UCI medical data classification databases). Experimental results show that DSW is superior in performance on all tested problems. In the 5-input symmetry Boolean function experiment, SSW and DSW boost the evolutionary performance by 465 and 745 times respectively. Due to the simplicity and effectiveness of SSW and DSW, they can also be applied to different population-based evolutionary algorithms.

A massively parallel single instruction multiple data stream (SIMD) processor designed specifically for cryptographic key search applications is presented. This design exploits fine grain parallelism and the high memory bandwidth available in an FPGA (field programmable gate array) by integrating 95 simple processors and memory on a single FPGA chip. Performance is compared with a previously reported hardwired design on a RC4 key search application.

A module generator is described that allows for the generation of synthesizable VHDL modules which implement arbitrary functions in fixed point precision using the Symmetric Table Addition Method (STAM). This module generator was interfaced to a high level synthesis tool "fly" which automatically generates fully-pipelined circuits from a Perl-like language. The resulting system was applied to the N-body problem and results are presented. It was found that a function generator module is a very useful addition to a hardware description language.

Abstract This paper presents a stochastic dynamic load balancing algorithm for Internet computing, which is a new type of distributed computing involving heterogeneous workstations from different organizations on the Internet. To realize the practical environment, we assume the system to be comprised of heterogeneous, untrusted and non‐dedicated workstations connected by a non‐dedicated network. Our algorithm uses the product of the average processing time and the queue length of system jobs as the load index. Dynamic communication delay is included in the execution cost calculation. The transfer policy and the location policy are combined in a stochastic algorithm. State information exchange is done via information feedback and mutual updating. Simulations demonstrate that our algorithm outperforms conventional approaches over a wide range of system parameters. These results are reconfirmed by empirical experiments after we have implemented the algorithms on the Distributed Java Machine global virtual machine. Copyright © 2003 John Wiley & Sons, Ltd.

Abstract Many real‐world optimization problems in the scientific and engineering fields can be solved by genetic algorithms (GAs) but it still requires a long execution time for complex problems. At the same time, there are many under‐utilized workstations on the Internet. In this paper, we present a self‐adaptive parallel GA system named APGAIN, which utilizes the spare power of the heterogeneous workstations on the Internet to solve complex optimization problems. In order to maintain a balance between exploitation and exploration, we have devised a novel probabilistic rule‐driven adaptive model (PRDAM) to adapt the GA parameters automatically. APGAIN is implemented on an Internet Computing system called DJM. In the implementation, we discover that DJM's original load balancing strategy is insufficient. Hence the strategy is extended with the job migration capability. The performance of the system is evaluated by solving the traveling salesman problem with data from a public database. Copyright © 2003 John Wiley & Sons, Ltd.

This paper proposes a novel genetic parallel programming (GPP) paradigm for evolving optimal parallel programs running on a multi-ALU processor by linear genetic programming. GPP uses a two-phase evolution approach. It evolves completely correct solution programs in the first phase. Then it optimizes execution speeds of solution programs in the second phase. Besides, GPP also employs a new genetic operation that swaps sub-instructions of a solution program. Three experiments (Sextic, Fibonacci and Factorial) are given as examples to show that GPP could discover novel parallel programs that fully utilize the processor's parallelism.

A massively parallel implementation of an RC4 key search engine on an FPGA is described. The design employs parallelism at the logic level to perform many operations per cycle, uses on-chip memories to achieve very high memory bandwidth, floorplanning to reduce routing delays and multiple decryption units to achieve further parallelism. A total of 96 RC4 decryption engines were integrated on a single Xilinx Virtex XCV1000-E field programmable gate array (FPGA). The resulting design operates at a 50 MHz clock rate and achieves a search speed of 6.06 /spl times/ 10/sup 6/ keys/second, which is a speedup of 58 over a 1.5 GHz Pentium 4 PC.

This paper describes system level issues encountered in a high performance implementation of a Rijndael encryption core on a memory-slot based reconfigurable computing platform called Pilchard. The Rijndael algorithm was adopted in 2000 by the US National Institute of Standards and Technology (NIST) as the Advanced Encryption Standard (AES). In the implementation of Rijndael, changing the number of unrolled rounds in the encryption core can affect the performance of the system. It is shown that for the design presented, the highest performance of 755 Mbit/sec was achieved by implementing a core with a single round. Although it is relatively easy to implement a high performance core on an FPGA, due to I/O bottlenecks, achieving high system level performance is more difficult. In order to optimize the performance of the host/FPGA interface, special instructions from the Intel Pentium III streaming SIMD extensions (SSE) along with write-combining memory operations were used. These features enabled the measured throughput of the AES core to reach 445 Mbit/sec which, although still slower than the AES core, was double that of an unoptimized interface.

Chinese spell checking is different from its counterparts for Western languages because Chinese words in texts are not separated by spaces. Chinese spell checking in this article refers to how to identify the misuse of characters in text composition. In other words, it is error correction at the word level rather than at the character level. Before Chinese sentences are spell checked, the text is segmented into semantic units. Error detection can then be carried out on the segmented text based on thesaurus and grammar rules. Segmentation is not a trivial process due to ambiguities in the Chinese language and errors in texts. Because it is not practical to define all Chinese words in a dictionary, words not predefined must also be dealt with. The number of word combinations increases exponentially with the length of the sentence. In this article, a Block-of-Combinations (BOC) segmentation method based on frequency of word usage is proposed to reduce the word combinations from exponential growth to linear growth. From experiments carried out on Hong Kong newspapers, BOC can correctly solve 10% more ambiguities than the Maximum Match segmentation method. To make the segmentation more suitable for spell checking, user interaction is also suggested.

In this paper, we present the design and implementation of a novel model of distributed computing on the Internet and Intranet environment. Our model is called the Distributed Java Machine (DJM). It is a global distributed virtual machine used to realize the concept of ‘network is the computer’. DJM explores coarse-grained parallelism by using the under-utilized workstations on the network, combining the elements of object-oriented technology, distributed computing, World-Wide Web and Java programming. It can run on machines with heterogeneous hardware and software platforms without relinking or recompilation. DJM has two unique features. First, using an original applet helper mechanism, DJM allows machines without any DJM software and of different levels of ‘trust’ to work together. Secondly, DJM has implemented concurrency enhancement mechanisms (one-way message, future and redirected future) to increase the efficiency of method invocation. The prototype of DJM has been implemented and tested under both the Intranet and the Internet environments. Using the workstations from our teaching laboratories, which are already running under normal loading, experimental results show that we can achieve a speedup of about 5–8 times by 14 workstations in a Local Area Network (LAN) environment, and about 4.5 times speedup for eight workstations in a Wide Area Network (WAN) environment. © 1998 John Wiley & Sons, Ltd.