The breakpoint distance for signed sequences

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.
Liste complète des métadonnées

Cited literature [11 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620356
Contributor : Guillaume Blin <>
Submitted on : Friday, September 30, 2011 - 4:20:34 PM
Last modification on : Thursday, April 5, 2018 - 10:36:49 AM
Document(s) archivé(s) le : Saturday, December 31, 2011 - 2:21:01 AM

File

Hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620356, version 1

Collections

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. pp.3-16. ⟨hal-00620356⟩

Share

Metrics

Record views

207

Files downloads

246