zbMATH — the first resource for mathematics

Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem. (English) Zbl 1397.92465
Summary: Clusters of paralogous genes such as the famous HOX cluster of developmental transcription factors tend to evolve by stepwise duplication of its members, often involving unequal crossing over. Gene conversion and possibly other mechanisms of concerted evolution further obfuscate the phylogenetic relationships. As a consequence, it is very difficult or even impossible to disentangle the detailed history of gene duplications in gene clusters. In this contribution we show that the expansion of gene clusters by unequal crossing over as proposed by Walter Gehring leads to distinctive patterns of genetic distances, namely a subclass of circular split systems. Furthermore, when the gene cluster was left undisturbed by genome rearrangements, the shortest Hamiltonian paths with respect to genetic distances coincide with the genomic order. This observation can be used to detect ancient genomic rearrangements of gene clusters and to distinguish gene clusters whose evolution was dominated by unequal crossing over within genes from those that expanded through other mechanisms.
92D10 Genetics and epigenetics
92D15 Problems related to evolution
05C45 Eulerian and Hamiltonian graphs
05C90 Applications of graph theory
62P10 Applications of statistics to biology and medical sciences; meta analysis
92-08 Computational methods for problems pertaining to biology
Full Text: DOI
[1] Al Ait, L; Yamak, Z; Morgenstern, B, DIALIGN at GOBICS—multiple sequence alignment using various sources of external information, Nucleic Acids Res, 41, w3-w7, (2013)
[2] Bandelt, HJ; Dress, AWM, A canonical decomposition theory for metrics on a finite set, Adv Math, 92, 47, (1992) · Zbl 0789.54036
[3] Bellman, R, Dynamic programming treatment of the travelling salesman problem, J ACM, 9, 61-63, (1962) · Zbl 0106.14102
[4] Bryant, D; Moulton, V; Spillner, A, Neighbornet: an agglomerative method for the construction of planar phylogenetic networks, Mol Biol Evol, 21, 255-265, (2004)
[5] Bryant, D; Moulton, V; Spillner, A, Consistency of the neighbornet algorithm, Alg Mol Biol, 2, 8, (2007)
[6] Buneman, P, A note on the metric property of trees, J Comb Theory Ser B, 17, 48-50, (1974) · Zbl 0286.05102
[7] Carson, AR; Scherer, SW, Identifying concerted evolution and gene conversion in Mammalian gene pairs lasting over 100 million years, BMC Evol Biol, 9, 156, (2009)
[8] Chang, CL; Semyonov, J; Cheng, PJ; Huang, SY; Park, JI; Tsai, HJ; Lin, CY; Grützner, F; Soong, YK; Cai, JJ; etal., Widespread divergence of the CEACAM/PSG genes in vertebrates and humans suggests sensitivity to selection, PLoS ONE, 8, e61701, (2013)
[9] Chepoi, V; Fichet, B, A note on circular decomposable metrics, Geom Dedic, 69, 237-240, (1998) · Zbl 0896.54013
[10] Chor, B; Sudan, M, A geometric approach to betweenness, SIAM J Discrete Math, 11, 511-523, (1998) · Zbl 0912.68058
[11] Christopher G, Farach M, Trick M (1996) The structure of circular decomposable metrics. In: Diaz J, Serna M (eds) Algorithms ESA’96, Lecture notes in computer science. Springer, New York, pp 406-418 · Zbl 1380.90234
[12] Critchley, F; Diday, E (ed.); Lechevallier, Y (ed.); Schader, M (ed.); Bertrand, P (ed.); Burtschy, B (ed.), On quadripolar Robinson dissimilarity matrices, 93-101, (1994), Heidelberg
[13] Cunningham, P, Free trees and bidirectional trees as representations of psychological distance, J Math Psychol, 17, 165-188, (1978) · Zbl 0383.94041
[14] Diday, E; Leeuw, J (ed.); Heiser, WJ (ed.); Meulman, JJ (ed.); Critchley, F (ed.), Orders and overlapping clusters in pyramids, 201-234, (1986), Leiden
[15] Dobson, AJ, Unrooted trees for numerical taxonomy, J Appl Probab, 11, 32-42, (1974) · Zbl 0277.92004
[16] Dress, AW; Flamm, C; Fritzsch, G; Grünewald, S; Kruspe, M; Prohaska, SJ; Stadler, PF, Noisy: identification of problematic columns in multiple sequence alignments, Alg Mol Biol, 3, 7, (2008)
[17] Dress, AWM; Huber, KT; Moulton, V, An exceptional split geometry, Ann Comb, 4, 1-11, (2000) · Zbl 0947.05081
[18] Farach, M, Recognizing circular decomposable metrics, J Comput Biol, 4, 157-162, (1997)
[19] Force, A; Lynch, M; Pickett, FB; Amores, A; Yan, YL; Postlethwait, J, Preservation of duplicate genes by complementary, degenerative mutations, Genetics, 151, 1531-1545, (1999)
[20] Garcia-Fernàndez, J, The genesis and evolution of homeobox gene clusters, Nat Rev Genet, 6, 881-892, (2005)
[21] Gehring WJ (1998) Master controle genes in development and evolution: the homeobox story. Yale University Press, New Haven
[22] Grünewald, S; Moulton, V; Spillner, A, Consistency of the qnet algorithm for generating planar split networks from weighted quartets, Discrete Appl Math, 157, 2325-2334, (2009) · Zbl 1182.92056
[23] Grünewald, S; Forslund, K; Dress, AWM; Moulton, V, Qnet: an agglomerative method for the construction of phylogenetic networks from weighted quartets, Mol Biol Evol, 24, 532-538, (2007)
[24] Halin, R; Welsh, DJA (ed.), Studies on minimally \(n\)-connected graphs, 129-136, (1971), London
[25] Hardison, R; Slightom, JL; Gumucio, DL; Goodman, M; Stojanovic, N; Miller, W, Locus control regions of Mammalian \(β \)-globin gene clusters: combining phylogenetic analyses and experimental results to gain functional insights, Gene, 205, 73-94, (1997)
[26] Höner zu Siederdissen C, Prohaska SJ, Stadler PF (2014) Dynamic programming for set data types. In: Campos S (ed) Advances in bioinformatics and computational biology: BSB 2014, vol 8826 of Lect. Notes Comp. Sci., pp 57-64
[27] Höner zu Siederdissen, C; Prohaska, SJ; Stadler, PF, Algebraic dynamic programming over general data structures, BMC Bioinform, 16, s2, (2015)
[28] Jukes, TH; Cantor, CR; Munro, HN (ed.), Evolution of protein molecules, 21-132, (1969), New York
[29] Kalmanson, K, Edgeconvex circuits and the traveling salesman problem, Can J Math, 27, 1000-1010, (1975) · Zbl 0284.05117
[30] Kleinman, A; Harel, M; Pachter, L, Affine and projective tree metric theorems, Ann Comb, 17, 205-228, (2013) · Zbl 1263.05013
[31] Korostensky, C; Gonnet, G, Using traveling salesman problem algorithms for evolutionary tree construction, Bioinformatics, 16, 619-627, (2000)
[32] Levy, D; Pachter, L, The neighbor-net algorithm, Adv Appl Math, 47, 240-258, (2011) · Zbl 1274.92005
[33] Liiv, I, Seriation and matrix reordering methods: an historical overview, Stat Anal Data Min, 3, 70-91, (2010)
[34] MacLean, JA; Wilkinson, MF, The rhox genes, Reproduction, 140, 195-213, (2010)
[35] MacLean, JA; Lorenzetti, D; Hu, Z; Salerno, WJ; Miller, J; Wilkinson, MF, Rhox homeobox gene cluster: recent duplication of three family members, Genesis, 44, 122-129, (2006)
[36] Makarychev, Y, A short proof of kuratowski’s graph planarity criterion, J Graph Theory, 25, 129-131, (1997) · Zbl 0878.05025
[37] Maniatis, T; Fritsch, EF; Lauer, J; Lawn, RM, The molecular genetics of human hemoglobins, Ann Rev Genet, 14, 145-178, (1980)
[38] Meggido, N, Partial and complete cyclic orders, Bull Am Math Soc, 82, 274-276, (1976) · Zbl 0361.06001
[39] Montavon, T; Duboule, D, Chromatin organization and global regulation of hox gene clusters, Phil Trans R Soc B, 368, 20120367, (2013)
[40] Moret, BME; Tang, J; Wang, LS; Warnow, T, Steps toward accurate reconstructions of phylogenies from gene-order data, J Comp Syst Sci, 65, 508-525, (2002) · Zbl 1058.68531
[41] Nei, M, Genetic distance between populations, Am Nat, 106, 283-292, (1972)
[42] Nieselt-Struwe, K, Graphs in sequence spaces: a review of statistical geometry, Biophys Chem, 66, 111-131, (1997)
[43] Noonan, JP; Grimwood, J; Schmutz, J; Dickson, M; Myers, RM, Gene conversion and the evolution of protocadherin gene cluster diversity, Genome Res, 14, 354-366, (2004)
[44] Notredame, C; Higgins, DG; Heringa, J, T-coffee: a novel method for fast and accurate multiple sequence alignment, J Mol Biol, 302, 205-217, (2000)
[45] Novák, V, Cuts in cyclically ordered sets, Czech Math J, 34, 322-333, (1984) · Zbl 0551.06002
[46] Ohno S (1970) Evolution by gene duplication. Springer, Berlin
[47] Oota, H; Dunn, CW; Speed, WC; Pakstis, AJ; Palmatier, MA; Kidd, JR; Kidd, KK, Conservative evolution in duplicated genes of the primate class I ADH cluster, Gene, 392, 64-76, (2007)
[48] Opatrny, J, Total ordering problem, SIAM J Comput, 8, 111-114, (1979) · Zbl 0395.68065
[49] Pascual-Anaya, J; Adachi, N; Álvarez, S; Kuratani, S; Daniello, S; Garcia-Fernàndez, J, Broken colinearity of the amphioxus hox cluster, EvoDevo, 3, 28, (2012)
[50] Pascual-Anaya, J; Daniello, S; Kuratani, S; Garcia-Fernàndez, J, Evolution of hox gene clusters in deuterostomes, BMC Dev Biol, 13, 26, (2013)
[51] Préa, P; Fortin, D, An optimal algorithm to recognize Robinsonian dissimilarities, J Classif, 31, 1-35, (2014) · Zbl 1360.68887
[52] Rice, P; Longden, I; Bleasby, A, EMBOSS: the European molecular biology open software suite, Trends Genet, 16, 276-277, (2000)
[53] Robinson, WS, A method for chronologically ordering archaeological deposits, Am Antiq, 16, 293-301, (1951)
[54] Semple C, Steel MA (2003) Phylogenetics, vol 24. Oxford University Press on Demand, Oxford · Zbl 1043.92026
[55] Simões-Pereira, JMS, A note on the tree realizability of a distance matrix, J Combin Theory, 6, 303-310, (1969) · Zbl 0177.26903
[56] Zid, M; Drouin, G, Gene conversions are under purifying selection in the carcinoembryonic antigen immunoglobulin gene families of primates, Genomics, 102, 301-309, (2013)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.