The breakpoint distance for signed sequences

Guillaume Blin 1 Guillaume Fertin 1 Cedric Chauve 2
1 LINA - Laboratoire d'Informatique de Nantes Atlantique
2 Department of Mathematics
Abstract : We consider the problem of estimating the rearrangement distance in terms of reversals, insertion and deletion between two genomes, G and H with possibly multiple genes from the same gene family. We define a notion of breakpoint distance for this problem, based on matching genes from the same family between G and H. We show that this distance is a good approximation of the edit distance, but NP-hard to compute, even when just one family of genes is non-trivial. We also propose a branch-and-cut exact algorithm for the computation of the breakpoint distance.
Type de document :
Communication dans un congrès
1st Conference on Algorithms and Computational Methods for biochemical and Evolutionary Networks (CompBioNets'04), Dec 2004, Recife, Brazil, Brazil. King's College London publications, 3, pp.3-16, 2004, Texts in Algorithms
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger
https://hal-upec-upem.archives-ouvertes.fr/hal-00620356
Contributeur : Guillaume Blin <>
Soumis le : vendredi 30 septembre 2011 - 16:20:34
Dernière modification le : jeudi 5 avril 2018 - 10:36:49
Document(s) archivé(s) le : samedi 31 décembre 2011 - 02:21:01

Fichier

Hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00620356, version 1

Collections

LINA | UNIV-NANTES | LINA-COMBI | UPEC-UPEM

Citation

Guillaume Blin, Guillaume Fertin, Cedric Chauve. The breakpoint distance for signed sequences. 1st Conference on Algorithms and Computational Methods for biochemical and Evolutionary Networks (CompBioNets'04), Dec 2004, Recife, Brazil, Brazil. King's College London publications, 3, pp.3-16, 2004, Texts in Algorithms. 〈hal-00620356〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

204

Téléchargements de fichiers

236

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD