OpenRaiser/Intern-Atlas huggingface dataset:
Inferring Chemical Reaction Patterns Using Rule Composition in Graph Grammars
Venue: arXiv cs.DM 2012
Year: 2012

Modeling molecules as undirected graphs and chemical reactions as graph rewriting operations is a natural and convenient approach tom odeling chemistry. Graph grammar rules are most naturally employed to model elementary reactions like merging, splitting, and isomerisation of molecules. It is often convenient, in particular in the analysis of larger systems, to summarize several subsequent reactions into a single composite chemical reaction. We use a generic approach for composing graph grammar rules to define a chemically useful rule compositions. We iteratively apply these rule compositions to elementary transformations in order to automatically infer complex transformation patterns. This is useful for instance to understand the net effect of complex catalytic cycles such as the Formose reaction. The automatically inferred graph grammar rule is a generic representative that also covers the overall reaction pattern of the Formose cycle, namely two carbonyl groups that can react with a bound glycolaldehyde to a second glycolaldehyde. Rule composition also can be used to study polymerization reactions as well as more complicated iterative reaction schemes. Terpenes and the polyketides, for instance, form two naturally occurring classes of compounds of utmost pharmaceutical interest that can be understood as "generalized polymers" consisting of five-carbon (isoprene) and two-carbon units, respectively.
Multiplicative Updates in Coordination Games and the Theory of Evolution
Venue: arXiv cs.GT 2012
Year: 2012

We study the population genetics of Evolution in the important special case of weak selection, in which all fitness values are assumed to be close to one another. We show that in this regime natural selection is tantamount to the multiplicative updates game dynamics in a coordination game between genes. Importantly, the utility maximized in this game, as well as the amount by which each allele is boosted, is precisely the allele's mixability, or average fitness, a quantity recently proposed in [1] as a novel concept that is crucial in understanding natural selection under sex, thus providing a rigorous demonstration of that insight. We also prove that the equilibria in two-person coordination games can have large supports, and thus genetic diversity does not suffer much at equilibrium. Establishing large supports involves answering through a novel technique the following question: what is the probability that for a random square matrix A both systems Ax = 1 and A^T y = 1 have positive solutions? Both the question and the technique may be of broader interest. [1] A. Livnat, C. Papadimitriou, J. Dushoff, and M.W. Feldman. A mixability theory for the role of sex in evolution. Proceedings of the National Academy of Sciences, 105(50):19803-19808, 2008.
Anonymous Communication in Peer-to-Peer Networks for providing more Privacy and Security
Venue: arXiv cs.NI 2012
Year: 2012

One of the most important issues in peer-to-peer networks is anonymity. The major anonymity for peer-to-peer users concerned with the users' identities and actions which can be revealed by any other members. There are many approaches proposed to provide anonymous peer-to-peer communications. An intruder can get information about the content of the data, the sender's and receiver's identities. Anonymous approaches are designed with the following three goals: to protect the identity of provider, to protect the identity of requester and to protect the contents of transferred data between them. This article presents a new peer-to-peer approach to achieve anonymity between a requester and a provider in peer-to-peer networks with trusted servers called suppernode so that the provider will not be able to identify the requester and no other peers can identify the two communicating parties with certainty. This article shows that the proposed algorithm improved reliability and has more security. This algorithm, based on onion routing and randomization, protects transferring data against traffic analysis attack. The ultimate goal of this anonymous communications algorithm is to allow a requester to communicate with a provider in such a manner that nobody can determine the requester's identity and the content of transferred data.
Cache Replacement Policies for Cooperative Caching in Mobile Ad hoc Networks
Venue: arXiv cs.NI 2012
Year: 2012

Cooperative caching is a technique used in mobile ad hoc networks to improve the efficiency of information access by reducing the access latency and bandwidth usage. Cache replacement policy plays a significant role in response time reduction by selecting suitable subset of items for eviction from the cache. In this paper we have made a review of the existing cache replacement algorithms proposed for cooperative caching in ad hoc networks. We made an attempt to classify existing replacement policies for ad hoc networks based on the replacement decision taken. In addition, this paper suggests some alternative techniques for cache replacement. Finally, the paper concludes with a discussion on future research directions.
A Note on Efficient Computation of All Abelian Periods in a String
Venue: arXiv cs.DS 2012
Year: 2012

We derive a simple efficient algorithm for Abelian periods knowing all Abelian squares in a string. An efficient algorithm for the latter problem was given by Cummings and Smyth in 1997. By the way we show an alternative algorithm for Abelian squares. We also obtain a linear time algorithm finding all `long' Abelian periods. The aim of the paper is a (new) reduction of the problem of all Abelian periods to that of (already solved) all Abelian squares which provides new insight into both connected problems.
Anthropomorphic User Interface Feedback in a Sewing Context and Affordances
Venue: arXiv cs.HC 2012
Year: 2012

The aim of the authors' research is to gain better insights into the effectiveness and user satisfaction of anthropomorphism at the user interface. Therefore, this paper presents a between users experiment and the results in the context of anthropomorphism at the user interface and the giving of instruction for learning sewing stitches. Two experimental conditions were used, where the information for learning sewing stitches was the same. However the manner of presentation was varied. Therefore one condition was anthropomorphic and the other was non-anthropomorphic. Also the work is closely linked with Hartson's theory of affordances applied to user interfaces. The results suggest that facilitation of the affordances in an anthropomorphic user interface lead to statistically significant results in terms of effectiveness and user satisfaction in the sewing context. Further some violation of the affordances leads to an interface being less usable in terms of effectiveness and user satisfaction.
Leveraging Subjective Human Annotation for Clustering Historic Newspaper Articles
Venue: arXiv cs.IR 2012
Year: 2012

The New York Public Library is participating in the Chronicling America initiative to develop an online searchable database of historically significant newspaper articles. Microfilm copies of the newspapers are scanned and high resolution Optical Character Recognition (OCR) software is run on them. The text from the OCR provides a wealth of data and opinion for researchers and historians. However, categorization of articles provided by the OCR engine is rudimentary and a large number of the articles are labeled editorial without further grouping. Manually sorting articles into fine-grained categories is time consuming if not impossible given the size of the corpus. This paper studies techniques for automatic categorization of newspaper articles so as to enhance search and retrieval on the archive. We explore unsupervised (e.g. KMeans) and semi-supervised (e.g. constrained clustering) learning algorithms to develop article categorization schemes geared towards the needs of end-users. A pilot study was designed to understand whether there was unanimous agreement amongst patrons regarding how articles can be categorized. It was found that the task was very subjective and consequently automated algorithms that could deal with subjective labels were used. While the small scale pilot study was extremely helpful in designing machine learning algorithms, a much larger system needs to be developed to collect annotations from users of the archive. The "BODHI" system currently being developed is a step in that direction, allowing users to correct wrongly scanned OCR and providing keywords and tags for newspaper articles used frequently. On successful implementation of the beta version of this system, we hope that it can be integrated with existing software being developed for the Chronicling America project.
An Evaluation of Popular Copy-Move Forgery Detection Approaches
Venue: arXiv cs.CV 2012
Year: 2012

A copy-move forgery is created by copying and pasting content within the same image, and potentially post-processing it. In recent years, the detection of copy-move forgeries has become one of the most actively researched topics in blind image forensics. A considerable number of different algorithms have been proposed focusing on different types of postprocessed copies. In this paper, we aim to answer which copy-move forgery detection algorithms and processing steps (e.g., matching, filtering, outlier detection, affine transformation estimation) perform best in various postprocessing scenarios. The focus of our analysis is to evaluate the performance of previously proposed feature sets. We achieve this by casting existing algorithms in a common pipeline. In this paper, we examined the 15 most prominent feature sets. We analyzed the detection performance on a per-image basis and on a per-pixel basis. We created a challenging real-world copy-move dataset, and a software framework for systematic image manipulation. Experiments show, that the keypoint-based features SIFT and SURF, as well as the block-based DCT, DWT, KPCA, PCA and Zernike features perform very well. These feature sets exhibit the best robustness against various noise sources and downsampling, while reliably identifying the copied regions.
On the genericity properties in networked estimation: Topology design and sensor placement
Venue: arXiv cs.MA 2012
Year: 2012

In this paper, we consider networked estimation of linear, discrete-time dynamical systems monitored by a network of agents. In order to minimize the power requirement at the (possibly, battery-operated) agents, we require that the agents can exchange information with their neighbors only \emph{once per dynamical system time-step}; in contrast to consensus-based estimation where the agents exchange information until they reach a consensus. It can be verified that with this restriction on information exchange, measurement fusion alone results in an unbounded estimation error at every such agent that does not have an observable set of measurements in its neighborhood. To over come this challenge, state-estimate fusion has been proposed to recover the system observability. However, we show that adding state-estimate fusion may not recover observability when the system matrix is structured-rank ($S$-rank) deficient. In this context, we characterize the state-estimate fusion and measurement fusion under both full $S$-rank and $S$-rank deficient system matrices.
Synthetic Aperture Radar Imaging and Motion Estimation via Robust Principle Component Analysis
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of synthetic aperture radar (SAR) imaging and motion estimation of complex scenes. By complex we mean scenes with multiple targets, stationary and in motion. We use the usual setup with one moving antenna emitting and receiving signals. We address two challenges: (1) the detection of moving targets in the complex scene and (2) the separation of the echoes from the stationary targets and those from the moving targets. Such separation allows high resolution imaging of the stationary scene and motion estimation with the echoes from the moving targets alone. We show that the robust principal component analysis (PCA) method which decomposes a matrix in two parts, one low rank and one sparse, can be used for motion detection and data separation. The matrix that is decomposed is the pulse and range compressed SAR data indexed by two discrete time variables: the slow time, which parametrizes the location of the antenna, and the fast time, which parametrizes the echoes received between successive emissions from the antenna. We present an analysis of the rank of the data matrix to motivate the use of the robust PCA method. We also show with numerical simulations that successful data separation with robust PCA requires proper data windowing. Results of motion estimation and imaging with the separated data are presented, as well.
WiMAX or Wi-Fi: The Best Suited Candidate Technology for Building Wireless Access Infrastructure
Venue: arXiv cs.NI 2012
Year: 2012

This paper presents a description of the existing wireless technology Wi-Fi and WiMAX, and try to compare Wi-Fi (IEEE 802.11) and WiMAX (IEEE 802.16), with respect to which technology provides a better solution to build a wireless access infrastructure. Each technology is evaluated based on some key characteristics. This paper concludes with a statement of, which technology will be the best and most cost effective solution to end user.
General Midpoint Subdivision
Venue: arXiv cs.GR 2012
Year: 2012

In this paper, we introduce two generalizations of midpoint subdivision and analyze the smoothness of the resulting subdivision surfaces at regular and extraordinary points. The smoothing operators used in midpoint and mid-edge subdivision connect the midpoints of adjacent faces or of adjacent edges, respectively. An arbitrary combination of these two operators and the refinement operator that splits each face with m vertices into m quadrilateral subfaces forms a general midpoint subdivision operator. We analyze the smoothness of the resulting subdivision surfaces by estimating the norm of a special second order difference scheme and by using established methods for analyzing midpoint subdivision. The surfaces are smooth at their regular points and they are also smooth at extraordinary points for a certain subclass of general midpoint subdivision schemes. Generalizing the smoothing rules of non general midpoint subdivision schemes around extraordinary and regular vertices or faces results in a class of subdivision schemes, which includes the Catmull-Clark algorithm with restricted parameters. We call these subdivision schemes generalized Catmull-Clark schemes and we analyze their smoothness properties.
State distributions and minimum relative entropy noise sequences in uncertain stochastic systems: the discrete time case
Venue: arXiv cs.SY 2012
Year: 2012

The paper is concerned with a dissipativity theory and robust performance analysis of discrete-time stochastic systems driven by a statistically uncertain random noise. The uncertainty is quantified by the conditional relative entropy of the actual probability law of the noise with respect to a nominal product measure corresponding to a white noise sequence. We discuss a balance equation, dissipation inequality and superadditivity property for the corresponding conditional relative entropy supply as a function of time. The problem of minimizing the supply required to drive the system between given state distributions over a specified time horizon is considered. Such variational problems, involving entropy and probabilistic boundary conditions, are known in the literature as Schroedinger bridge problems. In application to control systems, this minimum required conditional relative entropy supply characterizes the robustness of the system with respect to an uncertain noise. We obtain a dynamic programming Bellman equation for the minimum required conditional relative entropy supply and establish a Markov property of the worst-case noise with respect to the state of the system. For multivariable linear systems with a Gaussian white noise sequence as the nominal noise model and Gaussian initial and terminal state distributions, the minimum required supply is obtained using an algebraic Riccati equation which admits a closed-form solution. We propose a computable robustness index for such systems in the framework of an entropy theoretic formulation of uncertainty and provide an example to illustrate this approach.
Modelling the effect of gap junctions on tissue-level cardiac electrophysiology
Venue: arXiv cs.CE 2012
Year: 2012

When modelling tissue-level cardiac electrophysiology, continuum approximations to the discrete cell-level equations are used to maintain computational tractability. One of the most commonly used models is represented by the bidomain equations, the derivation of which relies on a homogenisation technique to construct a suitable approximation to the discrete model. This derivation does not explicitly account for the presence of gap junctions connecting one cell to another. It has been seen experimentally [Rohr, Cardiovasc. Res. 2004] that these gap junctions have a marked effect on the propagation of the action potential, specifically as the upstroke of the wave passes through the gap junction. In this paper we explicitly include gap junctions in a both a 2D discrete model of cardiac electrophysiology, and the corresponding continuum model, on a simplified cell geometry. Using these models we compare the results of simulations using both continuum and discrete systems. We see that the form of the action potential as it passes through gap junctions cannot be replicated using a continuum model, and that the underlying propagation speed of the action potential ceases to match up between models when gap junctions are introduced. In addition, the results of the discrete simulations match the characteristics of those shown in Rohr 2004. From this, we suggest that a hybrid model -- a discrete system following the upstroke of the action potential, and a continuum system elsewhere -- may give a more accurate description of cardiac electrophysiology.
A Model of the Cellular Iron Homeostasis Network Using Semi-Formal Methods for Parameter Space Exploration
Venue: arXiv cs.CE 2012
Year: 2012

This paper presents a novel framework for the modeling of biological networks. It makes use of recent tools analyzing the robust satisfaction of properties of (hybrid) dynamical systems. The main challenge of this approach as applied to biological systems is to get access to the relevant parameter sets despite gaps in the available knowledge. An initial estimate of useful parameters was sought by formalizing the known behavior of the biological network in the STL logic using the tool Breach. Then, once a set of parameter values consistent with known biological properties was found, we tried to locally expand it into the largest possible valid region. We applied this methodology in an effort to model and better understand the complex network regulating iron homeostasis in mammalian cells. This system plays an important role in many biological functions, including erythropoiesis, resistance against infections, and proliferation of cancer cells.
Hybrid Automata and ε-Analysis on a Neural Oscillator
Venue: arXiv cs.CE 2012
Year: 2012

In this paper we propose a hybrid model of a neural oscillator, obtained by partially discretizing a well-known continuous model. Our construction points out that in this case the standard techniques, based on replacing sigmoids with step functions, is not satisfactory. Then, we study the hybrid model through both symbolic methods and approximation techniques. This last analysis, in particular, allows us to show the differences between the considered approximation approaches. Finally, we focus on approximations via epsilon-semantics, proving how these can be computed in practice.
On Expressing and Monitoring Oscillatory Dynamics
Venue: arXiv cs.CE 2012
Year: 2012

To express temporal properties of dense-time real-valued signals, the Signal Temporal Logic (STL) has been defined by Maler et al. The work presented a monitoring algorithm deciding the satisfiability of STL formulae on finite discrete samples of continuous signals. The logic has been used to express and analyse biological systems, but it is not expressive enough to sufficiently distinguish oscillatory properties important in biology. In this paper we define the extended logic STL* in which STL is augmented with a signal-value freezing operator allowing us to express (and distinguish) detailed properties of biological oscillations. The logic is supported by a monitoring algorithm prototyped in Matlab. The monitoring procedure of STL* is evaluated on a biologically-relevant case study.
Optimization of Bloom Filter Parameters for Practical Bloom Filter Based Epidemic Forwarding in DTNs
Venue: arXiv cs.NI 2012
Year: 2012

Epidemic forwarding has been proposed as a forwarding technique to achieve opportunistic communication in Delay Tolerant Networks. Even if this technique is well known and widely referred, one has to first deal with several practical problems before using it. In particular, in order to manage the redundancy and to avoid useless transmissions, it has been proposed to ask nodes to exchange information about the buffer content prior to sending information. While Bloom filter has been proposed to transport the buffer content information, up to our knowledge no real evaluation has been provided to study the tradeoff that exists in practice. In this paper we describe an implementation of an epidemic forwarding scheme using Bloom filters. Then we propose some strategies for Bloom filter management based on windowing and describe implementation tradeoffs. By simulating our proposed strategies in ns-3 both with random waypoint mobility and realistic mobility traces coming from San Francisco taxicabs, we show that our proposed strategies alleviate the challenge of using epidemic forwarding in DTNs.
Upper bounds for the formula size of the majority function
Venue: arXiv cs.DS 2012
Year: 2012

It is shown that the counting function of n Boolean variables can be implemented with the formulae of size O(n^3.06) over the basis of all 2-input Boolean functions and of size O(n^4.54) over the standard basis. The same bounds follow for the complexity of any threshold symmetric function of n variables and particularly for the majority function. Any bit of the product of binary numbers of length n can be computed by formulae of size O(n^4.06) or O(n^5.54) depending on basis. Incidentally the bounds O(n^3.23) and O(n^4.82) on the formula size of any symmetric function of n variables with respect to the basis are obtained.
Degrees of Freedom for MIMO Two-Way X Relay Channel
Venue: arXiv cs.IT 2012
Year: 2012

We study the degrees of freedom (DOF) of a multiple-input multiple-output (MIMO) two-way X relay channel, where there are two groups of source nodes and one relay node, each equipped with multiple antennas, and each of the two source nodes in one group exchanges independent messages with the two source nodes in the other group via the relay node. It is assumed that every source node is equipped with M antennas while the relay is equipped with N antennas. We first show that the upper bound on the total DOF for this network is 2min{2M,N} and then focus on the case of N \leq 2M so that the DOF is upper bounded by the number of antennas at the relay. By applying signal alignment for network coding and joint transceiver design for interference cancellation, we show that this upper bound can be achieved when N \leq8M/5. We also show that with signal alignment only but no joint transceiver design, the upper bound is achievable when N\leq4M/3. Simulation results are provided to corroborate the theoretical results and to demonstrate the performance of the proposed scheme in the finite signal-to-noise ratio regime.