×

A branch-price-and-cut algorithm for the minimum evolution problem. (English) Zbl 1346.90210

Summary: We investigate the Minimum Evolution Problem (MEP), an \(\mathcal{NP}\)-hard network design problem arising from computational biology. The MEP consists in finding a weighted unrooted binary tree having \(n\) leaves, minimal length, and such that the sum of the edge weights belonging to the unique path between each pair of leaves is greater than or equal to a prescribed value. We study the polyhedral combinatorics of the MEP and investigate its relationships with the Balanced Minimum Evolution Problem. We develop an exact solution approach for the MEP based on a nontrivial combination of a parallel branch-price-and-cut scheme and a non-isomorphic enumeration of all possible solutions to the problem. Computational experiments show that the new solution approach outperforms the best mixed integer linear programming formulation for the MEP currently described in the literature. Our results give a perspective on the combinatorics of the MEP and suggest new directions for the development of future exact solution approaches that may turn out useful in practical applications. We also show that the MEP is statistically consistent.

MSC:

90B10 Deterministic network models in operations research
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

fastDNAml
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Aringhieri, R.; Catanzaro, D.; Di Summa, M., Optimal solutions for the balanced minimum evolution problem, Computers and Operations Research, 38, 1845-1854 (2011)
[3] Aringhieri, R.; Hansen, P.; Malucelli, F., Chemical trees enumeration algorithms, 4OR, 1, 67-83 (2003) · Zbl 1041.05075
[4] Avis, D.; Fukuda, K., A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Computational Geometry, 8, 295-313 (1992) · Zbl 0752.68082
[5] Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete Applied Mathematics, 65, 21-46 (1996) · Zbl 0854.68070
[6] Bader, D. A.; Moret, B. M.E.; Vawter, L., Industrial applications of high-performance computing for phylogeny reconstruction, Spie itcom 4528, 159-168 (2001), SPIE, Denver, CO
[7] Beerenwinkel, N.; Schwartz, R. F.; Gerstung, M.; Markowetz, F., Cancer evolution: Mathematical models and computational inference, Systematic Biology, 64, 1, e1-e25 (2015)
[8] 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
[9] 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)
[10] Catanzaro, D., Estimating phylogenies from molecular data, (Bruni, R., Mathematical approaches to polymer sequence analysis and related problems (2011), Springer: Springer New York)
[11] 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
[12] 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
[13] 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)
[15] Chang, B. S.W.; Donoghue, M. J., Recreating ancestral proteins, Trends in Ecology and Evolution, 15, 3, 109-114 (2000)
[16] 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)
[17] Culberson, J.; Rudnicki, P., A fast algorithm for constructing trees from distance matrices, Information Processing Letters, 30, 215-220 (1989) · Zbl 0665.68052
[18] D’Ambrosio, C.; Lodi, A.; Martello, S., Combinatorial traveling salesman problem algorithms (2011), Wiley Encyclopedia of Operations Research and Management Science
[19] 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
[20] 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)
[21] Farach, M.; Kannan, S.; Warnow, T., A robust model for finding optimal evolutionary trees, Algorithmica, 13, 155-179 (1995) · Zbl 0831.92019
[22] Felsenstein, J., Inferring phylogenies (2004), Sinauer Associates: Sinauer Associates Sunderland, MA
[23] Fiorini, S.; Joret, G., Approximating the balanced minimum evolution problem, Operations Research Letters, 40, 31-35 (2012) · Zbl 1242.90275
[24] Fitch, W. M., Rate of change of concomitantly variable codons, Journal of Molecular Evolution, 1, 84-96 (1971)
[25] Galtier, N., Maximum-likelihood phylogenetic analysis under covarion-like model, Molecular Biology and Evolution, 18, 866-873 (2001)
[26] Gascuel, O., Mathematics of evolution and phylogeny (2005), Oxford University Press: Oxford University Press New York · Zbl 1104.92332
[27] Gascuel, O.; Bryant, D.; Denis, F., Strengths and limitations of the minimum evolution principle, Systematic Biology, 50, 621-627 (2001)
[28] Glover, F.; Kochenberger, G. A., Handbook of metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA, USA · Zbl 1058.90002
[29] Hansen, P.; Jaumard, B.; Labatteux, C.; Zeng, M., Coding chemical trees with the centered \(n\)-tuple code, Journal of Chemical Information and Computer Science, 34, 782-790 (1994)
[30] 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
[31] Hasegawa, M.; Kishino, H.; Yano, T., Evolutionary trees from DNA sequences: A maximum likelihood approach, Journal of Molecular Evolution, 17, 368-376 (1981)
[32] Huelsenbeck, J. P., Testing a covariotide model of DNA substitution, Molecular Biology and Evolution, 19, 698-707 (2002)
[33] 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)
[34] 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)
[35] 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
[36] Jordan, C., Sur les assemblages des lignes, Journal für die reine und angewandte Mathematik, 70, 185-190 (1869) · JFM 02.0344.01
[37] Jukes, T. H.; Cantor, C. R., Evolution of protein molecules, (Munro, H. N., Mammalian protein metabolism (1969), Academic Press: Academic Press New York), 21-123
[38] Kidd, K. K.; Sgaramella-Zonta, L. A., Phylogenetic analysis: Concepts and methods, American Journal of Human Genetics, 23, 235-252 (1971)
[39] 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)
[40] Kvasnička, V.; Pospichal, J., Canonical indexing and constructive enumeration of molecular graphs, Journal of Chemical Information and Computer Science, 56, 1777-1802 (1991)
[41] Lanave, C.; Preparata, G.; Saccone, C.; Serio, G., A new method for calculating evolutionary substitution rates, Journal of Molecular Evolution, 20, 86-93 (1984)
[42] Lopez, P.; Casane, D.; Philippe, H., Heterotachy: An important process of protein evolution, Molecular Biology and Evolution, 19, 1-7 (2002)
[43] Marra, M. A.; Jones, S. J.; Astell, C. R.; Holt, R. A.; Brooks-Wilson, A.; Butterfield, Y. S., The genome sequence of the SARS-associated coronavirus, Science, 300, 5624, 1399-1404 (2003)
[44] Misra, N.; Blelloch, G. E.; Ravi, R.; Schwartz, R., Generalized buneman pruning for inferring the most parsimonious multi-state phylogeny, Journal of Computational Biology, 18, 3, 445-457 (2011)
[45] Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization (1999), Wiley-Interscience: Wiley-Interscience New York · Zbl 0469.90052
[46] Ou, C. Y.; Ciesielski, C. A.; Myers, G.; Bandea, C. I.; Luo, C. C.; Korber, B. T.M., Molecular epidemiology of HIV transmission in a dental practice, Science, 256, 5060, 1165-1171 (1992)
[47] Pachter, L.; Sturmfels, B., The mathematics of phylogenomics, SIAM Review, 49, 1, 3-31 (2007) · Zbl 1107.92016
[48] Page, R. D.M.; Holmes, E. C., Molecular evolution: A phylogenetic approach (1998), Blackwell Science: Blackwell Science Oxford, UK
[49] 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
[50] Pauplin, Y., Direct calculation of a tree length using a distance matrix, Journal of Molecular Evolution, 51, 41-47 (2000)
[51] 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)
[52] Pop, P. C., Generalized network design problems: Modeling and optimization (2012), De Gruyter: De Gruyter Berlin · Zbl 1260.90143
[53] Read, R. C., Graph theory and computing (1972), Academic Press: Academic Press New York · Zbl 0243.00006
[54] Riester, M.; Attolini, C. S.-O.; Downey, R. J.; Singer, S.; Michor, F., A differentiation-based phylogeny of cancer subtypes, PLoS Computational Biology, 6, e1000777 (2010)
[55] Rodriguez, F.; Oliver, J. L.; Marin, A.; Medina, J. R., The general stochastic model of nucleotide substitution, Journal of Theoretical Biology, 142, 485-501 (1990)
[56] Ross, H. A.; Rodrigo, A. G., Immune-mediated positive selection drives human immunodeficiency virus type 1 molecular variation and predicts disease duration, Journal of Virology, 76, 22, 11715-11720 (2002)
[57] Rzhetsky, A.; Nei, M., Statistical properties of the ordinary least-squares generalized least-squares and minimum evolution methods of phylogenetic inference, Journal of Molecular Evolution, 35, 367-375 (1992)
[58] Rzhetsky, A.; Nei, M., Theoretical foundations of the minimum evolution method of phylogenetic inference, Molecular Biology and Evolution, 10, 1073-1095 (1993)
[59] Sattah, S.; Tversky, A., Additive similarity trees, Psychometrika, 42, 319-345 (1977)
[60] Semple, C.; Steel, M., Phylogenetics (2003), Oxford University Press: Oxford University Press New York · Zbl 1043.92026
[61] Semple, C.; Steel, M., Cyclic permutations and evolutionary trees, Advances in Applied Mathematics, 32, 4, 669-680 (2004) · Zbl 1050.05027
[62] 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)
[63] 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)
[64] 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)
[65] Trinajstić, N.; Nicolić, S.; Knop, J. V.; Müller, W. R.; Szymanski, K., Computational chemical graph theory (1991), Ellis Horwood: Ellis Horwood New York · Zbl 0746.05064
[66] 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)
[67] Waterman, M. S.; Smith, T. F.; Singh, M.; Beyer, W. A., Additive evolutionary trees, Journal of Theoretical Biology, 64, 199-213 (1977)
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.