OpenRaiser/Intern-Atlas huggingface dataset:
Mixing Energy Models in Genetic Algorithms for On-Lattice Protein Structure Prediction
Venue: arXiv cs.CE 2013
Year: 2013

Protein structure prediction (PSP) is computationally a very challenging problem. The challenge largely comes from the fact that the energy function that needs to be minimised in order to obtain the native structure of a given protein is not clearly known. A high resolution 20x20 energy model could better capture the behaviour of the actual energy function than a low resolution energy model such as hydrophobic polar. However, the fine grained details of the high resolution interaction energy matrix are often not very informative for guiding the search. In contrast, a low resolution energy model could effectively bias the search towards certain promising directions. In this paper, we develop a genetic algorithm that mainly uses a high resolution energy model for protein structure evaluation but uses a low resolution HP energy model in focussing the search towards exploring structures that have hydrophobic cores. We experimentally show that this mixing of energy models leads to significant lower energy structures compared to the state-of-the-art results.
Problems in Systematic Application of Software Metrics and Possible Solution
Venue: arXiv cs.SE 2013
Year: 2013

Systematic application of software metric techniques can lead to significant improvements of the quality of a final software product. However, there is still the evident lack of wider utilization of software metrics techniques and tools due to many reasons. In this paper we investigate some limitations of contemporary software metrics tools and then propose construction of a new tool that would solve some of the problems. We describe the promising prototype, its internal structure, and then focus on its independency of the input language.
Big Data Analytics in Future Internet of Things
Venue: arXiv cs.DC 2013
Year: 2013

Current research on Internet of Things (IoT) mainly focuses on how to enable general objects to see, hear, and smell the physical world for themselves, and make them connected to share the observations. In this paper, we argue that only connected is not enough, beyond that, general objects should have the capability to learn, think, and understand both the physical world by themselves. On the other hand, the future IoT will be highly populated by large numbers of heterogeneous networked embedded devices, which are generating massive or big data in an explosive fashion. Although there is a consensus among almost everyone on the great importance of big data analytics in IoT, to date, limited results, especially the mathematical foundations, are obtained. These practical needs impels us to propose a systematic tutorial on the development of effective algorithms for big data analytics in future IoT, which are grouped into four classes: 1) heterogeneous data processing, 2) nonlinear data processing, 3) high-dimensional data processing, and 4) distributed and parallel data processing. We envision that the presented research is offered as a mere baby step in a potentially fruitful research direction. We hope that this article, with interdisciplinary perspectives, will stimulate more interests in research and development of practical and effective algorithms for specific IoT applications, to enable smart resource allocation, automatic network operation, and intelligent service provisioning.
Finite-type-Dyck shift spaces
Venue: arXiv cs.FL 2013
Year: 2013

We study some basic properties of sofic-Dyck shifts and finite-type-Dyck shifts. We prove that the class of sofic-Dyck shifts is stable under proper conjugacies. We prove a Decomposition Theorem of a proper conjugacy between edge-Dyck shifts into a sequence of Dyck splittings and amalgamations.
On the definition of a general learning system with user-defined operators
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we push forward the idea of machine learning systems whose operators can be modified and fine-tuned for each problem. This allows us to propose a learning paradigm where users can write (or adapt) their operators, according to the problem, data representation and the way the information should be navigated. To achieve this goal, data instances, background knowledge, rules, programs and operators are all written in the same functional language, Erlang. Since changing operators affect how the search space needs to be explored, heuristics are learnt as a result of a decision process based on reinforcement learning where each action is defined as a choice of operator and rule. As a result, the architecture can be seen as a 'system for writing machine learning systems' or to explore new operators where the policy reuse (as a kind of transfer learning) is allowed. States and actions are represented in a Q matrix which is actually a table, from which a supervised model is learnt. This makes it possible to have a more flexible mapping between old and new problems, since we work with an abstraction of rules and actions. We include some examples sharing reuse and the application of the system gErl to IQ problems. In order to evaluate gErl, we will test it against some structured problems: a selection of IQ test tasks and some experiments on some structured prediction problems (list patterns).
Encoding Range Minimum Queries
Venue: arXiv cs.DS 2013
Year: 2013

We consider the problem of encoding range minimum queries (RMQs): given an array A[1..n] of distinct totally ordered values, to pre-process A and create a data structure that can answer the query RMQ(i,j), which returns the index containing the smallest element in A[i..j], without access to the array A at query time. We give a data structure whose space usage is 2n + o(n) bits, which is asymptotically optimal for worst-case data, and answers RMQs in O(1) worst-case time. This matches the previous result of Fischer and Heun [SICOMP, 2011], but is obtained in a more natural way. Furthermore, our result can encode the RMQs of a random array A in 1.919n + o(n) bits in expectation, which is not known to hold for Fischer and Heun's result. We then generalize our result to the encoding range top-2 query (RT2Q) problem, which is like the encoding RMQ problem except that the query RT2Q(i,j) returns the indices of both the smallest and second-smallest elements of A[i..j]. We introduce a data structure using 3.272n+o(n) bits that answers RT2Qs in constant time, and also give lower bounds on the effective entropy} of RT2Q.
CAVDM: Cellular Automata Based Video Cloud Mining Framework for Information Retrieval
Venue: arXiv cs.IR 2013
Year: 2013

Cloud Mining technique can be applied to various documents. Acquisition and storage of video data is an easy task but retrieval of information from video data is a challenging task. So video Cloud Mining plays an important role in efficient video data management for information retrieval. This paper proposes a Cellular Automata based framework for video Cloud Mining to extract the information from video data. This includes developing the technique for shot detection then key frame analysis is considered to compare the frames of each shot to each others to define the relationship between shots. Cellular automata based hierarchical clustering technique is adopted to make a group of similar shots to detect the particular event on some requirement as per user demand.
60 GHz Wireless Link Within Metal Enclosures: Channel Measurements and System Analysis
Venue: arXiv cs.IT 2013
Year: 2013

Wireless channel measurement results for 60 GHz within a closed metal cabinet are provided. A metal cabinet is chosen to emulate the environment within a mechatronic system, which have metal enclosures in general. A frequency domain sounding technique is used to measure the wireless channel for different volumes of the metal enclosure, considering both line-of-sight (LOS) and non-line-of-sight (NLOS) scenarios. Large-scale and small-scale characteristics of the wireless channel are extracted in order to build a comprehensive channel model. In contrast to conventional indoor channels at 60 GHz, the channel in the metal enclosure is highly reflective resulting in a rich scattering environment with a significantly large root-mean-square (RMS) delay spread. Based on the obtained measurement results, the bit error rate (BER) performance is evaluated for a wideband orthogonal frequency division multiplexing (OFDM) system.
3-D position estimation from inertial sensing: minimizing the error from the process of double integration of accelerations
Venue: arXiv cs.RO 2013
Year: 2013

This paper introduces a new approach to 3-D position estimation from acceleration data, i.e., a 3-D motion tracking system having a small size and low-cost magnetic and inertial measurement unit (MIMU) composed by both a digital compass and a gyroscope as interaction technology. A major challenge is to minimize the error caused by the process of double integration of accelerations due to motion (these ones have to be separated from the accelerations due to gravity). Owing to drift error, position estimation cannot be performed with adequate accuracy for periods longer than few seconds. For this reason, we propose a method to detect motion stops and only integrate accelerations in moments of effective hand motion during the demonstration process. The proposed system is validated and evaluated with experiments reporting a common daily life pick-and-place task.
A Notion of Dynamic Interface for Depth-Bounded Object-Oriented Packages
Venue: arXiv cs.SE 2013
Year: 2013

Programmers using software components have to follow protocols that specify when it is legal to call particular methods with particular arguments. For example, one cannot use an iterator over a set once the set has been changed directly or through another iterator. We formalize the notion of dynamic package interfaces (DPI), which generalize state-machine interfaces for single objects, and give an algorithm to statically compute a sound abstraction of a DPI. States of a DPI represent (unbounded) sets of heap configurations and edges represent the effects of method calls on the heap. We introduce a novel heap abstract domain based on depth-bounded systems to deal with potentially unboundedly many objects and the references among them. We have implemented our algorithm and show that it is effective in computing representations of common patterns of package usage, such as relationships between viewer and label, container and iterator, and JDBC statements and cursors.
A New Perspective for Hoare's Logic and Peano's Arithmetic
Venue: arXiv cs.LO 2013
Year: 2013

Hoare's logic is an axiomatic system of proving programs correct, which has been extended to be a separation logic to reason about mutable heap structure. We develop the most fundamental logical structure of strongest postcondition of Hoare's logic in Peano's arithmetic $PA$. Let $p\in L$ and $S$ be any while-program. The arithmetical definability of $\textbf{N}$-computable function $f_S^{\textbf{N}}$ leads to separate $S$ from $SP(p,S)$, which defines the strongest postcondition of $p$ and $S$ over $\textbf{N}$, achieving an equivalent but more meaningful form in $PA$. From the reduction of Hoare's logic to PA, together with well-defined underlying semantics, it follows that Hoare's logic is sound and complete relative to the theory of $PA$, which is different from the relative completeness in the sense of Cook. Finally, we discuss two ways to extend computability from the standard structure to nonstandard models of $PA$.
Data Portraits: Connecting People of Opposing Views
Venue: arXiv cs.HC 2013
Year: 2013

Social networks allow people to connect with each other and have conversations on a wide variety of topics. However, users tend to connect with like-minded people and read agreeable information, a behavior that leads to group polarization. Motivated by this scenario, we study how to take advantage of partial homophily to suggest agreeable content to users authored by people with opposite views on sensitive issues. We introduce a paradigm to present a data portrait of users, in which their characterizing topics are visualized and their corresponding tweets are displayed using an organic design. Among their tweets we inject recommended tweets from other people considering their views on sensitive issues in addition to topical relevance, indirectly motivating connections between dissimilar people. To evaluate our approach, we present a case study on Twitter about a sensitive topic in Chile, where we estimate user stances for regular people and find intermediary topics. We then evaluated our design in a user study. We found that recommending topically relevant content from authors with opposite views in a baseline interface had a negative emotional effect. We saw that our organic visualization design reverts that effect. We also observed significant individual differences linked to evaluation of recommendations. Our results suggest that organic visualization may revert the negative effects of providing potentially sensitive content.
Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph
Venue: arXiv cs.CG 2013
Year: 2013

A standard way to approximate the distance between any two vertices $p$ and $q$ on a mesh is to compute, in the associated graph, a shortest path from $p$ to $q$ that goes through one of $k$ sources, which are well-chosen vertices. Precomputing the distance between each of the $k$ sources to all vertices of the graph yields an efficient computation of approximate distances between any two vertices. One standard method for choosing $k$ sources, which has been used extensively and successfully for isometry-invariant surface processing, is the so-called Farthest Point Sampling (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources. In this paper, we analyze the stretch factor $\mathcal{F}_{FPS}$ of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph. We show that $\mathcal{F}_{FPS}$ can be bounded in terms of the minimal value $\mathcal{F}^*$ of the stretch factor obtained using an optimal placement of $k$ sources as $\mathcal{F}_{FPS}\leq 2 r_e^2 \mathcal{F}^*+ 2 r_e^2 + 8 r_e + 1$, where $r_e$ is the ratio of the lengths of the longest and the shortest edges of the graph. This provides some evidence explaining why farthest point sampling has been used successfully for isometry-invariant shape processing. Furthermore, we show that it is NP-complete to find $k$ sources that minimize the stretch factor.
Large-scale analysis of frequency modulation in birdsong databases
Venue: arXiv cs.SD 2013
Year: 2013

Birdsong often contains large amounts of rapid frequency modulation (FM). It is believed that the use or otherwise of FM is adaptive to the acoustic environment, and also that there are specific social uses of FM such as trills in aggressive territorial encounters. Yet temporal fine detail of FM is often absent or obscured in standard audio signal analysis methods such as Fourier analysis or linear prediction. Hence it is important to consider high resolution signal processing techniques for analysis of FM in bird vocalisations. If such methods can be applied at big data scales, this offers a further advantage as large datasets become available. We introduce methods from the signal processing literature which can go beyond spectrogram representations to analyse the fine modulations present in a signal at very short timescales. Focusing primarily on the genus Phylloscopus, we investigate which of a set of four analysis methods most strongly captures the species signal encoded in birdsong. In order to find tools useful in practical analysis of large databases, we also study the computational time taken by the methods, and their robustness to additive noise and MP3 compression. We find three methods which can robustly represent species-correlated FM attributes, and that the simplest method tested also appears to perform the best. We find that features representing the extremes of FM encode species identity supplementary to that captured in frequency features, whereas bandwidth features do not encode additional information. Large-scale FM analysis can efficiently extract information useful for bioacoustic studies, in addition to measures more commonly used to characterise vocalisations.
Semantic Word Cloud Representations: Hardness and Approximation Algorithms
Venue: arXiv cs.CG 2013
Year: 2013

We study a geometric representation problem, where we are given a set $\cal R$ of axis-aligned rectangles with fixed dimensions and a graph with vertex set $\cal R$. The task is to place the rectangles without overlap such that two rectangles touch if and only if the graph contains an edge between them. We call this problem Contact Representation of Word Networks (CROWN). It formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Here, we represent words by rectangles and semantic relationships by edges. We show that CROWN is strongly NP-hard even restricted trees and weakly NP-hard if restricted stars. We consider the optimization problem Max-CROWN where each adjacency induces a certain profit and the task is to maximize the sum of the profits. For this problem, we present constant-factor approximations for several graph classes, namely stars, trees, planar graphs, and graphs of bounded degree. Finally, we evaluate the algorithms experimentally and show that our best method improves upon the best existing heuristic by 45%.
Universal Generator for Complementary Pairs of Sequences Based on Boolean Functions
Venue: arXiv cs.IT 2013
Year: 2013

We present a general algorithm for generating arbitrary standard complementary pairs of sequences (including binary, polyphase, M-PSK and QAM) of length 2^N using Boolean functions. The algorithm follows our earlier paraunitary algorithm, but does not require matrix multiplications. The algorithm can be easily and efficiently implemented in hardware. As a special case, it reduces to the non-recursive (direct) algorithm for generating binary sequences given by Golay, to the algorithm for generating M-PSK sequences given by Davis and Jedwab (and later improved by Paterson) and to all published algorithms for generating QAM sequences. However the algorithm does not solve the problem of sequence uniqueness (except for the trivial M-PSK case), which must be treated separately for each QAM constellation.
Adaptive Hierarchical Data Aggregation using Compressive Sensing (A-HDACS) for Non-smooth Data Field
Venue: arXiv cs.NI 2013
Year: 2013

Compressive Sensing (CS) has been applied successfully in a wide variety of applications in recent years, including photography, shortwave infrared cameras, optical system research, facial recognition, MRI, etc. In wireless sensor networks (WSNs), significant research work has been pursued to investigate the use of CS to reduce the amount of data communicated, particularly in data aggregation applications and thereby improving energy efficiency. However, most of the previous work in WSN has used CS under the assumption that data field is smooth with negligible white Gaussian noise. In these schemes signal sparsity is estimated globally based on the entire data field, which is then used to determine the CS parameters. In more realistic scenarios, where data field may have regional fluctuations or it is piecewise smooth, existing CS based data aggregation schemes yield poor compression efficiency. In order to take full advantage of CS in WSNs, we propose an Adaptive Hierarchical Data Aggregation using Compressive Sensing (A-HDACS) scheme. The proposed schemes dynamically chooses sparsity values based on signal variations in local regions. We prove that A-HDACS enables more sensor nodes to employ CS compared to the schemes that do not adapt to the changing field. The simulation results also demonstrate the improvement in energy efficiency as well as accurate signal recovery.
Local Rank Modulation for Flash Memories
Venue: arXiv cs.IT 2013
Year: 2013

Local rank modulation scheme was suggested recently for representing information in flash memories in order to overcome drawbacks of rank modulation. For $s\leq t\leq n$ with $s|n$, $(s,t,n)$-LRM scheme is a local rank modulation scheme where the $n$ cells are locally viewed through a sliding window of size $t$ resulting in a sequence of small permutations which requires less comparisons and less distinct values. The distance between two windows equals to $s$. To get the simplest hardware implementation the case of sliding window of size two was presented. Gray codes and constant weight Gray codes were presented in order to exploit the full representational power of the scheme. In this work, a tight upper-bound for cyclic constant weight Gray code in $(1,2,n)$-LRM scheme where the weight equals to $2$ is given. Encoding, decoding and enumeration of $(1,3,n)$-LRM scheme is studied.
On the Structure of Bispecial Sturmian Words
Venue: arXiv cs.FL 2013
Year: 2013

A balanced word is one in which any two factors of the same length contain the same number of each letter of the alphabet up to one. Finite binary balanced words are called Sturmian words. A Sturmian word is bispecial if it can be extended to the left and to the right with both letters remaining a Sturmian word. There is a deep relation between bispecial Sturmian words and Christoffel words, that are the digital approximations of Euclidean segments in the plane. In 1997, J. Berstel and A. de Luca proved that \emph{palindromic} bispecial Sturmian words are precisely the maximal internal factors of \emph{primitive} Christoffel words. We extend this result by showing that bispecial Sturmian words are precisely the maximal internal factors of \emph{all} Christoffel words. Our characterization allows us to give an enumerative formula for bispecial Sturmian words. We also investigate the minimal forbidden words for the language of Sturmian words.
Comparative Study Of Image Edge Detection Algorithms
Venue: arXiv cs.CV 2013
Year: 2013

Since edge detection is in the forefront of image processing for object detection, it is crucial to have a good understanding of edge detection algorithms. The reason for this is that edges form the outline of an object. An edge is the boundary between an object and the background, and indicates the boundary between overlapping objects. This means that if the edges in an image can be identified accurately, all of the objects can be located and basic properties such as area, perimeter, and shape can be measured. Since computer vision involves the identification and classification of objects in an image, edge detection is an essential tool. We tested two edge detectors that use different methods for detecting edges and compared their results under a variety of situations to determine which detector was preferable under different sets of conditions.
Indagini in Deep Inference
Venue: arXiv cs.LO 2013
Year: 2013

Italian master's thesis in Computer Science. It is an overview of the standard tecniques developed in the field of Proof Theory, ending with some results in the new field of Deep Inference, plus an original contribution trying to relate Deep Inference and Process Algebras.