BACKGROUND: Detecting uncertain and negative assertions is essential in most BioMedical Text Mining tasks where, in general, the aim is to derive factual knowledge from textual data. This article reports on a corpus annotation project that has produced a freely available resource for research on handling negation and uncertainty in biomedical texts (we call this corpus the BioScope corpus). RESULTS: The corpus consists of three parts, namely medical free texts, biological full papers and biological scientific abstracts. The dataset contains annotations at the token level for negative and speculative keywords and at the sentence level for their linguistic scope. The annotation process was carried out by two independent linguist annotators and a chief linguist--also responsible for setting up the annotation guidelines --who resolved cases where the annotators disagreed. The resulting corpus consists of more than 20.000 sentences that were considered for annotation and over 10% of them actually contain one (or more) linguistic annotation suggesting negation or uncertainty. CONCLUSION: Statistics are reported on corpus size, ambiguity levels and the consistency of annotations. The corpus is accessible for academic purposes and is free of charge. Apart from the intended goal of serving as a common resource for the training, testing and comparing of biomedical Natural Language Processing systems, the corpus is also a good resource for the linguistic analysis of scientific and clinical texts.

In this article we present a theoretical analysis of the online Sum-of-Squares algorithm ( SS ) for bin packing along with several new variants. SS is applicable to any instance of bin packing in which the bin capacity B and item sizes s ( a ) are integral (or can be scaled to be so), and runs in time O ( nB ). It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, SS also has sublinear expected waste. For any discrete distribution where the optimal expected waste is bounded, SS has expected waste at most O (log n ). We also discuss several interesting variants on SS , including a randomized O ( nB log B )-time online algorithm SS * whose expected behavior is essentially optimal for all discrete distributions. Algorithm SS * depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution F , just what is the growth rate for the optimal expected waste.

Owing to their relative simplicity and wide range of applications, static slices are specifically proposed for software maintenance and program understanding. Unfortunately, in many cases static slices are overly conservative and therefore too large to supply useful information to the software maintainer. Dynamic slicing methods can produce more precise results, but only for one test case. In this paper we introduce the concept of union slices (the union of dynamic slices for many test cases) and suggest using a combination of static and union slices. This way the size of program parts that need to be investigated can be reduced by concentrating on the most important parts first. We performed a series of experiments with our experimental implementation on three medium size C programs. Our initial results suggest that union slices are in most cases far smaller than static slices, and that the growth rate of union slices (by adding more test cases) significantly declines after several representative executions of the program.

In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing, introduced and studied experimentally in [8], along with several new variants.SS is applicable to any instance of bin packing in which the bin capacity B and item sizes s(a) are integral (or can be scaled to be so), and runs in time O(nB).It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, SS also has sublinear expected waste.For any discrete distribution where the optimal expected waste is bounded, SS has expected waste at most O(log n).In addition, we present a randomized O(nB log B)-time on-line algorithm SS*, based on SS, whose expected behavior is essentially optimal for all discrete distributions.Algorithm SS* also depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution F, just what is the growth rate for the optimal expected waste.An off-line randomized variant SS** performs well in a worst-case sense: For any list L of integer-sized items to be packed into bins of a fixed size B, the expected number of bins used by SS** is at most OPT(L) + ~.

A generalized version of the string matching algorithm by Wagner and Fischer (1974) is proposed. It is based on a parametrization of the edit cost. We assume constant cost for any delete and insert operation, but the cost for replacing a symbol is given as a parameter /spl tau/. For any two strings A and B, our algorithm computes their edit distance in terms of the parameter /spl tau/. We give the new algorithm, study some of its properties, and discuss potential applications to pattern recognition.>

String matching is a useful concept in pattern recognition that is constantly receiving attention from both theoretical and practical points of view. The authors propose a generalized version of the string matching algorithm by Wagner and Fischer (1974). It is based on a parametrization of the edit cost. The authors assume constant cost for any delete and insert operation, but the cost for replacing a symbol is given as a parameter r. For any two given strings A and B, the algorithm computes the edit distance of A and B in terms of the parameter r. The authors give the new algorithm and study some of its properties. Its time complexity is O(n/sup 2/.m), where n and m are the lengths of the two strings to be compared and n>

A feature vector is introduced for measuring pattern similarities between two strings. The following problem is solved: Given strings A and B and a distance d, let the distance between A and B be D=d(A,B). Then, for r=0, 1, 2 . . . D determine substrings I and J of A and B, respectively, such that the sum of the length of I and J is maximum and the distance between I and J is maximum and the distance between I and J is equal to r, i.e. d(I,J)=r. The algorithm used to solve this problem has a time complexity of O(n/sup 2/m/sup 2/).>

A new algorithm is proposed to determine the type-II restriction endonucleases' recognition site knowing the digested DNA sequence and fragment lengths in an actual case. The algorithm is implemented for the Commodore 64 microcomputer.