Single Tandem Halving by Block Interchange - Biomedical Engineering Systems and Technologies - page 152

6 Conclusions

In this paper, we introduced the single tandem halving problem. We used the DCJ model
to simulate BI operations and we showed that it is always possible to choose two con-
secutive sorting DCJ operations such that they are equivalent to a BI operation. This
is an interesting result as it shows that restricting the scope of allowed DCJ operations
under the constraint of performing only BI doesn't affect our halving distance. This
also means our BI scenarios are in fact optimal DCJ scenarios. We thus provided a
quadratic time and space algorithm to obtain a most parsimonious scenario for the BI
single tandem halving problem, but also a most parsimonious scenario for the DCJ sin-
gle tandem halving problem for genomes that present the orientation constraint that all
markers must have the same orientation as their paralogs. A further extension of these
results will be a generalization to the more general DCJ model, without the orientation
constraints on the genome that the BI model implies, as well as ways of reconstructing
more than a single tandem. Another direction for further studies of variants of the BI
single tandem halving problem is to consider multichromosomal genomes.

References

1. Thomas, A., Ouangraoua, A., Varre, J.S.: Genome halving by block interchange. In: BIOIN-
FORMATICS 2012, Third International Conference on Bioinformatics Models, Methods and
Algorithms, Vilamoura, Portugal, February 1-4 (2012)
2. Christie, D.A.: Sorting permutations by block-interchanges. Inf. Process. Lett. 60, 165-169
(1996)
3. Lin, Y.C., Lu, C.L., Chang, H.Y., Tang, C.Y.: An efficient algorithm for sorting by block-
interchanges and its application to the evolution of vibrio species. Journal of Computational
Biology 12, 102-112 (2005)
4. Yancopoulos, S., Attie, O., Friedberg, R.: Efficient sorting of genomic permutations by
translocation, inversion and block interchange. Bioinformatics 21, 3340-3346 (2005)
5. El-Mabrouk, N., Nadeau, J.H., Sankoff, D.: Genome Halving. In: Farach-Colton, M. (ed.)
CPM 1998. LNCS, vol. 1448, pp. 235-250. Springer, Heidelberg (1998)
6. El-Mabrouk, N., Sankoff, D.: The reconstruction of doubled genomes. SIAM J. Comput. 32,
754-792 (2003)
7. Tannier, E., Zheng, C., Sankoff, D.: Multichromosomal Genome Median and Halving Prob-
lems. In: Crandall, K.A., Lagergren, J. (eds.) WABI 2008. LNCS (LNBI), vol. 5251, pp.
1-13. Springer, Heidelberg (2008)
8. Warren, R., Sankoff, D.: Genome halving with double cut and join. In: Brazma, A., Miyano,
S., Akutsu, T. (eds.) Proceedings of APBC 2008. Advances in Bioinformatics and Computa-
tional Biology, vol. 6, pp. 231-240. Imperial College Press (2008)
9. Mixtacki, J.: Genome Halving under DCJ Revisited. In: Hu, X., Wang, J. (eds.) COCOON
2008. LNCS, vol. 5092, pp. 276-286. Springer, Heidelberg (2008)
10. Kovac, J., Braga, M.D.V., Stoye, J.: The Problem of Chromosome Reincorporation in DCJ
Sorting and Halving. In: Tannier, E. (ed.) RECOMB-CG 2010. LNCS, vol. 6398, pp. 13-24.
Springer, Heidelberg (2010)