Approximate Common Intervals in Multiple Genome Comparison

Pierre Riou 1 Eric Rivals 1, * Annie Château 1
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
Fang-Xiang Wu and Mohammed Zaki and Shinichi Morishita. BIBM'11: Bioinformatics and Biomedicine, Nov 2011, Atlanta, United States. IEEE Computer Society, pp.131-134, 2011, 〈http://www.cs.gsu.edu/BIBM2011/〉. 〈10.1109/BIBM.2011.96〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00659473
Contributeur : Riou Pierre <>
Soumis le : jeudi 12 janvier 2012 - 18:14:13
Dernière modification le : jeudi 11 janvier 2018 - 06:26:12
Document(s) archivé(s) le : mardi 13 décembre 2016 - 22:22:32

Fichier

BIBM_ApproximateCommonInterval...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre Riou, Eric Rivals, Annie Château. Approximate Common Intervals in Multiple Genome Comparison. Fang-Xiang Wu and Mohammed Zaki and Shinichi Morishita. BIBM'11: Bioinformatics and Biomedicine, Nov 2011, Atlanta, United States. IEEE Computer Society, pp.131-134, 2011, 〈http://www.cs.gsu.edu/BIBM2011/〉. 〈10.1109/BIBM.2011.96〉. 〈lirmm-00659473〉

Partager

Métriques

Consultations de la notice

164

Téléchargements de fichiers

158