Search

The tenth year of the annual International Conference on Research in Computational Biology (RECOMB) provides an opportunity to reflect on its history. RECOMB has been held across the world, including 6 different countries spanning 3 continents (Table 1). Over its 10 year history, RECOMB has published 373 papers and 170 individuals have served on its various committees. While there are many new faces in RECOMB each year, a significant number of researchers have participated over many years forming the core of the RECOMB community. [ABSTRACT FROM AUTHOR]

In this paper, we consider Kearns' [4] Statistical Query Model of learning. It is well known [3] that the number of statistical queries, needed for "weakly learning" an unknown target concept (i.e. for gaining significant advantage over random guessing) is polynomially related to the so-called Statistical Query dimension of the concept class. In this paper, we provide a similar characterization for "strong learning" where the learners final hypothesis is required to approximate the unknown target concept up to a small rate of misclassification. The quantity that characterizes strong learnability in the Statistical Query model is a surprisingly close relative of (though not identical to) the Statistical Query dimension. For the purpose of proving the main result, we provide other characterizations of strong learnability which are given in terms of covering numbers and related notions. These results might find some interest in their own right. All characterizations are purely information-theoretical and ignore computational issues. [ABSTRACT FROM AUTHOR]

We introduce and analyse a simple probabilistic model of genome evolution. It is based on three fundamental evolutionary events: gene duplication, loss and innovation, and it is called DLI model. The focus of the paper is around the size distribution of gene families. The formulas for equilibrium gene family sizes are derived showing that they follow a logarithmic distribution. We consider also a disjoint union of DLI models and we present the result of this study. Some empirical results for microbial genomes are presented. [ABSTRACT FROM AUTHOR]

This paper considers the quantum query complexity of ε-biased oracles that return the correct value with probability only 1/2 + ε. In particular, we show a quantum algorithm to compute N-bit OR functions with $O(\sqrt{N}/{\varepsilon})$ queries to ε-biased oracles. This improves the known upper bound of $O(\sqrt{N}/{\varepsilon}^2)$ and matches the known lower bound; we answer the conjecture raised by the paper [1] affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of ε. This contrasts with the corresponding classical situation, where it is almost hopeless to achieve more than a constant success probability without knowing the value of ε. [ABSTRACT FROM AUTHOR]

The aim of this paper is to study communication in networks where nodes fail in a random dependent way. In order to capture fault dependencies, we introduce the neighborhood fault model, where damaging events, called spots, occur randomly and independently with probability p at nodes of a network, and cause faults in the given node and all of its neighbors. Faults at distance at most 2 become dependent in this model and are positively correlated. We investigate the impact of spot probability on feasibility and time of communication in the fault-free part of the network. We show a network which supports fast communication with high probability, if p ≤ 1/clogn. We also show that communication is not feasible with high probability in most classes of networks, for constant spot probabilities. For smaller spot probabilities, high probability communication is supported even by bounded degree networks. It is shown that the torus supports communication with high probability when p decreases faster than 1/n1/2, and does not when p ∈ 1/O(n1/2). Furthermore, a network built of tori is designed, with the same fault-tolerance properties and additionally supporting fast communication. We show, however, that networks of degree bounded by a constant d do not support communication with high probability, if p ∈ 1/O(n1/d). While communication in networks with independent faults was widely studied, this is the first analytic paper which investigates network communication for random dependent faults. [ABSTRACT FROM AUTHOR]

We initiate a study on automata recognizing labelled posets constructed from scattered and countable linear orderings. More precisely, the class of labelled posets considered in this paper is the smallest containing letters, closed under finite parallel operation and sequential product indexed by all countable and scattered linear orderings. The first result of this paper establishes that those labelled posets are precisely the N-free ones. The second result is a Kleene-like theorem, which establishes that the class of languages of labelled posets accepted by branching automata is exactly the class of rational languages. This generalizes both the finite [9] and ω-labelled posets [2,6] cases, and the Kleene-like theorem on words on linear orderings [3]. [ABSTRACT FROM AUTHOR]

Compression is most important when space is in short supply, so compression algorithms are often implemented in limited memory. Most analyses ignore memory constraints as an implementation detail, however, creating a gap between theory and practice. In this paper we consider the effect of memory limitations on compression algorithms. In the first part of the paper we assume the memory available is fixed and prove nearly tight upper and lower bound on how much is needed to compress a string close to its k-th order entropy. In the second part we assume the memory available grows (slowly) as more and more characters are read. In this setting we show that the rate of growth of the available memory determines the speed at which the compression ratio approaches the entropy. In particular, we establish a relationship between the rate of growth of the sliding window in the LZ77 algorithm and its convergence rate. [ABSTRACT FROM AUTHOR]

The small world phenomenon, a.k.a. the six degree of separation between individuals, was identified by Stanley Milgram at the end of the 60s. Milgram experiment demonstrated that letters from arbitrary sources and bound to an arbitrary target can be transmitted along short chains of closely related individuals, based solely on some characteristics of the target (professional occupation, state of leaving, etc.). In his paper on small world navigability, Jon Kleinberg modeled this phenomenon in the framework of augmented networks, and analyzed the performances of greedy routing in augmented multi-dimensional meshes. This paper objective is to survey the results that followed up Kleinberg seminal work, including results about: extensions of the augmented network model, and variants of greedy routing,designs of ${\mbox{\rm polylog}}$-navigable graph classes,the quest for universal augmentation schemes, anddiscussions on the validation of the model in the framework of doubling metrics. [ABSTRACT FROM AUTHOR]

Association, or LD (linkage disequilibrium), mapping is an intensely-studied approach to gene mapping (genome-wide or in candidate regions) that is widely hoped to be able to efficiently locate genes influencing both complex and Mendelian traits. The logic underlying association mapping implies that the best possible mapping results would be obtained if the genealogical history of the sampled individuals were explicitly known. Such a history would be in the form of an "ancestral recombination graph (ARG)". But despite the conceptual importance of genealogical histories to association mapping, few practical association mapping methods have explicitly used derived genealogical aspects of ARGs. Two notable exceptions are [35] and [23]. In this paper we develop an association mapping method that explicitly constructs and samples minARGs (ARGs that minimize the number of recombinations). We develop an ARG sampling method that provably samples minARGs uniformly at random, and that is practical for moderate sized datasets. We also develop a different, faster, ARG sampling method that still samples from a well-defined subspace of ARGs, and that is practical for larger sized datasets. We present novel efficient algorithms on extensions of the "phenotype likelihood" problem, a key step in the method in [35]. We also prove that computing the phenotype likelihood for a different natural extension of the penetrance model in [35] is NP-hard, answering a question unresolved in that paper. Finally, we put all of these results into practice, and examine how well the implemented methods perform, compared to the results in [35]. The empirical results show great speed ups, and definite but sometimes small, improvements in mapping accuracy. Speed is particularly important in doing genome-wide scans for causative mutations. [ABSTRACT FROM AUTHOR]

This paper addresses strategies for the stable roommates problem, assuming that a stable matching is chosen at random. We investigate how a cheating man should permute his preference list so that he has a higher-ranking roommate probabilistically. In the first part of the paper, we identify a necessary condition for creating a new stable roommate for the cheating man. This condition precludes any possibility of his getting a new roommate ranking higher than all his stable roommates when everyone is truthful. Generalizing to the case that multiple men collude, we derive another impossibility result: given any stable matching in which a subset of men get their best possible roommates, they cannot cheat to create a new stable matching in which they all get strictly better roommates than in the given matching. Our impossibility result, considered in the context of the stable marriage problem, easily re-establishes the celebrated Dubins-Freedman Theorem. The more generalized Demange-Gale-Sotomayor Theorem states that a coalition of men and women cannot cheat to create a stable matching in which everyone of them gets a strictly better partner than in the Gale-Shapley algorithm (with men proposing). We give a sharper result: a coalition of men and women cannot cheat together so that, in a newly-created stable matching, every man in the coalition gets a strictly better partner than in the Gale-Shapley algorithm while none of the women in the coalition is worse off. In the second part of the paper, we present two cheating strategies that guarantee that the cheating man's new probability distribution over stable roommates majorizes the original one. These two strategies do not require the knowledge of the probability distribution of the cheating man. This is important because the problem of counting stable matchings is #P-complete. Our strategies only require knowing the set of stable roommates that the cheating man has and can be formulated in polynomial time. Our second cheating strategy has an interesting corollary in the context of stable marriage with the Gale-Shapley algorithm. Any woman-optimal strategy will ensure that every woman, cheating or otherwise, ends up with a partner at least as good as when everyone is truthful. [ABSTRACT FROM AUTHOR]

The problem of dynamically recognizing a class of graphs has received much attention recently. Given an input graph and a sequence of operations (vertex and edge additions and deletions) to be performed on that graph, the algorithm must determine after each operation if the resulting graph is still a member of the class in question. This paper presents the first dynamic recognition algorithm for distance-hereditary graphs. The algorithm handles edge additions and deletions, and is optimal in that each operation can be performed in constant time. In doing so, the paper completely characterizes when an edge can be added to and removed from a distance-hereditary graph with the result remaining distance-hereditary, and develops a new representation for these graphs in terms of cographs. [ABSTRACT FROM AUTHOR]

The problem of image matching is to find for two given digital images A and B an admissible transformation that converts image A as close as possible to B. This problem becomes hard if the space of admissible transformations is too complex. Consequently, in many real applications, like the ones allowing nonlinear elastic transformations, the known algorithms solving the problem either work in exponential worst-case time or can only guarantee to find a local optimum. Recently Keysers and Unger have proved that the image matching problem for this class of transformations is NP-complete, thus giving evidence that the known exponential time algorithms are justified. On the other hand, allowing only such transformations as translations, rotations, or scalings the problem becomes tractable. In this paper we analyse the computational complexity of image matching for a larger space of admissible transformations, namely for all affine transformations. In signal processing there are no efficient algorithms known for this class. Similarly, the research in combinatorial pattern matching does not cover this set of transformations neither providing efficient algorithms nor proving intractability of the problem, although it is a basic one and of high practical importance. The main result of this paper is that the image matching problem can be solved in polynomial time even allowing all affine transformations. [ABSTRACT FROM AUTHOR]

In the last decade there has been an ongoing interest in string comparison problems; to a large extend the interest was stimulated by genome rearrangement problems in computational biology but related problems appear in many other areas of computer science. Particular attention has been given to the problem of sorting by reversals(SBR): given two strings, A and B, find the minimum number of reversals that transform the string A into the string B (a reversalρ(i,j), i

LSH (Locality Sensitive Hashing) is one of the best known methods for solving the c-approximate nearest neighbor problem in high dimensional spaces. This paper presents a variant of the LSH algorithm, focusing on the special case of where all points in the dataset lie on the surface of the unit hypersphere in a d-dimensional Euclidean space. The LSH scheme is based on a family of hash functions that preserves locality of points. This paper points out that when all points are constrained to lie on the surface of the unit hypersphere, there exist hash functions that partition the space more efficiently than the previously proposed methods. The design of these hash functions uses randomly rotated regular polytopes and it partitions the surface of the unit hypersphere like a Voronoi diagram. Our new scheme improves the exponent ρ, the main indicator of the performance of the LSH algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes a methodology to analyze graph transformation systems by means of Alloy and its supporting tools. Alloy is a simple structural modeling language, based on first-order logic, that allows the user to produce models of software systems by abstracting their key characteristics. The tools can generate instances of invariants, and check properties of models, on user-constrained representations of the world under analysis. The paper describes how to render a graph transformation system —specified using AGG— as an Alloy model and how to exploit its tools to prove significant properties of the system. Specifically, it allows the user to decide whether a given configuration (graph) can be obtained through a finite and bounded sequence of steps (invocation of rules), whether a given sequence of rules can be applied on an initial graph, and, given an initial graph and an integer n, which are the configurations that can be obtained by applying a sequence of n (particular) rules. [ABSTRACT FROM AUTHOR]

The paper presents a case study on the synthesis of labelled transition systems (ltss) for process calculi, choosing as testbed Milner's Calculus of Communicating System (ccs). The proposal is based on a graphical encoding: each ccs process is mapped into a graph equipped with suitable interfaces, such that the denotation is fully abstract with respect to the usual structural congruence. Graphs with interfaces are amenable to the synthesis mechanism based on borrowed contexts (bcs), proposed by Ehrig and König (which are an instance of relative pushouts, originally introduced by Milner and Leifer). The bc mechanism allows the effective construction of an lts that has graphs with interfaces as both states and labels, and such that the associated bisimilarity is automatically a congruence. Our paper focuses on the analysis of the lts distilled by exploiting the encoding of ccs processes: besides offering some technical contributions towards the simplification of the bc mechanism, the key result of our work is the proof that the bisimilarity on processes obtained via bcs coincides with the standard strong bisimilarity for ccs. [ABSTRACT FROM AUTHOR]

Graph transformation techniques have already been used successfully by several research groups to support re-engineering of large legacy systems. Where others often aim at transforming the system to improve it, we advocate an evolutionary approach that embeds transformations within the ordinary development process and provides tool support to monitor the ongoing progress regularly. In this paper, we discuss how temporal graph queries based on Fujaba story diagrams can provide a natural means to express trend-oriented metrics and consistency rules that we identified in our industrial case studies. To this end, we discuss a first-order logic rather than operational interpretation of a graph queries and show how well-known temporal logic operators can be added to express rules over consecutive states of the same instance graph. [ABSTRACT FROM AUTHOR]

In unreliable environments, e.g. wireless networks, often there are messages lost, connection and process crashes, among other undesirable fault occurrences. Mechanisms to enhance the dependability of these systems can be employed, but with a performance cost. Analytical approaches are useful to predict performance and dependability values, guiding the system developer to adjust bounds for specific requirements in complex systems. In this paper we use non-functional analysis of Stochastic Object-Based Graph Grammars (SOBGG) models considering classical fault behaviors in distributed systems, allowing the developer to predict performance and dependability values for high performance and resilient systems. The specific contributions of this paper are: (i) revisit the notion of fault representation to allow non-functional analysis, more specifically, steady-state analysis; (ii) discuss the specification of rates associated to SOBGG rules, describing an adequate approach to distributed systems; (iii) show the suitability of the proposed techniques through their application to a case study. Keywords: Object-based graph grammars, distributed systems, fault-tolerance, non-functional analysis, dependability. [ABSTRACT FROM AUTHOR]

A distributed graph (N,D) consists of a network graph N and a commutative diagram D over the scheme N which associates local graphs D(ni) and graph morphisms D(e): D(n1) →D(n2) to nodes n1, n2 and edges e: n1 →n2 in N. Although there are several interesting applications of distributed graphs and transformations, even the basic pushout constructions for the double pushout approach of distributed graph transformation could be shown up to now only in very special cases. In this paper we show that the category of distributed graphs can be considered as a Grothendieck category over a specific indexed category, which assigns to each network N the category of all diagrams D of shape N. In this framework it is possible to give a free construction which allows to construct for each diagram D1 over N1 and network morphism h:N1 →N2 a free extension Fh(D1) over N2 and to show that the Grothendieck category is complete and cocomplete if the underlying category of local graphs has these properties. Moreover, an explicit construction for general pushouts of distributed graphs is given. This pushout construction is based on the free construction. The non-trivial proofs for free constructions and pushouts are the main contributions of this paper and they are compared with the special cases known up to now. [ABSTRACT FROM AUTHOR]

In this paper we describe a way to integrate Taentzer's rule amalgamation with the recently proposed notions of nested graph conditions. The resulting so-called quantified graph transformation rules include (universally and existentially) quantified sub-structures in a flexible way. This can be used for instance to specify a larger-step operational semantics, thus improving the scalability of graph transformation as a technique for software verification. [ABSTRACT FROM AUTHOR]

Various international efforts are underway to catalog the genomic similarities and variations in the human population. Some key discoveries such as inversions and transpositions within the members of the species have also been made over the years. The task of constructing a phylogeny tree of the members of the same species, given this knowledge and data, is an important problem. In this context, a key observation is that the "distance" between two members, or member and ancestor, within the species is small. In this paper, we pose the tree reconstruction problem exploiting some of these peculiarities. The central idea of the paper is based on the notion of minimal consensus PQ tree T of sequences introduced in [29]. We use a modified PQ structure (termed oPQ) and show that both the number and size of each T is $\mathcal{O}(1)$. We further show that the tree reconstruction problem is statistically well-defined (Theorem [7]) and give a simple scheme to construct the phylogeny tree and the common ancestors. Our preliminary experiments with simulated data look very promising. Keywords: PQ tree, inversion, reversal, transposition, genome rearrangement, phylogeny, evolution, genealogy, common ancestor, tree construction. [ABSTRACT FROM AUTHOR]

We introduce and analyse a simple discrete probabilistic model of genome evolution. It is based on four fundamental evolutionary events: gene duplication, loss, change and innovation, and it is called DLCI model. This is the first such model rigorously analysed. The focus of the paper is around the size distribution of gene families. The formulas for equilibrium gene family sizes are derived showing that they follow a logarithmic distribution. We consider also a disjoint union of DLCI models and we present the result of this study. Some empirical results for microbial genomes are presented. [ABSTRACT FROM AUTHOR]

Pharmacogenomics and clinical studies that measure the temporal expression levels of patients can identify important pathways and biomarkers that are activated during disease progression or in response to treatment. However, researchers face a number of challenges when trying to combine expression profiles from these patients. Unlike studies that rely on lab animals or cell lines, individuals vary in their baseline expression and in their response rate. In this paper we present a generative model for such data. Our model represents patient expression data using two levels, a gene level which corresponds to a common response pattern and a patient level which accounts for the patient specific expression patterns and response rate. Using an EM algorithm we infer the parameters of the model. We used our algorithm to analyze multiple sclerosis patient response to Interferon-β. As we show, our algorithm was able to improve upon prior methods for combining patients data. In addition, our algorithm was able to correctly identify patient specific response patterns. [ABSTRACT FROM AUTHOR]

This paper proposes a method of domain specificity estimation of technical terms using the Web. In the proposed method, it is assumed that, for a certain technical domain, a list of known technical terms of the domain is given. Technical documents of the domain are collected through the Web search engine, which are then used for generating a vector space model for the domain. The domain specificity of a target term is estimated according to the distribution of the domain of the sample pages of the target term. Experimental evaluation results show that the proposed method achieved mostly 90% precision/recall. [ABSTRACT FROM AUTHOR]

In a competitive environment, providing suitable information and products to meet customer requirements and improve customer satisfaction is one key factor to measure a company's competitiveness. In this paper, we propose a preference perception system by combining fuzzy set with data mining technology to detect the information preference of each user on a web-based environment. An experiment was implemented to demonstrate the feasibility and effectiveness of the proposed system in this study. It indicates that the proposed system can effectively perceive the change of information preference for users in a Web environment. Keywords: Customer Satisfaction, Preference Perception, Data Mining, Fuzzy Set Theory, Web environment. [ABSTRACT FROM AUTHOR]

This paper presents a 3D graphic information retrieval system which supports a content-based retrieval for 3D. The user can pose a visual query involving various 3D graphic features such as inclusion of a given object, object's shape, descriptive information and spatial relations on the web interface. The data model underlying the retrieval system models 3D scenes using domain objects and their spatial relations. An XML-based data modeling language called 3DGML has been designed to support the data model. We discuss the data modeling technique and the retrieval system in detail. [ABSTRACT FROM AUTHOR]

In this paper we propose a clustering-based hybrid approach for multi-document summarization which integrates sentence clustering, local recommendation and global search. For sentence clustering, we adopt a stability-based method which can determine the optimal cluster number automatically. We weight sentences with terms they contain for local sentence recommendation of each cluster. For global selection, we propose a global criterion to evaluate overall performance of a summary. Thus the sentences in the final summary are determined by not only the configuration of individual clusters but also the overall performance. This approach successfully gets top-level performance running on corpus of DUC04. [ABSTRACT FROM AUTHOR]

This paper presents an approach for image annotation propagation to images which have no annotations. In some specific domains, the assumption that visual similarity implies (partial) semantic similarity can be made. For instance, in medical imaging, two images of the same anatomic part in a given modality have a very similar appearance. In the proposed approach, a conceptual indexing phase extracts concepts from texts; a visual similarity between images is computed and then combined with conceptual text indexing. Annotation propagation driven by prior knowledge on the domain is finally performed. Domain knowledge used is a meta-thesaurus for both indexing and annotations propagation. The proposed approach has been applied on the imageCLEF medical image collection. Keywords: Conceptual Indexing, Annotation Propagation, Visual Similarity. [ABSTRACT FROM AUTHOR]

Keyword search from Informational Retrieval (IR) can be seen as one most convenient processing mode catering for common users to obtain interesting information. As XML data becomes more and more widespread, the trend of adapting keyword search on XML data also becomes more and more active. In this paper, we first try nesting mechanism for XML keyword search, which just uses a little nesting skill. This attempt has several benefits. For example, it is convenient for common users, because they need not to know any organization knowledge of the target XML data. Secondly, the nesting pattern can be easily transformed into structural hints, which has same mechanism as what XML data model does. Finally, since there is no need of label information, we can retrieve XML fragments from different schemas. Besides, this paper also proposes a new similarity measuring method for retrieved XML fragments which can be from different schemas. Its kernel is KCAM (Keyword Common Ancestor Matrix) structure, which stores the level information of SLCA (Smallest Lowest Common Ancestor) node between two keywords. By mapping XML fragments into KCAMs, the structural similarity can be computed using matrix distance. KCAM distance can go well with the nesting keyword method. [ABSTRACT FROM AUTHOR]

This paper proposes a novel hierarchical learning strategy to deal with the data sparseness problem in relation extraction by modeling the commonality among related classes. For each class in the hierarchy either manually predefined or automatically clustered, a discriminative function is determined in a top-down way. As the upper-level class normally has much more positive training examples than the lower-level class, the corresponding discriminative function can be determined more reliably and effectively, and thus guide the discriminative function learning in the lower-level, which otherwise might suffer from limited training data. In this paper, the state-of-the-art Support Vector Machines is applied as the basic classifier learning approach using the hierarchical learning strategy. Evaluation on the ACE RDC 2003 and 2004 corpora shows that the hierarchical learning strategy much improves the performance on least- and medium- frequent relations. [ABSTRACT FROM AUTHOR]

This paper compares the utilization of ConceptNet and WordNet in query expansion. Spreading activation selects candidate terms for query expansion from these two resources. Three measures including discrimination ability, concept diversity, and retrieval performance are used for comparisons. The topics and document collections in the ad hoc track of TREC-6, TREC-7 and TREC-8 are adopted in the experiments. The results show that ConceptNet and WordNet are complementary. Queries expanded with WordNet have higher discrimination ability. In contrast, queries expanded with ConceptNet have higher concept diversity. The performance of queries expanded by selecting the candidate terms from ConceptNet and WordNet outperforms that of queries without expansion, and queries expanded with a single resource. [ABSTRACT FROM AUTHOR]

In this paper, we consider an interesting variant of the well-known Steiner tree problem: Given a complete graph G = (V,E) with a cost function c:E →R+ and two subsets R and R′ satisfying $R'\subset R\subseteq V$, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R′ cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we show that the problem is MAX SNP-hard even when the costs of all edges in the input graph are restricted to either 1 or 2. We also present an approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

The enumerate-and-expand paradigm for solving NP-hard problems has been introduced and applied to some Vertex Cover variants in a recently published preliminary paper. In this paper we improve on the runtime for Connected Vertex Cover, obtaining a bound of O*(2.7606k),The O*-notation is equivalent to the well-known Landau notation, except that polynomial factors may be suppressed. For instance, 2kk2n3=O*(2k). and use the technique in order to gain the fastest known method for counting the number of vertex covers in a graph, which takes O*(1.3803k) time. [ABSTRACT FROM AUTHOR]

This paper studies the problem of finding the 1-median on a graph where vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. Averbakh and Berman had an O(mn2log n)-time algorithm for the problem on a general graph, and had an O(nlog2n)-time algorithm on a tree. In this paper, we improve these two bounds to O(mn2 + n3log n) and O(nlog n), respectively. Keywords: Location theory, minmax regret optimization, medians. [ABSTRACT FROM AUTHOR]

Accessibility of high-throughput genotyping technology makes possible genome-wide association studies for common complex diseases. When dealing with common diseases, it is necessary to search and analyze multiple independent causes resulted from interactions of multiple genes scattered over the entire genome. This becomes computationally challenging since interaction even of pairs gene variations require checking more than 1012 possibilities genome-wide. This paper first explores the problem of searching for the most disease-associated and the most disease-resistant multi-gene interactions for a given population sample of diseased and non-diseased individuals. A proposed fast complimentary greedy search finds multi-SNP combinations with non-trivially high association on real data. Exploiting the developed methods for searching associated risk and resistance factors, the paper addresses the disease susceptibility prediction problem. We first propose a relevant optimum clustering formulation and the model-fitting algorithm transforming clustering algorithms into susceptibility prediction algorithms. For three available real data sets (Crohn's disease (Daly et al, 2001), autoimmune disorder (Ueda et al, 2003), and tick-borne encephalitis (Barkash et al, 2006)), the accuracies of the prediction based on the combinatorial search (respectively, 84%, 83%, and 89%) are higher by 15% compared to the accuracies of the best previously known methods. The prediction based on the complimentary greedy search almost matches the best accuracy but is much more scalable. [ABSTRACT FROM AUTHOR]

Given a metric (V,d), a spanner is a sparse graph whose shortest-path metric approximates the distance d to within a small multiplicative distortion. In this paper, we study the problem of spanners with slack: e.g., can we find sparse spanners where we are allowed to incur an arbitrarily large distortion on a small constant fraction of the distances, but are then required to incur only a constant (independent of n) distortion on the remaining distances? We answer this question in the affirmative, thus complementing similar recent results on embeddings with slack into ℓp spaces. For instance, we show that if we ignore an ε fraction of the distances, we can get spanners with O(n) edges and $O(\log {\frac{1}{\epsilon}})$ distortion for the remaining distances. We also show how to obtain sparse and low-weight spanners with slack from existing constructions of conventional spanners, and these techniques allow us to also obtain the best known results for distance oracles and distance labelings with slack. This paper complements similar results obtained in recent research on slack embeddings into normed metric spaces. [ABSTRACT FROM AUTHOR]

This paper describes novel methods we developed to lay out graphs using Sugiyama's scheme [16] in a tool named GLEE. The main contributions are: a heuristic for creating a graph layout with a given aspect ratio, an efficient method of edge-crossings counting while performing adjacent vertex swaps, and a simple and fast spline routing algorithm. [ABSTRACT FROM AUTHOR]

Given a graph G with n vertices and a set S of n points in the plane, a point-set embedding of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding of a subgraph G′ ⊂ G on a subset of S. The desired output is a point-set embedding of G on S that includes the given partial drawing of G′. We concentrate on trees and show how to compute the output in O(n2 logn) time and with at most 1 + 2 ⌈k/2 ⌉ bends per edge, where k is the number of vertices of the given subdrawing. We also prove that there are instances of the problem which require at least k − 3 bends for some of the edges. [ABSTRACT FROM AUTHOR]

In this paper we introduce cyclic level planar graphs, which are a planar version of the recurrent hierarchies from Sugiyama et al. [8] and the cyclic extension of level planar graphs, where the first level is the successor of the last level. We study the testing and embedding problem and solve it for strongly connected graphs in time $\O(V \log V)$. [ABSTRACT FROM AUTHOR]

Mapping intra-cellular signaling networks is a critical step in developing an understanding of and treatments for many devastating diseases. The predominant ways of discovering pathways in these networks are knockout and pharmacological inhibition experiments. However, experimental evidence for new pathways can be difficult to explain within existing maps of signaling networks. In this paper, we present a novel computational method that integrates pharmacological intervention experiments with protein interaction data in order to predict new signaling pathways that explain unexpected experimental results. Biologists can use these hypotheses to design experiments to further elucidate underlying signaling mechanisms or to directly augment an existing signaling network model. When applied to experimental results from human breast cancer cells targeting the epidermal growth factor receptor (EGFR) network, our method proposes several new, biologically-viable pathways that explain the evidence for a new signaling pathway. These results demonstrate that the method has potential for aiding biologists in generating hypothetical pathways to explain experimental findings. Our method is implemented as part of the PathwayOracle toolkit and is available from the authors upon request. [ABSTRACT FROM AUTHOR]

In this paper, we develop a theory that studies words with nested data values with the help of shuffle expressions. We study two cases, which we call "ordered" and "unordered". In the unordered case, we show that emptiness (of the two related problems) is decidable. In the ordered case, we prove undecidability. As a proof vehicle for the latter, we introduce the notion of higher-order multicounter automata. [ABSTRACT FROM AUTHOR]

In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both cases, we develop solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem. [ABSTRACT FROM AUTHOR]

We say that, for k ≥ 2 and ℓ> k, a tree T is a (k,ℓ)-leaf root of a graph G = (VG,EG) if VG is the set of leaves of T, for all edges xy ∈ EG, the distance dT(x,y) in T is at most k and, for all non-edges $xy \not\in E_G$, dT(x,y) is at least ℓ. A graph G is a (k,ℓ)-leaf power if it has a (k,ℓ)-leaf root. This new notion modifies the concept of k-leaf power which was introduced and studied by Nishimura, Ragde and Thilikos motivated by the search for underlying phylogenetic trees. Recently, a lot of work has been done on k-leaf powers and roots as well as on their variants phylogenetic roots and Steiner roots. For k = 3 and k = 4, structural characterisations and linear time recognition algorithms of k-leaf powers are known, and, recently, a polynomial time recognition of 5-leaf powers was given. For larger k, the recognition problem is open. We give structural characterisations of (k,ℓ)-leaf powers, for some k and ℓ, which also imply an efficient recognition of these classes, and in this way we also improve and extend a recent paper by Kennedy, Lin and Yan on strictly chordal graphs and leaf powers. [ABSTRACT FROM AUTHOR]

Finding the sub-vector with the largest sum in a sequence of n numbers is known as the maximum sum problem. Finding the k sub-vectors with the largest sums is a natural extension of this, and is known as the k maximal sums problem. In this paper we design an optimal O(n + k) time algorithm for the k maximal sums problem. We use this algorithm to obtain algorithms solving the two-dimensional k maximal sums problem in O(m2·n + k) time, where the input is an m ×n matrix with m ≤ n. We generalize this algorithm to solve the d-dimensional problem in O(n2d − 1 + k) time. The space usage of all the algorithms can be reduced to O(nd − 1 + k). This leads to the first algorithm for the k maximal sums problem in one dimension using O(n + k) time and O(k) space. [ABSTRACT FROM AUTHOR]

Consider a rooted directed acyclic graph G = (V, E) with root r, representing a collection V of web pages connected via a set E of hyperlinks. Each node v is associated with the probability that a user wants to access the node v. The access cost is defined as the expected number of steps required to reach a node from the root r. A bookmark is an additional shortcut from r to a node of G, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper presents a polynomial time approximation algorithm with factor (1 − 1/e), and shows that there exists no polynomial time approximation algorithm with a better constant factor than (1 − 1/e) unless ${\cal NP}\subseteq {\cal DTIME}(N^{O(\log\log N)})$, where N is the size of the inputs. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of creating partitioned drawings of graphs. In a partitioned drawing each vertex is placed inside a given partition cell of a rectangular partition of the drawing area. This problem has several applications in practice, e.g. for UML activity diagrams or wiring schematics. We first formalize the problem and analyze its complexity. Then we give a heuristic approach which is based on the topology-shape-metrics approach and produces partitioned drawings in time O((V + c)2log(V + c)), where c denotes the number of crossings. [ABSTRACT FROM AUTHOR]

In this paper we study connections between Schnyder woods and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and dimension theory. Orthogonal surfaces explain the connections between these seemingly unrelated notions. We use these connections for an intuitive proof of the Brightwell-Trotter Theorem which says that the face lattice of a 3-polytope minus one face has dimension three. Our proof yields a companion linear time algorithm for the construction of the three linear orders that realize the face lattice. Coplanar orthogonal surfaces are in correspondance with a large class of convex straight line drawings of 3-connected planar graphs. We show that Schnyder's face counting approach with weighted faces can be used to construct all coplanar orthogonal surfaces and hence the corresponding drawings. Appropriate weights are computable in linear time. [ABSTRACT FROM AUTHOR]

Node-link diagrams are widely used in information visualization to show relationships among data. However, when the size of data becomes very large, node-link diagrams will become cluttered and visually confusing for users. In this paper, we propose a novel controllable edge clustering method based on Delaunay triangulation to reduce visual clutter for node-link diagrams. Our method uses curves instead of straight lines to represent links and these curves can be grouped together according to their relative positions and directions. We further introduce progressive edge clustering to achieve continuous level-of-details for large networks. [ABSTRACT FROM AUTHOR]

In real systems, such as operating systems, the scheduler is often unaware of the remaining work in each job or of the ability of the job to take advantage of more resources. In this paper, we adopt the setting for non-clairvoyance of [3,2]. Based on the particular case of malleable jobs, it is generally assumed in the literature that "Equi never starves a job since it allocates to every job the same amount of processing power". We provide an analysis of the competitiveness of Equi for the makespan objective which shows that under this more general setting this statement is at the same time true and false: false, because, some jobs may be stretched by a factor as large as, but no more than, $\frac{\ln n}{\ln\ln n}$ with respect to the optimal, where n is the size of the largest set; true, because no algorithm can achieve a better competitive ratio up to a constant factor. In this paper, we extend the results in [2,11] to the batch scheduling of sets of jobs that go through arbitrary phases: user request all together at time 0, for the execution of a set of jobs and is served when the last job completes. We prove that the algorithm EquioEqui is $(2+\sqrt3+o(1))\frac{\ln n}{\ln\ln n}$-competitive, where n is the maximum size of a set, which is optimal up to a constant factor. We provide experimental evidences that this algorithm may have the same asymptotic competitive ratio $\Theta(\frac{\ln n}{\ln\ln n})$ (independent of the number of requests) for the flowtime objective when requests have release dates, if it is given sufficiently large extra processing power with respect to the optimum. [ABSTRACT FROM AUTHOR]

We investigate Knuth's eleventh open question on stable matchings. In the stable family problem, sets of women, men, and dogs are given, all of whom state their preferences among the other two groups. The goal is to organize them into family units, so that no three of them have incentive to desert their assigned family members to join in a new family. A similar problem, called the threesome roommates problem, assumes that a group of persons, each with their preferences among the combinations of two others, are to be partitioned into triples. Similarly, the goal is to make sure that no three persons want to break up with their assigned roommates. Ng and Hirschberg were the first to investigate these two problems. In their formulation, each participant provides a strictly-ordered list of all combinations. They proved that under this scheme, both problems are NP-complete. Their paper reviewers pointed out that their reduction exploits inconsistent preference lists and they wonder whether these two problems remain NP-complete if preferences are required to be consistent. We answer in the affirmative. In order to give these two problems a broader outlook, we also consider the possibility that participants can express indifference, on the condition that the preference consistency has to be maintained. As an example, we propose a scheme in which all participants submit two (or just one in the roommates case) lists ranking the other two groups separately. The order of the combinations is decided by the sum of their ordinal numbers. Combinations are tied when the sums are equal. By introducing indifference, a hierarchy of stabilities can be defined. We prove that all stability definitions lead to NP-completeness for existence of a stable matching. [ABSTRACT FROM AUTHOR]