Abstract
DNA-based species assignment and delimitation are two important problems in systematic biology. In a recent work of O’Meara, species delimitation is investigated through coupling it with species tree inference in the framework of gene tree and species tree reconciliation. We present a polynomial time algorithm for splitting individuals into species to minimize the deep coalescence cost of the gene tree and species tree reconciliation, a species assignment problem arises from species delimitation via gene tree and species tree reconciliation. How to incorporate this proposed algorithm into the heuristic search strategy of O’Meara for species delimitation is also discussed. The proposed algorithm is implemented in C++.
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
Agapow, P.M.: The impact of species concept on biodiversity studies. Q. Rev. Biol. 79, 161–179 (2004)
Bafna, V., Hannenhalli, S., Rice, K., Vawter, L.: Ligand-Receptor pairing via tree comparison. J. Comput. Biol. 7, 59–70 (2000)
Baum, D.A., Shaw, K.L.: Genealogical perspectives on the species problem. In: Hoch, P.C., Stephenson, A.C. (eds.) Experimental and molecular approaches to plant biosystematics, pp. 289–303. Missouri Botanical Garden, Saint Louis (1995)
Brockelman, W.Y., Gittins, S.P.: Natural hybridization in the Hylobates lar species group: implications for speciation in gibbons. In: Preushcoft, H., Chivers, D.J., Brockelman, W.Y., et al. (eds.) The Lesser Apes. Evolutionary and Behavioral Biology. Edinburgh University Press, Edinburgh (1984)
Burns, J.M., Janzen, D.H., Hajibabaei, M., Hallwachs, W., Hebert, P.D.: DNA barcodes and cryptic species of skipper butterflies in the genus Perichares in Area de Conservacion Guanacaste, Costa Rica. Proc. Nat’l. Acad. Sci. USA 105, 6350–6355 (2008)
De Queiroz, K.: Species concepts and species delimitation. Syst. Biol. 56, 879–886 (2007)
Degnan, J.H., Rosenberg, N.A.: Discordance of species trees with their most likely gene trees. PLoS Genet. 2, e68 (2006)
Doyle, J.J.: Gene trees and species trees: molecular systematics as one-character taxonomy. Syst. Bot. 17, 144–163 (1992)
Fitch, W.: Distinguishing homologous from analogous proteins. Syst. Zool. 19, 99–113 (1970)
Goodman, M., et al.: Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences. Syst. Zool. 28, 132–163 (1979)
Guigó, R., Muchnik, I., Smith, T.: Reconstruction of ancient molecular phylogeny. Mol. Phylogenet Evol. 6, 189–213 (1996)
Hebert, P.D.N., Cywinska, A., Ball, S.L., DeWaard, J.R.: Biological identification through DNA barcodes. Proc. R. Soc. B 270, 313–321 (2003)
Hebert, P.D.N., Gregory, T.R.: The promise of DNA barcoding for taxonomy. Syst. Biol. 54, 852–859 (2005)
Knowles, L.L., Carstens, B.C.: Delimiting species without monophyletic gene trees. Syst. Biol. 56, 887–895 (2007)
Leaché, A.D., et al.: Quantifying ecological, morphological, and genetic variation to delimit speceis in the coast horned lizard speceis complex (Phrynosoma). Proc. Nat’l Acad. Sci. USA 106, 12418–12423 (2009)
Leliaert, F., Verbruggen, H., Wysor, B., De Clerck, O.: DNA taxonomy in morphologically plastic taxa: algorithmic species delimitation in the Boodlea complex (Chlorophyta: Cladophorales). Mol. Phylogenet. Evol. 53, 122–133 (2009)
Libeskind-Hadas, R., Charleston, M.A.: On the computational complexity of the reticulate cophylogeny reconstruction problem. J. Comput. Biol. 16, 105–117 (2009)
Ma, B., Li, M., Zhang, L.X.: From gene trees to species trees. SIAM J. Comput. 30, 729–752 (2000)
Maddison, W.P.: Gene trees in species trees. Syst. Biol. 46, 523–536 (1997)
Mallet, J., Willmott, K.: Taxonomy: Renaissance or tower of babel? Trends Ecol. Evol. 18, 57–59 (2003)
Matz, M.V., Nielsen, R.: A likelihood ratio test for species membership based on DNA sequence data. Phil. Trans. R. Soc. B 360, 1969–1974 (2005)
Nielsen, R., Matz, M.: Statistical approaches for DNA barcoding. Syst. Biol. 55, 162–169 (2006)
O’Meara, B.C.: New heuristic methods for joint species delimitation and species tree inference. Syst. Biol. 59, 59–73 (2010)
Page, R.: Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas. Syst. Biol. 43, 58–77 (1994)
Pamilo, P., Nei, M.: Relationship between gene trees and species trees. Mol. Biol. Evol. 5, 568–583 (1988)
Petit, J.R., Excoffier, L.: Gene flow and species delimitation. Trends Ecol. Evol. 24, 386–393 (2009)
Pons, J., et al.: Sequence-based species delimitation for the DNA taxonomy of undescribed insects. Syst. Biol. 55, 595–609 (2006)
Ronquist, F.: Three-dimensional cost matrix optimisation and maximum cospeciation. Cladistics 14, 167–172 (1998)
Steinke, D., Vences, N., Salzburger, W., Meyer, A.: TaxI: a software tool for DNA barcoding using distance methods. Phil. Trans. R. Soc. B 360, 1975–1980 (2005)
Tautz, D., et al.: DNA points the way ahead in taxonomy. Nature 418, 479 (2002)
Will, K.W., Rubinoff, D.: Myth of the molecule: DNA barcodes for species cannot replace morphology for identification and classigication. Cladistics 20, 47–55 (2004)
Xu, S.: Phylogenetic analysis under reticulate evolution. Mol. Biol. Evol. 17, 897–907 (2000)
Zhang, L.X.: From gene trees to species trees II: Species tree inference in the deep coalescence model. Manuscript (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, L., Cui, Y. (2010). An Efficient Method for DNA-Based Species Assignment via Gene Tree and Species Tree Reconciliation. In: Moulton, V., Singh, M. (eds) Algorithms in Bioinformatics. WABI 2010. Lecture Notes in Computer Science(), vol 6293. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15294-8_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-15294-8_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15293-1
Online ISBN: 978-3-642-15294-8
eBook Packages: Computer ScienceComputer Science (R0)