Robustness of phylogenetic inference based on minimum evolution. (English) Zbl 1202.92064
Summary: Minimum evolution is the guiding principle of an important class of distance-based phylogeny reconstruction methods, including neighbor-joining (NJ), which is the most cited tree inference algorithm to date. The minimum evolution principle involves searching for the tree with minimum length, where the length is estimated using various least-squares criteria. Since evolutionary distances cannot be known precisely but only estimated, it is important to investigate the robustness of phylogenetic reconstruction to imprecise estimates for these distances. The safety radius is a measure of this robustness: it consists of the maximum relative deviation that the input distances can have from the correct distances, without compromising the reconstruction of the correct tree structure. Answering some open questions, we here derive the safety radius of two popular minimum evolution criteria: balanced minimum evolution (BME) and minimum evolution based on ordinary least squares (OLS + ME). Whereas BME has a radius of \(1/2\), which is the best achievable, OLS + ME has a radius tending to 0 as the number of taxa increases. This difference may explain the gap in reconstruction accuracy observed in practice between OLS + ME and BME (which forms the basis of popular programs such as NJ and FastME).
MSC:
| 92D15 | Problems related to evolution |
| 62P10 | Applications of statistics to biology and medical sciences; meta analysis |
References:
| [1] | Atteson, K., 1999. The performance of neighbor-joining methods of phylogenetic reconstruction. Algorithmica 25, 251–278. · Zbl 0938.68747 · doi:10.1007/PL00008277 |
| [2] | Bandelt, H.J., Dress, A.W., 1992. Split decomposition: a new and useful approach to phylogenetic analysis of distance data. Mol. Phylogenet. Evol. 1(3), 242–252. · doi:10.1016/1055-7903(92)90021-8 |
| [3] | Bordewich, M., Gascuel, O., Huber, K., Moulton, V., 2009. Consistency of topological moves based on the balanced minimum evolution principle of phylogenetic inference. IEEE/ACM Trans. Comput. Biol. Bioinf. 6, 110–117. · doi:10.1109/TCBB.2008.37 |
| [4] | Bulmer, M., 1991. Use of the method of generalized least squares in reconstructing phylogenies from sequence data. Mol. Biol. Evol. 8(6), 868. |
| [5] | Buneman, P., 1971. The recovery of trees from measures of dissimilarity. In: Hodson, F. (Ed.), Mathematics in the Archaeological and Historical Sciences, pp. 387–395. Edinburgh University Press, Edinburgh. |
| [6] | Cavalli-Sforza, L.L., Edwards, A.W.F., 1964. Analysis of human evolution. In: Proceedings 11th International Congress of Genetics, vol. 3, pp. 923–933. |
| [7] | Cavalli-Sforza, L.L., Edwards, A.W.F., 1967. Phylogenetic analysis: models and estimation procedures. Am. J. Hum. Genet. 19(3 part 1), 233–257. |
| [8] | Desper, R., Gascuel, O., 2002. Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. J. Comput. Biol. 9, 687–705. · Zbl 1016.68692 · doi:10.1089/106652702761034136 |
| [9] | Desper, R., Gascuel, O., 2004. Theoretical foundation of the balanced minimum evolution method of phylogenetic inference and its relationship to weighted least-squares tree fitting. Mol. Biol. Evol. 21, 587–598. · doi:10.1093/molbev/msh049 |
| [10] | Desper, R., Gascuel, O., 2005. The minimum evolution distance-based approach to phylogenetic inference. In: Gascuel, O. (Ed.), Mathematics of Evolution & Phylogeny, pp. 1–32. Oxford University Press, Oxford. · Zbl 1090.62121 |
| [11] | Gascuel, O., 2000. On the optimization principle in phylogenetic analysis and the minimum-evolution criterion. Mol. Biol. Evol. 17, 401–405. |
| [12] | Gascuel, O., McKenzie, A., 2004. Performance analysis of hierarchical clustering algorithms. J. Classif. 21(1), 3–18. · Zbl 1091.91059 · doi:10.1007/s00357-004-0003-2 |
| [13] | Gascuel, O., Steel, M., 2006. Neighbor-joining revealed. Mol. Biol. Evol. 23, 1997–2000. · doi:10.1093/molbev/msl072 |
| [14] | Gascuel, O., Bryant, D., Denis, F., 2001. Strengths and limitations of the minimum evolution principle. Syst. Biol. 50, 621–627. · doi:10.1080/106351501753328767 |
| [15] | Kidd, K.K., Sgaramella-Zonta, L.A., 1971. Phylogenetic analysis: concepts and methods. Am. J. Hum. Genet. 23, 235–252. |
| [16] | Kumar, S., 1996. A stepwise algorithm for finding minimum evolution trees. Mol. Biol. Evol. 13, 584–593. |
| [17] | Mihaescu, R., Pachter, L., 2008. Combinatorics of least squares trees. Proc. Natl. Acad. Sci. USA 105, 13206–13211. · Zbl 1205.05054 · doi:10.1073/pnas.0802089105 |
| [18] | Nei, M., Kumar, S., 2000. Molecular Evolution and Phylogenetics. Oxford University Press, Oxford. |
| [19] | Pauplin, Y., 2000. Direct calculation of a tree length using a distance matrix. J. Mol. Evol. 51, 41–47. |
| [20] | Rzhetsky, A., Nei, M., 1992. A simple method for estimating and testing minimum-evolution trees. Mol. Biol. Evol. 9, 945–967. |
| [21] | Rzhetsky, A., Nei, M., 1993. Theoretical foundation of the minimum-evolution method of phylogenetic inference. Mol. Biol. Evol. 10, 1073–1095. |
| [22] | Saitou, N., Imanishi, T., 1989. Relative efficiencies of the Fitch–Margoliash, maximum-parsimony, maximum-likelihood, minimum-evolution, and neighbor-joining methods of phylogenetic tree construction in obtaining the correct tree. Mol. Biol. Evol. 6, 514–525. |
| [23] | Saitou, N., Nei, M., 1987. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4, 406–425. |
| [24] | Semple, C., Steel, M., 2004. Cyclic permutations and evolutionary trees. Adv. Appl. Math. 32, 669–680. · Zbl 1050.05027 · doi:10.1016/S0196-8858(03)00098-8 |
| [25] | Swofford, D.L., Olsen, G.J., Waddell, P.J., Hillis, D.M., 1996. Phylogenetic inference. In: Hillis, D., Moritz, C., Mable, B. (Eds.), Molecular Systematics, pp. 407–514. Sinauer, Sunderland. |
| [26] | Vinh, L.S., von Haeseler, A., 2005. Shortest triplet clustering: reconstructing large phylogenies using representative sets. BMC Bioinf. 6, 92. · doi:10.1186/1471-2105-6-92 |
| [27] | Willson, S.J., 2005a. Consistent formulas for estimating the total lengths of trees. Discrete Appl. Math. 148(3), 214–239. · Zbl 1065.92031 · doi:10.1016/j.dam.2005.03.005 |
| [28] | Willson, S.J., 2005b. Minimum evolution using ordinary least-squares is less robust than neighbor-joining. Bull. Math. Biol. 67(2), 261–279. · Zbl 1334.92300 · doi:10.1016/j.bulm.2004.07.007 |
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.
