Abstract
The previously fastest algorithm for computing the rooted triplet distance between two input galled trees (i.e., phylogenetic networks whose cycles are vertex-disjoint) runs in \(O(n^{2.687})\) time, where n is the cardinality of the leaf label set. Here, we present an \(O(n \log n)\)-time solution. Our strategy is to transform the input so that the answer can be obtained by applying an existing \(O(n \log n)\)-time algorithm for the simpler case of two phylogenetic trees a constant number of times.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bansal, M.S., Dong, J., Fernández-Baca, D.: Comparing and aggregating partially resolved trees. Theor. Comput. Sci. 412(48), 6634–6652 (2011)
Brodal, G.S., Fagerberg, R., Mailund, T., Pedersen, C.N.S., Sand, A.: Efficient algorithms for computing the triplet and quartet distance between trees of arbitrary degree. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 1814–1832. SIAM (2013)
Cardona, G., Llabrés, M., Rosselló, R., Valiente, G.: Comparison of galled trees. IEEE/ACM Trans. Comput. Biol. Bioinf. 8(2), 410–427 (2011)
Critchlow, D.E., Pearl, D.K., Qian, C.: The triples distance for rooted bifurcating phylogenetic trees. Syst. Biol. 45(3), 323–334 (1996)
Dobson, A.J.: Comparing the shapes of trees. In: Street, A.P., Wallis, W.D. (eds.) Combinatorial Mathematics III. LNM, vol. 452, pp. 95–100. Springer, Heidelberg (1975). doi:10.1007/BFb0069548
Gambette, P., Huber, K.T.: On encodings of phylogenetic networks of bounded level. J. Math. Biol. 65(1), 157–180 (2012)
Gusfield, D., Eddhu, S., Langley, C.: Optimal, efficient reconstruction of phylogenetic networks with constrained recombination. J. Bioinf. Comput. Biol. 2(1), 173–213 (2004)
Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts Algorithms and Applications. Cambridge University Press, Cambridge (2010)
Jansson, J., Lingas, A.: Computing the rooted triplet distance between galled trees by counting triangles. J. Discrete Algorithms 25, 66–78 (2014)
Jansson, J., Rajaby, R.: A more practical algorithm for the rooted triplet distance. J. Comput. Biol. 24(2), 106–126 (2017)
Kuhner, M.K., Felsenstein, J.: A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates. Mol. Biol. Evol. 11(3), 459–468 (1994)
Morrison, D.: Introduction to Phylogenetic Networks. RJR Productions (2011)
Wang, L., Ma, B., Li, M.: Fixed topology alignment with recombination. Discrete Appl. Math. 104(1–3), 281–300 (2000)
Acknowledgments
J.J. was partially funded by The Hakubi Project at Kyoto University and KAKENHI grant number 26330014.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Jansson, J., Rajaby, R., Sung, WK. (2017). An Efficient Algorithm for the Rooted Triplet Distance Between Galled Trees. In: Figueiredo, D., Martín-Vide, C., Pratas, D., Vega-Rodríguez, M. (eds) Algorithms for Computational Biology. AlCoB 2017. Lecture Notes in Computer Science(), vol 10252. Springer, Cham. https://doi.org/10.1007/978-3-319-58163-7_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-58163-7_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-58162-0
Online ISBN: 978-3-319-58163-7
eBook Packages: Computer ScienceComputer Science (R0)