Jakub Kovac, Robert Warren, Marilia D. V. Braga, Jens Stoye. Restricted DCJ Model: Rearrangement Problems with Chromosome Reincorporation. Journal of Computational Biology, 18(9):1231-1231. 2011.
Download preprint: not available
Download from publisher: http://www.liebertonline.com/doi/abs/10.1089/cmb.2011.0116
Related web page: not available
Bibliography entry: BibTeX
See also: early version
We study three classical problems of genome rearrangement-sorting, halving, and the median problem-in a restricted double cut and join (DCJ) model. In the DCJ model, introduced by Yancopoulos et al., we can represent rearrangement events that happen in multichromosomal genomes, such as inversions, translocations, fusions, and fissions. Two DCJ operations can mimic transpositions or block interchanges by first extracting an appropriate segment of a chromosome, creating a temporary circular chromosome, and then reinserting it in its proper place. In the restricted model, we are concerned with multichromosomal linear genomes and we require that each circular excision is immediately followed by its reincorporation. Existing linear-time DCJ sorting and halving algorithms ignore this reincorporation constraint. In this article, we propose a new algorithm for the restricted sorting problem running in O(n log n) time, thus improving on the known quadratic time algorithm. We solve the restricted halving problem and give an algorithm that computes a multilinear halved genome in linear time. Finally, we show that the restricted median problem is NP-hard as conjectured.