A massively parallel branch-&-bound algorithm for the balanced minimum evolution problem. (English) Zbl 1542.90236
Summary: We build upon recent theoretical advances in the Balanced Minimum Evolution Problem (BMEP) to design a new massively parallel exact solution algorithm that proves to be up to one order of magnitude faster than the current state-of-the-art under the same computing settings and environment.
MSC:
| 90C35 | Programming involving graphs or networks |
| 05C05 | Trees |
| 90C27 | Combinatorial optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 92D15 | Problems related to evolution |
Keywords:
combinatorial optimization; integer programming; parallel branch-and-bound; network design; balanced minimum evolution problemReferences:
| [1] | Allen, B. L.; Steel, M., Subtree transfer operations and their induced metrics on evolutionary trees, Ann. Comb., 5, 1-15 (2001) · Zbl 0978.05023 |
| [2] | Aringhieri, R.; Catanzaro, D.; Di Summa, M., Optimal solutions for the balanced minimum evolution problem, Comput. Oper. Res., 38, 1845-1854 (2011) |
| [3] | Auch, A. F.; R., H. S.; Holland, B. R.; M., G., Genome BLAST distance phylogenies inferred from whole plastid and whole mitochondrion genome sequences, BMC Bioinformatics, 7, 350, 1-5 (2006) |
| [4] | Batagelj, V.; Pisanski, T.; Simoes-Pereira, J. M., An algorithm for tree-realizability of distance matrices, Int. J. Comput. Math., 34, 171-176 (1990) · Zbl 0699.68056 |
| [5] | Bordewich, M.; Gascuel, O.; Huber, K. T.; Moulton, V., Consistency of topological moves based on the balanced minimum evolution principle of phylogenetic inference, IEEE/ACM Trans. Comput. Biol. Bioinform., 6, 1, 110-117 (2009) |
| [6] | 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 |
| [7] | Buneman, P., A note on the metric properties of trees, J. Combin. Theory, 17, B, 48-50 (1974) · Zbl 0286.05102 |
| [8] | Caminiti, S.; Finocchi, I.; Petreschi, R., On coding labeled trees, Theoret. Comput. Sci., 382, 97-108 (2007) · Zbl 1188.68116 |
| [9] | Catanzaro, D.; Aringhieri, R.; di Summa, M.; Pesenti, R., A branch-price-and-cut algorithm for the minimum evolution problem, European J. Oper. Res., 244, 3, 753-765 (2015) · Zbl 1346.90210 |
| [10] | Catanzaro, D.; Frohn, M.; Gascuel, O.; Pesenti, R., A tutorial on the balanced minimum evolution, European J. Oper. Res., 300, 1, 1-19 (2022) · Zbl 1495.90148 |
| [11] | Catanzaro, D.; Frohn, M.; Pesenti, R., An information theory perspective on the balanced minimum evolution problem, Oper. Res. Lett., 48, 3, 362-367 (2020) · Zbl 1525.92050 |
| [12] | Catanzaro, D.; Labbé, M.; Pesenti, R.; Salazar-Gonzáles, J. J., The balanced minimum evolution problem, INFORMS J. Comput., 24, 2, 276-294 (2012) · Zbl 1461.92066 |
| [13] | Catanzaro, D.; Pesenti, R., Enumerating vertices of the balanced minimum evolution polytope, Comput. Oper. Res., 109, 209-217 (2019) · Zbl 1458.90639 |
| [14] | 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] | Catanzaro, D.; Pesenti, R.; Wolsey, L. A., On the balanced minimum evolution polytope, Discrete Optim., 36, 1-33 (2020) · Zbl 1506.90274 |
| [16] | Çela, E., The Quadratic Assignment Problem (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA |
| [17] | Chandra, R.; Dagum, L.; Kohr, D.; Menon, R.; Maydan, D.; McDonald, J., Parallel Programming in Open MP (2001), Morgan Kaufmann |
| [18] | Cheng, X.; Du, D. Z., Steiner Trees in Industry (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA |
| [19] | Cieslik, D., Steiner Minimal Trees (1998), Springer: Springer Boston, MA, USA · Zbl 0997.05500 |
| [20] | Criscuolo, A.; Michel, C. J., Phylogenetic inference with weighted codon evolutionary distances, J. Mol. Evol., 68, 377-392 (2009) |
| [21] | Cueto, M. A.; Matsen, F. A., Polyhedral geometry of phylogenetic rogue taxa, Bull. Math. Biol., 73, 6, 1202-1226 (2011) · Zbl 1215.92047 |
| [22] | 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 |
| [23] | 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, Mol. Biol. Evol., 21, 3, 587-598 (2004) |
| [24] | Desper, R.; Gascuel, O., Chapter Distance-based phylogeny reconstruction (optimal radius), (Kao, Ming-Yang, Encyclopedia of Algorithms (2008), Springer), 1-99 |
| [25] | 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 |
| [26] | 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 |
| [27] | Felsenstein, J., Distance methods for inferring phylogenies: A justification, Evolution, 38, 16-24 (1984) |
| [28] | Felsenstein, J., Inferring Phylogenies (2004), Sinauer Associates: Sinauer Associates Sunderland, MA |
| [29] | Fiorini, S.; Joret, G., Approximating the balanced minimum evolution problem, Oper. Res. Lett., 40, 1, 31-35 (2012) · Zbl 1242.90275 |
| [30] | Forcey, S.; Keefe, L.; Sands, W., Facets of the balanced minimal evolution polytope, J. Math. Biol., 73, 2, 447-468 (2015) · Zbl 1346.90572 |
| [31] | Forcey, S.; Keefe, L.; Sands, W., Split-facets for balanced minimal evolution polytopes and the permutoassociahedron, Bull. Math. Biol., 79, 975-994 (2017), (in press) · Zbl 1373.90072 |
| [32] | Frohn, M., On the approximability of the fixed-tree balanced minimum evolution problem, Optim. Lett. (2020), (in press) |
| [33] | Gascuel, O., A note on Sattath and Tversky’s, Saitou and Nei’s and Studier and Keppler’s algorithms for inferring phylogenies from evolutionary distances, Mol. Biol. Evol., 11, 961 (1994) |
| [34] | Gascuel, O., BIONJ: An improved version of the NJ algorithm based on a simple model of sequence data, Mol. Biol. Evol., 14, 7, 685-695 (1997) |
| [35] | Gascuel, O., Mathematics of Evolution and Phylogeny (2005), Oxford University Press: Oxford University Press New York, NY · Zbl 1104.92332 |
| [36] | Gascuel, O.; Steel, M. A., Neighbor-joining revealed, Mol. Biol. Evol., 23, 11, 1997-2000 (2006) |
| [37] | Gascuel, O.; Steel, M., A ’stochastic safety radius’ for distance-based tree reconstruction, Algorithmica, 74, 1386-1403 (2016) · Zbl 1350.92035 |
| [38] | Gusfield, D., The Steiner Tree Problem in PhylogenyTechnical Report 334 (1984), Dep. Computer Science, Yale University: Dep. Computer Science, Yale University New Haven, CT |
| [39] | Haws, D. C.; Hodge, T. L.; Yoshida, R., Optimality of the neighbor joining algorithm and faces of the balanced minimum evolution polytope, Bull. Math. Biol., 73, 2627-2648 (2011) · Zbl 1334.92292 |
| [40] | Hendy, M. D.; Penny, D., Branch and bound algorithms to determine minimal evolutionary trees, Math. Biosci. (1982) · Zbl 0488.92004 |
| [41] | Hwang, F. K.; Richards, D. S.; Winter, P., The Steiner Tree Problem (1992), North-Holland: North-Holland Amsterdam, The Netherlands · Zbl 0774.05001 |
| [42] | Jung, M., Évolution Du VIH: MÉthodes, ModÈles et Algorithmes (2012), Université Montpellier II - Sciences et Techniques du Languedoc: Université Montpellier II - Sciences et Techniques du Languedoc France, (Ph.D. thesis) |
| [43] | Le, S. Q.; Gascuel, O., An improved general amino acid replacement matrix, Mol. Biol. Evol., 25, 7, 1307-1320 (2008) |
| [44] | Lefort, V.; Desper, R.; Gascuel, O., FastME 2.0: A comprehensive, accurate, and fast distance-based phylogeny inference program, Mol. Biol. Evol., 32, 10, 2798-2800 (2015) |
| [45] | Li, X.; Mao, Y., Generalized Connectivity of Graphs (2016), Springer: Springer Boston, MA, USA · Zbl 1346.05001 |
| [46] | Lu, C. L.; Tang, C. Y.; Lee, R. C.T., The full Steiner tree problem, Theoret. Comput. Sci., 306, 55-67 (2003) · Zbl 1061.68121 |
| [47] | Page, R. D.M.; Holmes, E. C., Molecular Evolution: A Phylogenetic Approach (1998), Blackwell Science: Blackwell Science Oxford, UK |
| [48] | Pardi, F., Algorithms on Phylogenetic Trees (2009), University of Cambridge: University of Cambridge UK, (Ph.D. thesis) |
| [49] | Pardi, F.; Gascuel, O., Combinatorics of distance-based tree inference, Proc. Natl. Acad. Sci. USA, 109, 41, 16443-16448 (2012) |
| [50] | Pardi, F.; Gascuel, O., Encyclopedia of evolutionary biology, (Kliman, Richard M., Distance-Based Methods in Phylogenetics (2016), Elsevier), 458-465 |
| [51] | Pardi, F.; Guillemot, S.; Gascuel, O., Robustness of phylogenetic inference based on minimum evolution, Bull. Math. Biol., 72, 1820-1839 (2010) · Zbl 1202.92064 |
| [52] | Parker, D. S.; Ram, P., The construction of Huffman codes is a submodular (“convex”) optimization problem over a lattice of binary trees, SIAM J. Comput., 28, 5, 1875-1905 (1996) · Zbl 0967.94005 |
| [53] | Pop, P. C., Generalized Network Design Problems: Modeling and Optimization (2012), De Gruyter: De Gruyter Berlin, Germany · Zbl 1260.90143 |
| [54] | 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 |
| [55] | Saitou, N.; Nei, M., The neighbor-joining method: A new method for reconstructing phylogenetic trees, Mol. Biol. Evol., 4, 406-425 (1987) |
| [56] | Semple, C.; Steel, M. A., Cyclic permutations and evolutionary trees, Adv. Appl. Math., 32, 4, 669-680 (2004) · Zbl 1050.05027 |
| [57] | Steel, M., Phylogenetic diversity and the greedy algorithm, Syst. Biol., 54, 4, 527-529 (2005) |
| [58] | Studier, J. A.; Keppler, K. J., A note on the neighbor-joining algorithm of Saitou and Nei, Mol. Biol. Evol., 5, 729-731 (1988) |
| [59] | 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 |
| [60] | Yang, Z., Molecular Evolution: A Statistical Approach (2014), Oxford University Press: Oxford University Press Oxford, UK · Zbl 1288.92002 |
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.
