Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion

Computing the edit distance between two genomes under certain operations is a basic problem in the study of genome evolution. The double-cut-and-join (DCJ) model has formed the basis for most algorithmic research on rearrangements over the last few years. The edit distance under the DCJ model can be easily computed for genomes without duplicate genes. In this paper, we study the edit distance for genomes with duplicate genes under a model that includes DCJ operations, insertions and deletions. We prove that computing the edit distance is equivalent to finding the optimal cycle decomposition of the corresponding adjacency graph, and give an approximation algorithm with an approximation ratio of 1.5 + L.


Published in:
BMC Bioinformatics, 13, S19
Presented at:
10th Workshop on Comparative Genomics RECOMB-CG'12, 2012
Year:
2012
Publisher:
London, Biomed Central Ltd
ISSN:
1471-2105
Laboratories:




 Record created 2013-03-28, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)