Swipe to navigate through the chapters of this book

Published in:

2019 | OriginalPaper | Chapter

Computing a Consensus Phylogeny via Leaf Removal

Authors : Zhi-Zhong Chen, Shohei Ueta, Jingyu Li, Lusheng Wang

Published in:

Publisher:

Abstract

Given a set $$\mathcal{T} = \{T_1, T_2, \ldots , T_m\}$$ of phylogenetic trees with the same leaf-label set X, we wish to remove some leaves from the trees so that there is a tree T with leaf-label set X displaying all the resulting trees. One objective is to minimize the total number of leaves removed from the trees, while the other is to minimize the maximum number of leaves removed from an input tree. Chauve et al. [6] refer to the problem with the first (respectively, second) objective as AST-LR (respectively, AST-LR-d), and show that both problems are NP-hard. They further present algorithms for the parameterized versions of both problems, but it seems that their algorithm for the parameterized version of AST-LR is flawed [7]. In this paper, we present a new algorithm for the parameterized version of AST-LR and also show that Chauve et al.’s algorithm for the parameterized version of AST-LR-d can be sped up by an exponential factor. We further design heuristic integer-linear programming (ILP for short) models for AST-LR and AST-LR-d. Our experimental results show that the heuristic models can be used to significantly speed up solving the exact models proposed in [7].
Literature
1.
Aho, A.V., Sagiv, Y., Szymanski, T.G., Ullman, J.D.: Inferring a tree from lowest common ancestors with application to the optimization of relational expressions. SIAM J. Comput. 10, 405–421 (1981)
2.
Baroni, M., Grunewald, S., Moulton, V., Semple, C.: Bounding the number of hybridisation events for a consistent evolutionary history. J. Math. Biol. 51, 171–182 (2015)
3.
Beiko, R.G., Hamilton, N.: Phylogenetic identification of lateral genetic transfer events. BMC Evol. Biol. 6, 15 (2006) CrossRef
4.
Bordewich, M., Semple, C.: On the computational complexity of the rooted subtree prune and regraft distance. Ann. Comb. 8, 409–423 (2005)
5.
Buneman, P.: The recovery of trees from measures of dissimilarity. In: Kendall, D., Tauta, P. (eds.) Mathematics in the Archaeological and Historical Sciences, pp. 387–395. Edinburgh University Press, Edinburgh (1971)
6.
Chauve, C., Jones, M., Lafond, M., Scornavacca, C., Weller, M.: Constructing a consensus phylogeny from a leaf-removal distance (extended abstract). In: Fici, G., Sciortino, M., Venturini, R. (eds.) SPIRE 2017. LNCS, vol. 10508, pp. 129–143. Springer, Cham (2017). https://​doi.​org/​10.​1007/​978-3-319-67428-5_​12 CrossRef
7.
Chen, Z.-Z., Ueta, S., Li, J., Wang, L.: Finding a center tree of phylogenetic trees via leaf removal. In: Proceedings of the 2018 IEEE International Conference on Bioinformatics and Biomedicine (to appear)
8.
Cole, R., Farach-Colton, M., Hariharan, R., Przytycka, T.M., Thorup, M.: An $$O(n\log n)$$ algorithm for the maximum agreement subtree problem for binary trees. SIAM J. Comput. 30, 1385–1404 (2000)
9.
Guillemot, S., Mnich, M.: Kernel and fast algorithm for dense triplet inconsistency. Theor. Comput. Sci. 494, 134–143 (2013)
10.
Li, M., Tromp, J., Zhang, L.: On the nearest neighbour interchange distance between evolutionary trees. J. Theor. Biol. 182, 463–467 (1996) CrossRef
11.
Ma, B., Wang, L., Zhang, L.: Fitting distances by tree metrics with increment error. J. Comb. Optim. 3, 213–225 (1999)
12.
Maddison, W.P.: Gene trees in species trees. Syst. Biol. 46, 523–536 (1997) CrossRef
13.
Nakhleh, L., Warnow, T., Lindner, C.R., John, K.S.: Reconstructing reticulate evolution in species - theory and practice. J. Comput. Biol. 12, 796–811 (2005) CrossRef
14.
Robinson, D., Foulds, L.: Comparison of phylogenetic trees. Math. Biosci. 53, 131–147 (1981)
15.
Swofford, D., Olsen, G., Waddell, P., Hillis, D.: Phylogenetic inference. In: Hillis, D., Moritz, D., Mable, B. (eds.) Molecular Systematics, 2nd edn, pp. 407–514. Sinauer Associates, Sunderiand (1996)