 |
HAL UPEC - UPEM Portal |  |
 |
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.
Cited literature [11 references]
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 : Friday, December 18, 2020 - 5:12:01 PM
Long-term archiving on: : Saturday, December 31, 2011 - 2:21:01 AM
Contributor : Guillaume Blin <>
Submitted on : Friday, September 30, 2011 - 4:20:34 PM
Last modification on : Friday, December 18, 2020 - 5:12:01 PM
Long-term archiving on: : Saturday, December 31, 2011 - 2:21:01 AM
File
Hal.pdf
Files produced by the author(s)