Locating a tree in a phylogenetic network in quadratic time. (English) Zbl 1355.92075
Przytycka, Teresa M. (ed.), Research in computational molecular biology. 19th annual international conference, RECOMB 2015, Warsaw, Poland, April 12–15, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-16705-3/pbk; 978-3-319-16706-0/ebook). Lecture Notes in Computer Science 9029. Lecture Notes in Bioinformatics, 96-107 (2015).
Summary: A fundamental problem in the study of phylogenetic networks is to determine whether or not a given phylogenetic network contains a given phylogenetic tree. We develop a quadratic-time algorithm for this problem for binary nearly-stable phylogenetic networks. We also show that the number of reticulations in a reticulation visible or nearly stable phylogenetic network is bounded from above by a function linear in the number of taxa.
For the entire collection see [Zbl 1334.92006].
For the entire collection see [Zbl 1334.92006].
MSC:
| 92D15 | Problems related to evolution |
| 05C90 | Applications of graph theory |
| 92B10 | Taxonomy, cladistics, statistics in mathematical biology |
| 92-08 | Computational methods for problems pertaining to biology |
References:
| [1] | Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer (2008) · Zbl 1134.05001 |
| [2] | Cardona, G.; Rosselló, F.; Valiente, G., Comparison of tree-child phylogenetic networks, IEEE/ACM Trans. Comput. Biol. Bioinfo., 6, 4, 552-569 (2009) · doi:10.1109/TCBB.2007.70270 |
| [3] | Chan, JM; Carlsson, G.; Rabadan, R., Topology of viral evolution, PNAS, 110, 46, 18566-18571 (2013) · Zbl 1292.92014 · doi:10.1073/pnas.1313480110 |
| [4] | Dagan, T.; Artzy-Randrup, Y.; Martin, W., Modular networks and cumulative impact of lateral transfer in prokaryote genome evolution, PNAS, 105, 29, 10039-10044 (2008) · doi:10.1073/pnas.0800679105 |
| [5] | Gusfield, D.: ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks. The MIT Press (2014) · Zbl 1316.92001 |
| [6] | Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press (2011) |
| [7] | van Iersel, L.; Semple, C.; Steel, M., Locating a tree in a phylogenetic network, Inf. Process. Lett., 110, 23, 1037-1043 (2010) · Zbl 1379.68184 · doi:10.1016/j.ipl.2010.07.027 |
| [8] | Jenkins, P.; Song, Y.; Brem, R., Genealogy-based methods for inference of historical recombination and gene flow and their application in saccharomyces cerevisiae, PLoS ONE, 7, 11, e46947 (2012) · doi:10.1371/journal.pone.0046947 |
| [9] | Kanj, IA; Nakhleh, L.; Than, C.; Xia, G., Seeing the trees and their branches in the network is hard, Theor. Comput. Sci., 401, 153-164 (2008) · Zbl 1147.68059 · doi:10.1016/j.tcs.2008.04.019 |
| [10] | Marcussen, T.; Jakobsen, KS; Danihelka, J.; Ballard, HE; Blaxland, K.; Brysting, AK; Oxelman, B., Inferring species networks from gene trees in high-polyploid north american and hawaiian violets (viola, violaceae), Syst. Biol., 61, 107-126 (2012) · doi:10.1093/sysbio/syr096 |
| [11] | McBreen, K.; Lockhart, PJ, Reconstructing reticulate evolutionary histories of plants, Trends Plant Sci., 11, 8, 103-122 (2006) · doi:10.1016/j.tplants.2006.06.004 |
| [12] | Moret, BME; Nakhleh, L.; Warnow, T.; Linder, CR; Tholse, A.; Padolina, A.; Sun, J.; Timme, R., Phylogenetic networks: Modeling, reconstructibility, and accuracy, IEEE/ACM Trans. Comput. Biol. Bioinfo., 1, 1, 13-23 (2004) · doi:10.1109/TCBB.2004.10 |
| [13] | Nakhleh, L., Computational approaches to species phylogeny inference and gene tree reconciliation, Trends Ecol. Evolut., 28, 12, 719-728 (2013) · doi:10.1016/j.tree.2013.09.004 |
| [14] | Parida, L., Ancestral recombinations graph: a reconstructability perspective using random-graphs framework, J. Comput. Biol., 17, 10, 1345-1370 (2010) · doi:10.1089/cmb.2009.0243 |
| [15] | Sedgewick, R., Wayne, K.: Algorithms, 4th edn. Addison-Wesley (2011) |
| [16] | Treangen, TJ; Rocha, EP, Horizontal transfer, not duplication, drives the expansion of protein families in prokaryotes, PLoS Genetics, 7, 1, e1001284 (2011) · doi:10.1371/journal.pgen.1001284 |
| [17] | Wang, L.; Zhang, K.; Zhang, L., Perfect phylogenetic networks with recombination, J. Comp. Biol., 8, 1, 69-78 (2001) · doi:10.1089/106652701300099119 |
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.
