Skip to main content
Top

Hint

Swipe to navigate through the chapters of this book

Published in:
Cover of the book

2019 | OriginalPaper | Chapter

Computing a Consensus Phylogeny via Leaf Removal

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

Published in: Bioinformatics Research and Applications

Publisher: Springer International Publishing

share
SHARE

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.
go back to reference 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) MathSciNetCrossRef 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) MathSciNetCrossRef
2.
go back to reference 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) MathSciNetCrossRef 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) MathSciNetCrossRef
3.
go back to reference Beiko, R.G., Hamilton, N.: Phylogenetic identification of lateral genetic transfer events. BMC Evol. Biol. 6, 15 (2006) CrossRef Beiko, R.G., Hamilton, N.: Phylogenetic identification of lateral genetic transfer events. BMC Evol. Biol. 6, 15 (2006) CrossRef
4.
go back to reference Bordewich, M., Semple, C.: On the computational complexity of the rooted subtree prune and regraft distance. Ann. Comb. 8, 409–423 (2005) MathSciNetCrossRef Bordewich, M., Semple, C.: On the computational complexity of the rooted subtree prune and regraft distance. Ann. Comb. 8, 409–423 (2005) MathSciNetCrossRef
5.
go back to reference 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) 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)
7.
go back to reference 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) 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.
go back to reference 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) MathSciNetCrossRef 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) MathSciNetCrossRef
9.
go back to reference Guillemot, S., Mnich, M.: Kernel and fast algorithm for dense triplet inconsistency. Theor. Comput. Sci. 494, 134–143 (2013) MathSciNetCrossRef Guillemot, S., Mnich, M.: Kernel and fast algorithm for dense triplet inconsistency. Theor. Comput. Sci. 494, 134–143 (2013) MathSciNetCrossRef
10.
go back to reference Li, M., Tromp, J., Zhang, L.: On the nearest neighbour interchange distance between evolutionary trees. J. Theor. Biol. 182, 463–467 (1996) CrossRef Li, M., Tromp, J., Zhang, L.: On the nearest neighbour interchange distance between evolutionary trees. J. Theor. Biol. 182, 463–467 (1996) CrossRef
11.
go back to reference Ma, B., Wang, L., Zhang, L.: Fitting distances by tree metrics with increment error. J. Comb. Optim. 3, 213–225 (1999) MathSciNetCrossRef Ma, B., Wang, L., Zhang, L.: Fitting distances by tree metrics with increment error. J. Comb. Optim. 3, 213–225 (1999) MathSciNetCrossRef
12.
go back to reference Maddison, W.P.: Gene trees in species trees. Syst. Biol. 46, 523–536 (1997) CrossRef Maddison, W.P.: Gene trees in species trees. Syst. Biol. 46, 523–536 (1997) CrossRef
13.
go back to reference 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 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
15.
go back to reference 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) 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)
Metadata
Title
Computing a Consensus Phylogeny via Leaf Removal
Authors
Zhi-Zhong Chen
Shohei Ueta
Jingyu Li
Lusheng Wang
Copyright Year
2019
DOI
https://doi.org/10.1007/978-3-030-20242-2_1

Premium Partner