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].
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
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)
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)
Beiko, R.G., Hamilton, N.: Phylogenetic identification of lateral genetic transfer events. BMC Evol. Biol. 6, 15 (2006)
Bordewich, M., Semple, C.: On the computational complexity of the rooted subtree prune and regraft distance. Ann. Comb. 8, 409–423 (2005)
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)
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
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)
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)
Guillemot, S., Mnich, M.: Kernel and fast algorithm for dense triplet inconsistency. Theor. Comput. Sci. 494, 134–143 (2013)
Li, M., Tromp, J., Zhang, L.: On the nearest neighbour interchange distance between evolutionary trees. J. Theor. Biol. 182, 463–467 (1996)
Ma, B., Wang, L., Zhang, L.: Fitting distances by tree metrics with increment error. J. Comb. Optim. 3, 213–225 (1999)
Maddison, W.P.: Gene trees in species trees. Syst. Biol. 46, 523–536 (1997)
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)
Robinson, D., Foulds, L.: Comparison of phylogenetic trees. Math. Biosci. 53, 131–147 (1981)
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)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Chen, ZZ., Ueta, S., Li, J., Wang, L. (2019). Computing a Consensus Phylogeny via Leaf Removal. In: Cai, Z., Skums, P., Li, M. (eds) Bioinformatics Research and Applications. ISBRA 2019. Lecture Notes in Computer Science(), vol 11490. Springer, Cham. https://doi.org/10.1007/978-3-030-20242-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-20242-2_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-20241-5
Online ISBN: 978-3-030-20242-2
eBook Packages: Computer ScienceComputer Science (R0)