×

Rearrangements in phylogenetic inference: compare, model, or encode? (English) Zbl 1462.92042

Chauve, Cedric (ed.) et al., Models and algorithms for genome evolution. Selected contributions based on the presentations at the MAGE conference, Montréal, Canada, August 23–26, 2013. London: Springer. Comput. Biol. 19, 147-171 (2013).
Summary: We survey phylogenetic inference from rearrangement data, as viewed through the lens of the work of our group in this area, in tribute to David Sankoff, pioneer and mentor.
Genomic rearrangements were first used for phylogenetic analysis in the late 1920s, but it was not until the 1990s that this approach was revived, with the advent of genome sequencing. G. Watterson et al. proposed to measure the inversion distance between two genomes, J. Palmer et al. studied the evolution of mitochondrial and chloroplast genomes, and D. Sankoff and W. Day published the first algorithmic paper on phylogenetic inference from rearrangement data, giving rise to a fertile field of mathematical, algorithmic, and biological research.
Distance measures for sequence data are simple to define, but those based on rearrangements proved to be complex mathematical objects. The first approaches for phylogenetic inference from rearrangement data, due to D. Sankoff, used model-free distances, such as synteny (colocation on a chromosome) or breakpoints (disrupted adjacencies). The development of algorithms for distance and median computations led to modeling approaches based on biological mechanisms. However, the multiplicity of such mechanisms pose serious challenges. A unifying framework, proposed by S. Yancopoulos et al. and popularized by D. Sankoff, has supported major advances, such as precise distance corrections and efficient algorithms for median estimation, thereby enabling phylogenetic inference using both distance and maximum-parsimony methods.
Likelihood-based methods outperform distance and maximum-parsimony methods, but using such methods with rearrangements has proved problematic. Thus we have returned to an approach we first proposed 12 years ago: encoding the genome structure into sequences and using likelihood methods on these sequences. With a suitable a bias in the ground probabilities, we attain levels of performance comparable to the best sequence-based methods. Unsurprisingly, the idea of injecting such a bias was first proposed by D. Sankoff.
For the entire collection see [Zbl 1274.92002].

MSC:

92D10 Genetics and epigenetics
92D15 Problems related to evolution

Software:

RAxML; GRAPPA; GASTS; FastTree
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bader, M.: Genome rearrangements with duplications. BMC Bioinform. 11(Suppl. 1), S27 (2010)
[2] Bader, D., Moret, B., Yan, M.: A fast linear-time algorithm for inversion distance with an experimental comparison. J. Comput. Biol. 8(5), 483-491 (2001)
[3] Bergeron, A., Mixtacki, J., Stoye, J.: On sorting by translocations. In: Proc. 9th Ann. Int’l Conf. on Research in Computational Molecular Biology (RECOMB’05). Lecture Notes in Comp. Sci., vol. 3500, pp. 615-629 (2005) · Zbl 1119.92312
[4] Bergeron, A., Mixtacki, J., Stoye, J.: A unifying view of genome rearrangements. In: Proc. 6th Workshop Algs. in Bioinf. (WABI’06). Lecture Notes in Comp. Sci., vol. 4175, pp. 163-173. Springer, Berlin (2006)
[5] Bergeron, A., Mixtacki, J., Stoye, J.: A new linear time algorithm to compute the genomic distance via the double cut and join distance. Theor. Comput. Sci. 410(51), 5300-5316 (2009) · Zbl 1186.68144
[6] Blanchette, M., Bourque, G., Sankoff, D.: Breakpoint phylogenies. In: Miyano, S., Takagi, T. (eds.) Genome Informatics, pp. 25-34. Univ. Academy Press, Tokyo (1997)
[7] Bourque, G., Pevzner, P.: Genome-scale evolution: reconstructing gene orders in the ancestral species. Genome Res. 12, 26-36 (2002)
[8] Bulteau, L., Fertin, G., Rusu, I.: Sorting by transpositions is difficult. In: Proc. 38th Int’l Colloq. on Automata, Languages, and Programming (ICALP 2011). Lecture Notes in Comp. Sci., vol. 6756. Springer, Berlin (2011) · Zbl 1334.68085
[9] Burki, F., et al.: Phylogenomics reshuffles the eukaryotic supergroups. PLoS ONE 2(8), e790 (2007)
[10] Caprara, A.: Formulations and hardness of multiple sorting by reversals. In: Proc. 3rd Int’l Conf. Comput. Mol. Biol. (RECOMB’99), pp. 84-93. ACM Press, New York (1999)
[11] Caprara, A.: On the practical solution of the reversal median problem. In: Proc. 1st Workshop Algs. in Bioinf. (WABI’01). Lecture Notes in Comp. Sci., vol. 2149, pp. 238-251. Springer, Berlin (2001) · Zbl 1129.92315
[12] Chen, X., Zheng, J., Fu, Z., Nan, P., Zhong, Y., Lonardi, S., Jiang, T.: Computing the assignment of orthologous genes via genome rearrangement. In: Proc. 3rd Asia Pacific Bioinf. Conf. (APBC’05), pp. 363-378. Imperial College Press, London (2005)
[13] Chen, F., Mackey, A., Vermunt, J., Roos, D.: Assessing performance of orthology detection strategies applied to eukaryotic genomes. PLoS ONE 2(4), e383 (2007)
[14] Compeau, P.: A simplified view of DCJ-Indel distance. In: Proc. 12th Workshop Algs. in Bioinf. (WABI’12). Lecture Notes in Comp. Sci., vol. 7534, pp. 365-377. Springer, Berlin (2012)
[15] Cosner, M., Jansen, R., Moret, B., Raubeson, L., Wang, L., Warnow, T., Wyman, S.: An empirical comparison of phylogenetic methods on chloroplast gene order data in Campanulaceae. In: Sankoff, D., Nadeau, J. (eds.) Comparative Genomics, pp. 99-122. Kluwer Academic, Dordrecht (2000) · Zbl 1137.92351
[16] Cosner, M., Jansen, R., Moret, B., Raubeson, L., Wang, L., Warnow, T., Wyman, S.: A new fast heuristic for computing the breakpoint phylogeny and experimental phylogenetic analyses of real and synthetic data. In: Proc. 8th Int’l Conf. on Intelligent Systems for Mol. Biol. (ISMB’00), pp. 104-115 (2000)
[17] Day, W., Sankoff, D.: The computational complexity of inferring phylogenies from chromosome inversion data. J. Theor. Biol. 127, 213-218 (1987)
[18] Demongeot, J., et al.: Hot spots in chromosomal breakage: from description to etiology. In: Sankoff, D., Nadeau, J. (eds.) Comparative Genomics. Computational Biology, vol. 1, pp. 71-83. Springer, Berlin (2000) · Zbl 1137.92337
[19] Desper, R., Gascuel, O.: Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. J. Comput. Biol. 9(5), 687-705 (2002) · Zbl 1016.68692
[20] Desper, R., Gascuel, O.: Theoretical foundation of the balanced minimum evolution method of phylogenetic inference and its relationship to weighted least-squares tree fitting. Mol. Biol. Evol. 21(3), 587-598 (2003)
[21] Dobzhansky, T., Sturtevant, A.: Inversions in the chromosomes of Drosophila pseudoobscura. Genetics 23(1), 28-64 (1938)
[22] Downie, S.R., Palmer, J.D.: Use of chloroplast DNA rearrangements in reconstructing plant phylogeny. In: Soltis, D., Soltis, P., Doyle, J. (eds.) Molecular Systematics of Plants, pp. 14-35. Chapman and Hall, New York (1992)
[23] Durkin, K., et al.: Serial translocation by means of circular intermediates underlies colour sidedness in cattle. Nature 482(7383), 81-84 (2012)
[24] Ehrlich, J., Sankoff, D., Nadeau, J.: Synteny conservation and chromosome rearrangements during mammalian evolution. Genetics 147, 289-296 (1997)
[25] El-Mabrouk, N.: Genome rearrangement by reversals and insertions/deletions of contiguous segments. In: Proc. 11th Ann. Symp. Combin. Pattern Matching (CPM’00). Lecture Notes in Comp. Sci., vol. 1848, pp. 222-234. Springer, Berlin (2000) · Zbl 0964.92030
[26] El-Mabrouk, N., Sankoff, D.: The reconstruction of doubled genomes. SIAM J. Comput. 32(3), 754-792 (2003) · Zbl 1046.68056
[27] El-Mabrouk, N., Nadeau, J., Sankoff, D.: Genome halving. In: Proc. 9th Ann. Symp. Combin. Pattern Matching (CPM’98). Lecture Notes in Comp. Sci., pp. 235-250. Springer, Berlin (1998)
[28] El-Mabrouk, N., Bryant, D., Sankoff, D.: Reconstructing the pre-doubling genome. In: Proc. 3rd Int’l Conf. Comput. Mol. Biol. RECOMB’99, pp. 154-163. ACM Press, New York (1999)
[29] Fertin, G., Labarre, A., Rusu, I., Tannier, E., Vialette, S.: Combinatorics of Genome Rearrangements. MIT Press, Cambridge (2009) · Zbl 1170.92022
[30] Fitzpatrick, D., Logue, M., Stajich, J., Butler, G.: A fungal phylogeny based on 42 complete genomes derived from supertree and combined gene analysis. BMC Evol. Biol. 6(1), 99 (2006)
[31] Fujimura, K., Conte, M., Kocher, T.: Circular DNA intermediate in the duplication of Nile Tilapia vasa genes. PLoS ONE 6(12), e29477 (2011)
[32] Hannenhalli, S., Pevzner, P.: Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). In: Proc. 27th Ann. ACM Symp. Theory of Comput. (STOC’95), pp. 178-189. ACM Press, New York (1995) · Zbl 0978.68530
[33] Hannenhalli, S., Pevzner, P.: Transforming mice into men (polynomial algorithm for genomic distance problems). In: Proc. 36th Ann. IEEE Symp. Foundations of Comput. Sci. (FOCS’95), pp. 581-592. IEEE Press, Piscataway (1995) · Zbl 0938.68939
[34] Hilker, R., Sickinger, C., Pedersen, C., Stoye, J.: UniMoG—a unifying framework for genomic distance calculation and sorting based on DCJ. Bioinformatics 28(19), 2509-2511 (2012)
[35] Hu, F., Gao, N., Zhang, M., Tang, J.: Maximum likelihood phylogenetic reconstruction using gene order encodings. In: Proc. 2011 IEEE Symp. Comput. Intell. in Bioinf. & Comput. Biol. (CIBCB’11), pp. 117-122. IEEE Press, Piscataway (2011)
[36] Huson, D., Nettles, S., Warnow, T.: Disk-covering, a fast converging method for phylogenetic tree reconstruction. J. Comput. Biol. 6(3), 369-386 (1999)
[37] Jansen, R., Palmer, J.: A chloroplast DNA inversion marks an ancient evolutionary split in the sunflower family (Asteraceae). Proc. Natl. Acad. Sci. USA 84, 5818-5822 (1987)
[38] Jean, G., Nikolski, M.: Genome rearrangements: a correct algorithm for optimal capping. Inf. Process. Lett. 104(1), 14-20 (2007) · Zbl 1183.92034
[39] Larget, B., Simon, D., Kadane, J.: Bayesian phylogenetic inference from animal mitochondrial genome arrangements. J. R. Stat. Soc. B 64(4), 681-694 (2002) · Zbl 1067.62115
[40] Letunic, I., Bork, P.: Interactive tree of life v2: online annotation and display of phylogenetic trees made easy. Nucleic Acids Res. 39(S2), W475-W478 (2011)
[41] Lin, Y., Moret, B.: Estimating true evolutionary distances under the DCJ model. In: Proc. 16th Int’l Conf. on Intelligent Systems for Mol. Biol. (ISMB’08). Bioinformatics, vol. 24(13), pp. i114-i122 (2008)
[42] Lin, Y., Moret, B.: A new genomic evolutionary model for rearrangements, duplications, and losses that applies across eukaryotes and prokaryotes. J. Comput. Biol. 18(9), 1055-1064 (2011)
[43] Lin, Y., Rajan, V., Swenson, K., Moret, B.: Estimating true evolutionary distances under rearrangements, duplications, and losses. In: Proc. 8th Asia Pacific Bioinf. Conf. (APBC’10). BMC Bioinformatics, vol. 11(Suppl. 1), pp. S54 (2010)
[44] Lin, Y., Rajan, V., Moret, B.: Fast and accurate phylogenetic reconstruction from high-resolution whole-genome data and a novel robustness estimator. J. Comput. Biol. 18(9), 1130-1139 (2011)
[45] Lin, Y., Hu, F., Tang, J., Moret, B.: Maximum likelihood phylogenetic reconstruction from high-resolution whole-genome data and a tree of 68 eukaryotes. In: Proc. 18th Pacific Symp. on Biocomputing (PSB’13), pp. 285-296. World Scientific, Singapore (2013)
[46] López, M., Samuelsson, T.: eGOB: eukaryotic Gene Order Browser. Bioinformatics (2011)
[47] Ma, J., Ratan, A., Raney, B., Suh, B., Miller, W., Haussler, D.: The infinite sites model of genome evolution. Proc. Natl. Acad. Sci. USA 105(38), 14254-14261 (2008)
[48] Marron, M., Swenson, K., Moret, B.: Genomic distances under deletions and insertions. Theor. Comput. Sci. 325(3), 347-360 (2004) · Zbl 1071.92503
[49] Moret, B., Warnow, T.: Reconstructing optimal phylogenetic trees: a challenge in experimental algorithmics. In: Fleischer, R., Moret, B., Schmidt, E. (eds.) Experimental Algorithmics. Lecture Notes in Comp. Sci., vol. 2547, pp. 163-180. Springer, Berlin (2002) · Zbl 1026.68801
[50] Moret, B., Warnow, T.: Advances in phylogeny reconstruction from gene order and content data. In: Zimmer, E., Roalson, E. (eds.) Molecular Evolution: Producing the Biochemical Data, Part B. Methods in Enzymology, vol. 395, pp. 673-700. Elsevier, Amsterdam (2005)
[51] Moret, B., Wang, L.S., Warnow, T., Wyman, S.: New approaches for reconstructing phylogenies from gene-order data. In: Proc. 9th Int’l Conf. on Intelligent Systems for Mol. Biol. (ISMB’01). Bioinformatics, vol. 17, pp. S165-S173 (2001)
[52] Moret, B., Wyman, S., Bader, D., Warnow, T., Yan, M.: A new implementation and detailed study of breakpoint analysis. In: Proc. 6th Pacific Symp. on Biocomputing (PSB’01), pp. 583-594. World Scientific, Singapore (2001)
[53] Moret, B., Bader, D., Warnow, T.: High-performance algorithm engineering for computational phylogenetics. J. Supercomput. 22, 99-111 (2002) · Zbl 1007.92028
[54] Moret, B., Siepel, A., Tang, J., Liu, T.: Inversion medians outperform breakpoint medians in phylogeny reconstruction from gene-order data. In: Proc. 2nd Workshop Algs. in Bioinf. (WABI’02). Lecture Notes in Comp. Sci., vol. 2452, pp. 521-536. Springer, Berlin (2002) · Zbl 1016.68645
[55] Moret, B., Tang, J., Wang, L.S., Warnow, T.: Steps toward accurate reconstructions of phylogenies from gene-order data. J. Comput. Syst. Sci. 65(3), 508-525 (2002) · Zbl 1058.68531
[56] Moret, B., Tang, J., Warnow, T.: Reconstructing phylogenies from gene-content and gene-order data. In: Gascuel, O. (ed.) Mathematics of Evolution and Phylogeny, pp. 321-352. Oxford Univ. Press, London (2005) · Zbl 1090.92033
[57] Nadeau, J., Taylor, B.: Lengths of chromosome segments conserved since divergence of man and mouse. Proc. Natl. Acad. Sci. USA 81, 814-818 (1984)
[58] Negrisolo, E., Kuhl, H., Forcato, C., Vitulo, N., Reinhardt, R., Patarnello, T., Bargelloni, L.: Different phylogenomic approaches to resolve the evolutionary relationships among model fish species. Mol. Biol. Evol. 27(12), 2757-2774 (2010)
[59] Nozaki, H., et al.: The phylogenetic position of red algae revealed by multiple nuclear genes from mitochondria-containing eukaryotes and an alternative hypothesis on the origin of plastids. J. Mol. Evol. 56(4), 485-497 (2003)
[60] Ouangraoua, A., Boyer, F., McPherson, A., Tannier, E., Chauve, C.: Prediction of contiguous regions in the amniote ancestral genome. In: Proc. 5th Int’l Symp. Bioinformatics Research & Appls (ISBRA’09). Lecture Notes in Comp. Sci., vol. 5542, pp. 173-185. Springer, Berlin (2009)
[61] Palmer, J.D., Herbon, L.A.: Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence. J. Mol. Evol. 27, 87-97 (1988)
[62] Palmer, J.: Chloroplast and mitochondrial genome evolution in land plants. In: Herrmann, R. (ed.) Cell Organelles, pp. 99-133. Springer, Berlin (1992)
[63] Pe’er, I., Shamir, R.: The median problems for breakpoints are NP-complete. Elec. Colloq. on Comput. Complexity 71 (1998)
[64] Peng, Q., Pevzner, P., Tesler, G.: The fragile breakage versus random breakage models of chromosome evolution. PLoS Comput. Biol. 2(2), e14 (2006)
[65] Pevzner, P., Tesler, G.: Human and mouse genomic sequences reveal extensive breakpoint reuse in mammalian evolution. Proc. Natl. Acad. Sci. USA 100(13), 7672-7677 (2003)
[66] Ponting, C.: The functional repertoires of metazoan genomes. Nat. Rev. Genet. 9(9), 689-698 (2008)
[67] Price, M., Dehal, P., Arkin, A.: Fasttree: computing large minimum-evolution trees with profiles instead of a distance matrix. Mol. Biol. Evol. 26, 1641-1650 (2009)
[68] Rajan, V., Xu, A., Lin, Y., Swenson, K., Moret, B.: Heuristics for the inversion median problem. Proc. 8th Asia Pacific Bioinf. Conf. (APBC’10). BMC Bioinform. 11(Suppl. 1), S30 (2010)
[69] Rajan, V., Lin, Y., Moret, B.: TIBA: a tool for phylogeny inference from rearrangement data with bootstrap analysis. Bioinformatics 28(24), 3324-3325 (2012)
[70] Saitou, N., Nei, M.: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4, 406-425 (1987)
[71] Sankoff, D.: Minimal mutation trees of sequences. SIAM J. Appl. Math. 28(1), 35-42 (1975) · Zbl 0315.05101
[72] Sankoff, D.: Edit distance for genome comparison based on non-local operations. In: Proc. 3rd Ann. Symp. Combin. Pattern Matching (CPM’92). Lecture Notes in Comp. Sci., vol. 644, pp. 121-135. Springer, Berlin (1992)
[73] Sankoff, D., Blanchette, M.: The median problem for breakpoints in comparative genomics. In: Proc. 3rd Conf. Computing and Combinatorics (COCOON’97). Lecture Notes in Comp. Sci., vol. 1276, pp. 251-264. Springer, Berlin (1997) · Zbl 0889.92023
[74] Sankoff, D., Blanchette, M.: Multiple genome rearrangement and breakpoint phylogeny. J. Comput. Biol. 5, 555-570 (1998)
[75] Sankoff, D., Blanchette, M.: Phylogenetic invariants for metazoan mitochondrial genome evolution. In: Miyano, S., Takagi, T. (eds.) Genome Informatics, pp. 22-31. Univ. Academy Press, Tokyo (1998)
[76] Sankoff, D., Goldstein, M.: Probabilistic models for genome shuffling. Bull. Math. Biol. 51, 117-124 (1989) · Zbl 0658.92014
[77] Sankoff, D., Nadeau, J.: Conserved synteny as a measure of genomic distance. Discrete Appl. Math. 71(1-3), 247-257 (1996) · Zbl 0868.92018
[78] Sankoff, D., Nadeau, J. (eds.): Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment, and the Evolution of Gene Families. Kluwer Academic, Dordrecht (2000) · Zbl 0995.00023
[79] Sankoff, D., Trinh, P.: Chromosomal breakpoint re-use in genome sequence rearrangement. In: Proc. 9th Int’l Conf. Comput. Mol. Biol. (RECOMB’05). Lecture Notes in Comp. Sci., vol. 3388, pp. 30-35. Springer, Berlin (2005)
[80] Sankoff, D., Cedergren, R., Abel, Y.: Genomic divergence through gene rearrangement. In: Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences. Methods in Enzymology, vol. 183, pp. 428-438. Academic Press, San Diego (1990)
[81] Sankoff, D., Leduc, G., Antoine, N., Paquin, B., Lang, B., Cedergren, R.: Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome. Proc. Natl. Acad. Sci. USA 89(14), 6575-6579 (1992)
[82] 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)
[83] Siepel, A., Moret, B.: Finding an optimal inversion median: experimental results. In: Proc. 1st Workshop Algs. in Bioinf. (WABI’01). Lecture Notes in Comp. Sci., vol. 2149, pp. 189-203. Springer, Berlin (2001) · Zbl 1129.92309
[84] da Silva, P.H., Braga, M.D.V., Machado, R., Dantas, S.: DCJ-indel distance with distinct operation costs. In: Proc. 12th Workshop Algs. in Bioinf. (WABI’12). Lecture Notes in Comp. Sci., vol. 7534, pp. 378-390. Springer, Berlin (2012)
[85] Srivastava, M., et al.: The functional repertoires of metazoan genomes. Nature 454(7207), 955-960 (2008)
[86] Stamatakis, A.: RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics 22(21), 2688-2690 (2006)
[87] Sturtevant, A., Dobzhansky, T.: Inversions in the third chromosome of wild races of Drosophila pseudoobscura and their use in the study of the history of the species. Proc. Natl. Acad. Sci. USA 22, 448-450 (1936)
[88] Swenson, K., Marron, M., Earnest-DeYoung, J., Moret, B.: Approximating the true evolutionary distance between two genomes. ACM J. Experimental Algorithmics 12 (2008) · Zbl 1365.92078
[89] Swenson, K., Lin, Y., Rajan, V., Moret, B.: Hurdles and sorting by inversions: combinatorial, statistical, and experimental results. J. Comput. Biol. 16(10), 1339-1351 (2009)
[90] Tang, J., Moret, B.: Scaling up accurate phylogenetic reconstruction from gene-order data. In: Proc. 11th Int’l Conf. on Intelligent Systems for Mol. Biol. (ISMB’03). Bioinformatics, vol. 19, pp. i305-i312. Oxford Univ. Press, London (2003)
[91] Tang, J., Moret, B.: Linear programming for phylogenetic reconstruction based on gene rearrangements. In: Proc. 16th Ann. Symp. Combin. Pattern Matching (CPM’05). Lecture Notes in Comp. Sci., vol. 3537, pp. 406-416. Springer, Berlin (2005) · Zbl 1131.92351
[92] Tannier, E., Zheng, C., Sankoff, D.: Multichromosomal genome median and halving problems. In: Proc. 8th Workshop Algs. in Bioinf. (WABI’08). Lecture Notes in Comp. Sci., vol. 5251, pp. 1-13. Springer, Berlin (2008)
[93] Tesler, G.: Efficient algorithms for multichromosomal genome rearrangements. J. Comput. Syst. Sci. 63(5), 587-609 (2002) · Zbl 1059.68160
[94] Wang, L.S.: Exact-IEBP: a new technique for estimating evolutionary distances between whole genomes. In: Proc. 1st Workshop Algs. in Bioinf. (WABI’01). Lecture Notes in Comp. Sci., vol. 2149, pp. 175-188. Springer, Berlin (2001) · Zbl 1129.92319
[95] Wang, L.S., Warnow, T.: Estimating true evolutionary distances between genomes. In: Proc. 33rd Ann. ACM Symp. Theory of Comput. (STOC’01), pp. 637-646. ACM Press, New York (2001) · Zbl 1323.92143
[96] Wang, L.S., Warnow, T.: Distance-based genome rearrangement phylogeny. In: Gascuel, O. (ed.) Mathematics of Evolution and Phylogeny, pp. 353-383. Oxford Univ. Press, London (2005) · Zbl 1090.92035
[97] Wang, L.S., Jansen, R., Moret, B., Raubeson, L., Warnow, T.: Fast phylogenetic methods for genome rearrangement evolution: an empirical study. In: Proc. 7th Pacific Symp. on Biocomputing (PSB’02), pp. 524-535. World Scientific, Singapore (2002)
[98] Wang, H., Xu, Z., Gao, L., Hao, B.: A fungal phylogeny based on 82 complete genomes using the composition vector method. BMC Evol. Biol. 9(1), 195 (2009)
[99] Wang, L.S., Leebens-Mack, J., Wall, P., Beckmann, K., dePamphilis, C., Warnow, T.: The impact of multiple protein sequence alignment on phylogenetic estimation. IEEE/ACM Trans. Comput. Biol. Bioinform. 8, 1108-1119 (2011)
[100] Watterson, G., Ewens, W., Hall, T., Morgan, A.: The chromosome inversion problem. J. Theor. Biol. 99(1), 1-7 (1982)
[101] Xu, A., Sankoff, D.: Decompositions of multiple breakpoint graphs and rapid exact solutions to the median problem. In: Proc. 8th Workshop Algs. in Bioinf. (WABI’08). Lecture Notes in Comp. Sci., vol. 5251, pp. 25-37. Springer, Berlin (2008)
[102] Xu, A.: A fast and exact algorithm for the median of three problem—a graph decomposition approach. J. Comput. Biol. 16(10), 1369-1381 (2009)
[103] Xu, A., Moret, B.: GASTS: parsimony scoring under rearrangements. In: Proc. 11th Workshop Algs. in Bioinf. (WABI’11). Lecture Notes in Comp. Sci., vol. 6833, pp. 351-363. Springer, Berlin (2011)
[104] Yancopoulos, S., Friedberg, R.: Sorting genomes with insertions, deletions and duplications by DCJ. In: Proc. 6th RECOMB Workshop Comp. Genomics (RECOMB-CG’08). Lecture Notes in Comp. Sci., vol. 5267, pp. 170-183. Springer, Berlin (2008)
[105] Yancopoulos, S., Attie, O., Friedberg, R.: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 21(16), 3340-3346 (2005)
[106] Zhang, M., Arndt, W., Tang, J.: A branch-and-bound method for the multichromosomal reversal median problem. In: Proc. 8th Workshop Algs. in Bioinf. (WABI’08), pp. 1-13 (2008)
[107] Zheng, C., Zhu, Q., Adam, Z., Sankoff, D.: Guided genome halving: hardness, heuristics and the history of the hemiascomycetes. In: Proc. 16th Int’l Conf. on Intelligent Systems for Mol. Biol. (ISMB’08). Bioinformatics, vol. 24, pp
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.