Approximate Common Intervals in Multiple Genome Comparison - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2011

Approximate Common Intervals in Multiple Genome Comparison


We consider the problem of inferring approximate common intervals of multiple genomes. Genomes are modelled as sequences of homologous genes families identifiers, and approximate common intervals represent conserved regions possibly showing rearrangements, as well as repetitions, or insertions/deletions. This problem is already known, but existing approaches are not incremental and somehow limited to special cases. We adopt a simple, classical graph-based approach, where the vertices of the graph represent the exact common intervals of the sequences (\ie, regions containing the same gene set), and where edges link vertices that differ by less than $\delta$ elements (with $\delta$ being parameter). With this model, approximate gene clusters are maximal cliques of the graph: computing them can exploit known and well designed algorithms. For a proof of concept, we applied the method to several datasets of bacterial genomes and compared the two maximal cliques algorithms, a static and a dynamic one. While being quite flexible, this approach opens the way to a combinatorial characterization of genomic rearrangements in terms of graph substructures.
Fichier principal
Vignette du fichier
BIBM_ApproximateCommonIntervals.pdf (175.18 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00659473 , version 1 (12-01-2012)



Pierre Riou, Eric Rivals, Annie Chateau. Approximate Common Intervals in Multiple Genome Comparison. BIBM'11: Bioinformatics and Biomedicine, Nov 2011, Atlanta, United States. pp.131-134, ⟨10.1109/BIBM.2011.96⟩. ⟨lirmm-00659473⟩
174 View
270 Download



Gmail Facebook X LinkedIn More