A cubic-time algorithm for computing the trinet distance between level-1 networks. (English) Zbl 1407.92096
Summary: In evolutionary biology, phylogenetic networks are constructed to represent the evolution of species in which reticulate events are thought to have occurred, such as recombination and hybridization. It is therefore useful to have efficiently computable metrics with which to systematically compare such networks. Through developing an optimal algorithm to enumerate all trinets displayed by a level-1 network (a type of network that is slightly more general than an evolutionary tree), here we propose a cubic-time algorithm to compute the trinet distance between two level-1 networks. Employing simulations, we also present a comparison between the trinet metric and the so-called Robinson-Foulds phylogenetic network metric restricted to level-1 networks. The algorithms described in this paper have been implemented in JAVA and are freely available at https://www.uea.ac.uk/computing/TriLoNet.
MSC:
| 92D15 | Problems related to evolution |
| 68W40 | Analysis of algorithms |
| 92-04 | Software, source code, etc. for problems pertaining to biology |
Software:
TriLoNetReferences:
| [1] | Huson, D.; Rupp, R.; Scornavacca, C., Phylogenetic Networks: Concepts, Algorithms and Applications (2010), Cambridge University Press |
| [2] | Cardona, G.; Llabres, M.; Rossello, F.; Valiente, G., Comparison of galled trees, IEEE/ACM Trans. Comput. Biol. Bioinform., 8, 410-427 (2011) |
| [3] | Huber, K.; van Iersel, L.; Kelk, S.; Suchecki, R., A practical algorithm for reconstructing level-1 phylogenetic networks, IEEE/ACM Trans. Comput. Biol. Bioinform., 8, 635-649 (2011) |
| [4] | Oldman, J.; Wu, T.; van Iersel, L.; Moulton, V., Trilonet: piecing together small networks to reconstruct reticulate evolutionary histories, Mol. Biol. Evol., 33, 2151-2162 (2016) |
| [5] | Wang, L.; Zhang, K.; Zhang, L., Perfect phylogenetic networks with recombination, J. Comput. Biol., 8, 69-78 (2001) |
| [6] | Jansson, J.; Nguyen, N. B.; Sung, W.-K., Algorithms for combining rooted triplets into a galled phylogenetic network, SIAM J. Comput., 35, 1098-1121 (2006) · Zbl 1100.68081 |
| [7] | Gusfield, D., ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks (2014), MIT Press · Zbl 1316.92001 |
| [8] | Huson, D.; Scornavacca, C., A survey of combinatorial methods for phylogenetic networks, Genome Biol. Evol., 3, 23-35 (2011) |
| [9] | Huber, K.; Moulton, V., Encoding and constructing 1-nested phylogenetic networks with trinets, Algorithmica, 616, 714-738 (2012) · Zbl 1267.05240 |
| [10] | Jansson, J.; Lingas, A., Computing the rooted triplet distance between galled trees by counting triangles, J. Discret. Algorithms, 25, 66-78 (2014) · Zbl 1284.05293 |
| [11] | Moret, B. M.; Nakhleh, L.; Warnow, T.; Linder, C. R.; Tholse, A.; Padolina, A.; Sun, J.; Timme, R., Phylogenetic networks: modeling, reconstructibility, and accuracy, IEEE/ACM Trans. Comput. Biol. Bioinform., 1, 13-23 (2004) |
| [12] | Cardona, G.; Rossello, F.; Valiente, G., Comparison of tree-child phylogenetic networks, IEEE/ACM Trans. Comput. Biol. Bioinform., 6, 552-569 (2009) |
| [13] | Huber, K.; Linz, S.; Moulton, V.; Wu, T., Spaces of phylogenetic networks from generalised nearest-neighbor interchange operations, J. Math. Biol., 72, 699-725 (2016) · Zbl 1330.05150 |
| [14] | Fischer, J.; Huson, D. H., New common ancestor problems in trees and directed acyclic graphs, Inf. Process. Lett., 110, 331-335 (2010) · Zbl 1211.05162 |
| [15] | Steel, M.; Penny, D., Distributions of tree comparison metrics-some new results, Syst. Biol., 42, 126-141 (1993) |
| [16] | Moulton, V.; Zuker, M.; Steel, M.; Pointon, R.; Penny, D., Metrics on RNA secondary structures, J. Comput. Biol., 7, 277-292 (2000) |
| [17] | Robinson, D.; Foulds, L., Comparison of phylogenetic trees, Math. Biosci., 53, 131-147 (1981) · Zbl 0451.92006 |
| [18] | Day, W., Optimal algorithms for comparing trees with labeled leaves, J. Classif., 2, 7-28 (1985) · Zbl 0589.62044 |
| [19] | Pattengale, N.; Gottlieb, E.; Moret, B., Efficiently computing the Robinson-Foulds metric, J. Comput. Biol., 14, 724-735 (2007) |
| [20] | van Iersel, L.; Moulton, V., Trinets encode tree-child and level-2 phylogenetic networks, J. Math. Biol., 68, 1707-1729 (2014) · Zbl 1339.92008 |
| [21] | Huber, K.; Van Iersel, L.; Moulton, V.; Wu, T., How much information is needed to infer reticulate evolutionary histories?, Syst. Biol., 64, 102-111 (2015) |
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.
