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 :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00071730
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:37:33 PM
Last modification on : Friday, March 15, 2019 - 5:06:23 PM
Long-term archiving on : Sunday, April 4, 2010 - 10:35:29 PM

Identifiers

  • HAL Id : inria-00071730, version 1

Citation

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

Share

Metrics

Record views

360

Files downloads

182