Genome Rearrangement Analysis : Cut and Join Genome Rearrangements and Gene Cluster Preserving Approaches.
Cut and join
Gene cluster
Gene order analysis
Genome rearrangements
Journal
Methods in molecular biology (Clifton, N.J.)
ISSN: 1940-6029
Titre abrégé: Methods Mol Biol
Pays: United States
ID NLM: 9214969
Informations de publication
Date de publication:
2024
2024
Historique:
medline:
31
5
2024
pubmed:
31
5
2024
entrez:
31
5
2024
Statut:
ppublish
Résumé
Genome rearrangements are mutations that change the gene content of a genome or the arrangement of the genes on a genome. Several years of research on genome rearrangements have established different algorithmic approaches for solving some fundamental problems in comparative genomics based on gene order information. This review summarizes the literature on genome rearrangement analysis along two lines of research. The first line considers rearrangement models that are particularly well suited for a theoretical analysis. These models use rearrangement operations that cut chromosomes into fragments and then join the fragments into new chromosomes. The second line works with rearrangement models that reflect several biologically motivated constraints, e.g., the constraint that gene clusters have to be preserved. In this chapter, the border between algorithmically "easy" and "hard" rearrangement problems is sketched and a brief review is given on the available software tools for genome rearrangement analysis.
Identifiants
pubmed: 38819562
doi: 10.1007/978-1-0716-3838-5_9
doi:
Types de publication
Journal Article
Review
Langues
eng
Sous-ensembles de citation
IM
Pagination
215-245Informations de copyright
© 2024. The Author(s), under exclusive license to Springer Science+Business Media, LLC, part of Springer Nature.
Références
Adam Z, Sankoff D (2008) The ABCs of MGR with DCJ. Evol Bioinform Online 4:69–74
pubmed: 19204809
pmcid: 2614205
doi: 10.1177/117693430800400004
Alekseyev MA (2008) Multi-break rearrangements and breakpoint re-uses: from circular to linear genomes. J Comput Biol 15(8):1117–1131
pubmed: 18788907
doi: 10.1089/cmb.2008.0080
Alekseyev MA, Pevzner PA (2008) Multi-break rearrangements and chromosomal evolution. Theor Comput Sci 395(2):193–202
doi: 10.1016/j.tcs.2008.01.013
Alekseyev MA, Pevzner PA (2009) Breakpoint graphs and ancestral genome reconstructions. Genome Res 19(5):943–957
pubmed: 19218533
pmcid: 2675983
doi: 10.1101/gr.082784.108
Alekseyev MA, Pevzner PA (2009) MGRA. http://mgra.cblab.org/
Alexandrino AO, Brito KL, Oliveira AR, Dias U, Dias Z (2021) Reversal distance on genomes with different gene content and intergenic regions information. In: International Conference on Algorithms for Computational Biology. Springer, Berlin, pp 121–133
doi: 10.1007/978-3-030-74432-8_9
Alexandrino AO, Oliveira AR, Dias U, Dias Z (2021) Incorporating intergenic regions into reversal and transposition distances with indels. J Bioinform Comput Biol 19(06):2140011
pubmed: 34775923
doi: 10.1142/S0219720021400114
Bachmann L, Fromm B, Patella de Azambuja L, Boeger WA (2016) The mitochondrial genome of the egg-laying flatworm aglaiogyrodactylus forficulatus (platyhelminthes: Monogenoidea). Parasit Vectors 9(1):1–8
doi: 10.1186/s13071-016-1586-2
Bader DA, Moret BM, Warnow T, Wyman SK, Yan M, Tang J, Siepel AC, Caprara A (2004) GRAPPA. https://www.cs.unm.edu/~moret/GRAPPA/
Bader M (2009) dcjdDist. http://www.uni-ulm.de/in/theo/m/alumni/bader/
Bader M (2009) Sorting by reversals, block interchanges, tandem duplications, and deletions. BMC Bioinform 10(Suppl 1):S9
doi: 10.1186/1471-2105-10-S1-S9
Bader M (2011) The transposition median problem is NP-complete. Theor Comput Sci 412(12–14):1099–1110
doi: 10.1016/j.tcs.2010.12.009
Bader M, Abouelhoda MI, Ohlebusch E (2002) MGR. http://grimm.ucsd.edu/MGR/
Bader M, Abouelhoda MI, Ohlebusch E (2008) A fast algorithm for the multiple genome rearrangement problem with weighted reversals and transpositions. BMC Bioinform 9(1):1–13
doi: 10.1186/1471-2105-9-516
Bader M, Abouelhoda MI, Ohlebusch E (2008) phylo. http://www.uni-ulm.de/in/theo/m/alumni/bader/
Belda E, Moya A, Silva FJ (2005) Genome rearrangement distances and gene order phylogeny in γ-proteobacteria. Mol Biol Evol 22(6):1456–1467
pubmed: 15772379
doi: 10.1093/molbev/msi134
Bérard S, Bergeron A, Chauve C, Paul C (2007) Perfect sorting by reversals is not always difficult. IEEE/ACM Trans Comput Biol Bioinform 4(1):4–16
pubmed: 17277409
doi: 10.1109/TCBB.2007.1011
Bérard S, Chateau A, Chauve C, Paul C, Tannier E (2008) Perfect DCJ rearrangement. In: Proc. RECOMB Int’l Workshop Comparative Genomics (RCG ’08), LNCS, vol 5267, pp 158–169
Bérard S, Chauve C, Paul C (2008) A more efficient algorithm for perfect sorting by reversals. Inf Process Lett 106(3):90–95
doi: 10.1016/j.ipl.2007.10.012
Bérard S, Chateau A, Chauve C, Paul C, Tannier E (2009) Computation of perfect DCJ rearrangement scenarios with linear and circular chromosomes. J Comput Biol 16(10):1287–1309
pubmed: 19803733
doi: 10.1089/cmb.2009.0088
Bergeron A, Stoye J (2013) The Genesis of the DCJ Formula, Computational Biology, vol 19. Springer, Berlin, pp 63–81
Bergeron A, Mixtacki J, Stoye J (2006) CEGeD. http://bibiserv.techfak.uni-bielefeld.de/ceged
Bergeron A, Mixtacki J, Stoye J (2006) A unifying view of genome rearrangements. In: Proc. 6th Int’l Workshop Algorithms in Bioinformatics (WABI ’06), LNCS, vol 4175, pp 163–173
Bergeron A, Medvedev P, Stoye J (2010) Rearrangement models and single-cut operations. J Comput Biol 17(9):1213–1225
pubmed: 20874405
doi: 10.1089/cmb.2010.0091
Bernt M (2009) Gene order rearrangement methods for the reconstruction of phylogeny. PhD thesis, University Leipzig
Bernt M, Middendorf M (2011) A method for computing an inventory of metazoan mitochondrial gene order rearrangements. BMC Bioinform 12(9):1
Bernt M, Merkle D, Middendorf M (2007) A fast and exact algorithm for the perfect reversal median problem. In: Proc. 3rd Int’l Symp. Bioinformatics Research and Applications (ISBRA ’07), LNCS, vol 4463, pp 305–316
Bernt M, Merkle D, Ramsch K, Fritzsch G, Perseke M, Bernhard D, Schlegel M, Stadler PF, Middendorf M (2007) CREx. http://pacosy.informatik.uni-leipzig.de/crex
Bernt M, Merkle D, Ramsch K, Fritzsch G, Perseke M, Bernhard D, Schlegel M, Stadler PF, Middendorf M (2007) CREx: inferring genomic rearrangements based on common intervals. Bioinformatics 23(21):2957–2958
pubmed: 17895271
doi: 10.1093/bioinformatics/btm468
Bernt M, Merkle D, Middendorf M (2008) Solving the preserving reversal median problem. IEEE/ACM Trans Comput Biol Bioinform 5(3):332–347
pubmed: 18670038
doi: 10.1109/TCBB.2008.39
Bernt M, Chao KM, Kao JW, Middendorf M, Tannier E (2012) Preserving inversion phylogeny reconstruction. In: Proc. 12th Int’l Workshop Algorithms in Bioinformatics (WABI ’12), LNCS, vol 7534, pp 1–13
Bohnenkämper L, Braga MD, Doerr D, Stoye J (2021) Computing the rearrangement distance of natural genomes. J Comput Biol 28(4):410–431. https://doi.org/10.1089/cmb.2020.0434
pubmed: 33393848
pmcid: 8082732
doi: 10.1089/cmb.2020.0434
Bohnenkämper L, Braga MD, Doerr D, Stoye J (2021) DING. https://gitlab.ub.uni-bielefeld.de/gi/ding
Boore JL (2000) The duplication/random loss model for gene rearrangement exemplified by mitochondrial genomes of deuterostome animals. Springer, Berlin, pp 133–147
Booth KS, Lueker GS (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J Comput Syst Sci 13(3):335–379
doi: 10.1016/S0022-0000(76)80045-1
Bourque G, Pevzner PA (2002) Genome-scale evolution: Reconstructing gene orders in the ancestral species. Genome Res 12(1):26–36
pubmed: 11779828
pmcid: 155248
Bouvel M, Chauve C, Mishna M, Rossin D (2011) Average-case analysis of perfect sorting by reversals. Discrete Math Algorithms and Appl 3(3):369–392
doi: 10.1142/S1793830911001280
Braga MD (2008) baobabLUNA. http://doua.prabi.fr/software/luna#perm
Braga MD (2009) baobabluna: the solution space of sorting by reversals. Bioinformatics 25(14):1833–1835
pubmed: 19401401
pmcid: 2705226
doi: 10.1093/bioinformatics/btp285
Brito KL, Jean G, Fertin G, Oliveira AR, Dias U, Dias Z (2020) Sorting by genome rearrangements on both gene order and intergenic sizes. J Comput Biol 27(2):156–174
pubmed: 31891533
doi: 10.1089/cmb.2019.0293
Brown TA (2006) Genomes. Garland science
Bulteau L, Fertin G, Rusu I (2012) Sorting by transpositions is difficult. SIAM J Discrete Math 26(3):1148–1180
doi: 10.1137/110851390
Bulteau L, Fertin G, Tannier E (2016) Genome rearrangements with indels in intergenes restrict the scenario space. BMC Bioinform 17(14):225–231
Caprara A (1997) Sorting by reversals is difficult. In: Proc. 1th Ann. Int’l Conf. Computational Molecular Biology (RECOMB ’97), pp 75–83
Caprara A (2003) The reversal median problem. INFORMS J Comput 15(1):93–113
doi: 10.1287/ijoc.15.1.93.15155
Casjens S, Palmer N, van Vugt R, Huang WM, Stevenson B, Rosa P, Lathigra R, Sutton G, Peterson J, Dodson RJ, Haft D, Hickey E, Gwinn M, White O, Fraser CM (2000) A bacterial genome in flux: the twelve linear and nine circular extrachromosomal DNAs in an infectious isolate of the Lyme disease spirochete Borrelia burgdorferi. Mol Microbiol 35(3):490–516
pubmed: 10672174
doi: 10.1046/j.1365-2958.2000.01698.x
Chaudhuri K, Chen K, Mihaescu R, Rao S (2006) On the tandem duplication-random loss model of genome rearrangement. In: Proc. 17th Ann. ACM-SIAM Symp. Discrete Algorithm (SODA ’06), pp 564–570
Chen X (2010) On sorting permutations by double-cut-and-joins. In: Proc. 16th Ann. Int’l Computing and Combinatorics Conf. (COCOON ’10), LNCS, vol 6196, pp 439–448
Christie DA (1996) Sorting permutations by block-interchanges. Inf Process Lett 60(4):165–169
doi: 10.1016/S0020-0190(96)00155-X
Darling AC, Mau B, Blattner FR, Perna NT (2004) Mauve: multiple alignment of conserved genomic sequence with rearrangements. Genome Res 14(7):1394–1403
pubmed: 15231754
pmcid: 442156
doi: 10.1101/gr.2289704
Darling AC, Mau B, Blattner FR, Perna NT (2015) Mauve. http://darlinglab.org/mauve/mauve.html
Dias U, Oliveira AR, Brito KL, Dias Z (2019) Block-interchange distance considering intergenic regions. In: Brazilian Symposium on Bioinformatics. Springer, Berlin, pp 58–69
Doerr D, Chauve C (2021) SPP-DJC. https://github.com/danydoerr/spp_dcj
Elias I, Hartman T (2006) A 1.375-approximation algorithm for sorting by transpositions. IEEE/ACM Trans Comput Biol Bioinform 3(4):369–379
pubmed: 17085846
doi: 10.1109/TCBB.2006.44
Feijão P, Meidanis J (2009) SCJ: a variant of breakpoint distance for which sorting, genome median and genome halving problems are easy. In: Proc. 9th Int’l Workshop Algorithms in Bioinformatics (WABI ’09), LNCS, vol 5724, pp 85–96
Feijão P, Meidanis J (2011) SCJ: a breakpoint-like distance that simplifies several rearrangement problems. IEEE/ACM Trans Comput Biol Bioinform 8(5):1318–1329
pubmed: 21339538
doi: 10.1109/TCBB.2011.34
Felsenstein J, Felenstein J (2004) Inferring phylogenies, vol 2. Sinauer Associates Sunderland
Fertin G, Labarre A, Rusu I, Tannier E, Vialette S (2009) Combinatorics of genome rearrangements, 1st edn. The MIT Press, Cambridge
doi: 10.7551/mitpress/9780262062824.001.0001
Fertin G, Jean G, Tannier E (2017) Algorithms for computing the double cut and join distance on both gene order and intergenic sizes. Algorithms for Mol Biol 12(1):1–11
doi: 10.1186/s13015-017-0107-y
Figeac M, Varré JS (2004) Sorting by reversals with common intervals. In: Proc. 4th Int’l Workshop Algorithms in Bioinformatics (WABI ’04), LNCS, vol 3240, pp 26–37
Fitch WM (1971) Toward defining the course of evolution: minimum change for a specific tree topology. Syst Biol 20(4):406–416
doi: 10.1093/sysbio/20.4.406
Foulds LR, Graham RL (1982) The Steiner problem in phylogeny is NP-complete. Adv Appl Math 3(1):43–49
doi: 10.1016/S0196-8858(82)80004-3
Friedberg R, Darling AE, Yancopoulos S (2008) Genome rearrangement by the double cut and join operation, methods in molecular biology, vol 452. Humana Press, pp 385–416
Fu Z, Chen X, Vacic V, Nan P, Zhong Y, Jiang T (2007) MSOAR: a high-throughput ortholog assignment system based on genome rearrangement. J Comput Biol 14(9):1160–1175
pubmed: 17990975
doi: 10.1089/cmb.2007.0048
Fu Z, Chen X, Vacic V, Nan P, Zhong Y, Jiang T (2009) MSOAR. http://msoar.cs.ucr.edu/index.php
Gibbs RA, Weinstock GM, Metzker ML, Muzny DM, Sodergren EJ, Scherer S, Scott G, Steffen D, Worley KC, Burch PE, et al. (2004) Genome sequence of the Brown Norway rat yields insights into mammalian evolution. Nature 428(6982):493–521
pubmed: 15057822
doi: 10.1038/nature02426
Gog S, Bader M, Ohlebusch E (2008) Genesis: genome evolution scenarios. Bioinformatics 24(5):711–712
pubmed: 18204053
doi: 10.1093/bioinformatics/btn026
Gog S, Bader M, Ohlebusch E (2009) GENESIS. http://www.uni-ulm.de/en/in/institute-of-theoretical-computer-science/m/alumni/bader/
Graham GJ (1995) Tandem genes and clustered genes. J Theor Biol 175(1):71 – 87
pubmed: 7564393
doi: 10.1006/jtbi.1995.0122
Hannenhalli S, Pevzner P (1995) Transforming men into mice (polynomial algorithm for genomic distance problem). In: Proc. 36th Ann. Symp. Foundations of Computer Science (FOCS ’95), pp 581–592
Hannenhalli S, Pevzner PA (1999) Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J ACM 46(1):1–27
doi: 10.1145/300515.300516
Heber S, Stoye J (2001) Finding all common intervals of k permutations. In: Proc. 12th Ann. Symp. Combinatorial Pattern Matching (CPM ’01), LNCS, vol 2089, pp 207–218
Hilker R, Sickinger C, Friesen R, Mixtacki J, Stoye J (2005) UniMoG. http://bibiserv.techfak.uni-bielefeld.de/dcj
Hu F, Lin Y, Tang J (2014) MLGO. http://www.geneorder.org/server.php
Hu F, Lin Y, Tang J (2014) MLGO: phylogeny reconstruction and ancestral inference from gene-order data. BMC Bioinform 15(1):1–6
doi: 10.1186/s12859-014-0354-6
Huang YL, Lu CL (2010) Sorting by reversals, generalized transpositions, and translocations using permutation groups. J Comput Biol 17(5):685–705
pubmed: 20500022
doi: 10.1089/cmb.2009.0025
Huang YL, Huang CC, Tang CY, Lu CL (2009) SoRT[Formula: see text]. http://genome.cs.nthu.edu.tw/SORT2/
Inoue JG, Miya M, Tsukamoto K, Nishida M (2003) Evolution of the deep-sea gulper eel mitochondrial genomes: large-scale gene rearrangements originated within the eels. Mol Biol Evol 20(11):1917–1924
pubmed: 12949142
doi: 10.1093/molbev/msg206
Jiang S, Alekseyev MA (2015) Implicit transpositions in shortest DCJ scenarios. In: Proc. 2nd Int’l Conf. Algorithms for Computational Biology (AlCoB ’15), LNCS, vol 9199, pp 13–24
Kececioglu J, Sankoff D (1995) Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica 13(1-2):180–210
doi: 10.1007/BF01188586
Krell P (2014) GEvolutionS. http://bibiserv.techfak.uni-bielefeld.de/gevolutions
Lenne R, Solnon C, Stützle T, Tannier E, Birattari M (2008) Reactive stochastic local search algorithms for the genomic median problem. In: Proc. 8th European Conf. Evolutionary Computation in Combinatorial Optimisation (EvoCOP ’08), LNCS, vol 4972, pp 266–276
Lin Y, Moret BM (2008) Estimating true evolutionary distances under the DCJ model. Bioinformatics 24(13):114–122
doi: 10.1093/bioinformatics/btn148
Ma J, Zhang L, Suh BB, Raney BJ, Burhans RC, Kent WJ, Blanchette M, Haussler D, Miller W (2006) Reconstructing contiguous regions of an ancestral genome. Genome Res 16(12):1557–1565
pubmed: 16983148
pmcid: 1665639
doi: 10.1101/gr.5383506
Martin M (2007) SBBI. http://bibiserv.techfak.uni-bielefeld.de/sbbi
Moret BME, Wang LS, Warnow T, Wyman SK (2001) New approaches for reconstructing phylogenies from gene order data. Bioinformatics 17(9):165–173
doi: 10.1093/bioinformatics/17.suppl_1.S165
Murphy WJ, Larkin DM, der Wind AEv, Bourque G, Tesler G, Auvil L, Beever JE, Chowdhary BP, Galibert F, Gatzke L, Hitte C, Meyers SN, Milan D, Ostrander EA, Pape G, Parker HG, Raudsepp T, Rogatcheva MB, Schook LB, Skow LC, Welge M, Womack JE, O’Brien SJ, Pevzner PA, Lewin HA (2005) Dynamics of mammalian chromosome evolution inferred from multispecies comparative maps. Science 309(5734):613–617
Ohlebusch E, Abouelhoda M, Hockel K (2007) A linear time algorithm for the inversion median problem in circular bacterial genomes. J Discrete Algorithms 5(4):637–646
doi: 10.1016/j.jda.2006.12.006
Oliveira AR, Jean G, Fertin G, Brito KL, Bulteau L, Dias U, Dias Z (2020) Sorting signed permutations by intergenic reversals. IEEE/ACM Trans Comput Biol Bioinform 18(6):2870–2876
doi: 10.1109/TCBB.2020.2993002
Oliveira AR, Jean G, Fertin G, Brito KL, Dias U, Dias Z (2020) A 3.5-approximation algorithm for sorting by intergenic transpositions. In: International Conference on Algorithms for Computational Biology. Springer, Berlin, pp 16–28
doi: 10.1007/978-3-030-42266-0_2
Oliveira AR, Jean G, Fertin G, Brito KL, Dias U, Dias Z (2021) Sorting permutations by intergenic operations. IEEE/ACM Trans Comput Biol Bioinform 18(6):2080–2093
pubmed: 33945484
doi: 10.1109/TCBB.2021.3077418
Pe’er I, Shamir R (1998) The median problems for breakpoints are NP-complete. Elec Colloq Comput Complexity 5(71)
Pevzner P, Tesler G (2003) Transforming men into mice: The Nadeau–Taylor chromosomal breakage model revisited. In: Proc. 7th Ann. Int’l Conf. Computational Molecular Biology (RECOMB ’03), pp 247–256
Qiu WG, Schutzer SE, Bruno JF, Attie O, Xu Y, Dunn JJ, Fraser CM, Casjens SR, Luft BJ (2004) Genetic exchange and plasmid transfers in Borrelia burgdorferi sensu stricto revealed by three-way genome comparisons and multilocus sequence typing. Proc Natl Acad Sci USA 101(39):14150–14155
pubmed: 15375210
pmcid: 521097
doi: 10.1073/pnas.0402745101
Raphael BJ, Pevzner PA (2004) Reconstructing tumor amplisomes. Bioinformatics 20(Suppl 1):265–273
doi: 10.1093/bioinformatics/bth931
San Mauro D, Gower DJ, Zardoya R, Wilkinson M (2006) A hotspot of gene order rearrangement by tandem duplication and random loss in the vertebrate mitochondrial genome. Mol Biol Evol 23(1):227–234
pubmed: 16177229
doi: 10.1093/molbev/msj025
Sankoff D (1992) Edit distance for genome comparison based on non-local operations. In: Proc. 3rd Ann. Symp. Combinatorial Pattern Matching (CPM ’92), LNCS, vol 644, pp 121–135
Sankoff D, Blanchette M (1998) Multiple genome rearrangement and breakpoint phylogeny. J Comput Biol 5(3):555–570
pubmed: 9773350
doi: 10.1089/cmb.1998.5.555
Shao M (2015) GREDU. https://github.com/shaomingfu/gredu
Shao M, Lin Y, Moret B (2014) An exact algorithm to compute the DCJ distance for genomes with duplicate genes. In: Proc. 18th Ann. Int’l Conf. Computational Molecular Biology (RECOMB ’14), LNCS, vol 8394, pp 280–292
Stoye J, Wittler R (2009) A unified approach for reconstructing ancient gene clusters. IEEE/ACM Trans Comput Biol Bioinform 6(3):387–400
pubmed: 19644167
doi: 10.1109/TCBB.2008.135
Swenson KM, Simonaitis P, Blanchette M (2016) Models and algorithms for genome rearrangement with positional constraints. Algorithm Mol Biol 11(1):1–10
doi: 10.1186/s13015-016-0065-9
Tannier E, Sagot MF (2004) Sorting by reversals in subquadratic time. In: Proc. 15th Ann. Symp. Combinatorial Pattern Matching (CPM ’04), LNCS, vol 3109, pp 1–13
Tannier E, Bergeron A, Sagot MF (2007) Advances on sorting by reversals. Discrete Appl Math 155(6):881–888
doi: 10.1016/j.dam.2005.02.033
Tannier E, Zheng C, Sankoff D (2009) Multichromosomal median and halving problems under different genomic distances. BMC Bioinform 10(1):1–15
doi: 10.1186/1471-2105-10-120
Tesler G (2002) GRIMM: genome rearrangements web server. Bioinformatics 18(3):492–493
pubmed: 11934753
doi: 10.1093/bioinformatics/18.3.492
Tesler G, Yu Y, Pevzner P (2002) GRIMM. http://grimm.ucsd.edu/GRIMM/
Véron AS, Lemaitre C, Gautier C, Lacroix V, Sagot MF (2011) Close 3D proximity of evolutionary breakpoints argues for the notion of spatial synteny. BMC Genom 12(1):1–13
doi: 10.1186/1471-2164-12-303
Volff JN, Altenbuchner J (2000) A new beginning with new ends: linearisation of circular chromosomes during bacterial evolution. FEMS Microbiol Lett 186(2):143–150
pubmed: 10802162
doi: 10.1111/j.1574-6968.2000.tb09095.x
Wang LS, Warnow T, Moret BME, Jansen RK, Raubeson LA (2006) Distance-based genome rearrangement phylogeny. J Mol Evol 63(4):473–483
pubmed: 17021931
doi: 10.1007/s00239-005-0216-y
Watterson G, Ewens W, Hall T, Morgan A (1982) The chromosome inversion problem. J Theor Biol 99(1):1–7
doi: 10.1016/0022-5193(82)90384-8
Wittler R (2004) Roci. http://bibiserv.techfak.uni-bielefeld.de/roci
Xu AW, Sankoff D (2008) Decompositions of multiple breakpoint graphs and rapid exact solutions to the median problem. In: Proc. 8th Int’l Workshop Algorithms in Bioinformatics (WABI ’08), LNCS, vol 5251, pp 25–37
Yancopoulos S, Attie O, Friedberg R (2005) Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21(16):3340–3346
pubmed: 15951307
doi: 10.1093/bioinformatics/bti535
Zhang M, Arndt W, Tang J (2009) An exact solver for the DCJ median problem. In: Proc. Pacific Symp. on Biocomputing (PSB ’09), pp 138–149
Zhao H, Bourque G (2009) EMRAE. http://www.gis.a-star.edu.sg/~bourque/software.html
Zhao H, Bourque G (2009) Recovering genome rearrangements in the mammalian phylogeny. Genome Res 19(5):934–942
pubmed: 19411607
pmcid: 2675982
doi: 10.1101/gr.086009.108
Zheng C, Sankoff D (2011) On the pathgroups approach to rapid small phylogeny. BMC Bioinform 12(1):1–9
Zheng C, Sankoff D (2011) Pathgroups. http://albuquerque.bioinformatics.uottawa.ca/lab/software.html