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 [Burnaby]
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.
Document type :
Conference papers
Complete list of metadatas

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 : Wednesday, June 26, 2019 - 4:28:03 PM
Long-term archiving on : 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

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

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

220

Files downloads

250

Contact

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