Skip to main content
Top

2015 | OriginalPaper | Chapter

Sorting by Cuts, Joins and Whole Chromosome Duplications

Authors : Ron Zeira, Ron Shamir

Published in: Combinatorial Pattern Matching

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Genome rearrangement problems have been extensively studied due to their importance in biology. Most studied models assumed a single copy per gene. However, in reality duplicated genes are common, most notably in cancer. Here we make a step towards handling duplicated genes by considering a model that allows the atomic operations of cut, join and whole chromosome duplication. Given two linear genomes, \(\varGamma \) with one copy per gene, and \(\varDelta \) with two copies per gene, we give a linear time algorithm for computing a shortest sequence of operations transforming \(\varGamma \) into \(\varDelta \) such that all intermediate genomes are linear. We also show that computing an optimal sequence with fewest duplications is NP-hard.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Bader, M.: Sorting by reversals, block interchanges, tandem duplications, and deletions. BMC Bioinform. 10(Suppl 1), S9 (2009)MathSciNetCrossRef Bader, M.: Sorting by reversals, block interchanges, tandem duplications, and deletions. BMC Bioinform. 10(Suppl 1), S9 (2009)MathSciNetCrossRef
2.
go back to reference Bader, M.: Genome rearrangements with duplications. BMC Bioinform. 11(Suppl 1), S27 (2010)CrossRef Bader, M.: Genome rearrangements with duplications. BMC Bioinform. 11(Suppl 1), S27 (2010)CrossRef
3.
go back to reference Bayani, J., Selvarajah, S., Maire, G., Vukovic, B., Al-Romaih, K., Zielenska, M., Squire, J.A.: Genomic mechanisms and measurement of structural and numerical instability in cancer cells. Semin. Cancer Biol. 17(1), 5–18 (2007)CrossRef Bayani, J., Selvarajah, S., Maire, G., Vukovic, B., Al-Romaih, K., Zielenska, M., Squire, J.A.: Genomic mechanisms and measurement of structural and numerical instability in cancer cells. Semin. Cancer Biol. 17(1), 5–18 (2007)CrossRef
4.
go back to reference Bergeron, A., Mixtacki, J., Stoye, J.: A unifying view of genome rearrangements. In: Bücher, P., Moret, B.M.E. (eds.) WABI 2006. LNCS (LNBI), vol. 4175, pp. 163–173. Springer, Heidelberg (2006) CrossRef Bergeron, A., Mixtacki, J., Stoye, J.: A unifying view of genome rearrangements. In: Bücher, P., Moret, B.M.E. (eds.) WABI 2006. LNCS (LNBI), vol. 4175, pp. 163–173. Springer, Heidelberg (2006) CrossRef
5.
go back to reference Biller, P., Feijão, P., Meidanis, J.: Rearrangement-based phylogeny using the single-cut-or-join operation. IEEE/ACM Trans. Comput. Biol. Bioinform. 10(1), 122–134 (2013)CrossRef Biller, P., Feijão, P., Meidanis, J.: Rearrangement-based phylogeny using the single-cut-or-join operation. IEEE/ACM Trans. Comput. Biol. Bioinform. 10(1), 122–134 (2013)CrossRef
6.
go back to reference Blanc, G., Barakat, A., Guyot, R., Cooke, R., Delseny, M.: Extensive duplication and reshuffling in the arabidopsis genome. Plant cell 12(7), 1093–1101 (2000)CrossRef Blanc, G., Barakat, A., Guyot, R., Cooke, R., Delseny, M.: Extensive duplication and reshuffling in the arabidopsis genome. Plant cell 12(7), 1093–1101 (2000)CrossRef
7.
8.
go back to reference Caprara, A.: Sorting by reversals is difficult. In: Proceedings of the First Annual International Conference on Computational Molecular Biology (RECOMB), pp. 75–83, New York, USA (1997) Caprara, A.: Sorting by reversals is difficult. In: Proceedings of the First Annual International Conference on Computational Molecular Biology (RECOMB), pp. 75–83, New York, USA (1997)
10.
go back to reference Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., et al.: Introduction to algorithms, vol. 2. MIT press, Cambridge (2001) MATH Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., et al.: Introduction to algorithms, vol. 2. MIT press, Cambridge (2001) MATH
11.
go back to reference Dias, Z., Meidanis, J.: Genome rearrangements distance by fusion, fission, and transposition is easy. In: International Symposium on String Processing and Information Retrieval, pp. 250. IEEE Computer Society (2001) Dias, Z., Meidanis, J.: Genome rearrangements distance by fusion, fission, and transposition is easy. In: International Symposium on String Processing and Information Retrieval, pp. 250. IEEE Computer Society (2001)
12.
go back to reference Feijão, P., Meidanis, J.: SCJ: a breakpoint-like distance that simplifies several rearrangement problems. IEEE/ACM Trans. Comput. Biol. Bioinform. 8(5), 1318–1329 (2011)CrossRef Feijão, P., Meidanis, J.: SCJ: a breakpoint-like distance that simplifies several rearrangement problems. IEEE/ACM Trans. Comput. Biol. Bioinform. 8(5), 1318–1329 (2011)CrossRef
13.
go back to reference Fertin, G., Labarre, A., Rusu, I., Tannier, E., Vialette, S.: Combinatorics of Genome Rearrangements. MIT Press, Cambridge (2009)MATHCrossRef Fertin, G., Labarre, A., Rusu, I., Tannier, E., Vialette, S.: Combinatorics of Genome Rearrangements. MIT Press, Cambridge (2009)MATHCrossRef
14.
go back to reference Hannenhalli, S.: Polynomial-time algorithm for computing translocation distance between genomes. Discrete Appl. Math. 71(1–3), 137–151 (1996)MATHMathSciNetCrossRef Hannenhalli, S.: Polynomial-time algorithm for computing translocation distance between genomes. Discrete Appl. Math. 71(1–3), 137–151 (1996)MATHMathSciNetCrossRef
15.
go back to reference Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing (STOC), vol. 46, pp. 178–189, New York, USA (1995) Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing (STOC), vol. 46, pp. 178–189, New York, USA (1995)
16.
go back to reference Kováč, J.: On the complexity of rearrangement problems under the breakpoint distance. J. Comput. Biol. 21(1), 1–15 (2014)MathSciNetCrossRef Kováč, J.: On the complexity of rearrangement problems under the breakpoint distance. J. Comput. Biol. 21(1), 1–15 (2014)MathSciNetCrossRef
17.
go back to reference Lu, C.L., Huang, Y.L., Wang, T.C., Chiu, H.-T.: Analysis of circular genome rearrangement by fusions, fissions and block-interchanges. BMC Bioinform. 7(1), 295 (2006)CrossRef Lu, C.L., Huang, Y.L., Wang, T.C., Chiu, H.-T.: Analysis of circular genome rearrangement by fusions, fissions and block-interchanges. BMC Bioinform. 7(1), 295 (2006)CrossRef
18.
go back to reference Mira, C.V.G., Meidanis, J.: Sorting by block-interchanges and signed reversals. ITNG 7, 670–676 (2007) Mira, C.V.G., Meidanis, J.: Sorting by block-interchanges and signed reversals. ITNG 7, 670–676 (2007)
19.
go back to reference Ozery-Flato, M., Shamir, R.: Sorting cancer karyotypes by elementary operations. J. Comput. Biol. 16(10), 1445–1460 (2009)MathSciNetCrossRef Ozery-Flato, M., Shamir, R.: Sorting cancer karyotypes by elementary operations. J. Comput. Biol. 16(10), 1445–1460 (2009)MathSciNetCrossRef
20.
go back to reference Plesnik, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett. 8(4), 199–201 (1979)MATHMathSciNetCrossRef Plesnik, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett. 8(4), 199–201 (1979)MATHMathSciNetCrossRef
21.
go back to reference Savard, O.T., Gagnon, Y., Bertrand, D., El-Mabrouk, N.: Genome halving and double distance with losses. J. Comput. Biol. 18(9), 1185–1199 (2011)MathSciNetCrossRef Savard, O.T., Gagnon, Y., Bertrand, D., El-Mabrouk, N.: Genome halving and double distance with losses. J. Comput. Biol. 18(9), 1185–1199 (2011)MathSciNetCrossRef
22.
go back to reference Shao, M., Lin, Y.: Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion. BMC Bioinform. 13(Suppl 19), S13 (2012)CrossRef Shao, M., Lin, Y.: Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion. BMC Bioinform. 13(Suppl 19), S13 (2012)CrossRef
23.
go back to reference Shao, M., Lin, Y., Moret, B.: Sorting genomes with rearrangements and segmental duplications through trajectory graphs. BMC Bioinform. 14(Suppl 15), S9 (2013)CrossRef Shao, M., Lin, Y., Moret, B.: Sorting genomes with rearrangements and segmental duplications through trajectory graphs. BMC Bioinform. 14(Suppl 15), S9 (2013)CrossRef
24.
go back to reference Shao, M., Lin, Y., Moret, B.: An exact algorithm to compute the DCJ distance for genomes with duplicate genes. In: Sharan, R. (ed.) RECOMB 2014. LNCS, vol. 8394, pp. 280–292. Springer, Heidelberg (2014) CrossRef Shao, M., Lin, Y., Moret, B.: An exact algorithm to compute the DCJ distance for genomes with duplicate genes. In: Sharan, R. (ed.) RECOMB 2014. LNCS, vol. 8394, pp. 280–292. Springer, Heidelberg (2014) CrossRef
25.
go back to reference Tannier, E., Zheng, C., Sankoff, D.: Multichromosomal median and halving problems under different genomic distances. BMC Bioinform. 10(1), 120 (2009)CrossRef Tannier, E., Zheng, C., Sankoff, D.: Multichromosomal median and halving problems under different genomic distances. BMC Bioinform. 10(1), 120 (2009)CrossRef
27.
go back to reference Yancopoulos, S., Attie, O., Friedberg, R.: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21(16), 3340–3346 (2005)CrossRef Yancopoulos, S., Attie, O., Friedberg, R.: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21(16), 3340–3346 (2005)CrossRef
Metadata
Title
Sorting by Cuts, Joins and Whole Chromosome Duplications
Authors
Ron Zeira
Ron Shamir
Copyright Year
2015
DOI
https://doi.org/10.1007/978-3-319-19929-0_34

Premium Partner