Avoiding overfitting in multilayer perceptrons with feeling-of-knowing using self-organizing maps

Overfitting in multilayer perceptron (MLP) training is a serious problem. The purpose of this study is to avoid overfitting in on-line learning. To overcome the overfitting problem, we have investigated feeling-of-knowing (FOK) using self-organizing maps (SOMs). We propose MLPs with FOK using the SOMs method to overcome the overfitting problem. In this method, the learning process advances according to the degree of FOK calculated using SOMs. The mean square error obtained for the test set using the proposed method is significantly less than that in a conventional MLP method. Consequently, the proposed method avoids overfitting.     

A powerful approach for effective finding of significantly differentially expressed genes

The problem of identifying significantly differentially expressed genes for replicated microarray experiments is accepted as significant and has been tackled by several researchers. Patterns from Gene Expression (PaGE) and q-values are two of the well-known approaches developed to handle this problem. This paper proposes a powerful approach to handle this problem. We first propose a method for estimating the prior probabilities used in the first version of the PaGE algorithm. This way, the problem definition of PaGE stays intact and we just estimate the needed prior probabilities. Our estimation method is similar to Storey's estimator without being its direct extension. Then, we modify the problem formulation to find significantly differentially expressed genes and present an efficient method for finding them. This formulation increases the power by directly incorporating Storey's estimator. We report the preliminary results on the BRCA data set to demonstrate the applicability and effectiveness of our approach.     

An analytical approach to the problem of inverse optimization with additive objective functions: an application to human prehension

We consider the problem of what is being optimized in human actions with respect to various aspects of human movements and different motor tasks. From the mathematical point of view this problem consists of finding an unknown objective function given the values at which it reaches its minimum. This problem is called the inverse optimization problem. Until now the main approach to this problems has been the cut-and-try method, which consists of introducing an objective function and checking how it reflects the experimental data. Using this approach, different objective functions have been proposed for the same motor action. In the current paper we focus on inverse optimization problems with additive objective functions and linear constraints. Such problems are typical in human movement science. The problem of muscle (or finger) force sharing is an example. For such problems we obtain sufficient conditions for uniqueness and propose a method for determining the objective functions. To illustrate our method we analyze the problem of force sharing among the fingers in a grasping task. We estimate the objective function from the experimental data and show that it can predict the force-sharing pattern for a vast range of external forces and torques applied to the grasped object. The resulting objective function is quadratic with essentially non-zero linear terms.     

Effective haplotype assembly via maximum Boolean satisfiability

The haplotype assembly problem seeks the haplotypes of an individual from which a set of aligned SNP fragments are available. The problem is important as the haplotypes contain all the SNP information, which is essential to such studies as the analysis of the association between specific diseases and their potential genetic causes. Using Minimum Error Correction as the objective function, the problem is NP-hard, which raises the demand for effective yet affordable solutions. In this paper, we propose a new method to solve the problem by providing a novel Max-2-SAT formulation for the problem. The proposed method is compared with several well-known algorithms proposed for the problem in the literature on a recent extensive benchmark, outperforming them all by achieving solutions of higher average quality.     

Human-like Manipulation Planning for Articulated Manipulator

A new method based on human-likeness assessment and optimization concept to solve the problem of human-like manipulation planning for articulated robot is proposed in this paper.This method intrinsically formulates the problem as a constrained optimization problem in robot configuration space.The robot configuration space is divided into different subregions by human likeness assessment.A widely used strategy,Rapid Upper Limb Assessment (RULA) in applied ergonomics,is adopted here to evaluate the human likeness of robot configuration.A task compatibility measurement of the robot velocity transmission ratio along a specified direction is used as the target function for the optimization problem.Simple illustrative examples of this method applied to a two Degree of Freedom (DOF) planar robot that resembles the upper limb of a human are presented.Further applications to a humanoid industrial robot SDA10D are also presented.The reasonable planning results for these applications assert the effectiveness of our method.     

A graph theoretic approach to the development of minimal phylogenetic trees

Summary The problem of determining the minimal phylogenetic tree is discussed in relation to graph theory. It is shown that this problem is an example of the Steiner problem in graphs which is to connect a set of points by a minimal length network where new points can be added. There is no reported method of solving realistically-sized Steiner problems in reasonable computing time. A heuristic method of approaching the phylogenetic problem is presented, together with a worked example with 7 mammalian cytochrome c sequences. It is shown in this case that the method develops a phylogenetic tree that has the smallest possible number of amino acid replacements. The potential and limitations of the method are discussed. It is stressed that objective methods must be used for comparing different trees. In particular it should be determined how close a given tree is to a mathematically determined lower bound. A theorem is proved which is used to establish a lower bound on the length of any tree and if a tree is found with a length equal to the lower bound, then no shorter tree can exist.     

Learning Petri net models of non-linear gene interactions

Understanding how an individual's genetic make-up influences their risk of disease is a problem of paramount importance. Although machine-learning techniques are able to uncover the relationships between genotype and disease, the problem of automatically building the best biochemical model or "explanation" of the relationship has received less attention. In this paper, I describe a method based on random hill climbing that automatically builds Petri net models of non-linear (or multi-factorial) disease-causing gene-gene interactions. Petri nets are a suitable formalism for this problem, because they are used to model concurrent, dynamic processes analogous to biochemical reaction networks. I show that this method is routinely able to identify perfect Petri net models for three disease-causing gene-gene interactions recently reported in the literature.     

Gene Regulatory Network Inferences Using a Maximum-Relevance and Maximum-Significance Strategy

Recovering gene regulatory networks from expression data is a challenging problem in systems biology that provides valuable information on the regulatory mechanisms of cells. A number of algorithms based on computational models are currently used to recover network topology. However, most of these algorithms have limitations. For example, many models tend to be complicated because of the “large p, small n” problem. In this paper, we propose a novel regulatory network inference method called the maximum-relevance and maximum-significance network (MRMSn) method, which converts the problem of recovering networks into a problem of how to select the regulator genes for each gene. To solve the latter problem, we present an algorithm that is based on information theory and selects the regulator genes for a specific gene by maximizing the relevance and significance. A first-order incremental search algorithm is used to search for regulator genes. Eventually, a strict constraint is adopted to adjust all of the regulatory relationships according to the obtained regulator genes and thus obtain the complete network structure. We performed our method on five different datasets and compared our method to five state-of-the-art methods for network inference based on information theory. The results confirm the effectiveness of our method.     

Sorting by reciprocal translocations via reversals theory.

The understanding of genome rearrangements is an important endeavor in comparative genomics. A major computational problem in this field is finding a shortest sequence of genome rearrangements that transforms, or sorts, one genome into another. In this paper we focus on sorting a multi-chromosomal genome by translocations. We reveal new relationships between this problem and the well studied problem of sorting by reversals. Based on these relationships, we develop two new algorithms for sorting by reciprocal translocations, which mimic known algorithms for sorting by reversals: a score-based method building on Bergeron's algorithm, and a recursive procedure similar to the Berman-Hannenhalli method. Though their proofs are more involved, our procedures for reciprocal translocations match the complexities of the original ones for reversals.     

Inference of S-system models of genetic networks using a cooperative coevolutionary algorithm

MOTIVATION: To resolve the high-dimensionality of the genetic network inference problem in the S-system model, a problem decomposition strategy has been proposed. While this strategy certainly shows promise, it cannot provide a model readily applicable to the computational simulation of the genetic network when the given time-series data contain measurement noise. This is a significant limitation of the problem decomposition, given that our analysis and understanding of the genetic network depend on the computational simulation. RESULTS: We propose a new method for inferring S-system models of large-scale genetic networks. The proposed method is based on the problem decomposition strategy and a cooperative coevolutionary algorithm. As the subproblems divided by the problem decomposition strategy are solved simultaneously using the cooperative coevolutionary algorithm, the proposed method can be used to infer any S-system model ready for computational simulation. To verify the effectiveness of the proposed method, we apply it to two artificial genetic network inference problems. Finally, the proposed method is used to analyze the actual DNA microarray data.     

Maximum likelihood estimation for a special type of grouped data with an application to a dose-response problem.

A short-cut method is given for calculating grouped maximum likelihood (ML) estimates when the data are relatively coarsely grouped in some directions, but more finely grouped in others. The algebraic details are then worked out for a dose-response problem that generates data of this kind. The situation envisaged is a variation on the usual quantal response problem in that dosage levels are taken to be random but grouped. Finally, the method is applied both to real and simulated response data conforming to this pattern and shown to work well in practice.     

Estimation of Spatial Variation in Risk Using Matched Case‐control Data

A common problem in environmental epidemiology is to estimate spatial variation in disease risk after accounting for known risk factors. In this paper we consider this problem in the context of matched case‐control studies. We extend the generalised additive model approach of Kelsall and Diggle (1998) to studies in which each case has been individually matched to a set of controls. We discuss a method for fitting this model to data, apply the method to a matched study on perinatal death in the North West Thames region of England and explain why, if spatial variation is of particular scientific interest, matching is undesirable.     

Approximate Confidence Interval on Ratio of Two Variances in a Two-way Crossed Model

The model considered is a two-factor cross-classification variance components model with one observation per cell. Let the two factors be A and B, the problem is to obtain an approximate confidence interval for the ratio of variance component A over variance component B. In this paper, a method of solving this problem is established and simulations are performed to check the method.     

A novel method for estimating linkage maps

The goal of linkage mapping is to find the true order of loci from a chromosome. Since the number of possible orders is large even for a modest number of loci, the problem of finding the optimal solution is known as a NP-hard problem or traveling salesman problem (TSP). Although a number of algorithms are available, many either are low in the accuracy of recovering the true order of loci or require tremendous amounts of computational resources, thus making them difficult to use for reconstructing a large-scale map. We developed in this article a novel method called unidirectional growth (UG) to help solve this problem. The UG algorithm sequentially constructs the linkage map on the basis of novel results about additive distance. It not only is fast but also has a very high accuracy in recovering the true order of loci according to our simulation studies. Since the UG method requires n-1 cycles to estimate the ordering of n loci, it is particularly useful for estimating linkage maps consisting of hundreds or even thousands of linked codominant loci on a chromosome.     

Accurate and robust gene selection for disease classification using a simple statistic

Discrimination of disease patients based on gene expression data is a crucial problem in clinical area. An important issue to solve this problem is to find a discriminative subset of genes from thousands of genes on a microarray or DNA chip. Aiming at finding informative genes for disease classification on microarray, we present a gene selection method based on the forward variable (gene) selection method (FSM) and show, using typical public microarray datasets, that our method can extract a small set of genes being crucial for discriminating different classes with a very high accuracy almost closed to perfect classification.     

Potential of the pseudo-inverse method as a constrained static optimization for musculo-tendon forces prediction

Inverse dynamics combined with a constrained static optimization analysis has often been proposed to solve the muscular redundancy problem. Typically, the optimization problem consists in a cost function to be minimized and some equality and inequality constraints to be fulfilled. Penalty-based and Lagrange multipliers methods are common optimization methods for the equality constraints management. More recently, the pseudo-inverse method has been introduced in the field of biomechanics. The purpose of this paper is to evaluate the ability and the efficiency of this new method to solve the muscular redundancy problem, by comparing respectively the musculo-tendon forces prediction and its cost-effectiveness against common optimization methods. Since algorithm efficiency and equality constraints fulfillment highly belong to the optimization method, a two-phase procedure is proposed in order to identify and compare the complexity of the cost function, the number of iterations needed to find a solution and the computational time of the penalty-based method, the Lagrange multipliers method and pseudo-inverse method. Using a 2D knee musculo-skeletal model in an isometric context, the study of the cost functions isovalue curves shows that the solution space is 2D with the penalty-based method, 3D with the Lagrange multipliers method and 1D with the pseudo-inverse method. The minimal cost function area (defined as the area corresponding to 5% over the minimal cost) obtained for the pseudo-inverse method is very limited and along the solution space line, whereas the minimal cost function area obtained for other methods are larger or more complex. Moreover, when using a 3D lower limb musculo-skeletal model during a gait cycle simulation, the pseudo-inverse method provides the lowest number of iterations while Lagrange multipliers and pseudo-inverse method have almost the same computational time. The pseudo-inverse method, by providing a better suited cost function and an efficient computational framework, seems to be adapted to the muscular redundancy problem resolution in case of linear equality constraints. Moreover, by reducing the solution space, this method could be a unique opportunity to introduce optimization methods for a posteriori articulation of preference in order to provide a palette of solutions rather than a unique solution based on a lot of hypotheses.     

A simple method for estimating the parameter of substitution rate variation among sites

When the rate variation among sites is described by a gamma distribution, an important problem is how to estimate the shape parameter alpha, which is an index of the degree of among-site rate variation. The parsimony-based methods for estimating alpha are simple but biased, i.e., alpha tends to be overestimated. On the other hand, the likelihood-based methods are asymptotically unbiased but take a huge amount of computational time. In this paper, we have developed a new method to solve this problem: we first estimate the expected number of substitutions at each site, which is corrected for multiple hits, and then estimate the parameter alpha. Our method is computationally as fast as the parsimony method, and the estimation accuracy is much higher than that of parsimony and similar to that of the likelihood method.      

Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem

As a class of hard combinatorial optimization problems, the school bus routing problem has received considerable attention in the last decades. For a multi-school system, given the bus trips for each school, the school bus scheduling problem aims at optimizing bus schedules to serve all the trips within the school time windows. In this paper, we propose two approaches for solving the bi-objective school bus scheduling problem: an exact method of mixed integer programming (MIP) and a metaheuristic method which combines simulated annealing with local search. We develop MIP formulations for homogenous and heterogeneous fleet problems respectively and solve the models by MIP solver CPLEX. The bus type-based formulation for heterogeneous fleet problem reduces the model complexity in terms of the number of decision variables and constraints. The metaheuristic method is a two-stage framework for minimizing the number of buses to be used as well as the total travel distance of buses. We evaluate the proposed MIP and the metaheuristic method on two benchmark datasets, showing that on both instances, our metaheuristic method significantly outperforms the respective state-of-the-art methods.     

Optimal Aggregation of Binary Classifiers for Multiclass Cancer Diagnosis Using Gene Expression Profiles

Multiclass classification is one of the fundamental tasks in bioinformatics and typically arises in cancer diagnosis studies by gene expression profiling. There have been many studies of aggregating binary classifiers to construct a multiclass classifier based on one-versus-the-rest (1R), one-versus-one (11), or other coding strategies, as well as some comparison studies between them. However, the studies found that the best coding depends on each situation. Therefore, a new problem, which we call the ldquooptimal coding problem,rdquo has arisen: how can we determine which coding is the optimal one in each situation? To approach this optimal coding problem, we propose a novel framework for constructing a multiclass classifier, in which each binary classifier to be aggregated has a weight value to be optimally tuned based on the observed data. Although there is no a priori answer to the optimal coding problem, our weight tuning method can be a consistent answer to the problem. We apply this method to various classification problems including a synthesized data set and some cancer diagnosis data sets from gene expression profiling. The results demonstrate that, in most situations, our method can improve classification accuracy over simple voting heuristics and is better than or comparable to state-of-the-art multiclass predictors.     

基于启发式广度优先搜索的SVR参数优化方法研究

支持向量回归机(Support vector regressio,SVR)模型的拟合精度和泛化能力取决于其相关参数的选择,其参数选择实质上是一个优化搜索过程。根据启发式广度优先搜索(Heuristic Breadth first Search,HBFS)算法在求解优化问题上高效的特点,提出了一种以k-fold交叉验证的最小化误差为目标,HBFS为寻优策略的SVR参数选择方法,通过3个基准数据集对该模型进行了仿真实验,结果表明该方法在保证预测精度前提下,大幅度的缩短了训练建模时间,为大样本的SVR参数选择提供了一种新的有效解决方案。