Abstract
Gene trees are leaf-labeled trees inferred from molecular sequences. Due to duplication events arising in genome evolution, gene trees usually have multiple copies of some labels, i.e. species. Inferring a species tree from a set of multi-labeled gene trees (MUL trees) is a well-known problem in computational biology. We propose a novel approach to tackle this problem, mainly to transform a collection of MUL trees into a collection of evolutionary trees, each containing single copies of labels. To that aim, we provide several algorithmic building stones and describe how they fit within a general species tree inference process. Most algorithms have a linear-time complexity, except for an FPT algorithm proposed for a problem that we show to be intractable.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cotton, J., Page, R.: Rates and patterns of gene duplication and loss in the human genome. Proceedings of Royal Soceity of London 272, 277–283 (2005)
Ma, B., Li, M., Zhang, L.: From gene trees to species trees. SIAM J. Comput. 30, 729–752 (2000)
Hallett, M.T., Lagergren, J.: New algorithms for the duplication-loss model. In: RECOMB 2000, Fourth Annual International Conference on Computational Molecular Biology, pp. 138–146 (2000)
Chen, K., Durand, D., Farach-Colton, M.: Notung: a program for dating gene duplications and optimizing gene family trees. J. Comput. Biol. 7, 429–444 (2000)
Vernot, B., Stolzer, M., Goldman, A., Durand, D.: Reconciliation with non-binary species trees. J. Comput. Biol. 15(8), 981–1006 (2008)
Chauve, C., Doyon, J.P., El-Mabrouk, N.: Gene family evolution by duplication, speciation, and loss. J. Comput. Biol. 15(8), 1043–1062 (2008)
Goodman, M., Czelusniak, J., Moore, G.W., Romero-Herrera, A.E., Matsuda, G.: Fitting the Gene Lineage into its Species Lineage, a Parsimony Strategy Illustrated by Cladograms Constructed from Globin Sequences. Systematic Zoology 28(2), 132–163 (1979)
Arvestad, L., Berglund, A., Lagergren, J., Sennblad, B.: Bayesian gene/species tree reconciliation and orthology analysis using MCMC. Bioinformatics 19(suppl. 1), 7–15 (2003)
Durand, D., Halld–rsson, B., Vernot, B.: A hybrid micro-macroevolutionary approach to gene tree reconstruction. J. Comput. Biol. 13, 320–335 (2006)
Baum, B.R., Ragan, M.A.: The MRP method. In: Bininda-Emonds, O. (ed.) Phylogenetic supertrees: combining information to reveal the Tree of Life, pp. 17–34. Kluwer, Dordrecht (2004)
Page, R.D.M.: Modified mincut supertrees. In: Guigó, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol. 2452, pp. 537–552. Springer, Heidelberg (2002)
Scornavacca, C., Berry, V., Lefort, V., Douzery, E.J.P., Ranwez, V.: Physic_ist: cleaning source trees to infer more informative supertrees. BMC Bioinformatics 9(8), 413 (2008)
Gusfield, D.: Efficient algorithms for inferring evolutionary trees. Networks 21, 12–28 (1991)
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. Comp. 10(3), 405–421 (1981)
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338–355 (1984)
Bender, M.A., Farach-Colton, M.: The lca problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000)
Berry, V., Semple, C.: Fast computation of supertrees for compatible phylogenies with nested taxa. Syst. Biol. 55, 270–288 (2006)
Henzinger, M., King, V., Warnow, T.: Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica 24, 1–13 (1999)
Berry, V., Nicolas, F.: Improved parameterized complexity of the maximum agreement subtree and maximum compatible tree problems. IEEE/ACM Trans. Comput. Biol. Bioinformatics 3(3), 289–302 (2006)
Aho, A., Hopcroft, J., Ullman, J.: The Design and Analysis of Computer Algorithms. Addison-Wesley Longman Publishing Co., Inc., Boston (1974)
Ranwez, V., Berry, V., Criscuolo, A., Fabre, P., Guillemot, S., Scornavacca, C., Douzery, E.: PhySIC: a veto supertree method with desirable properties. Syst. Biol. 56, 798–817 (2007)
Semple, C., Steel, M.: A supertree method for rooted trees. Discrete Appl. Math. 105, 147–158 (2000)
Thorley, J., Wilkinson, M., Charleston, M.: The information content of consensus trees. In: Rizzi, A., Vichi, M., Bock, H.H. (eds.) Advances in Data Science and Classification. Studies in Classification, Data Analysis, and Knowledge Organization, pp. 91–98 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Scornavacca, C., Berry, V., Ranwez, V. (2009). From Gene Trees to Species Trees through a Supertree Approach. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2009. Lecture Notes in Computer Science, vol 5457. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00982-2_60
Download citation
DOI: https://doi.org/10.1007/978-3-642-00982-2_60
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00981-5
Online ISBN: 978-3-642-00982-2
eBook Packages: Computer ScienceComputer Science (R0)