The breakpoint distance for signed sequences - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2004

The breakpoint distance for signed sequences

Résumé

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.
Fichier principal
Vignette du fichier
Hal.pdf (354.08 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00620356 , version 1 (30-09-2011)

Identifiants

  • HAL Id : hal-00620356 , version 1

Citer

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. pp.3-16. ⟨hal-00620356⟩
184 Consultations
277 Téléchargements

Partager

Gmail Facebook X LinkedIn More