Abstract The key property of monotone classifiers is that increasing (decreasing) input values lead to increasing (decreasing) the output value. Preserving monotonicity for a classifier typically requires many constraints to be respected by modelling approaches such as artificial intelligence techniques. The type of constraints strongly depends on the modelling assumptions. Of course, for sophisticated models, such conditions might be very complex. In this study, we present a new family of kernels that we call it Choquet kernels. Henceforth, it allows for employing popular kernel‐based methods, such as support vector machines. Instead of a naïve approach with exponential computational complexity, we propose an equivalent formulation with quadratic time in the number of attributes. Furthermore, because coefficients derived from kernel solutions are not necessarily monotone in the dual form, different approaches are proposed to monotonize coefficients. Finally, experiments illustrate beneficial properties of the Choquet kernels.

CavBase is a database containing information about the three-dimensional geometry and the physicochemical properties of putative protein binding sites. Analyzing CavBase data typically involves computing the similarity of pairs of binding sites. In contrast to sequence alignment, however, a structural comparison of protein binding sites is a computationally challenging problem, making large scale studies difficult or even infeasible. One possibility to overcome this obstacle is to precompute pairwise similarities in an all-against-all comparison, and to make these similarities subsequently accessible to data analysis methods. Pairwise similarities, once being computed, can also be used to equip CavBase with a neighborhood structure. Taking advantage of this structure, methods for problems such as similarity retrieval can be implemented efficiently. In this paper, we tackle the problem of performing an all-against-all comparison using CavBase, consisting of more than 200,000 protein cavities, by means of parallel computation and cloud computing techniques. We present the conceptual design and technical realization of a large-scale study to create a similarity database called CavSimBase. We illustrate how CavSimBase is constructed, is accessed, and is used to answer biological questions by data analysis and similarity retrieval.

Linear data transformations are essential operations in many machine learning algorithms, helping to make such models more flexible or to emphasize certain data directions. In particular for high dimensional data sets linear transformations are not necessarily uniquely determined, though, and alternative parameterizations exist which do not change the mapping of the training data. Thus, regularization is required to make the model robust to noise and more interpretable for the user. In this contribution, we characterize the group of transformations which leave a linear mapping invariant for a given finite data set, and we discuss the consequences on the interpretability of the models. We propose an intuitive regularization mechanism to avoid problems in under-determined configurations, and we test the approach in two machine learning models.

One aspect of self-organizing systems is their desired ability to be self-learning, i.e., to be able to adapt dynamically to conditions in their environment. This quality is awkward especially if it comes to applications in security or safety-sensitive areas. Here a step towards more trustful systems could be taken by providing transparency of the processes of a system. An important means of giving feedback to an operator is the visualization of the internal processes of a system. In this position paper we address the problem of visualizing dynamic processes especially in self-learning systems. We take an existing self-learning system from the field of computer vision as an example from which we derive questions of general interest such as possible options to visualize the flow of information in a dynamic learning system or the visualization of symbolic data. As a side effect the visualization of learning processes may provide a better understanding of underlying principles of learning in general, i.e, also in biological systems. That may also facilitate improved designs of future self-learning systems.

Array-based comparative genomic hybridization (Array-CGH) is an important technology in molecular biology for the detection of DNA copy number polymorphisms between closely related genomes. Hidden Markov Models (HMMs) are popular tools for the analysis of Array-CGH data, but current methods are only based on first-order HMMs having constrained abilities to model spatial dependencies between measurements of closely adjacent chromosomal regions. Here, we develop parsimonious higher-order HMMs enabling the interpolation between a mixture model ignoring spatial dependencies and a higher-order HMM exhaustively modeling spatial dependencies. We apply parsimonious higher-order HMMs to the analysis of Array-CGH data of the accessions C24 and Col-0 of the model plant Arabidopsis thaliana. We compare these models against first-order HMMs and other existing methods using a reference of known deletions and sequence deviations. We find that parsimonious higher-order HMMs clearly improve the identification of these polymorphisms. Moreover, we perform a functional analysis of identified polymorphisms revealing novel details of genomic differences between C24 and Col-0. Additional model evaluations are done on widely considered Array-CGH data of human cell lines indicating that parsimonious HMMs are also well-suited for the analysis of non-plant specific data. All these results indicate that parsimonious higher-order HMMs are useful for Array-CGH analyses. An implementation of parsimonious higher-order HMMs is available as part of the open source Java library Jstacs (www.jstacs.de/index.php/PHHMM).

A variational approach is proposed for the unsupervised assessment of attribute variability of high-dimensional data given a differentiable similarity measure. The key question addressed is how much each data attribute contributes to an optimum transformation of vectors for reaching maximum similarity. This question is formalized and solved in a mathematically rigorous optimization framework for each data pair of interest. Trivially, for the Euclidean metric minimization to zero distance induces highest vector similarity, but in case of the linear Pearson correlation measure the highest similarity of one is desired. During optimization the not necessarily symmetric trajectories between two vectors are recorded and analyzed in terms of attribute changes and line integral. The proposed formalism allows to assess partial covariance and correlation characteristics of data attributes for vectors being compared by any differentiable similarity measure. Its potential for generating alternative and localized views such as for contrast enhancement is demonstrated for hyperspectral images from the remote sensing domain.

MOTIVATION: Changes in gene expression levels play a central role in tumors. Additional information about the distribution of gene expression levels and distances between adjacent genes on chromosomes should be integrated into the analysis of tumor expression profiles. RESULTS: We use a Hidden Markov Model with distance-scaled transition matrices (DSHMM) to incorporate chromosomal distances of adjacent genes on chromosomes into the identification of differentially expressed genes in breast cancer. We train the DSHMM by integrating prior knowledge about potential distributions of expression levels of differentially expressed and unchanged genes in tumor. We find that especially the combination of these data and to a lesser extent the modeling of distances between adjacent genes contribute to a substantial improvement of the identification of differentially expressed genes in comparison to other existing methods. This performance benefit is also supported by the identification of genes well known to be associated with breast cancer. That suggests applications of DSHMMs for screening of other tumor expression profiles. AVAILABILITY: The DSHMM is available as part of the open-source Java library Jstacs (www.jstacs.de/index.php/DSHMM).

Transcription factors are a main component of gene regulation as they activate or repress gene expression by binding to specific binding sites in promoters. The de-novo discovery of transcription factor binding sites in target regions obtained by wet-lab experiments is a challenging problem in computational biology, which has not been fully solved yet. Here, we present a de-novo motif discovery tool called Dispom for finding differentially abundant transcription factor binding sites that models existing positional preferences of binding sites and adjusts the length of the motif in the learning process. Evaluating Dispom, we find that its prediction performance is superior to existing tools for de-novo motif discovery for 18 benchmark data sets with planted binding sites, and for a metazoan compendium based on experimental data from micro-array, ChIP-chip, ChIP-DSL, and DamID as well as Gene Ontology data. Finally, we apply Dispom to find binding sites differentially abundant in promoters of auxin-responsive genes extracted from Arabidopsis thaliana microarray data, and we find a motif that can be interpreted as a refined auxin responsive element predominately positioned in the 250-bp region upstream of the transcription start site. Using an independent data set of auxin-responsive genes, we find in genome-wide predictions that the refined motif is more specific for auxin-responsive genes than the canonical auxin-responsive element. In general, Dispom can be used to find differentially abundant motifs in sequences of any origin. However, the positional distribution learned by Dispom is especially beneficial if all sequences are aligned to some anchor point like the transcription start site in case of promoter sequences. We demonstrate that the combination of searching for differentially abundant motifs and inferring a position distribution from the data is beneficial for de-novo motif discovery. Hence, we make the tool freely available as a component of the open-source Java framework Jstacs and as a stand-alone application at http://www.jstacs.de/index.php/Dispom.

BACKGROUND: The recognition of functional binding sites in genomic DNA remains one of the fundamental challenges of genome research. During the last decades, a plethora of different and well-adapted models has been developed, but only little attention has been payed to the development of different and similarly well-adapted learning principles. Only recently it was noticed that discriminative learning principles can be superior over generative ones in diverse bioinformatics applications, too. RESULTS: Here, we propose a generalization of generative and discriminative learning principles containing the maximum likelihood, maximum a posteriori, maximum conditional likelihood, maximum supervised posterior, generative-discriminative trade-off, and penalized generative-discriminative trade-off learning principles as special cases, and we illustrate its efficacy for the recognition of vertebrate transcription factor binding sites. CONCLUSIONS: We find that the proposed learning principle helps to improve the recognition of transcription factor binding sites, enabling better computational approaches for extracting as much information as possible from valuable wet-lab data. We make all implementations available in the open-source library Jstacs so that this learning principle can be easily applied to other classification problems in the field of genome and epigenome analysis.

MOTIVATION: Array-based analysis of chromatin immunoprecipitation (ChIP-chip) data is a powerful technique for identifying DNA target regions of individual transcription factors. The identification of these target regions from comprehensive promoter array ChIP-chip data is challenging. Here, three approaches for the identification of transcription factor target genes from promoter array ChIP-chip data are presented. We compare (i) a standard log-fold-change analysis (LFC); (ii) a basic method based on a Hidden Markov Model (HMM); and (iii) a new extension of the HMM approach to an HMM with scaled transition matrices (SHMM) that incorporates information about the relative orientation of adjacent gene pairs on DNA. RESULTS: All three methods are applied to different promoter array ChIP-chip datasets of the yeast Saccharomyces cerevisiae and the important model plant Arabidopsis thaliana to compare the prediction of transcription factor target genes. In the context of the yeast cell cycle, common target genes bound by the transcription factors ACE2 and SWI5, and ACE2 and FKH2 are identified and evaluated using the Saccharomyces Genome Database. Regarding A.thaliana, target genes of the seed-specific transcription factor ABI3 are predicted and evaluate based on publicly available gene expression profiles and transient assays performed in the wet laboratory experiments. The application of the novel SHMM to these two different promoter array ChIP-chip datasets leads to an improved identification of transcription factor target genes in comparison to the two standard approaches LFC and HMM. AVAILABILITY: The software of LFC, HMM and SHMM, the ABI3 ChIP-chip dataset, and Supplementary Material can be downloaded from http://dig.ipk-gatersleben.de/SHMMs/ChIPchip/ChIPchip.html.

K-means clustering combines a variety of striking properties because of which it is widely used in applications: training is intuitive and simple, the final classifier represents classes by geometrically meaningful prototypes, and the algorithm is quite powerful compared to more complex alternative clustering algorithms. In this contribution, we focus on extensions which incorporate additional information into the clustering algorithm to achieve a better accuracy: neighborhood cooperation from neural gas, (possibly fuzzy) label information of input data, and general problem-adapted distances instead of the standard Euclidean metric. These extensions can be formulated in a simple general framework by means of a cost function. We demonstrate the ability of these variants on several representative clustering problems from computational biology.

BACKGROUND: Micro- and macroarray technologies help acquire thousands of gene expression patterns covering important biological processes during plant ontogeny. Particularly, faithful visualization methods are beneficial for revealing interesting gene expression patterns and functional relationships of coexpressed genes. Such screening helps to gain deeper insights into regulatory behavior and cellular responses, as will be discussed for expression data of developing barley endosperm tissue. For that purpose, high-throughput multidimensional scaling (HiT-MDS), a recent method for similarity-preserving data embedding, is substantially refined and used for (a) assessing the quality and reliability of centroid gene expression patterns, and for (b) derivation of functional relationships of coexpressed genes of endosperm tissue during barley grain development (0-26 days after flowering). RESULTS: Temporal expression profiles of 4824 genes at 14 time points are faithfully embedded into two-dimensional displays. Thereby, similar shapes of coexpressed genes get closely grouped by a correlation-based similarity measure. As a main result, by using power transformation of correlation terms, a characteristic cloud of points with bipolar sandglass shape is obtained that is inherently connected to expression patterns of pre-storage, intermediate and storage phase of endosperm development. CONCLUSION: The new HiT-MDS-2 method helps to create global views of expression patterns and to validate centroids obtained from clustering programs. Furthermore, functional gene annotation for developing endosperm barley tissue is successfully mapped to the visualization, making easy localization of major centroids of enriched functional categories possible.