Understanding the nature of many diseases, including cancer, requires locating somatically acquired rearrangements corresponding to large-scale chromosomal aberrations. Computational methods to detect inter-chromosomal rearrangements based on next-generation sequencing platforms face the big challenge of accurately predicting the location of sites spanned by a typically small number of reads, while the entire sample contains hundreds of millions of reads. In this work, we propose a method called TDJD that identifies the location of interchromosomal breakpoints corresponding to a large scale structural variations, in particular translocations and insertions. To reduce the huge dimension of the search space, we split candidate reads that can be potential break points into windows, and represent the windows as a sequence of binary fingerprints. We then search for the location of the breakpoint in the reference genome using Jaccard distance. We use a combination of parallel computing, search using Jaccard distance to solve the exact nearest neighbor problem. The dimensionality reduction takes advantage of an SSE multi-thread architecture to achieve efficient search. We applied our algorithm to identify several reads with breakpoints, including those characterizing the PAX8-PPARγ rearrangement, a frequent modification occurring in follicular thyroid cancer. Our results show that we could identify the breakpoints much faster than the previous method. We also compared our results to several recently published methods, and found that our method is faster than all other compared methods with high accuracy.

Many datasets from real-world applications have very high-dimensional or increasing feature space. It is a new research problem to learn and maintain a classifier to deal with very high dimensionality or streaming features. In this article, we adapt the well-known emerging-pattern--based classification models and propose a semi-streaming approach. For streaming features, it is computationally expensive or even prohibitive to mine long-emerging patterns, and it is nontrivial to integrate emerging-pattern mining with feature selection. We present an online feature selection step, which is capable of selecting and maintaining a pool of effective features from a feature stream. Then, in our offline step, separated from the online step, we periodically compute and update emerging patterns from the pool of selected features from the online step. We evaluate the effectiveness and efficiency of the proposed method using a series of benchmark datasets and a real-world case study on Mars crater detection. Our proposed method yields classification performance comparable to the state-of-art static classification methods. Most important, the proposed method is significantly faster and can efficiently handle datasets with streaming features.

Structural variations (SVs) are deletions, duplications and rearrangements of medium to large segments (>100 base pairs (bp)) of the genome. Such genomic mutations are often described as being the primary cause of many diseases, including cancer. Breakpoint detection using next-generation sequencing (NGS) platforms still remains an open problem since computational methods to detect SVs face the big challenge of accurately predicting the precise location of breakpoints, which are typically spanned by a very small number of reads among millions that are generated during the sequencing process. In this work, we propose a method called TIDE to identify reads from paired-end sequencing data containing inter-chromosomal translocation or insertion breakpoints, which are specific types of SVs involving different chromosomes. To achieve this, we use discordant read pairs to narrow the search space and split prospective breakpoint-spanning reads into windows that are subsequently represented by a sequence of k-mers indexes, which we call fingerprints. We then apply a distance-preserving embedding algorithm to solve the approximate nearest neighbor problem of pairing the most similar fingerprints originated from the sample and reference genome. Experimental results show the efficacy of the method to find reads containing breakpoints characterizing the PAX8-PPARγ rearrangement found in thyroid cancer samples. We also compare our results with the ones provided by two recently published algorithms for detecting structural variation in clinical data.

Building an accurate emerging pattern classifier with a high-dimensional dataset is a challenging issue. The problem becomes even more difficult if the whole feature space is unavailable before learning starts. This paper presents a new technique on mining emerging patterns using streaming feature selection. We model high feature dimensions with streaming features, that is, features arrive and are processed one at a time. As features flow in one by one, we online evaluate each coming feature to determine whether it is useful for mining predictive emerging patterns (EPs) by exploiting the relationship between feature relevance and EP discriminability (the predictive ability of an EP). We employ this relationship to guide an online EP mining process. This new approach can mine EPs from a high-dimensional dataset, even when its entire feature set is unavailable before learning. The experiments on a broad range of datasets validate the effectiveness of the proposed approach against other well-established methods, in terms of predictive accuracy, pattern numbers and running time.

Counting craters is a fundamental task of planetary science because it provides the only tool for measuring relative ages of planetary surfaces. However, advances in surveying craters present in data gathered by planetary probes have not kept up with advances in data collection. One challenge of auto-detecting craters in images is to identify an image's features that discriminate it between craters and other surface objects. The problem of optimal feature selection is known to be NP-hard and the search is computationally intractable. In this paper we propose a wrapper based randomized feature selection method to efficiently select relevant features for crater detection. We design and implement a dynamic programming algorithm to search for a relevant feature subset by removing irrelevant features and minimizing a cost objective function simultaneously. In order to only remove irrelevant features we use Bernoulli Trials to calculate the probability of such a case using the cost function. Our proposed algorithms are empirically evaluated on a large high-resolution Martian image exhibiting a heavily cratered Martian terrain characterized by heterogeneous surface morphology. The experimental results demonstrate that the proposed approach achieves a higher accuracy than other existing randomized approaches to a large extent with less runtime.

We study a discovery framework in which background knowledge on variables and their relations within a discourse area is available in the form of a graphical model. Starting from an initial, hand-crafted or possibly empty graphical model, the network evolves in an interactive process of discovery. We focus on the central step of this process: given a graphical model and a database, we address the problem of finding the most interesting attribute sets. We formalize the concept of interestingness of attribute sets as the divergence between their behavior as observed in the data, and the behavior that can be explained given the current model. We derive an exact algorithm that finds all attribute sets whose interestingness exceeds a given threshold. We then consider the case of a very large network that renders exact inference unfeasible, and a very large database or data stream. We devise an algorithm that efficiently finds the most interesting attribute sets with prescribed approximation bound and confidence probability, even for very large networks and infinite streams. We study the scalability of the methods in controlled experiments; a case-study sheds light on the practical usefulness of the approach.

We propose a novel and efficient solution to the problem of clustering XML documents based on their structure. We use operations on multisets of paths of document trees to define certain metrics on multisets. These metrics are used for clustering real and synthesized XML documents to produce high-quality clusterings.

Eye movements are certainly the most natural and repetitive movement of a human being. The most mundane activity, such as watching television or reading a newspaper, involves this automatic activity which consists of shifting our gaze from one point to another. Identification of the components of eye movements (fixations and saccades) is an essential part in the analysis of visual behavior because these types of movements provide the basic elements used by further investigations of human vision. However, many of the algorithms that detect fixations present a number of problems. In this article, we present a new fixation identification technique that is based on clustering of eye positions, using projections and projection aggregation applied to static pictures. We also present a new method that computes dispersion of eye fixations in videos considering a multiuser environment. To demonstrate the performance and usefulness of our approach we discuss our experimental work with two different applications: on fixed image and video.

Our demo focuses on eye tracking on web, image and video data. We use some state-of-the-art measurements, such as scan path, to determine how the user sees web documents, images and videos. Our approach is characterised by automatic eye/gaze tracking with non intrusive sensors, mainly infrared cameras of web, image and video documents. We analyse eye/gaze tracking concerns spatial regions of static documents (images and web pages) and spatial zones of dynamic documents (video, sequence of web pages hyperlinked). In the context of dynamic documents, the eye/gaze tracking is processed image-per -image in video documents, and page-per-page in web documents. The result is more rough on video, and more accurate on images and hyperlinked web pages. Eye/gaze tracking on video is relatively new and unexplored in the literature.

We study an algorithm for feature selection that clusters attributes using a special metric and then makes use of the dendrogram of the resulting cluster hierarchy to choose the most relevant attributes. The main interest of our technique resides in the improved understanding of the structure of the analyzed data and of the relative importance of the attributes for the selection process.

We present an algorithm/or clustering nominal data that is based on a metric on the set of partitions of a finite set of objects; this metric is defined starting from a lower valuation of the lattice of partitions. The proposed algorithm seeks to determine a clustering partition such that the total distance between this partition and the partitions determined by the attributes of the objects has a local minimum. The resulting clustering is quite stable relative to the ordering of the objects.

The paper presents a method for pruning frequent itemsets based on background knowledge represented by a Bayesian network. The interestingness of an itemset is defined as the absolute difference between its support estimated from data and from the Bayesian network. Efficient algorithms are presented for finding interestingness of a collection of frequent itemsets, and for finding all attribute sets with a given minimum interestingness. Practical usefulness of the algorithms and their efficiency have been verified experimentally.

Mining association rules may generate a large numbers of rules making the results hard to analyze manually. Pasquier et al. have discussed the generation of Guigues-Duquenne-Luxenburger basis (GD-L basis). Using a similar approach, we introduce a new rule of inference and define the notion of association rules cover as a minimal set of rules that are non-redundant with respect to this new rule of inference. Our experimental results (obtained using both synthetic and real data sets) show that our covers are smaller than the GD-L basis and they are computed in time that is comparable to the classic Apriori algorithm for generating rules.

The aim of this article is to present an axiomatization of a generalization of Shannon's entropy starting from partitions of finite sets. The proposed axiomatization defines a family of entropies depending on a real positive parameter that contains as a special case the Havrda-Charvat (1967) entropy, and thus, provides axiomatizations for the Shannon entropy, the Gini index, and for other types of entropy used in classification and data mining.

We propose a formalization of standard database management systems using topos theory. In this treatment, all constructions take place within an ambient topos, which thereby serves as the ‘universe of discourse’. A database schema is defined using objects and morphisms in the ambient topos. A database state for a given schema involves not only the ambient topos but also an internal category within the topos. This approach neatly separates the schema from the state data by placing them in distinct category structures. It is shown that database states can either be regarded syntactically as objects in an external topos or semantically as morphisms in an internal slice category. A number of operations are introduced that correspond to operations used in standard database systems. Extraction selects some of the tables, attributes and domains of a database state. The squeeze operation performs an ‘elimination of duplicates’, which can be combined with extraction to obtain an operation called ‘projection’ in standard relational database systems. A join operation is defined, which generalizes the relational join operation and can be used for the cartesian product and selection operations. Finally, ‘boolean’ operations of intersection, union and difference are introduced and related to the other operations.

The purpose of this correspondence is to survey the literature concerning the iterative properties of multivalued switching functions. These properties are important for the synthesis of switching circuits by cascades of simpler elements. Our presentation evolves around the graphs of transformations of finite sets. We discuss such topics as limitations of the computational capabilities of cascades, the existence of roots of given functions with respect to iteration powers, etc.

We introduce and characterize those Boolean functions (graph functions) which can be regarded as characteristic functions of graphs of other Boolean functions. An algorithm for detecting these functions is also presented. Finally, we discuss the complexity of computing a Boolean function which can be regarded as a graph function.

The solution of the problem of the existence of an analog with periodic-variable structure of a given fixed-structure connected automaton is presented. Using a Boolean approach, a necessary and sufficient condition for the existence of the periodic analog is proven, and an algorithm that enables us to actually find this analog is given. The saving of the memory capacity needed for the construction of a given automaton is the main interest of the existence of a periodic analog.

A class of linear algebraic structures over the set of Boolean functions is presented. Afterwards, from these structures a new one is studied—the right-weak algebra. By using the properties of this algebra, some new results are established about the commutativity of the superposition, the ideals, the annulators, and the properties of the iteration.