{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:46Z","timestamp":1763468086966},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"S10","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>To infer a species phylogeny from unlinked genes, phylogenetic inference methods must confront the biological processes that create incongruence between gene trees and the species phylogeny. Intra-specific gene variation in ancestral species can result in deep coalescence, also known as incomplete lineage sorting, which creates incongruence between gene trees and the species tree. One approach to account for deep coalescence in phylogenetic analyses is the deep coalescence problem, which takes a collection of gene trees and seeks the species tree that implies the fewest deep coalescence events. Although this approach is promising for phylogenetics, the consensus properties of this problem are mostly unknown and analyses of large data sets may be computationally prohibitive.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We prove that the deep coalescence consensus tree problem satisfies the highly desirable Pareto property for clusters (clades). That is, in all instances, each cluster that is present in all of the input gene trees, called a consensus cluster, will also be found in every optimal solution. Moreover, we introduce a new divide and conquer method for the deep coalescence problem based on the Pareto property. This method refines the strict consensus of the input gene trees, thereby, in practice, often greatly reducing the complexity of the tree search and guaranteeing that the estimated species tree will satisfy the Pareto property.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>Analyses of both simulated and empirical data sets demonstrate that the divide and conquer method can greatly improve upon the speed of heuristics that do not consider the Pareto consensus property, while also guaranteeing that the proposed solution fulfills the Pareto property. The divide and conquer method extends the utility of the deep coalescence problem to data sets with enormous numbers of taxa.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-13-s10-s12","type":"journal-article","created":{"date-parts":[[2012,6,29]],"date-time":"2012-06-29T16:35:52Z","timestamp":1340987752000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Consensus properties for the deep coalescence problem and their application for scalable tree search"],"prefix":"10.1186","volume":"13","author":[{"given":"Harris T","family":"Lin","sequence":"first","affiliation":[]},{"given":"J Gordon","family":"Burleigh","sequence":"additional","affiliation":[]},{"given":"Oliver","family":"Eulenstein","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,6,25]]},"reference":[{"issue":"6960","key":"5217_CR1","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1038\/nature02053","volume":"425","author":"A Rokas","year":"2003","unstructured":"Rokas A, Williams BL, King N, Carroll SB: Genome-scale approaches to resolving incongruence in molecular phylogenies. Nature. 2003, 425 (6960): 798-804. 10.1038\/nature02053.","journal-title":"Nature"},{"issue":"10","key":"5217_CR2","doi-asserted-by":"publisher","first-page":"e173.","DOI":"10.1371\/journal.pgen.0020173","volume":"2","author":"DA Pollard","year":"2006","unstructured":"Pollard DA, Iyer VN, Moses AM, Eisen MB: Widespread Discordance of Gene Trees with Species Tree in Drosophila: Evidence for Incomplete Lineage Sorting. PLoS Genet. 2006, 2 (10): e173.-","journal-title":"PLoS Genet"},{"issue":"2","key":"5217_CR3","doi-asserted-by":"publisher","first-page":"132","DOI":"10.2307\/2412519","volume":"28","author":"M Goodman","year":"1979","unstructured":"Goodman M, Czelusniak J, Moore GW, Romero-Herrera AE, Matsuda G: Fitting the Gene Lineage into its Species Lineage, a Parsimony Strategy Illustrated by Cladograms Constructed from Globin Sequences. Systematic Zoology. 1979, 28 (2): 132-163. 10.2307\/2412519.","journal-title":"Systematic Zoology"},{"issue":"3","key":"5217_CR4","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1093\/sysbio\/46.3.523","volume":"46","author":"WP Maddison","year":"1997","unstructured":"Maddison WP: Gene Trees in Species Trees. Systematic Biology. 1997, 46 (3): 523-536. 10.1093\/sysbio\/46.3.523.","journal-title":"Systematic Biology"},{"issue":"7","key":"5217_CR5","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/S0169-5347(01)02203-0","volume":"16","author":"R Nichols","year":"2001","unstructured":"Nichols R: Gene trees and species trees are not the same. Trends in Ecology & Evolution. 2001, 16 (7): 358-364. 10.1016\/S0169-5347(01)02203-0.","journal-title":"Trends in Ecology & Evolution"},{"key":"5217_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1558-5646.2008.00549.x","volume":"63","author":"SV Edwards","year":"2009","unstructured":"Edwards SV: Is a new and general theory of molecular systematics emerging?. Evolution; International Journal of Organic Evolution. 2009, 63: 1-19. 10.1111\/j.1558-5646.2008.00549.x.","journal-title":"Evolution; International Journal of Organic Evolution"},{"issue":"5","key":"5217_CR7","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1093\/sysbio\/syp061","volume":"58","author":"LL Knowles","year":"2009","unstructured":"Knowles LL: Estimating Species Trees: Methods of Phylogenetic Analysis When There Is Incongruence across Genes. Systematic Biology. 2009, 58 (5): 463-467. 10.1093\/sysbio\/syp061.","journal-title":"Systematic Biology"},{"key":"5217_CR8","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/978-3-642-20036-6_47","volume-title":"Proceedings of the 15th Annual international conference on Research in computational molecular biology","author":"Y Yu","year":"2011","unstructured":"Yu Y, Warnow T, Nakhleh L: Algorithms for MDC-based multi-locus phylogeny inference. Proceedings of the 15th Annual international conference on Research in computational molecular biology. 2011, RECOMB, Berlin, Heidelberg: Springer-Verlag, 531-545."},{"key":"5217_CR9","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1080\/10635150500354928","volume":"55","author":"WP Maddison","year":"2006","unstructured":"Maddison WP, Knowles LL: Inferring Phylogeny Despite Incomplete Lineage Sorting. Systematic Biology. 2006, 55: 21-30. 10.1080\/10635150500354928.","journal-title":"Systematic Biology"},{"issue":"6","key":"5217_CR10","doi-asserted-by":"publisher","first-page":"1685","DOI":"10.1109\/TCBB.2011.83","volume":"8","author":"L Zhang","year":"2011","unstructured":"Zhang L: From gene trees to species trees II: Species tree inference in the deep coalescence model. IEEE\/ACM Trans Comput Biol Bioinformatics. 2011, 8 (6): 1685-1691.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinformatics"},{"issue":"9","key":"5217_CR11","doi-asserted-by":"publisher","first-page":"e1000501","DOI":"10.1371\/journal.pcbi.1000501","volume":"5","author":"C Than","year":"2009","unstructured":"Than C, Nakhleh L: Species Tree Inference by Minimizing Deep Coalescences. PLoS Computational Biology. 2009, 5 (9): e1000501-10.1371\/journal.pcbi.1000501.","journal-title":"PLoS Computational Biology"},{"key":"5217_CR12","unstructured":"Than C, Nakhleh L: Estimating species trees: Practical and Theoretical Aspects. Wiley-VCH, Chichester 2010 chap. Inference of parsimonious species tree phylogenies from multi-locus data by minimizing deep coalescences, 79-98."},{"issue":"Suppl 1","key":"5217_CR13","doi-asserted-by":"publisher","first-page":"S42","DOI":"10.1186\/1471-2105-11-S1-S42","volume":"11","author":"M Bansal","year":"2010","unstructured":"Bansal M, Burleigh JG, Eulenstein O: Efficient genome-scale phylogenetic analysis under the duplication-loss and deep coalescence cost models. BMC Bioinformatics. 2010, 11 (Suppl 1): S42-10.1186\/1471-2105-11-S1-S42.","journal-title":"BMC Bioinformatics"},{"key":"5217_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-2330-9","volume-title":"Phylogenetic supertrees: combining information to reveal the Tree of Life","author":"ORP Bininda-Emonds","year":"2004","unstructured":"Bininda-Emonds ORP: Phylogenetic supertrees: combining information to reveal the Tree of Life. 2004, Springer"},{"key":"5217_CR15","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1090\/dimacs\/061\/11","volume-title":"BioConsensus, DIMACS. AMS","author":"D Bryant","year":"2003","unstructured":"Bryant D: A classification of consensus methods for phylogenies. BioConsensus, DIMACS. AMS. 2003, 163-184."},{"issue":"2","key":"5217_CR16","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1080\/10635150701245370","volume":"56","author":"M Wilkinson","year":"2007","unstructured":"Wilkinson M, Cotton JA, Lapointe F, Pisani D: Properties of Supertree Methods in the Consensus Setting. Systematic Biology. 2007, 56 (2): 330-337. 10.1080\/10635150701245370.","journal-title":"Systematic Biology"},{"key":"5217_CR17","doi-asserted-by":"crossref","unstructured":"Wilkinson M, Thorley J, Pisani D, Lapointe FJ, McInerney J: Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life. Springer, Dordrecht, the Netherlands 2004 chap. Some desiderata for liberal supertrees, 227-246.","DOI":"10.1007\/978-1-4020-2330-9_11"},{"key":"5217_CR18","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-69024-2_18","volume-title":"Numerical Taxonomy","author":"FR McMorris","year":"1983","unstructured":"McMorris FR, Meronk DB, Neumann DA: A view of some consensus methods for trees. Numerical Taxonomy. 1983, 122-125."},{"issue":"2","key":"5217_CR19","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1093\/bioinformatics\/19.2.301","volume":"19","author":"MJ Sanderson","year":"2003","unstructured":"Sanderson MJ: r8s: inferring absolute rates of molecular evolution and divergence times in the absence of a molecular clock. Bioinformatics (Oxford, England). 2003, 19 (2): 301-302. 10.1093\/bioinformatics\/19.2.301.","journal-title":"Bioinformatics (Oxford, England)"},{"key":"5217_CR20","volume-title":"Mesquite: a modular system for evolutionary analysis","author":"WP Maddison","year":"2001","unstructured":"Maddison WP, Maddison D: Mesquite: a modular system for evolutionary analysis. 2001, [http:\/\/mesquiteproject.org]"},{"key":"5217_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/cmb.2010.0102","volume":"18","author":"CV Than","year":"2011","unstructured":"Than CV, Rosenberg NA: Consistency properties of species tree inference by minimizing deep coalescences. Journal of Computational Biology. 2011, 18: 1-15. 10.1089\/cmb.2010.0102.","journal-title":"Journal of Computational Biology"},{"issue":"21","key":"5217_CR22","doi-asserted-by":"publisher","first-page":"2542","DOI":"10.1093\/bioinformatics\/btn484","volume":"24","author":"L Liu","year":"2008","unstructured":"Liu L: BEST: Bayesian estimation of species trees under the coalescent model. Bioinformatics. 2008, 24 (21): 2542-2543. 10.1093\/bioinformatics\/btn484.","journal-title":"Bioinformatics"},{"issue":"7","key":"5217_CR23","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1093\/bioinformatics\/btp079","volume":"25","author":"LS Kubatko","year":"2009","unstructured":"Kubatko LS, Carstens BC, Knowles LL: STEM: species tree estimation using maximum likelihood for gene trees under coalescence. Bioinformatics. 2009, 25 (7): 971-973. 10.1093\/bioinformatics\/btp079.","journal-title":"Bioinformatics"},{"issue":"3","key":"5217_CR24","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1093\/molbev\/msp274","volume":"27","author":"J Heled","year":"2010","unstructured":"Heled J, Drummond AJ: Bayesian Inference of Species Trees from Multilocus Data. Molecular Biology and Evolution. 2010, 27 (3): 570-580. 10.1093\/molbev\/msp274.","journal-title":"Molecular Biology and Evolution"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-13-S10-S12.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T19:14:17Z","timestamp":1630523657000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-13-S10-S12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":24,"journal-issue":{"issue":"S10","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["5217"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-13-s10-s12","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6]]},"assertion":[{"value":"25 June 2012","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S12"}}