OpenRaiser/Intern-Atlas huggingface dataset:
Faster and More Accurate Sequence Alignment with SNAP
Venue: arXiv cs.DS 2011
Year: 2011

We present the Scalable Nucleotide Alignment Program (SNAP), a new short and long read aligner that is both more accurate (i.e., aligns more reads with fewer errors) and 10-100x faster than state-of-the-art tools such as BWA. Unlike recent aligners based on the Burrows-Wheeler transform, SNAP uses a simple hash index of short seed sequences from the genome, similar to BLAST's. However, SNAP greatly reduces the number and cost of local alignment checks performed through several measures: it uses longer seeds to reduce the false positive locations considered, leverages larger memory capacities to speed index lookup, and excludes most candidate locations without fully computing their edit distance to the read. The result is an algorithm that scales well for reads from one hundred to thousands of bases long and provides a rich error model that can match classes of mutations (e.g., longer indels) that today's fast aligners ignore. We calculate that SNAP can align a dataset with 30x coverage of a human genome in less than an hour for a cost of $2 on Amazon EC2, with higher accuracy than BWA. Finally, we describe ongoing work to further improve SNAP.
Agile Professional Virtual Community Inheritance via Adaptation of Social Protocols
Venue: arXiv cs.CY 2011
Year: 2011

Support for human-to-human interactions over a network is still insufficient, particularly for professional virtual communities (PVC). Among other limitations, adaptation and learning-by-experience capabilities of humans are not taken into account in existing models for collaboration processes in PVC. This paper presents a model for adaptive human collaboration. A key element of this model is the use of negotiation for adaptation of social protocols modelling processes. A second contribution is the proposition of various adaptation propagation strategies as means for continuous management of the PVC inheritance.
Flip-OFDM for Optical Wireless Communications
Venue: arXiv cs.IT 2011
Year: 2011

We consider two uniploar OFDM techniques for optical wireless communications: asymmetric clipped optical OFDM (ACO-OFDM) and Flip-OFDM. Both techniques can be used to compensate multipath distortion effects in optical wireless channels. However, ACO-OFDM has been widely studied in the literature, while the performance of Flip-OFDM has never been investigated. In this paper, we conduct the performance analysis of Flip-OFDM and propose additional modification to the original scheme in order to compare the performance of both techniques. Finally, it is shown by simulation that both techniques have the same performance but different hardware complexities. In particular, for slow fading channels, Flip-OFDM offers 50% saving in hardware complexity over ACO-OFDM at the receiver.
MAPSS, a Multi-Aspect Partner and Service Selection Method
Venue: arXiv cs.SE 2011
Year: 2011

In Service-Oriented Virtual Organization Breeding Environments (SOVOBEs), services performed by people, organizations and information systems are composed in potentially complex business processes performed by a set of partners. In a SOVOBE, the success of a virtual organization depends largely on the partner and service selection process, which determines the composition of services performed by the VO partners. In this paper requirements for a partner and service selection method for SOVOBEs are defined and a novel Multi-Aspect Partner and Service Selection method, MAPSS, is presented. The MAPSS method allows a VO planner to select appropriate services and partners based on their competences and their relations with other services/partners. The MAPSS method relies on a genetic algorithm to select the most appropriate set of partners and services.
Efficient Joint Network-Source Coding for Multiple Terminals with Side Information
Venue: arXiv cs.IT 2011
Year: 2011

Consider the problem of source coding in networks with multiple receiving terminals, each having access to some kind of side information. In this case, standard coding techniques are either prohibitively complex to decode, or require network-source coding separation, resulting in sub-optimal transmission rates. To alleviate this problem, we offer a joint network-source coding scheme based on matrix sparsification at the code design phase, which allows the terminals to use an efficient decoding procedure (syndrome decoding using LDPC), despite the network coding throughout the network. Via a novel relation between matrix sparsification and rate-distortion theory, we give lower and upper bounds on the best achievable sparsification performance. These bounds allow us to analyze our scheme, and, in particular, show that in the limit where all receivers have comparable side information (in terms of conditional entropy), or, equivalently, have weak side information, a vanishing density can be achieved. As a result, efficient decoding is possible at all terminals simultaneously. Simulation results motivate the use of this scheme at non-limiting rates as well.
Modeling Virtual Organization Architecture with the Virtual Organization Breeding Methodology
Venue: arXiv cs.OH 2011
Year: 2011

While Enterprise Architecture Modeling (EAM) methodologies become more and more popular, an EAM methodology tailored to the needs of virtual organizations (VO) is still to be developed. Among the most popular EAM methodologies, TOGAF has been chosen as the basis for a new EAM methodology taking into account characteristics of VOs presented in this paper. In this new methodology, referred as Virtual Organization Breeding Methodology (VOBM), concepts developed within the ECOLEAD project, e.g. the concept of Virtual Breeding Environment (VBE) or the VO creation schema, serve as fundamental elements for development of VOBM. VOBM is a generic methodology that should be adapted to a given VBE. VOBM defines the structure of VBE and VO architectures in a service-oriented environment, as well as an architecture development method for virtual organizations (ADM4VO). Finally, a preliminary set of tools and methods for VOBM is given in this paper.
Agent Development Toolkits
Venue: arXiv cs.MA 2011
Year: 2011

Development of agents as well as their wide usage requires good underlying infrastructure. Literature indicates scarcity of agent development tools in initial years of research which limited the exploitation of this beneficial technology. However, today a wide variety of tools are available, for developing robust infrastructure. This technical note provides a deep overview of such tools and contrasts features provided by them.
Semantic Query Reformulation in Social PDMS
Venue: arXiv cs.DB 2011
Year: 2011

We consider social peer-to-peer data management systems (PDMS), where each peer maintains both semantic mappings between its schema and some acquaintances, and social links with peer friends. In this context, reformulating a query from a peer's schema into other peer's schemas is a hard problem, as it may generate as many rewritings as the set of mappings from that peer to the outside and transitively on, by eventually traversing the entire network. However, not all the obtained rewritings are relevant to a given query. In this paper, we address this problem by inspecting semantic mappings and social links to find only relevant rewritings. We propose a new notion of 'relevance' of a query with respect to a mapping, and, based on this notion, a new semantic query reformulation approach for social PDMS, which achieves great accuracy and flexibility. To find rapidly the most interesting mappings, we combine several techniques: (i) social links are expressed as FOAF (Friend of a Friend) links to characterize peer's friendship and compact mapping summaries are used to obtain mapping descriptions; (ii) local semantic views are special views that contain information about external mappings; and (iii) gossiping techniques improve the search of relevant mappings. Our experimental evaluation, based on a prototype on top of PeerSim and a simulated network demonstrate that our solution yields greater recall, compared to traditional query translation approaches proposed in the literature.
XML Information Retrieval Systems: A Survey
Venue: arXiv cs.IR 2011
Year: 2011

The continuous growth in the XML information repositories has been matched by increasing efforts in development of XML retrieval systems, in large parts aiming at supporting content-oriented XML retrieval. These systems exploit the available structural information, as market up in XML documents, in order to return documents components- the so called XML elements-instead of the complement documents in repose to the user query. In this paper, we provide an overview of the different XML information retrieval systems and classify them according to their storage and query evaluation strategies.
Graph based E-Government web service composition
Venue: arXiv cs.AI 2011
Year: 2011

Nowadays, e-government has emerged as a government policy to improve the quality and efficiency of public administrations. By exploiting the potential of new information and communication technologies, government agencies are providing a wide spectrum of online services. These services are composed of several web services that comply with well defined processes. One of the big challenges is the need to optimize the composition of the elementary web services. In this paper, we present a solution for optimizing the computation effort in web service composition. Our method is based on Graph Theory. We model the semantic relationship between the involved web services through a directed graph. Then, we compute all shortest paths using for the first time, an extended version of the Floyd-Warshall algorithm.
Minimizing the Risk of Architectural Decay by using Architecture-Centric Evolution Process
Venue: arXiv cs.SE 2011
Year: 2011

Software systems endure many noteworthy changes throughout their life-cycle in order to follow the evolution of the problem domains. Generally, the software system architecture cannot follow the rapid evolution of a problem domain which results in the discrepancies between the implemented and designed architecture. Software architecture illustrates a system's structure and global properties and consequently determines not only how the system should be constructed but also leads its evolution. Architecture plays an important role to ensure that a system satisfies its business and mission goals during implementation and evolution. However, the capabilities of the designed architecture may possibly be lost when the implementation does not conform to the designed architecture. Such a loss of consistency causes the risk of architectural decay. The architectural decay can be avoided if architectural changes are made as early as possible. The paper presents the Process Model for Architecture-Centric Evolution which improves the quality of software systems through maintaining consistency between designed architecture and implementation. It also increases architecture awareness of developers which assists in minimizing the risk of architectural decay. In the proposed approach consistency checks are performed before and after the change implementation.
The regular number of a graph
Venue: arXiv cs.DM 2011
Year: 2011

Let $G$ be a simple undirected graph. The regular number of $G$ is defined to be the minimum number of subsets into which the edge set of $G$ can be partitioned so that the subgraph induced by each subset is regular. In this work, we obtain the regular number of some families of graphs and discuss some general bounds on this parameter. Also, some of the lower or upper bounds proved in \cite{Kulli:Janakiram:Iyer:2001} are shown here to hold with equality.
Fast Private Data Release Algorithms for Sparse Queries
Venue: arXiv cs.DS 2011
Year: 2011

We revisit the problem of accurately answering large classes of statistical queries while preserving differential privacy. Previous approaches to this problem have either been very general but have not had run-time polynomial in the size of the database, have applied only to very limited classes of queries, or have relaxed the notion of worst-case error guarantees. In this paper we consider the large class of sparse queries, which take non-zero values on only polynomially many universe elements. We give efficient query release algorithms for this class, in both the interactive and the non-interactive setting. Our algorithms also achieve better accuracy bounds than previous general techniques do when applied to sparse queries: our bounds are independent of the universe size. In fact, even the runtime of our interactive mechanism is independent of the universe size, and so can be implemented in the "infinite universe" model in which no finite universe need be specified by the data curator.
Neuropsychological constraints to human data production on a global scale
Venue: arXiv cs.SI 2011
Year: 2011

Which are the factors underlying human information production on a global level? In order to gain an insight into this question we study a corpus of 252-633 Million publicly available data files on the Internet corresponding to an overall storage volume of 284-675 Terabytes. Analyzing the file size distribution for several distinct data types we find indications that the neuropsychological capacity of the human brain to process and record information may constitute the dominant limiting factor for the overall growth of globally stored information, with real-world economic constraints having only a negligible influence. This supposition draws support from the observation that the files size distributions follow a power law for data without a time component, like images, and a log-normal distribution for multimedia files, for which time is a defining qualia.
Dynamics of Knowledge in DeLP through Argument Theory Change
Venue: arXiv cs.AI 2011
Year: 2011

This article is devoted to the study of methods to change defeasible logic programs (de.l.p.s) which are the knowledge bases used by the Defeasible Logic Programming (DeLP) interpreter. DeLP is an argumentation formalism that allows to reason over potentially inconsistent de.l.p.s. Argument Theory Change (ATC) studies certain aspects of belief revision in order to make them suitable for abstract argumentation systems. In this article, abstract arguments are rendered concrete by using the particular rule-based defeasible logic adopted by DeLP. The objective of our proposal is to define prioritized argument revision operators à la ATC for de.l.p.s, in such a way that the newly inserted argument ends up undefeated after the revision, thus warranting its conclusion. In order to ensure this warrant, the de.l.p. has to be changed in concordance with a minimal change principle. To this end, we discuss different minimal change criteria that could be adopted. Finally, an algorithm is presented, implementing the argument revision operations.
Controls over Spreadsheets for Financial Reporting in Practice
Venue: arXiv cs.CY 2011
Year: 2011

Past studies show that only a small percent of organizations implement and enforce formal rules or informal guidelines for the designing, testing, documenting, using, modifying, sharing and archiving of spreadsheet models. Due to lack of such policies, there has been little research on how companies can effectively govern spreadsheets throughout their life cycle. This paper describes a survey involving 38 participants from the United States, representing companies that were working on compliance with the Sarbanes-Oxley Act of 2002 (SOX) as it relates to spreadsheets for financial reporting. The findings of this survey describe specific controls organizations have implemented to manage spreadsheets for financial reporting throughout the spreadsheet's lifecycle. Our findings indicate that there are problems in all stages of a spreadsheet's life cycle and suggest several important areas for future research.
Breviz: Visualizing Spreadsheets using Dataflow Diagrams
Venue: arXiv cs.SE 2011
Year: 2011

Spreadsheets are used extensively in industry, often for business critical purposes. In previous work we have analyzed the information needs of spreadsheet professionals and addressed their need for support with the transition of a spreadsheet to a colleague with the generation of data flow diagrams. In this paper we describe the application of these data flow diagrams for the purpose of understanding a spreadsheet with three example cases. We furthermore suggest an additional application of the data flow diagrams: the assessment of the quality of the spreadsheet's design.
PARIS: Probabilistic Alignment of Relations, Instances, and Schema
Venue: arXiv cs.DB 2011
Year: 2011

One of the main challenges that the Semantic Web faces is the integration of a growing number of independently designed ontologies. In this work, we present PARIS, an approach for the automatic alignment of ontologies. PARIS aligns not only instances, but also relations and classes. Alignments at the instance level cross-fertilize with alignments at the schema level. Thereby, our system provides a truly holistic solution to the problem of ontology alignment. The heart of the approach is probabilistic, i.e., we measure degrees of matchings based on probability estimates. This allows PARIS to run without any parameter tuning. We demonstrate the efficiency of the algorithm and its precision through extensive experiments. In particular, we obtain a precision of around 90% in experiments with some of the world's largest ontologies.
Nested Canalyzing Functions And Their Average Sensitivities
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, we obtain complete characterization for nested canalyzing functions (NCFs) by obtaining its unique algebraic normal form (polynomial form). We introduce a new concept, LAYER NUMBER for NCF. Based on this, we obtain explicit formulas for the the following important parameters: 1) Number of all the nested canalyzing functions, 2) Number of all the NCFs with given LAYER NUMBER, 3) Hamming weight of any NCF, 4) The activity number of any variable of any NCF, 5) The average sensitivity of any NCF. Based on these formulas, we show the activity number is greater for those variables in out layer and equal in the same layer. We show the average sensitivity attains minimal value when the NCF has only one layer. We also prove the average sensitivity for any NCF (No matter how many variables it has) is between 0 and 2. Hence, theoretically, we show why NCF is stable since a random Boolean function has average sensitivity $\frac{n}{2}$. Finally we conjecture that the NCF attain the maximal average sensitivity if it has the maximal LAYER NUMBER $n-1$. Hence, we guess the uniform upper bound for the average sensitivity of any NCF can be reduced to 4/3 which is tight.
A New Design for Array Multiplier with Trade off in Power and Area
Venue: arXiv cs.AR 2011
Year: 2011

In this paper a low power and low area array multiplier with carry save adder is proposed. The proposed adder eliminates the final addition stage of the multiplier than the conventional parallel array multiplier. The conventional and proposed multiplier both are synthesized with 16-T full adder. Among Transmission Gate, Transmission Function Adder, 14-T, 16-T full adder shows energy efficiency. In the proposed 4x4 multiplier to add carry bits with out using Ripple Carry Adder (RCA) in the final stage, the carries given to the input of the next left column input. Due to this the proposed multiplier shows 56 less transistor count, then cause trade off in power and area. The proposed multiplier has shown 13.91% less power, 34.09% more speed and 59.91% less energy consumption for TSMC 0.18nm technology at a supply voltage 2.0V than the conventional multiplier.
Information Theoretic Authentication and Secrecy Codes in the Splitting Model
Venue: arXiv cs.CR 2011
Year: 2011

In the splitting model, information theoretic authentication codes allow non-deterministic encoding, that is, several messages can be used to communicate a particular plaintext. Certain applications require that the aspect of secrecy should hold simultaneously. Ogata-Kurosawa-Stinson-Saido (2004) have constructed optimal splitting authentication codes achieving perfect secrecy for the special case when the number of keys equals the number of messages. In this paper, we establish a construction method for optimal splitting authentication codes with perfect secrecy in the more general case when the number of keys may differ from the number of messages. To the best knowledge, this is the first result of this type.
Dynamic Intrusion Detection in Resource-Constrained Cyber Networks
Venue: arXiv cs.SY 2011
Year: 2011

We consider a large-scale cyber network with N components (e.g., paths, servers, subnets). Each component is either in a healthy state (0) or an abnormal state (1). Due to random intrusions, the state of each component transits from 0 to 1 over time according to certain stochastic process. At each time, a subset of K (K < N) components are checked and those observed in abnormal states are fixed. The objective is to design the optimal scheduling for intrusion detection such that the long-term network cost incurred by all abnormal components is minimized. We formulate the problem as a special class of Restless Multi-Armed Bandit (RMAB) process. A general RMAB suffers from the curse of dimensionality (PSPACE-hard) and numerical methods are often inapplicable. We show that, for this class of RMAB, Whittle index exists and can be obtained in closed form, leading to a low-complexity implementation of Whittle index policy with a strong performance. For homogeneous components, Whittle index policy is shown to have a simple structure that does not require any prior knowledge on the intrusion processes. Based on this structure, Whittle index policy is further shown to be optimal over a finite time horizon with an arbitrary length. Beyond intrusion detection, these results also find applications in queuing networks with finite-size buffers.
Cooperative Beamforming for Dual-Hop Amplify-and-Forward Multi-Antenna Relaying Cellular Networks
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, linear beamforming design for amplify-and-forward relaying cellular networks is considered, in which base station, relay station and mobile terminals are all equipped with multiple antennas. The design is based on minimum mean-square-error criterion, and both uplink and downlink scenarios are considered. It is found that the downlink and uplink beamforming design problems are in the same form, and iterative algorithms with the same structure can be used to solve the design problems. For the specific cases of fully loaded or overloaded uplink systems, a novel algorithm is derived and its relationships with several existing beamforming design algorithms for conventional MIMO or multiuser systems are revealed. Simulation results are presented to demonstrate the performance advantage of the proposed design algorithms.