# Approximate Common Intervals in Multiple Genome Comparison

* Corresponding author
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Mots-clés :
Document type :
Conference papers
Domain :

Cited literature [13 references]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00659473
Contributor : Riou Pierre <>
Submitted on : Thursday, January 12, 2012 - 6:14:13 PM
Last modification on : Friday, March 15, 2019 - 5:02:19 PM
Long-term archiving on : Tuesday, December 13, 2016 - 10:22:32 PM

### File

BIBM_ApproximateCommonInterval...
Files produced by the author(s)

### Citation

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⟩

Record views