Search

Finding cohesive subgraphs in a network is a well-known problem in graph theory. Several alternative formulations of cohesive subgraph have been proposed, a notable example being $s$-club, which is a subgraph where each vertex is at distance at most $s$ to the others. Here we consider the problem of covering a given graph with the minimum number of $s$-clubs. We study the computational and approximation complexity of this problem, when $s$ is equal to 2 or 3. First, we show that deciding if there exists a cover of a graph with three $2$-clubs is NP-complete, and that deciding if there exists a cover of a graph with two $3$-clubs is NP-complete. Then, we consider the approximation complexity of covering a graph with the minimum number of $2$-clubs and $3$-clubs. We show that, given a graph $G=(V,E)$ to be covered, covering $G$ with the minimum number of $2$-clubs is not approximable within factor $O(|V|^{1/2 -\varepsilon})$, for any $\varepsilon>0$, and covering $G$ with the minimum number of $3$-clubs is not approximable within factor $O(|V|^{1 -\varepsilon})$, for any $\varepsilon>0$. On the positive side, we give an approximation algorithm of factor $2|V|^{1/2}\log^{3/2} |V|$ for covering a graph with the minimum number of $2$-clubs., Accepted in IWOCA 2018

The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (called MaxCDP) has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate how the complexity of the problem depends on graph parameters (namely the number of vertices to remove to make the graph a collection of disjoint paths and the size of the vertex cover of the graph), which makes sense since graphs in social networks are not random and have structure. The problem was known to be hard to approximate in polynomial time and not fixed-parameter tractable (FPT) for the natural parameter. Here, we show that it is still hard to approximate, even in FPT-time. Finally, we introduce a new variant of the problem, called MaxCDDP, whose goal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of MaxCDP to this new variant, and we prove that unlike MaxCDP, MaxCDDP is already hard on graphs at distance two from disjoint paths., Comment: Journal version in JOCO

In this special issue, we present two of the papers presented at the 10th Workshop on Biomedical and Bioinformatics Challenges for Computer Science—BBC2017, held in Zurich, 12–14 June 2017.

Social interaction allows to support the disease management by creating online spaces where patients can interact with clinicians, and share experiences with other patients. Therefore, promoting targeted communication in online social spaces is a means to group patients around shared goals, offer emotional support, and finally engage patients in their healthcare decision making process. In this paper, we approach the argument from a theoretical perspective: we design an optimization problem aimed to encourage the creation of (induced) sub-networks of patients which, being recently diagnosed, wish to deepen the knowledge about their medical treatment with some other similar profiled patients, which have already been followed up by specific (even alternative) care centers. In particular, due to the computational hardness of the proposed problem, we provide approximated solutions based on distributed heuristics (i.e., Genetic Algorithms). Results are given for simulated data using Erdos-Renyi random graphs.

Reconciling gene trees with a species tree is a fundamental problem to understand the evolution of gene families. Many existing approaches reconcile each gene tree independently. However, it is well-known that the evolution of gene families is interconnected. In this paper, we extend a previous approach to reconcile a set of gene trees with a species tree based on segmental macro-evolutionary events, where segmental duplication events and losses are associated with cost $\delta$ and $\lambda$, respectively. We show that the problem is polynomial-time solvable when $\delta \leq \lambda$ (via LCA-mapping), while if $\delta > \lambda$ the problem is NP-hard, even when $\lambda = 0$ and a single gene tree is given, solving a long standing open problem on the complexity of the reconciliation problem. On the positive side, we give a fixed-parameter algorithm for the problem, where the parameters are $\delta/\lambda$ and the number $d$ of segmental duplications, of time complexity $O(\lceil \frac{\delta}{\lambda} \rceil^{d} \cdot n \cdot \frac{\delta}{\lambda})$. Finally, we demonstrate the usefulness of this algorithm on two previously studied real datasets: we first show that our method can be used to confirm or refute hypothetical segmental duplications on a set of 16 eukaryotes, then show how we can detect whole genome duplications in yeast genomes., Comment: 23 pages, 7 figures, WABI 2018

This is a corrigendum for our paper [1], as we have found that the first FPT algorithm for the Maximum-Duo Preservation String Mapping Problem we presented is incorrect. However, we show that, by slightly modifying the color-coding technique on which the algorithm is based, we can fix the error, thus giving a correct FPT algorithm for Maximum-Duo Preservation String Mapping Problem.

Background Given a gene family, the relations between genes (orthology/paralogy), are represented by a relation graph, where edges connect pairs of orthologous genes and “missing” edges represent paralogs. While a gene tree directly induces a relation graph, the converse is not always true. Indeed, a relation graph is not necessarily “satisfiable”, i.e. does not necessarily correspond to a gene tree. And even if that holds, it may not be “consistent”, i.e. the tree may not represent a true history in agreement with a species tree. Previous studies have addressed the problem of correcting a relation graph for satisfiability and consistency. Here we consider the weighted version of the problem, where a degree of confidence is assigned to each orthology or paralogy relation. We also consider a maximization variant of the unweighted version of the problem. Results We provide complexity and algorithmic results for the approximation of the considered problems. We show that minimizing the correction of a weighted graph does not admit a constant factor approximation algorithm assuming the unique game conjecture, and we give an n-approximation algorithm, n being the number of vertices in the graph. We also provide polynomial time approximation schemes for the maximization variant for unweighted graphs. Conclusions We provided complexity and algorithmic results for variants of the problem of correcting a relation graph for satisfiability and consistency. For the maximization variants we were able to design polynomial time approximation schemes, while for the weighted minimization variants we were able to provide the first inapproximability results.

LNCS, vol. 10043; International audience; The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (MaxCDP) has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate how the complexity of the problem depends on graph parameters (distance from disjoint paths and size of vertex cover), and that is not FPT-approximable. Moreover, we introduce a new variant of the problem, called MaxCDDP, whose goal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of MaxCDP to this new variant, and we prove that unlike MaxCDP, MaxCDDP is already hard on graphs at distance two from disjoint paths.

International audience

Motivation: Haplotype assembly is the computational problem of reconstructing haplotypes in diploid organisms and is of fundamental importance for characterizing the effects of single-nucleotide polymorphisms on the expression of phenotypic traits. Haplotype assembly highly benefits from the advent of ‘future-generation’ sequencing technologies and their capability to produce long reads at increasing coverage. Existing methods are not able to deal with such data in a fully satisfactory way, either because accuracy or performances degrade as read length and sequencing coverage increase or because they are based on restrictive assumptions. Results: By exploiting a feature of future-generation technologies—the uniform distribution of sequencing errors—we designed an exact algorithm, called HapCol, that is exponential in the maximum number of corrections for each single-nucleotide polymorphism position and that minimizes the overall error-correction score. We performed an experimental analysis, comparing HapCol with the current state-of-the-art combinatorial methods both on real and simulated data. On a standard benchmark of real data, we show that HapCol is competitive with state-of-the-art methods, improving the accuracy and the number of phased positions. Furthermore, experiments on realistically simulated datasets revealed that HapCol requires significantly less computing resources, especially memory. Thanks to its computational efficiency, HapCol can overcome the limits of previous approaches, allowing to phase datasets with higher coverage and without the traditional all-heterozygous assumption. Availability and implementation: Our source code is available under the terms of the GNU General Public License at http://hapcol.algolab.eu/. Contact: bonizzoni@disco.unimib.it Supplementary information: Supplementary data are available at Bioinformatics online.

In diploid genomes, haplotype assembly is the computational problem of reconstructing the two parental copies, called haplotypes, of each chromosome starting from sequencing reads, called fragments, possibly affected by sequencing errors. Minimum error correction (MEC) is a prominent computational problem for haplotype assembly and, given a set of fragments, aims at reconstructing the two haplotypes by applying the minimum number of base corrections. MEC is computationally hard to solve, but some approximation-based or fixed-parameter approaches have been proved capable of obtaining accurate results on real data. In this work, we expand the current characterization of the computational complexity of MEC from the approximation and the fixed-parameter tractability point of view. In particular, we show that MEC is not approximable within a constant factor, whereas it is approximable within a logarithmic factor in the size of the input. Furthermore, we answer open questions on the fixed-parameter tractability for parameters of classical or practical interest: the total number of corrections and the fragment length. In addition, we present a direct 2-approximation algorithm for a variant of the problem that has also been applied in the framework of clustering data. Finally, since polyploid genomes, such as those of plants and fishes, are composed of more than two copies of the chromosomes, we introduce a novel formulation of MEC, namely the k-ploid MEC problem, that extends the traditional problem to deal with polyploid genomes. We show that the novel formulation is still both computationally hard and hard to approximate. Nonetheless, from the parameterized point of view, we prove that the problem is tractable for parameters of practical interest such as the number of haplotypes and the coverage, or the number of haplotypes and the fragment length.

Background While tree-oriented methods for inferring orthology and paralogy relations between genes are based on reconciling a gene tree with a species tree, many tree-free methods are also available (usually based on sequence similarity). Recently, the link between orthology relations and gene trees has been formally considered from the perspective of reconstructing phylogenies from orthology relations. In this paper, we consider this link from a correction point of view. Indeed, a gene tree induces a set of relations, but the converse is not always true: a set of relations is not necessarily in agreement with any gene tree. A natural question is thus how to minimally correct an infeasible set of relations. Another natural question, given a gene tree and a set of relations, is how to minimally correct a gene tree so that the resulting gene tree fits the set of relations. Results We consider four variants of relation and gene tree correction problems, and provide hardness results for all of them. More specifically, we show that it is NP-Hard to edit a minimum of set of relations to make them consistent with a given species tree. We also show that the problem of finding a maximum subset of genes that share consistent relations is hard to approximate. We then demonstrate that editing a gene tree to satisfy a given set of relations in a minimum way is NP-Hard, where “minimum” refers either to the number of modified relations depicted by the gene tree or the number of clades that are lost. We also discuss some of the algorithmic perspectives given these hardness results.

A relation graph for a gene family is a graph with vertices representing the genes, edges connecting pairs of orthologous genes and “missing” edges representing paralogs. While a gene tree directly leads to a set of orthology and paralogy relations, the converse is not always true. Indeed a relation graph cannot necessarily be inferred from any tree, and even if it is “satisfiable” by a tree, this tree is not necessarily “consistent”, i.e. does not necessarily reflect a valid history for the genes, in agreement with a species tree. Here, we consider the problems of minimally correcting a relation graph for satisfiability and consistency, when a degree of confidence is assigned to each orthology or paralogy relation, leading to a weighted relation graph. We provide complexity and algorithmic results for minimizing corrections on a weighted graph, and also for the maximization variant of the problems for unweighted graphs.

The haplotyping problem has emerged in recent years as one of the most relevant problems in Computational Biology. In particular, in the Single Individual Haplotyping (SIH) problem, starting from a matrix of incomplete haplotype fragments, the goal is the reconstruction of the two complete haplotypes of an individual. In this paper we consider one of the variants of the Single Individual Haplotyping problem, the Longest Haplotyping Reconstruction (LHR) problem. We prove that the LHR problem is NP-hard even in the restricted case when the input matrix is error-free. Furthermore, we investigate the approximation complexity of the problem, and we show that the problem cannot be approximated within factor 2^l^o^g^^^@d^n^m for any constant @d

The Correlation Clustering problem has been introduced recently [N. Bansal, A. Blum, S. Chawla, Correlation Clustering, in: Proc. 43rd Symp. Foundations of Computer Science, FOCS, 2002, pp. 238-247] as a model for clustering data when a binary relationship between data points is known. More precisely, for each pair of points we have two scores measuring the similarity and dissimilarity respectively, of the two points, and we would like to compute an optimal partition where the value of a partition is obtained by summing up the similarity scores of pairs involving points from the same cluster and the dissimilarity scores of pairs involving points from different clusters. A closely related problem is Consensus Clustering, where we are given a set of partitions and we would like to obtain a partition that best summarizes the input partitions. The latter problem is a restricted case of Correlation Clustering. In this paper we prove that Minimum Consensus Clustering is APX-hard even for three input partitions, answering an open question in the literature, while Maximum Consensus Clustering admits a PTAS. We exhibit a combinatorial and practical frac(4, 5)-approximation algorithm based on a greedy technique for Maximum Consensus Clustering on three partitions. Moreover, we prove that a PTAS exists for Maximum Correlation Clustering when the maximum ratio between two scores is at most a constant. © 2007 Elsevier Inc. All rights reserved.

In this paper we consider the p-ary transitive reduction (TR p ) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. Special cases of TR p have been investigated before in different contexts; the best previous results are as follows: The minimum equivalent digraph problem, that correspond to a special case of TR1 with no critical edges, is known to be MAX-SNP-hard, admits a polynomial time algorithm with an approximation ratio of 1.617+e for any constant e>0 (Chiu and Liu in Sci. Sin. 4:1396–1400, 1965) and can be solved in linear time for directed acyclic graphs (Aho et al. in SIAM J. Comput. 1(2):131–137, 1972). A 2-approximation algorithm exists for TR1 (Frederickson and JaJa in SIAM J. Comput. 10(2):270–283, 1981; Khuller et al. in 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 937–938, 1999). In this paper, our contributions are as follows: We observe that TRp, for any integer p>0, can be solved in linear time for directed acyclic graphs using the ideas in Aho et al. (SIAM J. Comput. 1(2):131–137, 1972). We provide a 1.78-approximation for TR1 that improves the 2-approximation mentioned in (2) above. We provide a 2+o(1)-approximation for TRp on general graphs for any fixed prime p>1.

International audience; The new sequencing technologies, called next-generation se-quencing, provide a huge amount of data that can be used to reconstruct genomes. However, the methods applied to reconstruct genomes often are not able to reconstruct a complete genome and provide only an incomplete information. Here we consider two combinatorial problems that aim to reconstruct complete genomes by inserting a collection of missing genes. The first problem we consider, called One-sided scaffold filling, given an incomplete genome B and a complete genome A, asks for the insertion of missing genes into an incomplete genome B with the goal of maximizing the common adjacencies between genomes B (resulting from the insertion of missing genes in B) and A. The second problem, called Two-sided scaffold filling, given two incomplete genomes A, B, asks for the insertion of missing genes into both genomes so that the resulting genomes A and B have the same multiset of genes and the number of common adjacencies between A and B is maximized. Both problems were proved to be NP-hard, while their parameterized complexity, when the parameter is the number of common adjacencies of the resulting genomes, was left as an open problem. In this paper, we settle this open problem by presenting fixed-parameter algorithms for One-sided scaffold filling and Two-sided scaffold filling.

The Computer Journal, 58 (7), ISSN:0010-4620, ISSN:1460-2067

In several areas, for example in bioinformatics and in AI planning, the Shortest Common Superstring problem (SCS) and variants thereof have been successfully applied for string comparison. In this paper we consider two variants of SCS recently introduced, namely Restricted Common Superstring (RCS) and Swapped Common Superstring (SRCS). In RCS we are given a set $$S$$S of strings and a multiset $$\mathcal {M}$$M of symbols, and we look for an ordering $$\mathcal {M}_o$$Mo of $$\mathcal {M}$$M such that the number of input strings which are substrings of $$\mathcal {M}_o$$Mo is maximized. In SRCS we are given a set $$S$$S of strings and a text $$\mathcal {T}$$T, and we look for a swap ordering $$\mathcal {T}_o$$To of $$\mathcal {T}$$T (an ordering of $$\mathcal {T}$$T obtained by swapping only some pairs of adjacent symbols) such that the number of input strings which are substrings of $$\mathcal {T}_o$$To is maximized. In this paper we propose a multivariate algorithmic analysis of the complexity of the two problems, aiming at determining how different parameters influence the complexity of the two problems. We consider as interesting parameters the size of the solutions (that is the number of input strings contained in the computed superstring), the maximum length of the given input strings, the size of the alphabet over which the input strings range. First, we give two fixed-parameter algorithms, where the parameter is the size of the solution, for SRCS and lRCS (the RCS problem restricted to strings of length bounded by a parameter $$\ell $$l). Furthermore, we complement these results by showing that SRCS and lRCS do not admit a polynomial kernel unless $$NP \subseteq coNP/Poly$$NP⊆coNP/Poly. Then, we show that SRCS is APX-hard even when the input strings have length bounded by a constant (equal to $$10$$10) or are over a binary alphabet.

When tens and even hundreds of schemas are involved in the integration process, criteria are needed for choosing clusters of schemas to be integrated, so as to deal with the integration problem through an efficient iterative process. Schemas in clusters should be chosen according to cohesion and coupling criteria that are based on similarities and dissimilarities among schemas. In this paper, we propose an algorithm for a novel variant of the correlation clustering approach that addresses the problem of assisting a designer in integrating a large number of conceptual schemas. The novel variant introduces upper and lower bounds to the number of schemas in each cluster, in order to avoid too complex and too simple integration contexts respectively. We give a heuristic for solving the problem, being an NP hard combinatorial problem. An experimental activity demonstrates an appreciable increment in the effectiveness of the schema integration process when clusters are computed by means of the proposed algorithm w.r.t. the ones manually defined by an expert.

A central issue in biological data analysis is that uncertainty, resulting from different factors of variability, may change the effect of the events being investigated. Therefore, robustness is a fundamental step to be considered. Robustness refers to the ability of a process to cope well with uncertainties, but the different ways to model both the processes and the uncertainties lead to many alternative conclusions in the robustness analysis. In this paper we apply a framework allowing to deal with such questions for mass spectrometry data. Specifically, we provide robust decisions when testing hypothesis over a case/control population of subject measurements (i.e. proteomic profiles). To this concern, we formulate (i) a reference model for the observed data (i.e., graphs), (ii) a reference method to provide decisions (i.e., test of hypotheses over graph properties) and (iii) a reference model of variability to employ sources of uncertainties (i.e., random graphs). We apply these models to a realcase study, analyzing the mass spectrometry profiles of the most common type of Renal Cell Carcinoma; the Clear Cell variant.

Gene tree correction with respect to a given species tree is a problem that has been recently proposed in order to better understand the evolution of gene families. One of the combinatorial methods proposed to tackle with this problem aims to correct a gene tree by removing the minimum number of leaves/labels (Minimum Leaf Removal and Minimum Label Removal, respectively). The two problems have been shown to be APX-hard, and fixed-parameter tractable, when parameterized by the number of leaves/labels removed. In this paper, we focus on the approximation complexity of these two problems and we show that they are not approximable within factor b log ? m , where m is the number of leaves of the species tree and b 0 is a constant. Furthermore, we introduce and study two new variants of the problem, where the goal is the correction of a gene tree with the minimum number of leaf/label modifications (Minimum Leaf Modification and Minimum Label Modification, respectively). We show that the two modification problems, differently from the removal versions, are unlikely to be fixed-parameter tractable. More precisely, we prove that the Minimum Leaf Modification problem is W 1 ] -hard, when parameterized by the number of leaf modifications, and that the Minimum Label Modification problem is W 2 ] -hard, when parameterized by the number of label modifications.

The general problem of reconciling the information from evolutionary trees representing the relationships between distinct gene families is of great importance in bioinformatics and has been popularized among the computer science researchers by Ma et al. [From gene trees to species trees, SIAM J. Comput. 30(3) (2000) 729–752] where the authors pose the intriguing question if a certain definition of minimum tree that reconciles a gene tree and a species tree is correct. We answer affirmatively to this question; moreover, we show an efficient algorithm for computing such minimum-leaf reconciliation trees and prove the uniqueness of such trees. We then tackle some different versions of the biological problem by showing that the exemplar problem, arising from the exemplar analysis of multigene genomes, is NP-hard even when the number of copies of a given label is at most two. Finally, we introduce two novel formulations for the problem of recombining evolutionary trees, extending the gene duplication problem studied in [Ma et al., From gene trees to species trees, SIAM J. Comput. 30(3) (2000) 729–752; M. Fellows et al., On the multiple gene duplication problem, in: Proc. Ninth Internat. Symp. on Algorithms and Computation (ISAAC98), 1998; R. Page, Maps between trees and cladistic analysis of historical associations among genes, Systematic Biology 43 (1994) 58–77; R.M. Page, J. Cotton, Vertebrate phylogenomics: reconciled trees and gene duplications, in: Proc. Pacific Symp. on Biocomputing 2002 (PSB2002), 2002, pp. 536–547; R. Guigò et al., Reconstruction of ancient molecular phylogeny, Mol. Phy. and Evol. 6(2) (1996) 189–213], and we give an exact algorithm (via dynamic programming) for one of these formulations.

The investigation of genetic differences among humans has given evidence that mutations in DNA sequences are responsible for some genetic diseases. The most common mutation is the one that involves only a single nucleotide of the DNA sequence, which is called a single nucleotide, polymorphism (SNP). As a consequence, computing a complete map of all SNPs occurring in the human populations is one of the primary goals of recent studies in human genomics. The construction of such a map requires to determine the DNA sequences that from all chromosomes. In diploid organisms like humans, each chromosome consists of two sequences called haplotypes. Distinguishing the information contained in both haplotypes when analyzing chromosome sequences poses several new computational issues which collectively form a new emerging topic of Computational Biology known as Haplotyping. This paper is a comprehensive study of some new combinatorial approaches proposed in this research area and it mainly focuses on the formulations and algorithmic solutions of some basic biological problems. Three statistical approaches are briefly discussed at the end of the paper.

The reconciliation of a gene tree and a species tree is a well-known method to understand the evolution of a gene family in order to identify which evolutionary events (speciations, duplications and losses) occurred during gene evolution. Since reconciliation is usually affected by errors in the gene trees, they have to be preprocessed before the reconciliation process. A method to tackle with this problem aims to correct a gene tree by removing the minimum number of leaves (Minimum Leaf Removal). In this paper we show that Minimum Leaf Removal is not approximable within factor b logm, where m is the number of leaves of the species tree and b > 0 is a constant. Furthermore, we introduce a new variant of the problem, where the goal is the correction of a gene tree with the minimum number of leaf modifications. We show that this problem, differently from the removal version, is W[1]-hard, when parameterized by the number of leaf modifications. © 2014 Springer International Publishing.

Reconciliation consists in mapping a gene tree T into a species tree S, and explaining the incongruence between the two as evidence for duplication, loss and other events shaping the gene family represented by the leaves of T. When S is unknown, the Species Tree Inference Problem is to infer, from a set of gene trees, a species tree leading to a minimum reconciliation cost. As reconciliation is very sensitive to errors in T, gene tree correction prior to reconciliation is a fundamental task. In this paper, we investigate the complexity of four different combinatorial approaches for deleting misplaced leaves from T. First, we consider two problems (Minimum Leaf Removal and Minimum Species Removal) related to the reconciliation of T with a known species tree S. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) so that T is ''MD-consistent'' with S. Second, we consider two problems (Minimum Leaf Removal Inference and Minimum Species Removal Inference) related to species tree inference. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) from T so that there exists a species tree S such that T is MD-consistent with S. We prove that Minimum Leaf Removal and Minimum Species Removal are APX-hard, even when each label has at most two occurrences in the input gene tree, and we present fixed-parameter algorithms for the two problems. We prove that Minimum Leaf Removal Inference is not only NP-hard, but also W[2]-hard and inapproximable within factor clnn, where n is the number of leaves in the gene tree. Finally, we show that Minimum Species Removal Inference is NP-hard and W[2]-hard, when parameterized by the size of the solution, that is the minimum number of species removals.

Motivation: Large-scale methods for inferring gene trees are error-prone. Correcting gene trees for weakly supported features often results in non-binary trees, i.e. trees with polytomies, thus raising the natural question of refining such polytomies into binary trees. A feature pointing toward potential errors in gene trees are duplications that are not supported by the presence of multiple gene copies. Results: We introduce the problem of refining polytomies in a gene tree while minimizing the number of created non-apparent duplications in the resulting tree. We show that this problem can be described as a graph-theoretical optimization problem. We provide a bounded heuristic with guaranteed optimality for well-characterized instances. We apply our algorithm to a set of ray-finned fish gene trees from the Ensembl database to illustrate its ability to correct dubious duplications. Availability and implementation: The C++ source code for the algorithms and simulations described in the article are available at http://www-ens.iro.umontreal.ca/~lafonman/software.php. Contact: lafonman@iro.umontreal.ca or mabrouk@iro.umontreal.ca Supplementary information: Supplementary data are available at Bioinformatics online.

International audience; Longest common subsequence is a widely used measure to compare strings, in particular in Computational Biology. Recently, several variants of the longest common subsequence have been introduced to tackle with the comparison of genomes. In particular, the Repetition Free Longest Common Subsequence problem (RFLCS) is a variant of the LCS problem that asks for a longest common subsequence problem of two input strings with no repetition of symbols. In this paper, we investigate the parameterized complexity of RFLCS. First, we show that the problem does not admit a polynomial kernel. Then, we present an FPT algorithm for the RFLCS problem, improving the time complexity of the existent FPT algorithm.

Publishing personal data without giving up privacy is becoming an increasingly important problem in different fields. In the last years, different interesting approaches have been proposed, i.e. k-Anonymity and l-Diversity. Given an input table, these approaches partition its rows so that the computed partition satisfies some constraint, in order to prevent the inference of the individuals the data belong to. Then, the rows in a same set of the partition are related to the same rows by suppressing some of their entries. Here we focus on the l-Diversity problem, where the attributes of the input table are distinguished in sensitive attributes and quasi-identifier attributes. The goal is to partition the rows of the input table, so that each set C of the partition contains at most |C|/l rows having a specific value in the sensitive attribute, and the number of suppressions is minimized. In this paper we investigate the approximation and parameterized complexity of l-Diversity. First, we prove that the problem is not approximable within factor c ln l, for some constant c>0, even if the input table consists of only two columns, and that the problem is APX-hard, even if l=4 and the input table contains exactly three columns. Then we give an approximation algorithm of factor m (where m+1 is the number of columns in the input table), when the sensitive attribute ranges over an alphabet of constant size. Concerning the parameterized complexity, we prove that the problem is W[1]-hard when parameterized by the cost-bound, by l, and by the size of the alphabet. Then we prove that the problem admits a fixed-parameter algorithm when both the maximum number of different values in a column and the number of columns are parameters

The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate the approximation and parameterized complexity of the problem. First, we show that, for any constant ε &gt, 0, the problem is not approximable within factor c1-ε, where c is the number of colors, and that the corresponding decision problem is W[1]-hard when parametrized by the number of disjoint paths. Then, we present a fixed-parameter algorithm for the problem parameterized by the number and the length of the disjoint paths.

The Minimum Rooted Triplet Inconsistency (MinRTI) problem represents a key computational task in the construction of phylogenetic trees. Inspired by Aho et al’s seminal paper and Bryant’s thesis, we describe an edge-labelled multigraph problem, Minimum Dissolving Graph (MinDG) and show that it is equivalent to MinRTI. We prove that on an n-vertex graph, for every e > 0, MinDG is hard to approximate within a factor in \(O(2^{\log^{1-\ensuremath{\varepsilon}}n})\), even on trees formed by multi-edges. Via a further reduction, this result applies to MinRTI, resolving the open question of whether there is a sub-linear approximation factor for MinRTI. In addition, we provide polynomial-time algorithms that return optimal solutions when the input multigraph is restricted to a multi-edge path or a simple tree.

International audience; 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 M as a multiset of colors. An occurrence of a motif M in a vertex-colored graph G is a connected induced subgraph of G whose vertex set is colored exactly as M. 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 M is a set, and the graph is a tree with maximum degree 4 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 M. 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 ∣M∣, even if the input graph has diameter 2.

International audience; The Minimum Duplication problem is a well-known problem in phylogenetics and comparative genomics. Given a set of gene trees, the Minimum Duplication problem asks for a species tree that induces the minimum number of gene duplications in the input gene trees. Recently, a variant of the Minimum Duplication problem, called Minimum Duplication Bi-partite, has been introduced, where the goal is to find all pre-duplications, that is duplications that in the evolution precede the first speciation with respect to a species tree. In this paper, we investigate the complexity of both Minimum Duplication and Minimum Duplication Bipartite. First of all, we prove that the Minimum Duplication problem is APX-hard, even when the input consists of five uniquely leaf-labelled gene trees (improving upon known results on the complexity of the problem). Then, we show that the Minimum Duplication Bipartite problem can be solved efficiently with a randomized algorithm when the input gene trees have bounded depth. An extended abstract of this paper appeared in SOFSEM 2012.

The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the $k$-anonymity. This approach requires that the rows of a table are partitioned in clusters of size at least $k$ and that all the rows in a cluster become the same tuple, after the suppression of some entries. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be APX-hard even when the records values are over a binary alphabet and $k=3$, and when the records have length at most 8 and $k=4$ . In this paper we study how the complexity of the problem is influenced by different parameters. In this paper we follow this direction of research, first showing that the problem is W[1]-hard when parameterized by the size of the solution (and the value $k$). Then we exhibit a fixed parameter algorithm, when the problem is parameterized by the size of the alphabet and the number of columns. Finally, we investigate the computational (and approximation) complexity of the $k$-anonymity problem, when restricting the instance to records having length bounded by 3 and $k=3$. We show that such a restriction is APX-hard.

The binary perfect phylogeny model is too restrictive to model biological events such as back mutations. In this paper we consider a natural generalization of the model that allows a special type of back mutation. We investigate the problem of reconstructing a near perfect phylogeny over a binary set of characters where characters are persistent: characters can be gained and lost at most once. Based on this notion, we define the problem of the Persistent Perfect Phylogeny (referred as P-PP). We restate the P-PP problem as a special case of the Incomplete Directed Perfect Phylogeny, called Incomplete Perfect Phylogeny with Persistent Completion, (refereed as IP-PP), where the instance is an incomplete binary matrix M having some missing entries, denoted by symbol ?, that must be determined (or completed) as 0 or 1 so that M admits a binary perfect phylogeny. We show that the IP-PP problem can be reduced to a problem over an edge colored graph since the completion of each column of the input matrix can be represented by a graph operation. Based on this graph formulation, we develop an exact algorithm for solving the P-PP problem that is exponential in the number of characters and polynomial in the number of species., Comment: 13 pages, 3 figures

Publishing personal data without giving up privacy is becoming an increasingly important problem in different fields. In the last years, different interesting approaches have been proposed, i.e. k-Anonymity and l-Diversity. Given an input table, these approaches partition its rows so that the computed partition satisfies some constraint, in order to prevent the inference of the individuals the data belong to. Then, the rows in a same set of the partition are related to the same rows by suppressing some of their entries. Here we focus on the l-Diversity problem, where the attributes of the input table are distinguished in sensitive attributes and quasi-identifier attributes. The goal is to partition the rows of the input table, so that each set C of the partition contains at most 1l |C| rows having a specific value in the sensitive attribute, and the number of suppressions is minimized. In this paper we investigate the approximation and parameterized complexity of l-Diversity. First, we prove that the problem is not approximable within factor c ln l, for some constant c > 0, even if the input table consists of only two columns, and that the problem is APX-hard, even if l = 4 and the input table contains exactly three columns. Then we give an approximation algorithm of factor m (where m+1 is the number of columns in the input table), when the sensitive attribute ranges over an alphabet of constant size. Concerning the parameterized complexity, we prove that the problem is W[1]-hard when parameterized by the cost-bound, by l, and by the size of the alphabet. Then we prove that the problemadmits a fixed-parameter algorithm when both the maximum number of different values in a column and the number of columns are parameters.

Searching for motifs in graphs has become a crucial problem in the analysis of biological networks. In the context of metabolic network analysis, Lacroix et al. [V. Lacroix, C.G. Fernandes, M.-F. Sagot, IEEE/ACM Transactions on Computational Biology and Bioinfor-matics 3 (4) (2006) 360-368] introduced the NP-hard general problem of finding occurrences of motifs in vertex-colored graphs, where a motifM is a multiset of colors and an occurrence of M in a vertex-colored graph G, called the target graph, is a subset of vertices that induces a connected graph and the multiset of colors induced by this subset is exactly the motif. Pursuing the line of research pioneered by Lacroix et al. and aiming at dealing with approximate solutions, we consider in this paper the above-mentioned problem in two of its natural optimization forms, referred hereafter as the Min-CC and the Maximum Motif problems. The Min-CC problem seeks for an occurrence of a motif M in a vertex-colored graph G that induces a minimum number of connected components whereas the Maximum Motif problem is concerned with finding a maximum cardinality submotif M^'@?M that occurs as a connected motif in G. We prove the Min-CC problem to be APX-hard even in the extremal case where the motif is a set and the target graph is a path. We complement this result by giving a polynomial-time algorithm in case the motif is built upon a fixed number of colors and the target graph is a path. Also, extending [M. Fellows, G. Fertin, D. Hermelin, S. Vialette, in: Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 4596, Springer, 2007, pp. 340-351], we prove the Min-CC problem to be fixed-parameter tractable when parameterized by the size of the motif, and we give a faster algorithm in case the target graph is a tree. Furthermore, we prove the Min-CC problem for trees not to be approximable within ratio clogn for some constant c>0, where n is the order of the target graph, and to be W[2]-hard when parameterized by the number of connected components in the occurrence of the motif. Finally, we give an exact exponential-time algorithm for the Min-CC problem in case the target graph is a tree. We prove that the Maximum Motif problem is APX-hard even in the case where the target graph is a tree of maximum degree 3, the motif is actually a set and each color occurs at most twice in the tree. Next, we strengthen this result by proving that the problem is not approximable within factor 2^l^o^g^^^@d^n, for any constant @d

The problem of publishing personal data without giving up privacy is be- coming increasingly important. An interesting formalization recently proposed is the k-anonymity. This approach requires that the rows in a table are clustered in sets of size at least k and that all the rows in a cluster become the same tuple, after the suppression of some records. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be NP-hard when the values are over a ternary alphabet, k = 3 and the rows length is unbounded. In this paper we give a lower bound on the approximation factor that any polynomial-time algorithm can achieve on two restrictions of the problem, namely (i) when the records values are over a binary alphabet and k = 3, and (ii) when the records have length at most 8 and k = 4, showing that these restrictions of the problem are APX-hard

The problem of clustering fingerprint vectors with missing values is an interesting problem in Computational Biology that has been proposed in Figueroa et al. (J. Comput. Biol. 11(5):887-901, 2004). In this paper we show some improvements in closing the gaps between the known lower bounds and upper bounds on the approximability of variants of the biological problem. Moreover, we have studied two additional variants of the original problem proposed in Figueroa et al. (Proc. 11th Computing: The Australasian Theory Symposium (CATS), CRPIT, vol. 41, pp. 57-60, 2005). We prove that all such problems are APX-hard even when each fingerprint contains only two unknown positions and we present a greedy algorithm that has constant approximation factors for these variants. Despite the hardness of these restricted versions of the problem, we show that the general clustering problem on an unbounded number of missing values such that they occur for every fixed position of an input vector in at most one fingerprint is polynomial time solvable

In Computational Biology, the notion of phylogeny has become synonymous with tree-like evolution. Recent advances in the Life Sciences have suggested that evolution has a much more diverse course. In this paper we will survey some of the models that have been proposed to overcome the limitations of using phylogenies to represent evolutionary histories.

We consider a variant of the classical Longest Common Subsequence problem called Doubly-Constrained Longest Common Subsequence (DC-LCS). Given two strings s"1 and s"2 over an alphabet @S, a set C"s of strings, and a function C"o:@S->N, the DC-LCS problem consists of finding the longest subsequence s of s"1 and s"2 such that s is a supersequence of all the strings in C"s and such that the number of occurrences in s of each symbol @[email protected][email protected] is upper bounded by C"o(@s). The DC-LCS problem provides a clear mathematical formulation of a sequence comparison problem in Computational Biology and generalizes two other constrained variants of the LCS problem that have been introduced previously in the literature: the Constrained LCS and the Repetition-Free LCS. We present two results for the DC-LCS problem. First, we illustrate a fixed-parameter algorithm where the parameter is the length of the solution which is also applicable to the more specialized problems. Second, we prove a parameterized hardness result for the Constrained LCS problem when the parameter is the number of the constraint strings (|C"s|) and the size of the alphabet @S. This hardness result also implies the parameterized hardness of the DC-LCS problem (with the same parameters) and its NP-hardness when the size of the alphabet is constant.

The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization recently proposed is the k-anonymity. This approach requires that the rows in a table are clustered in sets of size at least k and that all the rows in a cluster become the same tuple, after the suppression of some records. The natural optimization problem, where the goal is to minimize the number of suppressed entries, is known to be NP-hard when the values are over a ternary alphabet, k = 3 and the rows length is unbounded. In this paper we give a lower bound on the approximation factor that any polynomial-time algorithm can achive on two restrictions of the problem,namely (i) when the records values are over a binary alphabet and k = 3, and (ii) when the records have length at most 8 and k = 4, showing that these restrictions of the problem are APX-hard., 21 pages, A short version of this paper has been accepted in FCT 2009 - 17th International Symposium on Fundamentals of Computation Theory

Searching for motifs in graphs has become a crucial problem in the analysis of biological networks. In this context, different graph motif problems have been considered [13,7,5]. Pursuing a line of research pioneered by Lacroix et al. [13], we introduce in this paper a new graph motif problem: given a vertex colored graph G and a motif $\mathcal{M}$, where a motif is a multiset of colors, find a maximum cardinality submotif $\mathcal{M}' \subseteq \mathcal{M}$ that occurs as a connected motif in G . We prove that the problem is APX-hard even in the case where the target graph is a tree of maximum degree 3, the motif is actually a set and each color occurs at most twice in the tree. Next, we strengthen this result by proving that the problem is not approximable within factor $2^{\rm {log^{\delta} n}}$, for any constant *** < 1, unless NP *** DTIMEclass(2POLY log n). We complement these results by presenting two fixed-parameter algorithms for the problem, where the parameter is the size of the solution. Finally, we give exact fast exponential-time algorithms for the problem.

In this paper we present Farfalla, a web tool designed to support people with various limitations, ranging between mobility problems and visual impairments. The main goal of Farfalla is to integrate typical Assistive Technology functionalities into a web-based platform in order to enable users with disabilities to browse web pages and to fill forms using different input and output methods. The project is still in progress: the user interface and one of the possible input methods have already been prototyped, while some other functionalities have still to be developed.

In this paper we introduce a new method of combined synthesis and inference of biological signal transduction networks. A main idea of our method lies in representing observed causal relationships as network paths and using techniques from combinatorial optimization to find the sparsest graph consistent with all experimental observations. Our contributions are twofold: on the theoretical and algorithmic side, we formalize our approach, study its computational complexity and prove new results for exact and approximate solutions of the computationally hard transitive reduction substep of the approach. On the application side, we validate the biological usability of our approach by successfully applying it to a previously published signal transduction network by Li et al. [20] and show that our algorithm for the transitive reduction substep performs well on graphs with a structure similar to those observed in transcriptional regulatory and signal transduction networks.