Approximate Common Intervals in Multiple Genome Comparison

Pierre Riou 1 Eric Rivals 1, * Annie Chateau 1
* 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.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

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)

Identifiers

Collections

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⟩

Share

Metrics

Record views

753

Files downloads

338