×

NCHB: a method for constructing rooted phylogenetic networks from rooted triplets based on height function and binarization. (English) Zbl 1430.92057

Summary: Phylogenetics is a field that studies and models the evolutionary history of currently living species. The rooted phylogenetic network is an important approach that models non-tree-like events between currently living species. Rooted triplets are one type of inputs in constructing rooted phylogenetic networks. Constructing an optimal rooted phylogenetic network that contains all given rooted triplets is a NP-hard problem. To overcome this challenge efficiently, a novel heuristic method called NCHB is introduced in this paper. NCHB produces an optimal rooted phylogenetic network that covers all given rooted triplets. The NCHB optimality criterions in building a rooted phylogenetic network are minimizing the number of reticulation nodes, and minimizing the level of the final network. In NCHB, the two concepts: the height function and the binarization of a network are considered innovatively. In order to study the performance of NCHB, our proposed method is compared with the three state of the art algorithms that are LEV1ATHAN, SIMPLISTIC and TripNet in two scenarios. In the first scenario, triplet sets are generated under biological presumptions and our proposed method is compared with SIMPLISTIC and TripNet. The results show that NCHB outperforms TripNet and SIMPLISTIC according to the optimality criterions. In the second scenario, we designed a software for generating level-k networks. Then all triplets consistent with each network are obtained and are used as input for NCHB, LEV1THAN, SIMPLISTIC, and TripNet. LEV1ATHEN is just applicable for level-1 networks while the other algorithms can be performed to obtain higher level networks. The results show that the NCHB and LEV1ATHAN outputs are almost the same when we are restricted to level-1 networks. Also the results show that NCHB outperforms TripNet and SIMPLISTIC. Moreover NCHB outputs are very close to the generated networks (that are optimal) with respect to the criterions.

MSC:

92D15 Problems related to evolution
05C90 Applications of graph theory

Software:

QNet
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Sagiv, Y.; Szymanski, T. G.; Ullman, J. D., Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions, SIAM J. Comput., 10, 3, 405-421 (1981) · Zbl 0462.68086
[2] Bandelt, H.-J.; Forster, P.; Sykes, B. C.; Richards, M. B., Mitochondrial portraits of human populations using median networks., Genetics, 141, 2, 743-753 (1995)
[3] Bordewich, M.; Semple, C., Computing the minimum number of hybridization events for a consistent evolutionary history, Discrete Appl. Math., 155, 8, 914-928 (2007) · Zbl 1111.92041
[4] Bouckaert, R.; Lemey, P.; Dunn, M.; Greenhill, S. J.; Alekseyenko, A. V.; Drummond, A. J.; Gray, R. D.; Suchard, M. A.; Atkinson, Q. D., Mapping the origins and expansion of the indo-european language family, Science, 337, 6097, 957-960 (2012)
[5] Bryant, D., NeighborNet: an agglomerative method for the construction of planar phylogenetic networks, Mol. Biol. Evol., 21, 255-265 (2004)
[6] Canko, O.; Taşkın, F.; Argın, K., Phylogenetic tree and community structure from a tangled nature model, J. Theor. Biol., 382, 216-222 (2015) · Zbl 1343.92336
[7] Felsenstein, J.; Felenstein, J., Inferring Phylogenies, vol. 2 (2004), Sinauer associates Sunderland, MA
[8] Grassly, N., Rambaut, A., 1997. Treevole: a program to simulate the evolution of dna sequences under different population dynamic scenarios. 1.3. Wellcome centre for infectious disease, department of zoology.
[9] Grünewald, S.; Forslund, K.; Dress, A.; Moulton, V., QNet: an agglomerative method for the construction of phylogenetic networks from weighted quartets, Mol. Biol. Evol., 24, 2, 532-538 (2006)
[10] Hallett, M.; Lagergren, J.; Tofigh, A., Simultaneous identification of duplications and lateral transfers, Proceedings of the Eighth Annual International Conference on Resaerch in Computational Molecular Biology, 347-356 (2004), ACM
[11] Huber, K. T.; van Iersel, L.; Kelk, S.; Suchecki, R., A practical algorithm for reconstructing level-1 phylogenetic networks, IEEE/ACM Trans. Comput. Biol.Bioinf. (TCBB), 8, 3, 635-649 (2011)
[12] Huber, K. T.; Van Iersel, L.; Moulton, V.; Scornavacca, C.; Wu, T., Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets, Algorithmica, 77, 1, 173-200 (2017) · Zbl 1357.92056
[13] Hudson, R. R., Properties of a neutral allele model with intragenic recombination, Theor. Popul. Biol., 23, 2, 183-201 (1983) · Zbl 0505.62090
[14] Huson, D. H.; Rupp, R.; Scornavacca, C., Phylogenetic Networks: Concepts, Algorithms and Applications (2010), Cambridge University Press
[15] Van Iersel, L.; Keijsper, J.; Kelk, S.; Stougie, L.; Hagen, F.; Boekhout, T., Constructing level-2 phylogenetic networks from triplets, IEEE/ACM Trans. Comput. Biol.Bioinf. (TCBB), 6, 4, 667-681 (2009)
[16] van Iersel, L.; Kelk, S., Constructing the simplest possible phylogenetic network from triplets, Algorithmica, 60, 2, 207-235 (2011) · Zbl 1215.92052
[17] Jahangiri, S.; Hashemi, S. N.; Poormohammadi, H., New heuristics for rooted triplet consistency, Algorithms, 6, 3, 396-406 (2013) · Zbl 1461.92065
[18] Jansson, J.; Sung, W.-K., Inferring a level-1 phylogenetic network from a dense set of rooted triplets, Theor. Comput. Sci., 363, 1, 60-68 (2006) · Zbl 1110.68032
[19] Jansson, J.; Sung, W.-K., Algorithms for combining rooted triplets into a galled phylogenetic network, Encyclopedia of Algorithms, 48-52 (2016)
[20] Karp, R. M., Reducibility among combinatorial problems, Complexity of computer computations, 85-103 (1972), Springer · Zbl 1467.68065
[21] Linder, C. R.; Moret, B. M.; Nakhleh, L.; Warnow, T., Network (reticulate) evolution: biology, models, and algorithms, The Ninth Pacific Symposium on Biocomputing (PSB) (2004)
[22] Lyngsø, R. B.; Song, Y. S.; Hein, J., Minimum recombination histories by branch and bound, International Workshop on Algorithms in Bioinformatics, 239-250 (2005), Springer
[23] Maemura, K.; Jansson, J.; Ono, H.; Sadakane, K.; Yamashita, M., Approximation algorithms for constructing evolutionary trees from rooted triplets, Proceedings of 10th Korea-Japan Joint Workshop on Algorithms and Computation, 56-63 (2007)
[24] Moulton, V.; Semple, C.; Steel, M., Optimizing phylogenetic diversity under constraints, J. Theor. Biol., 246, 1, 186-194 (2007) · Zbl 1451.92227
[25] Oldman, J.; Wu, T.; Van Iersel, L.; Moulton, V., TriLoNet: piecing together small networks to reconstruct reticulate evolutionary histories, Mol. Biol. Evol., 33, 8, 2151-2162 (2016)
[26] Poormohammadi, H., A new heuristic algorithm for MRTC problem, J. Emerging Trends Comput. Inf. Sci., 3, 7 (2012)
[27] Poormohammadi, H.; Eslahchi, C.; Tusserkani, R., TripNet: a method for constructing rooted phylogenetic networks from rooted triplets, PLoS ONE, 9, 9, e106531 (2014)
[28] Poormohammadi, H., Zarchi, M. S., 2020. CBTH: a new algorithm for MRTC problem. Submitted.
[29] Reyhani, M. H.; Poormohammadi, H., RPNCH: a method for constructing rooted phylogenetic networks from rooted triplets based on height function, J. Paramed. Sci., 8, 4, 14-20 (2017)
[30] Sang, T.; Zhong, Y., Testing hybridization hypotheses based on incongruent gene trees, Syst. Biol., 49, 3, 422-434 (2000)
[31] Scornavacca, C.; Mayol, J. C.P.; Cardona, G., Fast algorithm for the reconciliation of gene trees and LGT networks, J. Theor. Biol., 418, 129-137 (2017) · Zbl 1369.92082
[32] Templeton, A. R.; Crandall, K. A.; Sing, C. F., A cladistic analysis of phenotypic associations with haplotypes inferred from restriction endonuclease mapping and dna sequence data. III. Cladogram estimation, Genetics, 132, 2, 619-633 (1992)
[33] Wang, J.; Guo, M.; Xing, L.; Che, K.; Liu, X.; Wang, C., BIMLR: a method for constructing rooted phylogenetic networks from rooted phylogenetic trees, Gene, 527, 1, 344-351 (2013)
[34] Willson, S. J., Reconstruction of certain phylogenetic networks from the genomes at their leaves, J. Theor. Biol., 252, 2, 338-349 (2008) · Zbl 1398.92193
[35] Wu, B. Y., Constructing the maximum consensus tree from rooted triples, J. Comb. Optim., 8, 1, 29-39 (2004) · Zbl 1058.90071
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.