Skip to Main content Skip to Navigation

Combinatorial approaches for segmentingbacterium genomes

Abstract : Bacterium genome plasticity analysis can efficiently be performed by Long-Range PCR (Polymerase Chain Reaction). The first step requires to split the genome into hundreds of short overlapping segments which, after amplification, are used to sketch the profile of different bacterium strains. The segments to be amplified are determined using a reference bacterium strain. They have to cover the entire genome and to be of nearly identical size. In this report, we use an interval graph for presenting the segments and their position. We show that the most appropriate choice for such segments is equivalent to solving a kind of Shortest Path Problem on a subgraph of the interval graph called covering graph. We propose two optimization models for this problem. These models correspond to two criteria for measuring the quality of the covering; (i) the maximal deviation of the segments lengths from a given ideal length should be minimal, (ii) to find a length such that that maximal deviation from it is minimal. For each criterium we derive two algorithms of linear complexity in respect to the number of arcs in the graph.
Document type :
Complete list of metadatas
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:37:33 PM
Last modification on : Friday, July 10, 2020 - 4:21:03 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:35:29 PM


  • HAL Id : inria-00071730, version 1


Rumen Andonov, Nicola Yanev, Dominique Lavenier, Philippe Veber. Combinatorial approaches for segmentingbacterium genomes. [Research Report] RR-4853, INRIA. 2003. ⟨inria-00071730⟩



Record views


Files downloads