We consider the single-machine time-dependent scheduling problem with linearly deteriorating jobs arriving over time. Each job i is associated with a release time ri and a processing time pi(si)=αi+βisi, where αi,βi>0 are parameters and si is the job's start time. In this setting, the approximability of both single-machine minimum makespan and total completion time problems remains open. We develop new bounds and approximation results for the special case of the problems with uniform deterioration, i.e. βi=β, for each i. The main contribution is a O(1+1/β)-approximation algorithm for the makespan problem and a O(1+1/β2) approximation algorithm for the total completion time problem. Further, we propose greedy constant-factor approximation algorithms for instances with β=O(1/n) and β=Ω(n), where n is the number of jobs. Our analysis is based on an approach for comparing computed and optimal schedules via bounding pseudomatchings.

Extended endocrine therapy beyond 5 years is of major concern to ER + breast cancer survivors. However, it might be unsuitable to apply routinely used genomic tests designed for early recurrence risks to distant recurrence within 10 years in extended treatment context. These tests initially aim at high sensitivities with Type I errors much higher than Type II. Having lower positive predictive values (PPVs), these tests can bring many false positives who might not need further treatment options to avoid adversely affecting quality of life. Alternatively, we proposed a top-down approach to the raised issues. We built 149 targeted genes from four genomic tests upon 381 ER-positive node-negative patients with either metastasis free beyond 10 years (n = 202) or metastasis within 10 years (n = 179). By a basket of SVM-wrapped length-constraint feature selection (LCFS), we discovered four genomic SVMs that traded off Type I against Type II errors. Two independent cohorts were used to validate disease outcome predictions. A 36-gene SVM balanced sensitivities with PPVs at good levels: 74% vs 76% on 10-fold cross validation (n = 347) and 75% vs 71% on a test set (n = 34). Neither Oncotype DX RS (cutoff = 18, 31, 60.97) nor PAM50 ROR-S (cutoff = 29, 53, 61.18) could. Independent cohorts showed the 36-gene SVM predicted disease free survival (n = 136, HR = 2.59; 95% CI, 1.4-4.8) and disease specific survival (n = 127, HR = 4.06; 95% CI, 1.63-10.11) better than RS (DFS, HR = 2.15; DSS, HR = 3.86) and ROR-S (DFS, HR = 2.29; DSS, HR = 2.76). The case study demonstrated how we identified a genomic test to balance Type I against Type II errors for risk stratification. The top-down approach centered around the LCFS-metaheuristics basket is a generic methodology for clinical decision-making and quality of life using targeted profiling data where the number of dimensions (p) is smaller than the number of samples (n).

Energy-efficient multicast routing algorithms have predominantly focused on wireless or ad-hoc mobile networks. However, since the turn of the century the need for energy efficient approaches to routing in wired networks has been steadily rising. In this paper, we introduce an objective function for multicast routing in wired networks taking energy consumption into consideration. A number of hybrid Genetic and Simulated Annealing based algorithms have been shown to be able to find solutions to the multicast routing problem superior to solely Genetic or Simulated Annealing based algorithms. Our approach adapts a population-based hybrid algorithm for routing multiple simultaneous multicast requests. We examine the performance in terms of energy efficiency against solutions found by Logarithmic Simulated Annealing and Genetic based algorithms. We find that the hybrid approach, in 87% of instances, was able to find superior solutions, and in 96% of instances, solutions superior or equal to the best solution given by either Simulated Annealing or Genetic approaches. The extent of the improvement however varied greatly from a few hundred to within ten Joules, with the improvement on the best solution ranging from 5.6 to 531.5 Joules.

Cancer classification through high-throughput gene expression profiles has been widely used in biomedical research. Most recently, we portrayed a multivariate method for large scale gene selection based on information theorem with a central issue of feature interdependence and validated its effectiveness using a colon cancer benchmark. The completed research work now contributes to this article. Firstly, we have refined the method and proposed a complete framework to select a gene signature for a certain disease phenotype prediction under high-throughput technologies. The framework has then been applied to a brain cancer gene expression profiles derived from Affymetrix Human Genome U95Av2 Array, where the interrogated genes are six times more than that in the previous studied colon cancer data set. Three information theorem based filters were used for comparison. Our experimental result shows that the framework outperformed them in terms of classification performance with three performance measures. Additionally, to demonstrate how effectively feature interdependence has been tackled in the framework, two sets of enrichment analysis have also been performed. The results also show that more statistically significant gene sets and regulatory interactions could be found in our gene signature. Therefore, this framework could be promising for high-throughput gene selection around gene synergy.

MOTIVATION: We study microRNA (miRNA) bindings to metastable RNA secondary structures close to minimum free energy conformations in the context of single nucleotide polymorphisms (SNPs) and messenger RNA (mRNA) concentration levels, i.e. whether features of miRNA bindings to metastable conformations could provide additional information supporting the differences in expression levels of the two sequences defined by a SNP. In our study, the instances [mRNA/3'UTR; SNP; miRNA] were selected based on strong expression level analyses, SNP locations within binding regions and the computationally feasible identification of metastable conformations. RESULTS: We identified 14 basic cases [mRNA; SNP; miRNA] of 3' UTR-lengths ranging from 124 up to 1078 nt reported in recent literature, and we analyzed the number, structure and miRNA binding to metastable conformations within an energy offset above mfe conformations. For each of the 14 instances, the miRNA binding characteristics are determined by the corresponding STarMir output. Among the different parameters we introduced and analyzed, we found that three of them, related to the average depth and average opening energy of metastable conformations, may provide supporting information for a stronger separation between miRNA bindings to the two alleles defined by a given SNP. AVAILABILITY AND IMPLEMENTATION: At http://kks.inf.kcl.ac.uk/MSbind.html the MSbind tool is available for calculating features of metastable conformations determined by putative miRNA binding sites.

BACKGROUND: The protein folding problem remains one of the most challenging open problems in computational biology. Simplified models in terms of lattice structure and energy function have been proposed to ease the computational hardness of this optimization problem. Heuristic search algorithms and constraint programming are two common techniques to approach this problem. The present study introduces a novel hybrid approach to simulate the protein folding problem using constraint programming technique integrated within local search. RESULTS: Using the face-centered-cubic lattice model and 20 amino acid pairwise interactions energy function for the protein folding problem, a constraint programming technique has been applied to generate the neighbourhood conformations that are to be used in generic local search procedure. Experiments have been conducted for a few small and medium sized proteins. Results have been compared with both pure constraint programming approach and local search using well-established local move set. Substantial improvements have been observed in terms of final energy values within acceptable runtime using the hybrid approach. CONCLUSION: Constraint programming approaches usually provide optimal results but become slow as the problem size grows. Local search approaches are usually faster but do not guarantee optimal solutions and tend to stuck in local minima. The encouraging results obtained on the small proteins show that these two approaches can be combined efficiently to obtain better quality solutions within acceptable time. It also encourages future researchers on adopting hybrid techniques to solve other hard optimization problems.

The paper aims at tight upper bounds on the size of pattern classification circuits that can be used for a priori parameter settings in a machine learning context. The upper bounds relate the circuit size S(C) to n L := [log 2 m L ], where m L is the number of training samples. In particular, we show that there exist unbounded fan-in threshold circuits with less than (a) S R cc := 2·√2 n L + 3 gates for unbounded depth, (b) S L cc := 34.8 · √2 n L + 14 · n L − 11 · log 2 n L + 2 gates for small bounded depth, where in both cases all m L samples are classified correctly. We note that the upper bounds do not depend on the length n of input (sample) vectors. Since n L << n in real-world problem settings, the upper bounds return values that are suitable for practical applications. We provide experimental evidence that the circuit size estimations work well on a number of pattern classification tasks. As a result, we formulate the conjecture that [1.25 · S R cc or [0.07 · S L cc ] gates are sufficient to achieve a high generalization rate of bounded-depth classification circuits.

Abstract—Over the past ten years, methods from statisti-cal physics have provided a deeper inside into the average complexity of hard combinatorial problems, culminating in a rigorous proof for the asymptotic behaviour of the k-SAT phase transition threshold by Achlioptas and Peres in 2004. On the other hand, when dealing with individual instances of hard problems, gathering information about specific properties of instances in a pre-processing phase might be helpful for an appropriate adjustment of local search-based procedures. In the present paper, we address both issues in the context of landscapes induced by k-SAT instances: Firstly, we utilize a sampling method devised by Garnier and Kallel in 2002 for approximations of the number of local maxima in land-scapes generated by individual k-SAT instances and a simple neighbourhood relation. The objective function is given by the number of satisfied clauses. Secondly, we outline a method for obtaining upper bounds for the average number of local maxima in k-SAT instances which indicates some kind of phase transition for the neighbourhood-specific ratio m/n = Θ(2k/k). I.

This poster paper addresses the problem of choosing sets of software components to combine in component-based software engineering. It formulates both ranking and selection problems as feature subset selection problems to which search based software engineering can be applied. We will consider selection and ranking of elements from a set of software components from the component base of a large telecommunications organisation.

This paper addresses the problem of determining the next set of releases in the course of software evolution. It formulates both ranking and selection of candidate software components as a series of feature subset selection problems to which search based software engineering can be applied. The approach is automated using greedy and simulated annealing algorithms and evaluated using a set of software components from the component base of a large telecommunications organization. The results are compared to those obtained by a panel of (human) experts. The results show that the two automated approaches convincingly outperform the expert judgment approach

We present a pattern classification method that combines the classical Perceptron algorithm with simulated annealing. For a sample set S of n-dimensional patterns labeled as positive and negative, our algorithm computes threshold circuits of small depth where the linear threshold functions of the first layer are calculated by simulated annealing with the logarithmic cooling schedule c(k) = Γ(k)/ ln (k + 2). The parameter Γ depends on the sample set and changes in time, and the neighborhood relation is determined by the Perceptron algorithm. We apply the approach to the recognition of focal liver tumours. From 400 positive (focal liver tumour) and 400 negative (normal liver tissue) examples a depth-six threshold circuit is calculated. The examples are of size n = 14161 = 119 × 119 and they are presented in the DICOM format. On test sets of 100 + 100 examples (disjoint from the learning set) we obtain a correct classification of more than 98%.