Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Guillaume Blin Connect in order to contact the contributor
Submitted on : Friday, September 30, 2011 - 4:20:34 PM
Last modification on : Wednesday, April 27, 2022 - 4:22:23 AM
Long-term archiving on: : Saturday, December 31, 2011 - 2:21:01 AM


Files produced by the author(s)


  • HAL Id : hal-00620356, version 1


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⟩



Record views


Files downloads