Projet ANR graal - Publications

Perfect sorting by reversals is not always difficult

S. Bérard, A. Bergeron, C. Chauve and C. Paul

Abstract: We propose new algorithms for computing pairwise rearrangement scenarios that conserve the combinatorial structure of genomes. More precisely, we investigate the problem of sorting signed permutations by reversals without breaking common intervals.  We describe a combinatorial framework for this problem that allows to characterize classes of signed permutations for which one can compute in polynomial time a shortest reversal scenario that conserves all common intervals. In particular we define a class of permutations for which this computation can be done in linear time with a very simple algorithm that does not rely on the classical Hannenhalli-Pevzner theory for sorting by reversals. We apply these methods to the computation of rearrangement scenarios between permutations obtained from 16 synteny blocks of the X chromosomes of the human, mouse and rat.

Keywords: Evolution scenarios, reversals, common intervals, modular decomposition

Download pdf

Interval completion with few edges.

P. Heggernes, C. Paul, J.A. Telle and Y. Villanger

Abstract: We present an algorithm with runtime O(k^{2k}n^3m) for the following NP-complete problem: Given an arbitrary graph G$ on n vertices and m edges, can we obtain an interval graph by adding at most k new edges to G? This resolves the long-standing open question, first posed by Kaplan, Shamir and Tarjan, of whether this problem could be solved in time f(k).n^{O(1)}. The problem has applications in Physical Mapping of DNA and in Profile Minimization for Sparse Matrix Computations. For the first application, our results show tractability for the case of a small number k of false negative errors, and for the second, a small number k of zero elements in the envelope.

Our algorithm performs bounded search among possible ways of adding edges to a graph to obtain an interval graph, and combines this with a greedy algorithm when graphs of a certain structure are reached by the search. The presented result is surprising, as it was not believed that a bounded search tree algorithm would suffice to answer the open question affirmatively.

Keywords: Interval graphs, fixed parameterized complexity

Download pdf

Dynamic distance hereditary graphs using split decomposition

Abstract: The problem of maintaining a representation of a dynamic graph as long as a certain property is satisfied, has recently been considered for a number of properties. This paper presents an optimal algorithm for this problem on vertex-dynamic connected distance hereditary graphs: both vertex insertion and deletion have complexity O(d), where d is the degree of the vertex involved in the modification. Our vertex-dynamic algorithm is competitive with the existing linear time recognition algorithms of distance hereditary graphs, and is also simpler. To achieve this, we revisit the split decomposition by which distance hereditary graphs are known to be completely decomposable.  We propose a formulation of this decomposition in terms of graph-labelled trees. Doing so, we are also able to derive an intersection model for distance hereditary graphs, which answers an open problem.

Keywords: Graph decomposition, dynamic graph algorithms, distance hereditary graphs

Download pdf