Search

Abstract: One of the most relevant topics in the analysis of biological networks is the identification of functional motifs inside a network. A recent approach introduced in literature, called Graph Motif, represents the network as a vertex-colored graph, and the motif as a multiset of colors. An occurrence of a motif in a vertex-colored graph is a connected induced subgraph of whose vertex set is colored exactly as . In this paper we investigate three different variants of the Graph Motif problem. The first two variants, Minimum Adding Motif (Min-Add Graph Motif) and Minimum Substitution Motif (Min-Sub Graph Motif), deal with approximate occurrences of a motif in the graph, while the third variant, Constrained Graph Motif (CGM), constrains the motif to contain a given set of vertices. We investigate the computational and parameterized complexity of the three problems. We show that Min-Add Graph Motifand Min-Sub Graph Motifare both NP-hard, even when is a set, and the graph is a tree with maximum degree in which each color appears at most twice. Then, we show that Min-Sub Graph Motifis fixed-parameter tractable when parameterized by the size of . Finally, we consider the parameterized complexity of the CGMproblem; we give a fixed-parameter algorithm for graphs of bounded treewidth, and show that the problem is W[2]-hard when parameterized by , even if the input graph has diameter . [Copyright &y& Elsevier]

Abstract: The Consensus Clustering problem has been introduced as an effective way to analyze the results of different microarray experiments (Filkov and Skiena (2004a,b) . The problem asks for a partition that summarizes a set of input partitions (each corresponding to a different microarray experiment) under a simple and intuitive cost. The problem on instances with two input partitions has a simple polynomial time algorithm, but it becomes APX-hard on instances with three input partitions. The quest for defining the boundary between tractable and intractable instances leads to the investigation of the restriction of Consensus Clustering when the output partition contains a fixed number of sets. In this paper, we give a randomized polynomial time approximation scheme for such problems, while proving its NP-hardness even for 2 output partitions, therefore definitively settling the approximation complexity of the problem. [Copyright &y& Elsevier]

Abstract: In comparative genomics, the first step of sequence analysis is usually to decompose two or more genomes into syntenic blocks that are segments of homologous chromosomes. For the reliable recovery of syntenic blocks, noise and ambiguities in the genomic maps need to be removed first. Maximal Strip Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff for reliably recovering syntenic blocks from genomic maps in the midst of noise and ambiguities. Given genomic maps as sequences of gene markers, the objective of MSR- is to find subsequences, one subsequence of each genomic map, such that the total length of syntenic blocks in these subsequences is maximized. For any constant , a polynomial-time -approximation for MSR- was previously known. In this paper, we show that for any , MSR- is APX-hard, even for the most basic version of the problem in which all gene markers are distinct and appear in positive orientation in each genomic map. Moreover, we provide the first explicit lower bounds on approximating MSR- for all . In particular, we show that MSR- is NP-hard to approximate within . From the other direction, we show that the previous -approximation for MSR- can be optimized into a polynomial-time algorithm even if is not a constant but is part of the input. We then extend our inapproximability results to several related problems including CMSR-, -gap-MSR-, and -gap-CMSR-. [Copyright &y& Elsevier]

Abstract: Simulation distances are essentially approximations of simulation which provide a measure of the extent by which behaviors in systems are inequivalent. In this paper, we consider the general quantitative model of weighted transition systems, where transitions are labeled with elements of a finite metric space. We study the so-called point-wise and accumulating simulation distances which provide extensions to the well-known Boolean notion of simulation on labeled transition systems. We introduce weighted process algebras for finite and regular behavior and offer sound and (approximate) complete inference systems for the proposed simulation distances. We also settle the algorithmic complexity of computing the simulation distances. [Copyright &y& Elsevier]

Abstract: In this paper, we consider single-machine scheduling problems under the job rejection constraint. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the single machine. However, the total rejection penalty of the rejected jobs cannot exceed a given upper bound. The objective is to find a schedule such that a given criterion is minimized, where is a non-decreasing function on the completion times of the accepted jobs. We analyze the computational complexities of the problems for distinct objective functions and present pseudo-polynomial-time algorithms. In addition, we provide a fully polynomial-time approximation scheme for the makespan problem with release dates. For other objective functions related to due dates, we point out that there is no approximation algorithm with a bounded approximation ratio. [Copyright &y& Elsevier]