Computational Biology
@ Comenius University in Bratislava

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

Abstract:

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.