Computational Biology
@ Comenius University in Bratislava

Jakub Kovac, Marilia D. V. Braga, Jens Stoye. The Problem of Chromosome Reincorporation in DCJ Sorting and Halving. In Eric Tannier, ed., Comparative Genomics - International Workshop, RECOMB-CG, 6398 volume of Lecture Notes in Computer Science, pp. 13-24, Ottawa, Canada, October 2010. Springer.

Download preprint: not available

Download from publisher: http://dx.doi.org/10.1007/978-3-642-16181-0_2

Related web page: not available

Bibliography entry: BibTeX

Abstract:

We study two problems in the double cut and join (DCJ) model:
sorting – transforming one multilinear genome into another and
halving – transforming a duplicated genome into a perfectly
duplicated one. The DCJ model includes rearrangement operations
such as reversals, translocations, fusions and fissions. We can
also mimic transpositions or block interchanges by two
operations: we extract an appropriate segment of a chromosome,
creating a temporary circular chromosome, and in the next step we
reinsert it in its proper place. Existing linear-time algorithms
solving both problems ignore the constraint of reincorporating
the temporary circular chromosomes immediately after their
creation. For the restricted sorting problem only a quadratic
algorithm was known, whereas the restricted halving problem was
stated as open by Tannier, Zheng, and Sankoff. In this paper we
address this constraint and show how to solve the problem of
sorting in O(nlogn) time and halving in O(n 3/2) time.