Algorithms for sorting unsigned linear genomes by the DCJ operations.
BACKGROUND
The double cut and join operation (abbreviated as DCJ) has been extensively used for genomic rearrangement. Although the DCJ distance between signed genomes with both linear and circular (uni- and multi-) chromosomes is well studied, the only known result for the NP-complete unsigned DCJ distance problem is an approximation algorithm for unsigned linear unichromosomal genomes. In this article, we study the problem of computing the DCJ distance on two unsigned linear multichromosomal genomes (abbreviated as UDCJ).


RESULTS
We devise a 1.5-approximation algorithm for UDCJ by exploiting the distance formula for signed genomes. In addition, we show that UDCJ admits a weak kernel of size 2k and hence an FPT algorithm running in O(2(2k)n) time.
Department of Computer Science, Montana State University, Bozeman, MT 59717, USA.
Haitao
H
Jiang
Binhai
B
Zhu
Daming
D
Zhu
D000465:Algorithms; D016678:Genome; D023281:Genomics / Q000379:methods*; D012984:Software