A tutorial on the balanced minimum evolution problem. (English) Zbl 1495.90148
Summary: The Balanced Minimum Evolution Problem (BMEP) is an \(\mathcal{APX}\)-hard network design problem that consists of finding a minimum length unrooted binary tree (also called a phylogeny) having as a leaf-set a given set of molecular sequences. The optimal solution to the BMEP (i.e., the optimal phylogeny) encodes the hierarchical evolutionary relationships of the input sequences. This information is crucial for a multitude of research fields, ranging from systematics to medical research, passing through drug discovery, epidemiology, ecology, biodiversity assessment and population dynamics. In this article, we introduce the reader to the problem and present the current state-of-the-art; we include the most important achievements reached so far and the challenges that still remain to be addressed.
MSC:
| 90C27 | Combinatorial optimization |
| 05C05 | Trees |
| 92D15 | Problems related to evolution |
| 90-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming |
Keywords:
combinatorial optimization; balanced minimum evolution problem; network design; information entropy; mathematics of evolution; phylogeneticsReferences:
| [1] | Albert, V. A., Parsimony, phylogeny, and genomics (2005), Oxford Bioscience: Oxford Bioscience UK · Zbl 1146.92026 |
| [2] | Amiroch, S.; Pradana, M. S.; Irawan, M. I.; Mukhlash, I., Multiple alignment analysis on phylogenetic tree of the spread of SARS epidemic using distance method, Journal of Physics: Conference Series, 890, 1, 012080 (2017) |
| [3] | Aringhieri, R.; Catanzaro, D.; Di Summa, M., Optimal solutions for the balanced minimum evolution problem, Computers and Operations Research, 38, 1845-1854 (2011) |
| [4] | Atteson, K., The performance of the neighbor-joining methods of phylogenetic reconstruction, Algorithmica, 25, 2-3, 251-278 (1999) · Zbl 0938.68747 |
| [5] | Bader, D. A.; Moret, B. M.E.; Vawter, L., Industrial applications of high-performance computing for phylogeny reconstruction, SPIE ITCom: Commercial application for high-performance computing, 159-168 (2001), SPIE, Bellingham, WA |
| [6] | Beerenwinkel, N.; Schwarz, R. F.; Gerstung, M.; Markowetz, F., Cancer evolution: Mathematical models and computational inference, Systematic Biology, 64, 1, e1-e25 (2015) |
| [7] | Beyer, W. A.; Stein, M.; Smith, T.; Ulam, S., A molecular sequence metric and evolutionary trees, Mathematical Biosciences, 19, 9-25 (1974) · Zbl 0273.92004 |
| [8] | Billera, L. J.; Holmes, S. P.; Vogtmann, K., Geometry of the space of phylogenetic trees, Advances in Applied Mathematics, 27, 4, 733-767 (2001) · Zbl 0995.92035 |
| [9] | Blaisdell, B. E., A measure of the similarity of sets of sequences not requiring sequence alignment, Proceedings of the National Academy of Sciences of the USA, 83, 5155-5159 (1986) · Zbl 0592.92011 |
| [10] | Böcherer, G.; Amjad, R. A., Informational divergence and entropy rate on rooted trees with probabilities, Ieee international symposium on information theory, 176-180 (2014), IEEE Computer Society: IEEE Computer Society Honolulu, HI, USA |
| [11] | Bordewich, M.; Gascuel, O.; Huber, K.; Moulton, V., Consistency of topological moves based on the balanced minimum evolution principle of phylogenetic inference, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6, 110-117 (2009) |
| [12] | Bowern, C.; Atkinson, Q., Computational phylogenetics and the internal structure of pama-nyungan, Language, 88, 4, 817-845 (2012) |
| [13] | Providence, Rhode Island, USA · Zbl 0303.15008 |
| [14] | Buneman, P., The recovery of trees from measure of dissimilarities, (Hodson, F. R.; Kendall, D. G.; Tautu, P., Archaeological and historical science (1971), Edinburgh University Press: Edinburgh University Press Edinburgh, UK), 387-395 |
| [15] | Bush, R. M.; Bender, C. A.; Subbarao, K.; Cox, N. J.; Fitch, W. M., Predicting the evolution of human influenza A, Science, 286, 5446, 1921-1925 (1999) |
| [16] | Caminiti, S.; Finocchi, I.; Petreschi, R., On coding labeled trees, Theoretical Computer Science, 382, 97-108 (2007) · Zbl 1188.68116 |
| [17] | Castro-Nallar, E.; Pérez-Losada, M.; Burton, G. F.; Crandall, K. A., The evolution of HIV: Inferences using phylogenetics, Molecular Phylogenetics and Evolution, 62, 2, 777-792 (2012) |
| [18] | Catanzaro, D., The minimum evolution problem: Overview and classification, Networks, 53, 2, 112-125 (2009) · Zbl 1168.92036 |
| [19] | Catanzaro, D., Estimating phylogenies from molecular data, (Bruni, R., Mathematical approaches to polymer sequence analysis and related problems (2011), Springer, NY), 149-176 |
| [20] | Catanzaro, D.; Aringhieri, R.; di Summa, M.; Pesenti, R., A branch-price-and-cut algorithm for the minimum evolution problem, European Journal of Operational Research, 244, 3, 753-765 (2015) · Zbl 1346.90210 |
| [21] | Catanzaro, D.; Frohn, M.; Pesenti, R., An information theory perspective on the balanced minimum evolution problem, Operations Research Letters, 48, 3, 362-367 (2020) · Zbl 1525.92050 |
| [22] | Catanzaro, D.; Gatto, L.; Milinkovitch, M., Assessing the applicability of the GTR nucleotide substitution model through simulations, Evolutionary Bioinformatics, 2, 145-155 (2006) |
| [23] | Catanzaro, D.; Labbé, M.; Pesenti, R., The balanced minimum evolution problem under uncertain data, Discrete Applied Mathematics, 161, 13-14, 1789-1804 (2013) · Zbl 1288.90071 |
| [24] | Catanzaro, D.; Labbé, M.; Pesenti, R.; Salazar-Gonzáles, J. J., Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion, Networks, 53, 2, 126-140 (2009) · Zbl 1168.92037 |
| [25] | Catanzaro, D.; Labbé, M.; Pesenti, R.; Salazar-Gonzáles, J. J., The balanced minimum evolution problem, INFORMS Journal on Computing, 24, 2, 276-294 (2012) · Zbl 1461.92066 |
| [26] | Catanzaro, D.; Pesenti, R., Enumerating vertices of the balanced minimum evolution polytope, Computers and Operations Research, 109, 209-217 (2019) · Zbl 1458.90639 |
| [27] | Catanzaro, D.; Pesenti, R.; Milinkovitch, M., A non-linear optimization procedure to estimate distances and instantaneous substitution rate matrices under the GTR model, Bioinformatics, 22, 6, 708-715 (2006) |
| [28] | Catanzaro, D.; Pesenti, R.; Wolsey, L. A., On the balanced minimum evolution polytope, Discrete Optimization, 36, 1-33 (2020) · Zbl 1506.90274 |
| [29] | Catanzaro, D.; Ravi, R.; Schwartz, R., A mixed integer linear programming model to reconstruct phylogenies from single nucleotide polymorphism fragments under the maximum parsimony criterion, BMC Algorithms for Molecular Biology, 8, 1, 3 (2013) |
| [30] | Catanzaro, D.; Schackney, S. E.; Schäffer, A. A.; Schwartz, R., Classifying the progression of Ductal Carcinoma from single-cell sampled data via integer linear programming: A case study, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 13, 4, 643-655 (2016) |
| [31] | Cavalli-Sforza, L. L.; Edwards, A. W.F., Phylogenetic analysis: Models and estimation procedures, American Journal of Human Genetics, 19, 233-257 (1967) |
| [32] | Çela, E., The quadratic assignment problem (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA |
| [33] | Chang, B. S.W.; Donoghue, M. J., Recreating ancestral proteins, Trends in Ecology and Evolution, 15, 3, 109-114 (2000) |
| [34] | Cheng, X.; Du, D. Z., Steiner trees in industry (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA |
| [35] | Chowdhury, S. A.; Shackney, S. E.; Heselmeyer-Haddad, K.; Ried, T.; Schäffer, A. A.; Schwartz, R., Phylogenetic analysis of multiprobe fluorescence in situ hybridization data from tumor cell populations, Bioinformatics, 29, 13, i189-i198 (2013) |
| [36] | Cieslik, D., Steiner minimal trees (1998), Springer: Springer Boston, MA, USA · Zbl 0997.05500 |
| [37] | Darwin, C., On the origin of species (1964), Harvard University Press: Harvard University Press Cambridge, MA, USA |
| [38] | Denis, F.; Gascuel, O., On the consistency of the minimum evolution principle of phylogenetic inference, Discrete Applied Mathematics, 127, 66-77 (2003) · Zbl 1023.62109 |
| [39] | Desper, R.; Gascuel, O., Fast and accurate phylogeny reconstruction algorithms based on the minimum evolution principle, Journal of Computational Biology, 9, 5, 687-705 (2002) · Zbl 1016.68692 |
| [40] | Desper, R.; Gascuel, O., Theoretical foundations of the balanced minimum evolution method of phylogenetic inference and its relationship to the weighted least-squares tree fitting, Molecular Biology and Evolution, 21, 3, 587-598 (2004) |
| [41] | Desper, R.; Gascuel, O., The minimum-evolution distance-based approach to phylogeny inference, Mathematics of Evolution and Phylogeny, 1-32 (2005) · Zbl 1090.62121 |
| [42] | Devadoss, S. L.; Durell, C.; Forcey, S., Split network polytopes and network spaces, The 31st international conference on formal power series and algebraic combinatorics, 82B, 68 (2019), Séminaire Lotharingien de Combinatoire · Zbl 1435.05050 |
| [43] | Du, D. Z.; Hu, X., Steiner tree problems in computer communication networks (2008), World Scientific Publishing Company: World Scientific Publishing Company Singapore · Zbl 1156.90014 |
| [44] | Du, D. Z.; Smith, J. M.; Rubinstein, J. H., Advances in Steiner trees (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA, USA · Zbl 0932.00010 |
| [45] | Duellman, W. E.; Marion, A. B.; Hedges, S. B., Phylogenetics, classification, and biogeography of the treefrogs (Amphibia: Anura: Arboranae), Zootaxa, 4104, 1, 1-109 (2016) |
| [46] | Eickmeyer, K.; Huggins, P.; Pachter, L.; Yoshida, R., On the optimality of the neighbor-joining algorithm, Algorithms for Molecular Biology, 3, 1, 5 (2008) |
| [47] | Erdös, P. L.; Steel, M. A.; Székély, L. A.; Warnow, T., A few logs suffice to build (almost) all trees: Part I, Random Structures and Algorithms, 14, 2, 153-184 (1999) · Zbl 0945.60004 |
| [48] | Farris, J. S., Methods for computing wagner trees, Systematic Biology, 19, 1, 83-92 (1970) |
| [49] | Felsenstein, J., Cases in which parsimony or compatibility methods will be positively misleading, Systematic Zoology, 27, 401-410 (1978) |
| [50] | Felsenstein, J., An alternating least-squares approach to inferring phylogenies from pairwise distances, Systematic Biology, 46, 101-111 (1997) |
| [51] | Felsenstein, J., Inferring phylogenies (2004), Sinauer Associates, Sunderland, MA |
| [52] | Fiorini, S.; Joret, G., Approximating the balanced minimum evolution problem, Operations Research Letters, 40, 1, 31-35 (2012) · Zbl 1242.90275 |
| [53] | Fitch, W. M., Toward defining the course of evolution: Minimum change for a specified tree topology, Systematic Zoology, 20, 4, 406-416 (1971) |
| [54] | Forcey, S.; Keefe, L.; Sands, W., Facets of the balanced minimal evolution polytope, Journal of Mathematical Biology, 73, 2, 447-468 (2015) · Zbl 1346.90572 |
| [55] | in press · Zbl 1373.90072 |
| [56] | Forster, P.; Forster, L.; Renfrew, C.; Forster, M., Phylogenetic network analysis of SARS-CoV-2 genomes, Proceedings of the National Academy of Sciences of the USA, 117, 11, 9241-9243 (2020) |
| [57] | Frohn, M. (2020). On the approximability of the fixed-tree balanced minimum evolution problem. To appear in Optimization Letters,. · Zbl 1475.90081 |
| [58] | Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness (2003), Freeman: Freeman New York, NY |
| [59] | Gascuel, O., On the optimization principle in phylogenetic analysis and the minimum evolution criterion, Journal of Classification, 19, 1, 67-69 (2000) |
| [60] | Gascuel, O., Mathematics of evolution and phylogeny (2005), Oxford University Press: Oxford University Press New York, NY · Zbl 1104.92332 |
| [61] | Gascuel, O.; Bryant, D.; Denis, F., Strengths and limitations of the minimum evolution principle, Systematic Biology, 50, 621-627 (2001) |
| [62] | Gascuel, O.; Levy, D., A reduction algorithm for approximating a (non-metric) dissimilarity by a tree distance, Journal of Classification, 13, 129-155 (1996) · Zbl 1008.62615 |
| [63] | Gascuel, O.; McKenzie, A., Performance analysis of hierarchical clustering algorithms, Journal of Classification, 21, 3-18 (2004) · Zbl 1091.91059 |
| [64] | Gascuel, O.; Steel, M., A ’stochastic safety radius’ for distance-based tree reconstruction, Algorithmica, 74, 1386-1403 (2016) · Zbl 1350.92035 |
| [65] | Gascuel, O.; Steel, M. A., Neighbor-joining revealed, Molecular Biology and Evolution, 23, 11, 1997-2000 (2006) |
| [66] | Gawrilow, E.; Joswig, M., Polymake: A framework for analyzing convex polytopes, (Kalai, G.; Ziegler, G. M., Polytopes - Combinatorics and computation (2000), Birkhäuser), 43-73 · Zbl 0960.68182 |
| [67] | Ge, X.-Y.; Li, J.-L.; Yang, X.-L.; Chmura, A. A.; Zhu, G.; Epstein, J. H.; Shi, Z.-L., Isolation and characterization of a bat SARS-like coronavirus that uses the ACE2 receptor, Nature, 503, 535-538 (2013) |
| [68] | Gusfield, D., The Steiner tree problem in phylogeny, Technical Report (1984), Yale University, New Haven, CT |
| [69] | Harvey, P. H.; Brown, A. J.L.; Smith, J. M.; Nee, S., New uses for new phylogenies (1996), Oxford University Press: Oxford University Press Oxford, UK |
| [70] | Hasegawa, M.; Kishino, H.; Yano, T., Evolutionary trees from DNA sequences: A maximum likelihood approach, Journal of Molecular Evolution, 17, 368-376 (1981) |
| [71] | Haws, D. C.; Hodge, T. L.; Yoshida, R., Optimality of the neighbor joining algorithm and faces of the balanced minimum evolution polytope, Bulletin of Mathematical Biology, 73, 2627-2648 (2011) · Zbl 1334.92292 |
| [72] | Hirschler, T.; Woess, W., Comparing entropy rates on finite and infinite rooted trees, IEEE Transactions on Information Theory, 64, 8, 5570-5580 (2018) · Zbl 1401.94076 |
| [73] | Hubert, L. J.; Arabie, P., Iterative projection strategies for the least-squares fitting of tree structures to proximity data, British Journal of Mathematical and Statistical Psychology, 48, 281-317 (1995) · Zbl 0858.62002 |
| [74] | Huelsenbeck, J. P.; Larget, B.; Miller, R. E.; Ronquist, F., Potential applications and pitfalls of Bayesian inference of phylogeny, Systematic Biology, 51, 673-688 (2002) |
| [75] | Huelsenbeck, J. P.; Ronquist, F.; Nielsen, R.; Bollback, J. P., Bayesian inference of phylogeny and its impact on evolutionary biology, Science, 294, 2310-2314 (2001) |
| [76] | Huson, D. H.; Rupp, R.; Scornavacca, C., Phylogenetic networks (2011), Cambridge University Press: Cambridge University Press Cambridge, UK |
| [77] | Hwang, F. K.; Richards, D. S.; Winter, P., The steiner tree problem (1992), North-Holland: North-Holland Amsterdam, The Netherlands · Zbl 0774.05001 |
| [78] | Idel, M. (2016). A review of matrix scaling and Sinkhorn’s normal form for matrices and positive maps. arXiv: 1609.06349. |
| [79] | Jäger, G., Global-scale phylogenetic linguistic inference from lexical resources, Scientific Data, 5, 180189 (2018) |
| [80] | Johnson, D. S.; Lenstra, J. K.; Kan, A. H.G. R., The complexity of the network design problem, Networks, 8, 279-285 (1978) · Zbl 0395.94048 |
| [81] | Jordan, C., Sur les assemblages des lignes, Journal für die reine und angewandte Mathematik, 70, 185-190 (1869) · JFM 02.0344.01 |
| [82] | Jukes, T. H.; Cantor, C., Evolution of protein molecules, (Munro, H. N., Mammalian protein metabolism (1969), Academic Press, New York, NY), 21-123 |
| [83] | Kadam, S.; Vuong, T. D.; Qiu, D.; Meinhardt, C. G.; Song, L.; Deshmukh, R.; Nguyen, H. T., Genomic-assisted phylogenetic analysis and marker development for next generation soybean cyst nematode resistance breeding, Plant Science, 242, 342-350 (2016) |
| [84] | Kapranov, M. M., The permutoassociahedron, Mac Lane’s coherence theorem and asymptotic zones for the KZ equation, Journal of Pure and Applied Algebra, 85, 2, 119-142 (1993) · Zbl 0812.18003 |
| [85] | Khachiyan, L., Diagonal matrix scaling is \(\mathcal{NP} \)-hard, Linear algebra and its applications, 234, 173-179 (1996) · Zbl 0840.65030 |
| [86] | Kidd, K. K.; Sgaramella-Zonta, L. A., Phylogenetic analysis: Concepts and methods, American Journal of Human Genetics, 23, 235-252 (1971) |
| [87] | Kimura, M., A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences, Journal of Molecular Evolution, 16, 111-120 (1980) |
| [88] | Klung, W. S.; Cummings, M. R.; Spencer, C. A.; Palladino, M. A.; Killian, D., Concepts of genetics (2019), Pearson: Pearson NY |
| [89] | Kreher, D. L.; Stinson, D. R., Combinatorial algorithms: Generation, enumeration, and search (1999), CRC Press: CRC Press Boca Raton, FL · Zbl 0911.05002 |
| [90] | Kress, W. J.; Erickson, D. L.; Swenson, N. G.; Thompson, J.; Uriarte, M.; Zimmermann, J. K., Advances in the use of DNA barcodes to build a community phylogeny for tropical trees in a puerto rican forest dynamics plot, PLoS One, 5, 11, e15409 (2010) |
| [91] | Lähnemann, D.; Köster, J.; Szczurek, E.; McCarthy, D. J.; Hicks, S. C.; Robinson, M. D.; Schönhuth, A., Eleven grand challenges in single-cell data science, Genome Biology, 21, 1, 1-35 (2020) |
| [92] | Lai, C. C.; Shih, T. P.; Ko, W. C.; Tang, H. J.; Hsue, P. R., Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) and coronavirus disease-2019 (COVID-19): The epidemic and the challenges, International Journal of Antimicrobial Agents, 55, 3, 105924 (2020) |
| [93] | Lanave, C.; Preparata, G.; Saccone, C.; Serio, G., A new method for calculating evolutionary substitution rates, Journal of Molecular Evolution, 20, 86-93 (1984) |
| [94] | Lawler, E.; Lenstra, J.; Kan, A. R.; Shmoys, D., The traveling salesman problem: A guided tour of combinatorial optimization (1985), John Wiley and Sons Ltd.: John Wiley and Sons Ltd. New York, NY · Zbl 0562.00014 |
| [95] | Lefort, V.; Desper, R.; Gascuel, O., FastME 2.0: A comprehensive, accurate, and fast distance-based phylogeny inference program, Molecular Biology and Evolution, 32, 10, 2798-2800 (2015) |
| [96] | Leibold, M. A.; Economo, E. P.; Peres-Neto, P., Metacommunity phylogenetics: Separating the roles of environmental filters and historical biogeography, Ecology Letters, 13, 10, 1290-1299 (2010) |
| [97] | Lemmon, E. M.; Lemmon, A. R., High-throughput genomic data in systematics and phylogenetics, Annual Review of Ecology, Evolution, and Systematics, 44, 99-121 (2013) |
| [98] | Lemoine, F.; Blassel, L.; Voznica, J.; Gascuel, O., COVID-Align: Accurate online alignment of hCoV-19 genomes using a profile HMM, Bioinformatics (2020) |
| [99] | Li, X.; Mao, Y., Generalized connectivity of graphs (2016), Springer: Springer Boston, MA, USA · Zbl 1346.05001 |
| [100] | Lourenço, H. R.; Martin, O.; Stützle, T., Iterated local search, (Glover, F.; Kochenberger, G. A., Handbook of metaheuristics. Handbook of metaheuristics, International Series in Operations Research & Management Science, 57 (2003), Springer: Springer Boston, MA, USA), 320-353 · Zbl 1116.90412 |
| [101] | Lu, C. L.; Tang, C. Y.; Lee, R. C.T., The full steiner tree problem, Theoretical Computer Science, 306, 55-67 (2003) · Zbl 1061.68121 |
| [102] | Makarenkov, V.; Leclerc, B., Circular orders of tree metrics, and their uses for the reconstruction and fitting of phylogenetic trees, (Mirkin, B.; McMorris, F.; Roberts, F.; Rzhetsky, A., Mathematical hierarchies and biology. Mathematical hierarchies and biology, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 37 (1997), American Mathematical Society: American Mathematical Society Providence, RI), 183-208 · Zbl 0886.05053 |
| [103] | Makarenkov, V.; Leclerc, B., An algorithm for the fitting of a tree metric according to a weighted least-squares criterion, Journal of Classification, 16, 3-26 (1999) · Zbl 0983.92020 |
| [104] | Marra, M. A.; Jones, S. J.; Astell, C. R.; Holt, R. A.; Brooks-Wilson, A.; Butterfield, Y. S.; Roper, R. L., The genome sequence of the SARS-associated coronavirus, Science, 300, 5624, 1399-1404 (2003) |
| [105] | Martin, R. K., Large scale linear and integer optimization: A unified approach (1999), Springer-Verlag: Springer-Verlag New York, NY · Zbl 1053.90001 |
| [106] | Mavian, C.; Pond, S. K.; Marini, S.; Magalis, B. R.; Vandamme, A. M.; Dellicour, S.; Salemi, M., Sampling bias and incorrect rooting make phylogenetic network tracing of SARS-COV-2 infections unreliable, Proceedings of the National Academy of Sciences of the USA, 117, 23, 12522-12523 (2020) |
| [107] | McCormack, J. E.; Hird, S. M.; Zellmer, A. J.; Carstens, B. C.; Brumfield, R. T., Applications of next-generation sequencing to phylogeography and phylogenetics, Molecular Phylogenetics and Evolution, 66, 2, 526-538 (2013) |
| [108] | McGuire, J. A.; Witt, C. C.; Remsen Jr., J. V.; Corl, A.; Rabosky, D. L.; Altshuler, D. L.; Dudley, R., Molecular phylogenetics and the diversification of hummingbirds, Current Biology, 24, 8, 910-916 (2014) |
| [109] | 445-57 |
| [110] | Myers, M. A.; Satas, G.; Raphael, B. J., Calder: Inferring phylogenetic trees from longitudinal tumor samples, Cell Systems, 8, 5, 514-522 (2019) |
| [111] | Nei, M., Molecular evolution and phylogenetics (2000), Oxford University Press: Oxford University Press Oxford, UK |
| [112] | Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization (1999), Wiley-Interscience: Wiley-Interscience New York, NY · Zbl 0944.90001 |
| [113] | Ng, H.-C.; Liu, S.; Luk, W., Reconfigurable acceleration of genetic sequence alignment: A survey of two decades of efforts, (Santambrogio, M.; Göhringer, D.; Stroobandt, D.; Mentens, N.; Nurmi, J., 2017 27th international conference on field programmable logic and applications (FPL) (2017)), 1-8 |
| [114] | Notredame, C., Recent progress in multiple sequence alignment: A survey, Pharmacogenomics, 3, 1, 131-144 (2004) |
| [115] | Ou, C. Y.; Ciesielski, C. A.; Myers, G.; Bandea, C. I.; Luo, C. C.; Korber, B. T.M.; Jaffe, H. W., Molecular epidemiology of HIV transmission in a dental practice, Science, 256, 5060, 1165-1171 (1992) |
| [116] | Pachter, L.; Sturmfels, B., The mathematics of phylogenomics, SIAM Review, 49, 1, 3-31 (2007) · Zbl 1107.92016 |
| [117] | Page, R. D.M.; Holmes, E. C., Molecular evolution: A phylogenetic approach (1998), Blackwell Science: Blackwell Science Oxford, UK |
| [118] | Pardi, F., Algorithms on Phylogenetic Trees (2009), University of Cambridge, UK, Ph.D. thesis. |
| [119] | Pardi, F.; Guillemot, S.; Gascuel, O., Robustness of phylogenetic inference based on minimum evolution, Bulletin of Mathematical Biology, 72, 1820-1839 (2010) · Zbl 1202.92064 |
| [120] | Parker, D. S.; Ram, P., The construction of Huffman codes is a submodular (“convex”) optimization problem over a lattice of binary trees, SIAM Journal on Computing, 28, 5, 1875-1905 (1996) · Zbl 0967.94005 |
| [121] | Pauplin, Y., Direct calculation of a tree length using a distance matrix, Journal of Molecular Evolution, 51, 1, 41-47 (2000) |
| [122] | Pennington, G.; Smith, C. A.; Shackney, S.; Schwartz, R., Reconstructing tumor phylogenies from heterogeneous single-cell data, Journal of Bioinformatics and Computational Biology, 5, 2a, 407-427 (2006) |
| [123] | Perovic, V. R., Novel algorithm for phylogenetic analysis of proteins: Application to analysis of the evolution of H5N1 influenza viruses, Journal of Mathematical Chemistry, 51, 2238-2255 (2013) · Zbl 1320.92064 |
| [124] | Poon, A. F.Y.; Joy, J. B.; Woods, C. K.; Shurgold, S.; Colley, G.; Brumme, C. J.; Harrigan, P. R., The impact of clinical, demographic and risk factors on rates of HIV transmission: A population-based phylogenetic analysis in British Columbia, Canada, The Journal of Infectious Diseases, 211, 6, 926-935 (2015) |
| [125] | Pop, P. C., Generalized network design problems: Modeling and optimization (2012), De Gruyter: De Gruyter Berlin, Germany · Zbl 1260.90143 |
| [126] | Popper, K., The logic of scientific discovery (2002), Routledge: Routledge London, UK · Zbl 1256.03001 |
| [127] | Prömel, H. J.; Steger, A., The Steiner tree problem: A tour through graphs, algorithms, and complexity (2002), Vieweg+Teubner Verlag: Vieweg+Teubner Verlag Berlin · Zbl 0992.68156 |
| [128] | Reiner, V.; Ziegler, G. M., Coxeter-associahedra, 41, 364-393 (1994), Zuse Institute Berlin (ZIB): Zuse Institute Berlin (ZIB) Berlin, Takustrasse 7, 14195, Germany · Zbl 0822.52007 |
| [129] | Riester, M.; Attolini, C. S.-O.; Downey, R. J.; Singer, S.; Michor, F., A differentiation-based phylogeny of cancer subtypes, PLoS Computational Biology, 6, 5, e1000777 (2010) |
| [130] | Riester, M.; Attolini, C. S.-O.; Downey, R. J.; Singer, S.; Michor, F., A differentiation-based phylogeny of cancer subtypes, PLoS Computational Biology, 6, e100077 (2010) |
| [131] | Rodriguez, F.; Oliver, J. L.; Marin, A.; Medina, J. R., The general stochastic model of nucleotide substitution, Journal of Theoretical Biology, 142, 4, 485-501 (1990) |
| [132] | Rosenberg, M. S., Sequence alignment: Methods, models, concepts, and strategies (2011), University of California Press: University of California Press LA |
| [133] | Ross, H. A.; Rodrigo, A. G., Immune-mediated positive selection drives Human Immunodeficency Virus type 1 molecular variation and predicts disease duration, Journal of Virology, 76, 22, 11715-11720 (2002) |
| [134] | Rzhetsky, A.; Nei, M., A simple method for estimating and testing minimum evolution trees., Computer Applications in the Biosciences, 10, 409-412 (1992) |
| [135] | Rzhetsky, A.; Nei, M., Theoretical foundations of the minimum evolution method of phylogenetic inference, Molecular Biology and Evolution, 10, 5, 1073-1095 (1993) |
| [136] | Rzhetsky, A.; Nei, M., METREE: A program package for inferring and testing minimum evolution trees, Computer Applications in the Biosciences, 10, 409-412 (1994) |
| [137] | Saitou, N.; Imanishi, T., Relative efficiencies of the Fitch-Margoliash, maximum-parsimony, maximum-likelihood, minimum-evolution, and neighbour-joining methods of phylogenetic tree construction in obtaining the correct tree, Molecular Biology and Evolution, 6, 514-525 (1989) |
| [138] | Saitou, N.; Nei, M., The neighbor-joining method: A new method for reconstructing phylogenetic trees, Molecular Biology and Evolution, 4, 406-425 (1987) |
| [139] | Sayood, K., Introduction to data compression (2017), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA |
| [140] | Scheiner, S. M.; Mindell, D. P., The theory of evolution: Principles, concepts and assumptions (2020), University of Chicago Press: University of Chicago Press Chicago, IL, USA |
| [141] | Schulmeister, S., Inconsistency of maximum parsimony revisited, Systematic Biology, 53, 4, 521-528 (2004) |
| [142] | Schwartz, R., Computational models for cancer phylogenetics, (Warnow, T., Bioinformatics and phylogenetics. computational biology, vol. 29 (2019), Springer, Cham), 243-275 · Zbl 1429.92003 |
| [143] | Semple, C.; Steel, M. A., Phylogenetics (2003), Oxford University Press, New York, NY · Zbl 1043.92026 |
| [144] | Semple, C.; Steel, M. A., Cyclic permutations and evolutionary trees, Advances in Applied Mathematics, 32, 4, 669-680 (2004) · Zbl 1050.05027 |
| [145] | Simonsen, M.; Mailund, T.; Pedersen, C. N.S., Rapid neighbour joining, Lecture Notes in Bioinformatics, 5251, 113-122 (2008) |
| [146] | Sinkhorn, R., A relationship between arbitrary positive matrices and doubly stochastic matrices, Annals of Mathematical Statistics, 35, 876-879 (1964) · Zbl 0134.25302 |
| [147] | Sridhar, S.; Dhamdhere, K.; Blelloch, G. E.; Halperin, E.; Ravi, R.; Schwartz, R., Algorithms for efficient near-perfect phylogenetic tree reconstruction in theory and practice, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4, 4, 561-571 (2007) |
| [148] | Sridhar, S.; Lam, F.; Blelloch, G. E.; Ravi, R.; Schwartz, R., Mixed integer linear programming for maximum parsimony phylogeny inference, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5, 3, 323-331 (2008) |
| [149] | Stuart, G. W.; Moffett, K.; Baker, S., Integrated gene and species phylogenies from unaligned whole genome protein sequences, Bioinformatics, 18, 1, 100-108 (2002) |
| [150] | Stuart, G. W.; Moffett, K.; Leader, J. J., A comprehensive vertebrate phylogeny using vector representations of protein sequences from whole genomes, Molecular Biology and Evolution, 19, 4, 554-562 (2002) |
| [151] | Studier, J. A.; Keppler, K. J., A note on the neighbor-joining algorithm of Saitou and Nei, Molecular Biology and Evolution, 5, 729-731 (1988) |
| [152] | Subramanian, A.; Shackney, S.; Schwartz, R., Novel multi-sample scheme for inferring phylogenetic markers from whole genome tumor profiles, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 10, 6, 1422-1431 (2013) |
| [153] | Tavare, S., Some probabilistic and statistical problems in the analysis of DNA sequences, Lectures on Mathematics in the Life Sciences, 17, 57-86 (1987) · Zbl 0587.92015 |
| [154] | Valiente-Banuet, A.; Verdú, M., Plant facilitation and phylogenetics, Annual Review of Ecology, Evolution, and Systematics, 44, 347-366 (2013) |
| [155] | Vinga, S., Information theory applications for biological sequence analysis, Briefings in Bioinformatics, 15, 3, 376-389 (2014) |
| [156] | Vinga, S.; Almeida, J., Alignment-free sequence comparison - A review, Bioinformatics, 19, 4, 513-523 (2003) |
| [157] | Vinh, L. S.; von Haeseler, A., Shortest triplet clustering: Reconstructing large phylogenies using representative sets, BMC bioinformatics, 6, 92, 1-14 (2005) |
| [158] | Volkenstein, M. V.; Livshits, M. A., Speciation and bifurcations, Biosystems, 23, 1, 1-5 (1989) |
| [159] | Waddell, P. J.; Steel, M. A., General time-reversible distances with unequal rates across sites: Mixing gamma and inverse gaussian distributions with invariant sites, Molecular Phylogenetics and Evolution, 8, 398-414 (1997) |
| [160] | Washburne, A. D.; Morton, J. T.; Sanders, J.; McDonald, D.; Zhu, Q.; Oliverio, A. M.; Knight, R., Methods for phylogenetic analysis of microbiome data, Nature Microbiology, 3, 652-661 (2018) |
| [161] | Waterman, M. S.; Smith, T. F.; Singh, M.; Beyer, W. A., Additive evolutionary trees, Journal of Theoretical Biology, 64, 199-213 (1977) |
| [162] | Wu, B. Y.; Chao, K. M., Spanning trees and optimization problems (2004), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton, FL · Zbl 1072.90047 |
| [163] | Yang, Z., Estimating the pattern of nucleotide substitution, Journal of Molecular Evolution, 39, 105-111 (1994) |
| [164] | Yang, Z., Molecular evolution: A statistical approach (2014), Oxford University Press: Oxford University Press Oxford, UK · Zbl 1288.92002 |
| [165] | Zhou, P.; Yang, X. L.; Shi, Z. L., A pneumonia outbreak associated with a new coronavirus of probable bat origin, Nature, 579, 270-273 (2020) |
| [166] | Zielezinski, A.; Vinga, S.; Almeida, J.; Karlowski, W. M., Alignment-free sequence comparison: Benefits, applications, and tools, Genome Biology, 18, 1, 186 (2017) |
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.
