waashk/dblp huggingface dataset:
finding biologically accurate clusterings in hierarchical tree decompositions using the variation of information. hierarchical clustering is a popular method for grouping together similar elements based on a distance measure between them. in many cases, annotations for some elements are known beforehand, which can aid the clustering process. we present a novel approach for decomposing a hierarchical clustering into the clusters that optimally match a set of known annotations, as measured by the variation of information metric. our approach is general and does not require the user to enter the number of clusters desired. we apply it to two biological domains: finding protein complexes within protein interaction networks and identifying species within metagenomic dna samples. for these two applications, we test the quality of our clusters by using them to predict complex and species membership, respectively. we find that our approach generally outperforms the commonly used heuristic methods.
parameter synthesis in nonlinear dynamical systems: application to systems biology. the dynamics of biological processes are often modeled as systems of nonlinear ordinary differential equations (ode). an important feature of nonlinear odes is that seemingly minor changes in initial conditions or parameters can lead to radically different behaviors. this is problematic because in general it is never possible to know/measure the precise state of any biological system due to measurement errors. the parameter synthesis problem is to identify sets of parameters (including initial conditions) for which a given system of nonlinear odes does not reach a given set of undesirable states. we present an efficient algorithm for solving this problem that combines sensitivity analysis with an efficient search over initial conditions. it scales to high-dimensional models and is exact if the given model is affine. we demonstrate our method on a model of the acute inflammatory response to bacterial infection, and identify initial conditions consistent with 3 biologically relevant outcomes.
coe: a general approach for efficient genome-wide two-locus epistasis test in disease association study. the availability of high density single nucleotide polymorphisms (snps) data has made genome-wide association study computationally challenging. two-locus epistasis (gene-gene interaction) detection has attracted great research interest as a promising method for genetic analysis of complex diseases. in this paper, we propose a general approach, coe, for efficient large scale gene-gene interaction analysis, which supports a wide range of tests. in particular, we show that many commonly used statistics are convex functions. from the observed values of the events in two-locus association test, we can develop an upper bound of the test value. such an upper bound only depends on single-locus test and the genotype of the snp-pair. we thus group and index snp-pairs by their genotypes. this indexing structure can benefit the computation of all convex statistics. utilizing the upper bound and the indexing structure, we can prune most of the snp-pairs without compromising the optimality of the result. our approach is especially efficient for large permutation test. extensive experiments demonstrate that our approach provides orders of magnitude performance improvement over the brute force approach.
topology-free querying of protein interaction networks. in the network querying problem, one is given a protein complex or pathway of species a and a protein---protein interaction network of species b; the goal is to identify subnetworks of b that are similar to the query. existing approaches mostly depend on knowledge of the interaction topology of the query in the network of species a; however, in practice, this topology is often not known. to combat this problem, we develop a topology-free querying algorithm, which we call torque. given a query, represented as a set of proteins, torque seeks a matching set of proteins that are sequence-similar to the query proteins and span a connected region of the network, while allowing both insertions and deletions. the algorithm uses alternatively dynamic programming and integer linear programming for the search task. we test torque with queries from yeast, fly, and human, where we compare it to the qnet topology-based approach, and with queries from less studied species, where only topology-free algorithms apply. torque detects many more matches than qnet, while in both cases giving results that are highly functionally coherent.
deep sequencing of a genetically heterogeneous sample: local haplotype reconstruction and read error correction. we present a computational method for analyzing deep sequencing data obtained from a genetically diverse sample. the set of reads obtained from a deep sequencing experiment represents a statistical sample of the underlying population. we develop a generative probabilistic model for assigning observed reads to unobserved haplotypes in the presence of sequencing errors. this clustering problem is solved in a bayesian fashion using the dirichlet process mixture to define a prior distribution on the unknown number of haplotypes in the mixture. we devise a gibbs sampler for sampling from the joint posterior distribution of haplotype sequences, assignment of reads to haplotypes, and error rate of the sequencing process to obtain estimates of the local haplotype structure of the population. the method is evaluated on simulated data and on experimental deep sequencing data obtained from hiv samples.
optimization-based peptide mass fingerprinting for protein mixture identification. in current proteome research, the most widely used method for protein mixture identification is probably peptide sequencing. peptide sequencing is based on tandem mass spectrometry (ms/ms) data. the disadvantage is that ms/ms data only sequences a limited number of peptides and leaves many more peptides uncovered.peptide mass fingerprinting (pmf) has been widely used to identify single purified proteins from single-stage ms data. unfortunately, this technique is less accurate than the peptide sequencing method and can not handle protein mixtures, which hampers the widespread use of pmf.in this paper, we tackle the problem of protein mixture identification from an optimization point of view. we show that some simple heuristics can find good solutions to the optimization problem. as a result, we obtain much better identification results than previous methods. through a comprehensive simulation study, we identify a set of limiting factors that hinder the performance of pmf-based protein mixture identification. we argue that it is feasible to remove these limitations and pmf can be a powerful tool in the analysis of protein mixtures, especially in the identification of low-abundance proteins which are less likely to be sequenced by ms/ms scanning.availability: the source codes, data and supplementary documents are available at http://bioinformatics.ust.hk/pmfmixture.rar
post-partition reconciliation protocols for maintaining consistency. this paper addresses design exploration for protocols that are employed in systems with availability-consistency tradeoffs. distributed data is modelled as states of objects replicated across a network, and whose updates require satisfaction of integrity constraints over multiple objects. upon detection of a partition, such a network will continue to provide delivery of services in parallel partitions; but only for updates with non-critical integrity constraints. once the degraded mode ends, the parallel network partitions are reconciled to arrive at one partition.using a formal treatment of the reconciliation process, three algorithms are proposed and studied in terms of their influence on service outage duration. the longer the reconciliation time, the lower is system availability; since the interval in which no services are provided is longer. however, the reconciliation time in turn is affected by the time to construct the post-partition system state. the shorter the construction time the higher is the number of updates that took place in the degraded mode but that will not be taken up in the reconciled partition. this will lead to a longer interval for rejecting/redoing these operations and thereby increase reconciliation time.
automatic interpretation of soccer video for highlights extraction and annotation. broadcasters are demonstrating interest in systems that ease the process of annotation the huge amount of live and archived video materials. exploitation of such assets is considered a key method for the improvement of production quality, and sport videos are one of the most marketable assets. in particular, in europe, soccer is one of the most relevant sport types. this paper deals with detection and recognition of soccer highlights, using an approach based on temporal logic models.
authentication of lz-77 compressed data. the formidable dissemination capability allowed by the current network technology makes it increasingly important to devise new methods to ensure authenticity. nowadays it is common practice to distribute documents in compressed form. in this paper, we propose a simple variation on the classic lz-77 algorithm that allows one to hide, within the compressed document, enough information to warrant its authenticity. the design is based on the unpredictability of a certain class of pseudo-random generators, in such a way that the hidden data cannot be retrieved in a reasonable amount of time by an attacker (unless the secret bit-string key is known). since it can still be decompressed by the original lz-77 algorithm, the embedding is completely "transparent". preliminary experiments show also the degradation in compression due to the embedding is almost negligible.
efficient aes implementations for arm based platforms. the advanced encryption standard (aes) contest, started by the u.s. national institute of standards and technology (nist), saw the rijndael [13] algorithm as its winner [11]. although the aes is fully defined in terms of functionality, it requires best exploitation of architectural parameters in order to reach the optimum performance on specific architectures. our work concentrates on arm cores [1] widely used in the embedded industry. most promising implementation choices for the common arm instruction set architecture (isa) are identified, and a new implementation for the linear mixing layer is proposed. the performance improvement over current implementations is demonstrated by a case study on the intel strongarm sa-1110 microprocessor [2]. further improvements based on exploitation of memory hierarchies are also described, and the corresponding performance figures are presented.
self-manifestation of composite multimedia objects to satisfy security constraints. a composite multimedia object (cmo) is comprised of different media components such as text, video, audio and image, with a variety of constraints that must be adhered to. these constraints include synchronization and spatial relationships between components, as well as the confidentiality and integrity requirements on each component. while spatial and synchronization constraints are to preserve the semantics of the cmo, the security (confidentiality and integrity) constraints are to represent the access control policies and fidelity requirements. a subject (user) requesting access for a cmo may not possess the required credentials to meet the confidentiality constraints, or his computer system the desired capabilities to meet the integrity constraints. this necessitates modification to the original cmo.in this paper, we present a self-manifestation approach in which composite multimedia objects automatically manifest themselves to cater to the subjects' credentials, and the capabilities of their computer systems. we accomplish this in two steps. first, we present a logical model which is an enhanced petri net model, called multimedia color-time petri net (mmctpn) to represent the components as well as the constraints of the cmo. we then demonstrate how mmctpn lends itself to automatic manifestation of the cmo when subject's credentials and capabilities activate it. second, we show how the petri net behavior can be implemented using the synchronized multimedia integration language (smil): smil, which is an extension of xml, supports specification of synchronization of the multimedia components and facilitates automatic rendering. when credentials are specified with digital certificates in some xml format, our system automatically modifies the smil document to satisfy the security constraints. we avoid multiple certificate verifications at the component sources by generating a single security token, when multiple credentials are required to view a component.
organizational modeling in uml and xml in the context of workflow systems. workflow technology plays a key role as an enabler in e-commerce applications, such as supply chains. until recently the major share of the attention of workflow systems researchers has gone to the exchange of information in cross-organizational processes. increasingly the focus is shifting from the exchange of data to support for interorganizational workflow processes. one of the initiatives in this direction has been xrl (exchangeable routing language), an extendible instance-based language having an xml syntax and petri-net semantics. in this paper, we move to the next level by extending xrl with organizational entities, structures, and rules. hence, we describe an organizational model first in uml and then convert it into an xml dtd. our organizational model allows for the specification of non-human resources, collections of resources (e.g., departments, teams, etc.), availability of resources, delegation, and role inheritance. additional features of our proposal are the tight integration of organizational concepts and routing concepts. an important goal of this work is to create standard for organizational modeling much like the x. 500 standard for directories.
using dijkstra's algorithm to incrementally find the k-nearest neighbors in spatial network databases. one of the most important kinds of queries in spatial network databases (sndb) to support location-based services (lbs) is the k-nearest neighbors (k-nn) query. given a point in a network, e.g. a location of a car on a road network, and a set of points of interests, e.g. hotels, gas stations, etc., the k-nn query returns the k points of interest closest to the query point. the network distance is used in such a query instead of the euclidean distance. dijkstra's algorithm is a well known solution to this problem. in this paper, we propose a storage schema with a set of index structures to support an efficient execution of a slightly modified version of the dijkstra's algorithm. we show in an experimental evaluation with generated data sets that our proposal is more efficient than the state-of-the-art solution to this problem.
temporal analysis of infectious diseases: influenza. a bayesian network is developed to embed the probabilistic reasoning dependencies of the demographics on the incidence of infectious diseases. influenza epidemics occur every year in both hemispheres during the winter. the bayesian learning paradigm is used to create synthetic data sets that simulate an outbreak of influenza for a geographic area. the bayesian prior and posterior probabilities can be altered to represent an outbreak for various demographics in different geographic regions. epidemic curves are generated, via time series analysis of the data sets, for the temporal flow of influenza on different variants of the demographics. the analysis of the demographic-based epidemic curves facilitates in the identification of the risk levels among the different demographic sections. spread vaccination lowers the impact of the epidemic, depending on the efficacy of the vaccine. our model is equipped to analyze the effects of spread vaccination and design vaccination strategies, that optimize the use of public health resources, by identifying high-risk demographic groups. our results show that application of the vaccine in the order of risk levels will further lower the epidemic impact as compared to uniform spread vaccination.
a grid-based architecture for earth observation data access. a huge quantity of earth observation (eo) and geospatial data is daily produced by several organizations. these heterogeneous data are very useful in several scientific, civil, military and industrial applications.securely and transparently storing, managing and accessing this huge quantity of data spread over distributed systems is a challenging problem. grid computing offers today a way to achieve secure access to geographically spread storage and computational resources.in this paper we present the distributed earth observation system information service (deosis) a distributed information service, developed by cact/isufi at the university of lecce which aims at managing and accessing eo and geospatial heterogeneous data sources, in a grid environment.
automated recognition of event scenarios for digital forensics. the authors have previously developed the ecf (event correlation for forensics) framework for scenario matching in the forensic investigation of activity manifested in digital transactional logs. ecf incorporated a suite of log parsers to reduce event records from heterogeneous logs to a canonical form for lodging in an sql database. this paper presents work since then, the auto-ecf system, which represents significant advances on ecf. the paper reports on the development and implementation of the new event abstraction and scenario specification methodology and on the development of the auto-ecf system which builds on that to achieve the automated recognition of event scenarios. the paper also reports on the evaluation of auto-ecf using three scenarios including one from the well known darpa test data.
on the numerical solution to linear problems using stochastic arithmetic. it has been recently shown that computation with stochastic numbers as regard to addition and multiplication by scalars can be reduced to computation in familiar vector spaces. this result allows us to solve certain practical problems with stochastic numbers and to compare algebraically obtained results with practical applications of stochastic numbers, such as the ones provided by the cestac method. such comparisons give additional information related to the stochastic behavior of random roundings in the course of numerical computations. a number of original numerical experiments are presented that agree with the expected theoretical results.
monitoring and synchronization for teamwork in gpgp. this paper addresses the problem of coordinating a group of agents involved in a team. to achieve flexible teamwork, agents should synchronize their work and monitor their performance to avoid redundant work. generalized partial global planning (gpgp) is one of the most common techniques used in coordinating cooperative agents, however, no technique is without limitations. our work adopts some concepts of steam to overcome some of gpgp limitations. in particular, we suggest adding coordination mechanisms to gpgp and extending taems, the model underlying gpgp, to facilitate such mechanisms. the work has successfully been implemented using jaf architecture. the coordination mechanisms are written as soar rules where we implemented a jaf component that implements the soar engine. analysis of a case study is presented along with experimental results to illustrate the power of the proposed work.
an evidential approach in ensembles. in this paper, we describe an approach to modeling the general process of combining decisions involved in ensembles of classifiers as an evidential reasoning process. this work proposes a novel structure, theoretical properties and manipulation mechanisms for representing classifier decisions as pieces of evidence. the advantage of the representation formalism is that it not only facilitates the distinguishing of trivial focal elements from important ones, resulting in the improvement of the ensemble performance, but it also effectively reduces the computation-time from exponential (as required in the conventional process of combining multiple pieces of evidence) to linear. we have conducted a comparative analysis on the effectiveness of the proposed evidence representation formalism in the text categorization domain. by comparing this method with majority voting and the previous results, we also demonstrate the advantage of this novel approach in combining classifiers.
property-oriented testing: a strategy for exploring dangerous scenarios. property-oriented testing uses the specification of a property to drive the testing process. the aim is to validate a program with respect to a target property, that is, to exercise the program and observe whether the property is violated or not. the paper defines a test strategy for safety properties in cyclic control systems. it consists of the stepwise construction of test scenarios. each step explores possible continuations of the dangerous scenarios found at the previous step, using black-box sampling techniques. the feasibility of the strategy is illustrated on a stem boiler case study. the target property is the "non explosion" of the boiler in presence of faults in the physical devices. the experimental results are promising since four different explosive scenarios have been identified.
constructive negation by bottom-up computation of literal answers. in this paper, we present a new proposal for an efficient implementation of constructive negation. in our approach the answers for a literal are bottom-up computed by solving equality constraints, instead of by handling frontiers of subsidiary computation trees. the required equality constraints are given by shepherdson's operators which are, in a sense, similar to bottom-up immediate consequence operators. however, in order to make the procedure efficient two main techniques are applied. first, we restrict our constraints to a class of success-answers (resp. fail-answers) which are easy to manipulate and to solve (or to prove their unsatisfiability). and, second, we take advantage of the monotonic nature of shepherdson's operators to make the procedure incremental and to avoid recalculations that are typical in frontiers-based methods. then, goal computation is made in the usual top-down clp scheme of collecting the answers for the selected literal into the constraint of the goal. the procedural mechanism for constructive negation is designed not only to generate every correct answer of a goal, but also to detect failure. that is, in spite of the bottom-up nature of the calculation of literal answers, goal computation is not necessarily infinite. the operational semantics that makes use of these ideas, called bcn, is sound and complete with respect to three-valued program completion for the whole class of normal logic programs. a prototype implementation of this approach has been developed and the experimental results are very promising.