Summary For determining distances (fetch lengths) from points to polygons in a two‐dimensional Euclidean plane, cell‐based algorithms provide a simple and effective solution. They divide the input area into a grid of cells that cover the area. The objects are stored into the appropriate cells, and the resulting structure is used for solving the problem. When the input objects are distributed unevenly or the cell size is small, most of the cells may be empty. The representation is then called sparse. In the method proposed in this work, each cell contains information about its distance to the nonempty cells. It is then possible to skip over several empty cells at a time without memory accesses. A cell‐based fetch length algorithm is implemented on a graphics processing unit (GPU). Because control flow divergence reduces its performance, several methods to reduce the divergence are studied. While many of the explicit attempts turn out to be unsuccessful, sorting of the input data and sparse traversal are observed to greatly improve performance: compared with the initial GPU implementation, up to 45‐fold speedup is reached. The speed improvement is greatest when the map is very sparse and the points are given in a random order. Copyright © 2015 John Wiley & Sons, Ltd.

The use of inter-process communication can yield many benefits for event-driven desktop software. However, inter-process communication (IPC) research has traditionally been focused on calculation-oriented distributed computing. This article shows that existing IPC solutions are a poor fit for the constraints imposed by event-driven programming. Our novel solution is built on top of the D-Bus system, which enjoys increased practical usage, but is still scantily researched. We focus on efficient handling of asynchronous D-Bus method calls, in a fashion similar to how Hypertext Transfer Protocol requests are treated in Asynchronous JavaScript and XML Web applications. This is supplemented with two design patterns that simplify processing of results for many kinds of asynchronous operations in event-driven software, besides just D-Bus calls. Our approach is shown to be more appropriate for event-driven applications than traditional remote procedure call systems in aspects as diverse as interactivity, threading complexity and electrical power usage. Copyright © 2013 John Wiley & Sons, Ltd.

Most forest inventories based on the use of remote-sensing data produce the required species-specific information by fusing data from different sources (e.g., Light Detection And Ranging (LiDAR) and spectral data). We tested an active hyperspectral LiDAR instrument in a laboratory measurement of spruce and pine trees to find out whether these species could be separated by means of combined range and reflectance measurements. An analysis focused on those pulses that had penetrated through the foliage improved the classification accuracies of the species with otherwise highly similar reflectance properties. Based on a careful selection of the classification features, 18 spruce and pine trees could be classified with accuracies of 78%-97% using independent training and validation data acquired by separate scans. The results denote the potential of using active hyperspectral measurements for species classification.

BACKGROUND: Caspases are a family of proteases that have central functions in programmed cell death (apoptosis) and inflammation. Caspases mediate their effects through aspartate-specific cleavage of their target proteins, and at present almost 400 caspase substrates are known. There are several methods developed to predict caspase cleavage sites from individual proteins, but currently none of them can be used to predict caspase cleavage sites from multiple proteins or entire proteomes, or to use several classifiers in combination. The possibility to create a database from predicted caspase cleavage products for the whole genome could significantly aid in identifying novel caspase targets from tandem mass spectrometry based proteomic experiments. RESULTS: Three different pattern recognition classifiers were developed for predicting caspase cleavage sites from protein sequences. Evaluation of the classifiers with quality measures indicated that all of the three classifiers performed well in predicting caspase cleavage sites, and when combining different classifiers the accuracy increased further. A new tool, Pripper, was developed to utilize the classifiers and predict the caspase cut sites from an arbitrary number of input sequences. A database was constructed with the developed tool, and it was used to identify caspase target proteins from tandem mass spectrometry data from two different proteomic experiments. Both known caspase cleavage products as well as novel cleavage products were identified using the database demonstrating the usefulness of the tool. Pripper is not restricted to predicting only caspase cut sites, but it gives the possibility to scan protein sequences for any given motif(s) and predict cut sites once a suitable cut site prediction model for any other protease has been developed. Pripper is freely available and can be downloaded from http://users.utu.fi/mijopi/Pripper. CONCLUSIONS: We have developed Pripper, a tool for reading an arbitrary number of proteins in FASTA format, predicting their caspase cleavage sites and outputting the cleaved sequences to a new FASTA format sequence file. We show that Pripper is a valuable tool in identifying novel caspase target proteins from modern proteomics experiments.

BACKGROUND: Missing values frequently pose problems in gene expression microarray experiments as they can hinder downstream analysis of the datasets. While several missing value imputation approaches are available to the microarray users and new ones are constantly being developed, there is no general consensus on how to choose between the different methods since their performance seems to vary drastically depending on the dataset being used. RESULTS: We show that this discrepancy can mostly be attributed to the way in which imputation methods have traditionally been developed and evaluated. By comparing a number of advanced imputation methods on recent microarray datasets, we show that even when there are marked differences in the measurement-level imputation accuracies across the datasets, these differences become negligible when the methods are evaluated in terms of how well they can reproduce the original gene clusters or their biological interpretations. Regardless of the evaluation approach, however, imputation always gave better results than ignoring missing data points or replacing them with zeros or average values, emphasizing the continued importance of using more advanced imputation methods. CONCLUSION: The results demonstrate that, while missing values are still severely complicating microarray data analysis, their impact on the discovery of biologically meaningful gene groups can - up to a certain degree - be reduced by using readily available and relatively fast imputation methods, such as the Bayesian Principal Components Algorithm (BPCA).

Software houses sell their products by transferring usage licenses of various software components to the customers. Depending on the kind of software, there are several different license types that allow controlled access of services. The two most popular types are the fixed license, which gives access rights for an identified workstation, and the floating license, which restricts the number of simultaneous users to a certain bound. The latter of these types is advantageous when the users do not demand full-time services and occasional lack of access is bearable. The problem of deciding the number of floating licenses is studied in the present paper. Based on the expected usage profile of the software, we calculate the minimal number of licenses that guarantees that the customers get service better than a given lower bound. The problem is studied by using certain queuing models, known as the Erlang toss system, the Erlang delay system, and the Engset model. None of these analytic models consider, however, the transient period that we analyze by means of simulation and by the so-called modified offered load approximation. We also give simple formulas presenting how the number of software licenses needed to keep the probability of nonaccess below a given blocking level grows as a function of the offered load, which is the proportion of the time used in the case that all requests were successful. Results of the study may be used for setting license prices and for determining the proper number of licenses.

In optical character recognition (OCR), visible characters appearing as images (i.e. on paper) are recognized as symbolic characters and stored in a computer's memory or similar device. The purpose of this work is to find whether current mobile cameraphones are able to run OCR software without relying on dedicated hardware or facilities provided by the network. This article describes a simple OCR system that was implemented in Symbian C++ to be run on a stock Nokia 6630 cameraphone. The system is limited to recognizing English capital letters printed in black, against a white background. The opportunities and hardships related to bringing OCR to run on mobile platforms having image capturing capability are also discussed in more general terms

UNLABELLED: Peptide identification by tandem mass spectrometry is an important tool in proteomic research. Powerful identification programs exist, such as SEQUEST, ProICAT and Mascot, which can relate experimental spectra to the theoretical ones derived from protein databases, thus removing much of the manual input needed in the identification process. However, the time-consuming validation of the peptide identifications is still the bottleneck of many proteomic studies. One way to further streamline this process is to remove those spectra that are unlikely to provide a confident or valid peptide identification, and in this way to reduce the labour from the validation phase. RESULTS: We propose a prefiltering scheme for evaluating the quality of spectra before the database search. The spectra are classified into two classes: spectra which contain valuable information for peptide identification and spectra that are not derived from peptides or contain insufficient information for interpretation. The different spectral features developed for the classification are tested on a real-life material originating from human lymphoblast samples and on a standard mixture of 9 proteins, both labelled with the ICAT-reagent. The results show that the prefiltering scheme efficiently separates the two spectra classes.

MOTIVATION: Gene expression microarray experiments produce datasets with frequent missing expression values. Accurate estimation of missing values is an important prerequisite for efficient data analysis as many statistical and machine learning techniques either require a complete dataset or their results are significantly dependent on the quality of such estimates. A limitation of the existing estimation methods for microarray data is that they use no external information but the estimation is based solely on the expression data. We hypothesized that utilizing a priori information on functional similarities available from public databases facilitates the missing value estimation. RESULTS: We investigated whether semantic similarity originating from gene ontology (GO) annotations could improve the selection of relevant genes for missing value estimation. The relative contribution of each information source was automatically estimated from the data using an adaptive weight selection procedure. Our experimental results in yeast cDNA microarray datasets indicated that by considering GO information in the k-nearest neighbor algorithm we can enhance its performance considerably, especially when the number of experimental conditions is small and the percentage of missing values is high. The increase of performance was less evident with a more sophisticated estimation method. We conclude that even a small proportion of annotated genes can provide improvements in data quality significant for the eventual interpretation of the microarray experiments. AVAILABILITY: Java and Matlab codes are available on request from the authors. SUPPLEMENTARY MATERIAL: Available online at http://users.utu.fi/jotatu/GOImpute.html.

Classification of harvested apples when predicting their storage potential is an important task. This paper describes how chlorophyll a fluorescence images taken in blue light through a red filter, can be used to classify apples. In such an image, fluorescence appears as a relatively homogenous area broken by a number of small nonfluorescing spots, corresponding to normal corky tissue patches, lenticells, and to damaged areas that lower the quality of the apple. The damaged regions appear more longish, curved or boat-shaped compared to the roundish, regular lenticells. We propose an apple classification method that employs a hierarchy of two neural networks. The first network classifies each spot according to geometrical criteria and the second network uses this information together with global attributes to classify the apple. The system reached 95% accuracy using a test material classified by an expert for "bad" and "good" apples.

Local searching (LS) has proven to be an efficient optimization technique in clustering applications when minimizing stochastic complexity. In this paper, we propose a method for organizing LS in this context - the adaptive multi-operator local search (AMOLS) - and compare its performance to the non-adaptive multi-operator LS (MOLS) method. Both of these methods use several different LS operators to solve problems. MOLS applies the operators randomly, whereas AMOLS adapts itself to favour those operators which manage to improve the results more frequently. We use a large database of binary vectors representing strains of bacteria belonging to the family Enterobacteriaceae and a binary image as our test materials. The results show the benefits of self-adaptation.

This paper presents a hybrid genetic algorithm (GA) with an adaptive application of genetic operators for solving the 3-matching problem (3MP), an NP-complete graph problem. In the 3MP, we search for the partition of a point set into minimal total cost triplets, where the cost of a triplet is the Euclidean length of the minimal spanning tree of the three points. The problem is a special case of grouping and facility location problems. One common problem with GA applied to hard combinatorial optimization, like the 3MP, is to incorporate problem-dependent local search operators into the GA efficiently in order to find high-quality solutions. Small instances of the problem can be solved exactly, but for large problems, we use local optimization. We introduce several general heuristic crossover and local hill-climbing operators, and apply adaptation to choose among them. Our GA combines these operators to form an effective problem solver. It is hybridized as it incorporates local search heuristics, and it is adaptive as the individual recombination/improvement operators are fired according to their online performance. Test results show that this approach gives approximately the same or even slightly better results than our previous, fine tuned GA without adaptation. It is better than a grouping GA for the partitioning considered. The adaptive combination of operators eliminates a large set of parameters, making the method more robust, and it presents a convenient way to build a hybrid problem solver.

This paper introduces a new method for reducing the number of distance calculations in the generalized Lloyd algorithm (GLA), which is a widely used method to construct a codebook in vector quantization. Reduced comparison search detects the activity of the code vectors and utilizes it on the classification of the training vectors. For training vectors whose current code vector has not been modified, we calculate distances only to the active code vectors. A large proportion of the distance calculations can be omitted without sacrificing the optimality of the partition. The new method is included in several fast GLA variants reducing their running times over 50% on average.

This paper introduces a new method for reducing the number of distance calculations in the generalized Lloyd algorithm (GLA), which is a widely used method to construct a codebook in vector quantization. The reduced comparison search detects the activity of the code vectors and utilizes it on the classification of the training vectors. For training vectors whose current code vector has not been modified, we calculate distances only to the active code vectors. A large proportion of the distance calculations can be omitted without sacrificing the optimality of the partition. The new method is included in several fast GLA variants reducing their running times over 50% on average.

We propose a new iterative algorithm for the generation of a codebook in vector quantization. The algorithm starts with an initial codebook that is improved by a sequence of merge and split operations. By merging small neighboring clusters additional resources (code vectors) will be released. These extra code vectors can be reallocated by splitting large clusters. The process can be iterated until no improvement is achieved in the distortion of the codebook. Experimental results show that the proposed method performs well in comparison to other tested methods, including the Generalized Lloyd algorithm (GLA) and two hierarchical methods.

We consider the clustering problem in the case where the distances between elements are metric and both the number of attributes and the number of clusters are large. In this environment the genetic algorithm approach gives high quality clusterings, but at the expense of long running time. Three new and efficient crossover techniques are introduced her. The hybridization of the genetic algorithm and k-means algorithm is discussed.

Block truncation coding (BTC) is a simple and fast image compression algorithm which achieves a constant bit rate of 2.0 bits per pixel. The method is however suboptimal. We propose a modification of BTC in which the compression ratio is improved by coding the quantization data and the bit plane by arithmetic coding with an adaptive modelling scheme. The results compare favorable with other BTC variants. The bit rate for test image Lena is 1.53 bits per pixel with a mean square error of 16.51.>

Block truncation coding (BTC) is a lossy moment preserving quantization method for compressing digital gray-level images. Its advantages are simplicity, fault tolerance, the relatively high compression efficiency and good image quality of the decoded image. Several improvements of the basic method have been recently proposed in the literature. In this survey we will study the basic algorithm and its improvements by dividing it into three separate tasks; performing quantization, coding the quantization data and coding the bit plane. Each phase of the algorithm will be analyzed separately. On the basis of the analysis, a combined BTC algorithm will be proposed and the comparisons to the standard JPEG algorithm will be made.

A two-stage modelling schema to be used together with arithmetic coding is proposed. The main motivation of the work has been the relatively slow operation of arithmetic coding. The new modelling schema reduces the use of arithmetic coding by applying to large white regions global modelling which consumes less time. This composite method works well and with a set of test images it took only about 41% of the time required by a QM-coder. At the same time the loss in compression ratio is only marginal.

An algorithm for multiple sequence comparison was implemented in FORTRAN 77 for VAX/VMS in GCG-compatible format. The MULTICOMP program package includes several procedures with which one query sequence can be compared simultaneously to several DNA, RNA or amino acid sequences. The same technique was also introduced for comparing propensities of secondary structural features, which can be predicted on the basis of amino acid sequences. The technique has been applied to a wide range of sequence and structural analyses.

Two hybrid methods of distributive sort and quicksort are given. The first method sorts an array of records and the second one sorts a linearly linked list in a stable way. The expected running time of the methods is O(n) for n records and for a wide class of distributions of the keys (including all bounded densities with a compact support). For most other distributions the running time is O(n log n), and the worst case time is O(n2). The array version needs extra storage space for n records and approximately n/5 integers. In the linked list version only an array of n/5 pointers is needed. The observed running times of the algorithms compare favourably with those of other efficient bucket sort algorithms.

An algorithm for selection of an unbiased sample out of a set of possible elements without replacement is given. The storage space depends linearly on the sample size; also the running time of the algorithm is low.

Plotting time depends on the sequence of plotter operations. The system described in this paper selects a sequence in which the movements made while the pen is up are reduced. The separate lines forming a picture are temporarily stored in an internal memory area, from which the line nearest the present location of the pen is plotted next and replaced by a new one. The performance of the sequencer was experimentally tested.

A variant of indexed lists is proposed for the management of priority queues: the queue is divided into a number of two-way linked sublists. The adequate sublist can be found by using an address mapping function and a sublist index. The dynamic reorganisation of the sublists and the index is based on the analysis of the statistics collected during the process. The method is tested in the environment of discrete event simulation. Comparison with the previous index and tree algorithms, shows that the new method is advantageous at least for priority queues of moderate size.

The optimum blocking of sequential files is studied. The problem given by Mullin and Stuart (1974) is solved heuristically. The method of Waters (1971) is used for finding a set of initial feasible solutions. The best of these are then improved by making intelligent guesses.