OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Algorithms for de novo Assembly of Alternative Splicing Events from RNA-seq Data
Venue: arXiv cs.DS 2014
Year: 2014

In this thesis, we address the problem of identifying and quantifying variants (alternative splicing and genomic polymorphism) in RNA-seq data when no reference genome is available, without assembling the full transcripts. Based on the fundamental idea that each variant corresponds to a recognizable pattern, a bubble, in a de Bruijn graph constructed from the RNA-seq reads, we propose a general model for all variants in such graphs. We then introduce an exact method, called KisSplice, to extract alternative splicing events. Finally, we show that it enables to identify more correct events than general purpose transcriptome assemblers. In order to deal with ever-increasing volumes of NGS data, we put an extra effort to make KisSplice as scalable as possible. First, to improve its running time, we propose a new polynomial delay algorithm to enumerate bubbles. We show that it is several orders of magnitude faster than previous approaches. Then, to reduce its memory consumption, we propose a new compact way to build and represent a de Bruijn graph. We show that our approach uses 30% to 40% less memory than the state of the art, with an insignificant impact on the construction time. Additionally, we apply the same techniques developed to list bubbles in two classical problems: cycle enumeration and the K-shortest paths problem. We give the first optimal algorithm to list cycles in undirected graphs, improving over Johnson's algorithm. This is the first improvement to this problem in almost 40 years. We then consider a different parameterization of the classical K-shortest (simple) paths problem: instead of bounding the number of st-paths, we bound the weight of the st-paths. We present new algorithms with the same time complexities but using exponentially less memory than previous approaches.
Improved Frame Level Features and SVM Supervectors Approach for the Recogniton of Emotional States from Speech: Application to categorical and dimensional states
Venue: arXiv cs.CL 2014
Year: 2014

The purpose of speech emotion recognition system is to classify speakers utterances into different emotional states such as disgust, boredom, sadness, neutral and happiness. Speech features that are commonly used in speech emotion recognition rely on global utterance level prosodic features. In our work, we evaluate the impact of frame level feature extraction. The speech samples are from Berlin emotional database and the features extracted from these utterances are energy, different variant of mel frequency cepstrum coefficients, velocity and acceleration features.
Random Logic Programs: Linear Model
Venue: arXiv cs.AI 2014
Year: 2014

This paper proposes a model, the linear model, for randomly generating logic programs with low density of rules and investigates statistical properties of such random logic programs. It is mathematically shown that the average number of answer sets for a random program converges to a constant when the number of atoms approaches infinity. Several experimental results are also reported, which justify the suitability of the linear model. It is also experimentally shown that, under this model, the size distribution of answer sets for random programs tends to a normal distribution when the number of atoms is sufficiently large.
PDF/A-3u as an archival format for Accessible mathematics
Venue: arXiv cs.IR 2014
Year: 2014

Including LaTeX source of mathematical expressions, within the PDF document of a text-book or research paper, has definite benefits regarding `Accessibility' considerations. Here we describe three ways in which this can be done, fully compatibly with international standards ISO 32000, ISO 19005-3, and the forthcoming ISO 32000-2 (PDF 2.0). Two methods use embedded files, also known as `attachments', holding information in either LaTeX or MathML formats, but use different PDF structures to relate these attachments to regions of the document window. One uses structure, so is applicable to a fully `Tagged PDF' context, while the other uses /AF tagging of the relevant content. The third method requires no tagging at all, instead including the source coding as the /ActualText replacement of a so-called `fake space'. Information provided this way is extracted via simple Select/Copy/Paste actions, and is available to existing screen-reading software and assistive technologies.
Composite Likelihood Estimation for Restricted Boltzmann machines
Venue: arXiv cs.LG 2014
Year: 2014

Learning the parameters of graphical models using the maximum likelihood estimation is generally hard which requires an approximation. Maximum composite likelihood estimations are statistical approximations of the maximum likelihood estimation which are higher-order generalizations of the maximum pseudo-likelihood estimation. In this paper, we propose a composite likelihood method and investigate its property. Furthermore, we apply our composite likelihood method to restricted Boltzmann machines.
Optimal strongly conflict-avoiding codes of even length and weight three
Venue: arXiv cs.IT 2014
Year: 2014

Strongly conflict-avoiding codes (SCACs) are employed in a slot-asynchronous multiple-access collision channel without feedback to guarantee that each active user can send at least one packet successfully in the worst case within a fixed period of time. Assume all users are assigned distinct codewords, the number of codewords in an SCAC is equal to the number of potential users that can be supported. SCACs have different combinatorial structure compared with conflict-avoiding codes (CACs) due to additional collisions incurred by partially overlapped transmissions. In this paper, we establish upper bounds on the size of SCACs of even length and weight three. Furthermore, it is shown that some optimal CACs can be used to construct optimal SCACs of weight three.
The Expressive Power of Modal Dependence Logic
Venue: arXiv cs.LO 2014
Year: 2014

We study the expressive power of various modal logics with team semantics. We show that exactly the properties of teams that are downward closed and closed under team k-bisimulation, for some finite k, are definable in modal logic extended with intuitionistic disjunction. Furthermore, we show that the expressive power of modal logic with intuitionistic disjunction and extended modal dependence logic coincide. Finally we establish that any translation from extended modal dependence logic into modal logic with intuitionistic disjunction increases the size of some formulas exponentially.
A Lower Bound of $2^n$ Conditional Branches for Boolean Satisfiability on Post Machines
Venue: arXiv cs.CC 2014
Year: 2014

We establish a lower bound of $2^n$ conditional branches for deciding the satisfiability of the conjunction of any two Boolean formulas from a set called a full representation of Boolean functions of $n$ variables - a set containing a Boolean formula to represent each Boolean function of $n$ variables. The contradiction proof first assumes that there exists a Post machine (Post's Formulation 1) that correctly decides the satisfiability of the conjunction of any two Boolean formulas from such a set by following an execution path that includes fewer than $2^n$ conditional branches. By using multiple runs of this Post machine, with one run for each Boolean function of $n$ variables, the proof derives a contradiction by showing that this Post machine is unable to correctly decide the satisfiability of the conjunction of at least one pair of Boolean formulas from a full representation of $n$-variable Boolean functions if the machine executes fewer than $2^n$ conditional branches. This lower bound of $2^n$ conditional branches holds for any full representation of Boolean functions of $n$ variables, even if a full representation consists solely of minimized Boolean formulas derived by a Boolean minimization method. We discuss why the lower bound fails to hold for satisfiability of certain restricted formulas, such as 2CNF satisfiability, XOR-SAT, and HORN-SAT. We also relate the lower bound to 3CNF satisfiability. The lower bound does not depend on sequentiality of access to the boxes in the symbol space and will hold even if a machine is capable of non-sequential access.
A Quantitative Neural Coding Model of Sensory Memory
Venue: arXiv cs.NE 2014
Year: 2014

The coding mechanism of sensory memory on the neuron scale is one of the most important questions in neuroscience. We have put forward a quantitative neural network model, which is self organized, self similar, and self adaptive, just like an ecosystem following Darwin theory. According to this model, neural coding is a mult to one mapping from objects to neurons. And the whole cerebrum is a real-time statistical Turing Machine, with powerful representing and learning ability. This model can reconcile some important disputations, such as: temporal coding versus rate based coding, grandmother cell versus population coding, and decay theory versus interference theory. And it has also provided explanations for some key questions such as memory consolidation, episodic memory, consciousness, and sentiment. Philosophical significance is indicated at last.
$ N^4 $-Fields: Neural Network Nearest Neighbor Fields for Image Transforms
Venue: arXiv cs.CV 2014
Year: 2014

We propose a new architecture for difficult image processing operations, such as natural edge detection or thin object segmentation. The architecture is based on a simple combination of convolutional neural networks with the nearest neighbor search. We focus our attention on the situations when the desired image transformation is too hard for a neural network to learn explicitly. We show that in such situations, the use of the nearest neighbor search on top of the network output allows to improve the results considerably and to account for the underfitting effect during the neural network training. The approach is validated on three challenging benchmarks, where the performance of the proposed architecture matches or exceeds the state-of-the-art.
Support vector machine classification of dimensionally reduced structural MRI images for dementia
Venue: arXiv cs.CV 2014
Year: 2014

We classify very-mild to moderate dementia in patients (CDR ranging from 0 to 2) using a support vector machine classifier acting on dimensionally reduced feature set derived from MRI brain scans of the 416 subjects available in the OASIS-Brains dataset. We use image segmentation and principal component analysis to reduce the dimensionality of the data. Our resulting feature set contains 11 features for each subject. Performance of the classifiers is evaluated using 10-fold cross-validation. Using linear and (gaussian) kernels, we obtain a training classification accuracy of 86.4% (90.1%), test accuracy of 85.0% (85.7%), test precision of 68.7% (68.5%), test recall of 68.0% (74.0%), and test Matthews correlation coefficient of 0.594 (0.616).
SROIQsigma is decidable
Venue: arXiv cs.LO 2014
Year: 2014

We consider a dynamic extension of the description logic $\mathcal{SROIQ}$. This means that interpretations could evolve thanks to some actions such as addition and/or deletion of an element (respectively, a pair of elements) of a concept (respectively, of a role). The obtained logic is called $\mathcal{SROIQ}$ with explicit substitutions and is written $\mathcal{SROIQ^σ}$. Substitution is not treated as meta-operation that is carried out immediately, but the operation of substitution may be delayed, so that sub-formulae of $\mathcal{SROIQ}^σ$ are of the form $Φσ$, where $Φ$ is a $\mathcal{SROIQ}$ formula and $σ$ is a substitution which encodes changes of concepts and roles. In this paper, we particularly prove that the satisfiability problem of $\mathcal{SROIQ}^σ$ is decidable.
Managing LTL properties in Event-B refinement
Venue: arXiv cs.SE 2014
Year: 2014

Refinement in Event-B supports the development of systems via proof based step-wise refinement of events. This refinement approach ensures safety properties are preserved, but additional reasoning is required in order to establish liveness and fairness properties. In this paper we present results which allow a closer integration of two formal methods, Event-B and linear temporal logic. In particular we show how a class of temporal logic properties can carry through a refinement chain of machines. Refinement steps can include introduction of new events, event renaming and event splitting. We also identify a general liveness property that holds for the events of the initial system of a refinement chain. The approach will aid developers in enabling them to verify linear temporal logic properties at early stages of a development, knowing they will be preserved at later stages. We illustrate the results via a simple case study.
Clash of the Lambdas
Venue: arXiv cs.PL 2014
Year: 2014

The introduction of lambdas in Java 8 completes the slate of statically-typed, mainstream languages with both object-oriented and functional features. The main motivation for lambdas in Java has been to facilitate stream-based declarative APIs, and, therefore, easier parallelism. In this paper, we evaluate the performance impact of lambda abstraction employed in stream processing, for a variety of high-level languages that run on a virtual machine (C#, F#, Java and Scala) and runtime platforms (JVM on Linux and Windows, .NET CLR for Windows, Mono for Linux). Furthermore, we evaluate the performance gain that two optimizing libraries (ScalaBlitz and LinqOptimizer) can offer for C#, F# and Scala. Our study is based on small-scale throughput-benchmarking, with significant care to isolate different factors, consult experts on the systems involved, and identify causes and opportunities. We find that Java exhibits high implementation maturity, which is a dominant factor in benchmarks. At the same time, optimizing frameworks can be highly effective for common query patterns.
Causality Networks
Venue: arXiv cs.LG 2014
Year: 2014

While correlation measures are used to discern statistical relationships between observed variables in almost all branches of data-driven scientific inquiry, what we are really interested in is the existence of causal dependence. Designing an efficient causality test, that may be carried out in the absence of restrictive pre-suppositions on the underlying dynamical structure of the data at hand, is non-trivial. Nevertheless, ability to computationally infer statistical prima facie evidence of causal dependence may yield a far more discriminative tool for data analysis compared to the calculation of simple correlations. In the present work, we present a new non-parametric test of Granger causality for quantized or symbolic data streams generated by ergodic stationary sources. In contrast to state-of-art binary tests, our approach makes precise and computes the degree of causal dependence between data streams, without making any restrictive assumptions, linearity or otherwise. Additionally, without any a priori imposition of specific dynamical structure, we infer explicit generative models of causal cross-dependence, which may be then used for prediction. These explicit models are represented as generalized probabilistic automata, referred to crossed automata, and are shown to be sufficient to capture a fairly general class of causal dependence. The proposed algorithms are computationally efficient in the PAC sense; $i.e.$, we find good models of cross-dependence with high probability, with polynomial run-times and sample complexities. The theoretical results are applied to weekly search-frequency data from Google Trends API for a chosen set of socially "charged" keywords. The causality network inferred from this dataset reveals, quite expectedly, the causal importance of certain keywords. It is also illustrated that correlation analysis fails to gather such insight.
Face Identification with Second-Order Pooling
Venue: arXiv cs.CV 2014
Year: 2014

Automatic face recognition has received significant performance improvement by developing specialised facial image representations. On the other hand, generic object recognition has rarely been applied to the face recognition. Spatial pyramid pooling of features encoded by an over-complete dictionary has been the key component of many state-of-the-art image classification systems. Inspired by its success, in this work we develop a new face image representation method inspired by the second-order pooling in Carreira et al. [1], which was originally proposed for image segmentation. The proposed method differs from the previous methods in that, we encode the densely extracted local patches by a small-size dictionary; and the facial image signatures are obtained by pooling the second-order statistics of the encoded features. We show the importance of pooling on encoded features, which is bypassed by the original second-order pooling method to avoid the high computational cost. Equipped with a simple linear classifier, the proposed method outperforms the state-of-the-art face identification performance by large margins. For example, on the LFW databases, the proposed method performs better than the previous best by around 13% accuracy.
A Model-Based Approach to Impact Analysis Using Model Differencing
Venue: arXiv cs.SE 2014
Year: 2014

Impact analysis is concerned with the identification of consequences of changes and is therefore an important activity for software evolution. In modelbased software development, models are core artifacts, which are often used to generate essential parts of a software system. Changes to a model can thus substantially affect different artifacts of a software system. In this paper, we propose a modelbased approach to impact analysis, in which explicit impact rules can be specified in a domain specific language (DSL). These impact rules define consequences of designated UML class diagram changes on software artifacts and the need of dependent activities such as data evolution. The UML class diagram changes are identified automatically using model differencing. The advantage of using explicit impact rules is that they enable the formalization of knowledge about a product. By explicitly defining this knowledge, it is possible to create a checklist with hints about development steps that are (potentially) necessary to manage the evolution. To validate the feasibility of our approach, we provide results of a case study.
From Citation count to Argumentation count: a new metric to indicate the usefulness of an article
Venue: arXiv cs.IR 2014
Year: 2014

Citation count is a quantifiable measure to indicate the number of times an article is cited by other articles. It is believed that if an article is cited often then it must be an important or influential article; however, there is no guarantee that the most cited articles are good in quality. In this paper, the author suggests argumentation count, a new metric for citation analysis. The proposed metric, argumentation count is a triplet of quantities for each concept of an article that helps in providing a quantifiable measure about the usefulness of an article.
Pattern-wave model of brain. Mechanisms of information processing, memory organization
Venue: arXiv cs.AI 2014
Year: 2014

The structure of the axon-dendrite connections of neurons of the brain creates a rich spatial structure in which provided various combinations of signals surrounding neurons. Structure of dendritic trees and shape of dendritic spines allow repeatedly increase combinatorial component through cross synapses influence neighboring neurons. In this paper it is shown that the diffuse spreading of neurotransmitters allows neurons to detect and remember significant set of environmental activity patterns. As a core element fixation described extrasynaptic metabotropic receptive clusters. The described mechanism leads to the appearance of wave processes, based on the propagation of the front-line areas of spontaneous activity. In the proposed model, any compact pattern of neural activity is seen as a source emitting a diverging wave endogenous spikes. It is shown that the spike pattern of the wave front is strictly unique and uniquely defined pattern that started the wave. The propagation of waves with a unique pattern allows anywhere in nature undergoing brain wave patterns there to judge the whole brain processes information. In these assumptions naturally described mechanism of projection information between regions of the cortex. Performed computer simulations show the high effectiveness of such information model.
On tight bounds for binary frameproof codes
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study $w$-frameproof codes, which are equivalent to $\{1,w\}$-separating hash families. Our main results concern binary codes, which are defined over an alphabet of two symbols. For all $w \geq 3$, and for $w+1 \leq N \leq 3w$, we show that an $SHF(N; n,2, \{1,w \})$ exists only if $n \leq N$, and an $SHF(N; N,2, \{1,w \})$ must be a permutation matrix of degree $N$.
Communicating and resolving entity references
Venue: arXiv cs.AI 2014
Year: 2014

Statements about entities occur everywhere, from newspapers and web pages to structured databases. Correlating references to entities across systems that use different identifiers or names for them is a widespread problem. In this paper, we show how shared knowledge between systems can be used to solve this problem. We present "reference by description", a formal model for resolving references. We provide some results on the conditions under which a randomly chosen entity in one system can, with high probability, be mapped to the same entity in a different system.
Analysis of Coverage Region for MIMO Relay Network with Multiple Cooperative DF-Relays
Venue: arXiv cs.IT 2014
Year: 2014

We study and analyze coverage region in MIMO communication systems for a multiple-relay network with decode-and-forward (DF) strategy at the relays. Assuming that there is a line-of-sight (LOS) propagation environment for source-relay channels and channel state information is available at receivers (CSIR), we consider the objective of maximizing coverage region for a given transmission rate and show numerically the significant effect of propagation environment on capacity bounds, optimal relay location and coverage region. Also, we study the situation in which two adjacent relays cooperate in transmission signals to the destination and show analytically that the coverage region is extended compared to noncooperative scenario.
Maximum Multipath Routing Throughput in Multirate Wireless Mesh Networks
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we consider the problem of finding the maximum routing throughput between any pair of nodes in an arbitrary multirate wireless mesh network (WMN) using multiple paths. Multipath routing is an efficient technique to maximize routing throughput in WMN, however maximizing multipath routing throughput is a NP-complete problem due to the shared medium for electromagnetic wave transmission in wireless channel, inducing collision-free scheduling as part of the optimization problem. In this work, we first provide problem formulation that incorporates collision-free schedule, and then based on this formulation we design an algorithm with search pruning that jointly optimizes paths and transmission schedule. Though suboptimal, compared to the known optimal single path flow, we demonstrate that an efficient multipath routing scheme can increase the routing throughput by up to 100% for simple WMNs.