Tractability results for the Double-Cut-and-Join circular median problem

2011/11/24 by Ahmad Mahmoody-Ghaidary, Mahmoody-Ghaidary, Ahmad, Cedric Chauve +3
Computer Science · #68R10 #90C27 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.1 #acm:68R10 #acm:90C27 #cs.DM #cs.DS #msc:68R10 #msc:90C27

paper · pdf · doi:10.48550/arxiv.1111.5872

12 pages, 6 figures, submitted

arxiv created 2011/11/24 · arxiv updated 2011/11/28

Abstract

The circular median problem in the Double-Cut-and-Join (DCJ) distance asks to find, for three given genomes, a fourth circular genome that minimizes the sum of the mutual distances with the three other ones. This problem has been shown to be NP-complete. We show here that, if the number of vertices of degree 3 in the breakpoint graph of the three input genomes is fixed, then the problem is tractable

Related

• Investigating the complexity of the double distance problems
• Complexity of the Swap Median and Swap Closest Problems
• A framework for cost-constrained genome rearrangement under Double Cut and Join
• On the Matrix Median Problem
• A New Linear Time Algorithm to Compute the Genomic Distance Via the Double Cut and Join Distance