×

zbMATH — the first resource for mathematics

Computing the minimum number of hybridization events for a consistent evolutionary history. (English) Zbl 1111.92041
Summary: It is now well-documented that the structure of evolutionary relationships between a set of present-day species is not necessarily tree-like. The reason for this is that reticulation events such as hybridizations mean that species are a mixture of genes from different ancestors. Since such events are relatively rare, a fundamental problem for biologists is to determine the smallest number of hybridization events required to explain a given (input) set of data in a single (hybrid) phylogeny.
The main results of this paper show that computing this smallest number is APX-hard, and thus NP-hard, in the case the input is a collection of phylogenetic trees on sets of present-day species. This answers a problem which was raised at a recent conference [Phylogenetic Combinatorics and Applications, Uppsala Univ. (2004)]. As a consequence of these results, we also correct a previously published NP-hardness proof [L. Wang et al., J. Comput. Biol. 8, 69–78 (2001)] in the case the input is a collection of binary sequences, where each sequence represents the attributes of a particular present-day species. The APX-hardness of these problems means that it is unlikely that there is an efficient algorithm for either computing the result exactly or approximating it to any arbitrary degree of accuracy.

MSC:
92D15 Problems related to evolution
05C05 Trees
65Y20 Complexity and performance of numerical algorithms
05C90 Applications of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., Complexity and approximation, (1999), Springer Berlin · Zbl 0937.68002
[2] Baroni, M.; Grünewald, S.; Moulton, V.; Semple, C., Bounding the number of hybridization events for a consistent evolutionary history, J. math. biol., 51, 171-182, (2005) · Zbl 1068.92034
[3] Baroni, M.; Semple, C.; Steel, M., A framework for representing reticulate evolution, Ann. combin., 8, 391-408, (2004) · Zbl 1059.05034
[4] M.K. Bonet, K. St. John, R. Mahindru, N. Amenta, Approximating subtree distances between phylogenies, Technical Report #669, Centre de Recerca Matematica, Barcelona, 2006.
[5] Bordewich, M.; Semple, C., On the computational complexity of the rooted subtree prune and regraft distance, Ann. combin., 8, 409-423, (2004) · Zbl 1059.05035
[6] Chlebík, M.; Chlebíková, J., Inapproximability results for bounded variants of optimization problems, (), 27-38 · Zbl 1278.68098
[7] S. Grünewald, Private communication.
[8] Gusfield, D.; Eddhu, S.; Langley, C., Optimal, efficient reconstruction of phylogenetic networks with constrained recombination, J. bioinform. comput. biol., 2, 173-213, (2004)
[9] E. Hazan, S. Safra, O. Schwartz, On the hardness of approximating k-dimensional matching, ECCC Report TR03-20, 2003. · Zbl 1279.68106
[10] Hein, J., Reconstructing evolution of sequences subject to recombination using parsimony, Math. biosci., 98, 185-200, (1990) · Zbl 0692.92014
[11] Hein, J.; Jing, T.; Wang, L.; Zhang, K., On the complexity of comparing evolutionary trees, Discrete appl. math., 71, 153-169, (1996) · Zbl 0876.92020
[12] Kann, V., Maximum bounded 3-dimensional matching is MAX SNP-complete, Inform. process. lett., 37, 27-35, (1991) · Zbl 0711.68045
[13] Maddison, W., Gene trees in species trees, Systematic biol., 46, 523-536, (1997)
[14] Nakhleh, L.; Warnow, T.; Randal Linder, C.; John, K.St., Reconstructing reticulate evolution in species—theory and practice, J. comput. biol., 12, 796-811, (2005)
[15] Papadimitriou, C.H.; Yannakakis, M., Optimization, approximation, and complexity classes, J. comput. system sci., 43, 425-440, (1991) · Zbl 0765.68036
[16] Rodrigues, E.M.; Sagot, M.-F.; Wakabayashi, Y., Some approximation results for the maximum agreement forest problem, (), 159-169 · Zbl 1001.92038
[17] Semple, C.; Steel, M., Phylogenetics, (2003), Oxford University Press Oxford · Zbl 1043.92026
[18] Song, Y.; Hein, J., Parsimonious reconstruction of sequence evolution and haplotyde blocks: finding the minimum number of recombination events, (), 287-302
[19] Song, Y.; Hein, J., Constructing minimal ancestral recombination graphs, J. comput. biol., 12, 147-169, (2005)
[20] Wang, L.; Zhang, K.; Zhang, L., Perfect phylogenetic networks with recombination, J. comput. biol., 8, 69-78, (2001)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.