An analytical upper bound on the number of loci required for all splits of a species tree to appear in a set of gene trees

Lawrence H. Uricchio, Tandy Warnow, Noah A. Rosenberg

Research output: Contribution to journalArticle

Abstract

Background: Many methods for species tree inference require data from a sufficiently large sample of genomic loci in order to produce accurate estimates. However, few studies have attempted to use analytical theory to quantify "sufficiently large". Results: Using the multispecies coalescent model, we report a general analytical upper bound on the number of gene trees n required such that with probability q, each bipartition of a species tree is represented at least once in a set of n random gene trees. This bound employs a formula that is straightforward to compute, depends only on the minimum internal branch length of the species tree and the number of taxa, and applies irrespective of the species tree topology. Using simulations, we investigate numerical properties of the bound as well as its accuracy under the multispecies coalescent. Conclusions: Our results are helpful for conservatively bounding the number of gene trees required by the ASTRAL inference method, and the approach has potential to be extended to bound other properties of gene tree sets under the model.

Original languageEnglish (US)
Article number417
JournalBMC bioinformatics
Volume17
DOIs
StatePublished - Nov 11 2016

Fingerprint

Locus
Genes
Upper bound
Gene
Topology
Genomics
Quantify
Branch
Internal
Model
Estimate
Simulation

Keywords

  • Bipartitions
  • Coalescent
  • Gene trees
  • Species trees

ASJC Scopus subject areas

  • Structural Biology
  • Biochemistry
  • Molecular Biology
  • Computer Science Applications
  • Applied Mathematics

Cite this

An analytical upper bound on the number of loci required for all splits of a species tree to appear in a set of gene trees. / Uricchio, Lawrence H.; Warnow, Tandy; Rosenberg, Noah A.

In: BMC bioinformatics, Vol. 17, 417, 11.11.2016.

Research output: Contribution to journalArticle

@article{07aa8849ef254fccb056c2d57bc48aeb,
title = "An analytical upper bound on the number of loci required for all splits of a species tree to appear in a set of gene trees",
abstract = "Background: Many methods for species tree inference require data from a sufficiently large sample of genomic loci in order to produce accurate estimates. However, few studies have attempted to use analytical theory to quantify {"}sufficiently large{"}. Results: Using the multispecies coalescent model, we report a general analytical upper bound on the number of gene trees n required such that with probability q, each bipartition of a species tree is represented at least once in a set of n random gene trees. This bound employs a formula that is straightforward to compute, depends only on the minimum internal branch length of the species tree and the number of taxa, and applies irrespective of the species tree topology. Using simulations, we investigate numerical properties of the bound as well as its accuracy under the multispecies coalescent. Conclusions: Our results are helpful for conservatively bounding the number of gene trees required by the ASTRAL inference method, and the approach has potential to be extended to bound other properties of gene tree sets under the model.",
keywords = "Bipartitions, Coalescent, Gene trees, Species trees",
author = "Uricchio, {Lawrence H.} and Tandy Warnow and Rosenberg, {Noah A.}",
year = "2016",
month = "11",
day = "11",
doi = "10.1186/s12859-016-1266-4",
language = "English (US)",
volume = "17",
journal = "BMC Bioinformatics",
issn = "1471-2105",
publisher = "BioMed Central",

}

TY - JOUR

T1 - An analytical upper bound on the number of loci required for all splits of a species tree to appear in a set of gene trees

AU - Uricchio, Lawrence H.

AU - Warnow, Tandy

AU - Rosenberg, Noah A.

PY - 2016/11/11

Y1 - 2016/11/11

N2 - Background: Many methods for species tree inference require data from a sufficiently large sample of genomic loci in order to produce accurate estimates. However, few studies have attempted to use analytical theory to quantify "sufficiently large". Results: Using the multispecies coalescent model, we report a general analytical upper bound on the number of gene trees n required such that with probability q, each bipartition of a species tree is represented at least once in a set of n random gene trees. This bound employs a formula that is straightforward to compute, depends only on the minimum internal branch length of the species tree and the number of taxa, and applies irrespective of the species tree topology. Using simulations, we investigate numerical properties of the bound as well as its accuracy under the multispecies coalescent. Conclusions: Our results are helpful for conservatively bounding the number of gene trees required by the ASTRAL inference method, and the approach has potential to be extended to bound other properties of gene tree sets under the model.

AB - Background: Many methods for species tree inference require data from a sufficiently large sample of genomic loci in order to produce accurate estimates. However, few studies have attempted to use analytical theory to quantify "sufficiently large". Results: Using the multispecies coalescent model, we report a general analytical upper bound on the number of gene trees n required such that with probability q, each bipartition of a species tree is represented at least once in a set of n random gene trees. This bound employs a formula that is straightforward to compute, depends only on the minimum internal branch length of the species tree and the number of taxa, and applies irrespective of the species tree topology. Using simulations, we investigate numerical properties of the bound as well as its accuracy under the multispecies coalescent. Conclusions: Our results are helpful for conservatively bounding the number of gene trees required by the ASTRAL inference method, and the approach has potential to be extended to bound other properties of gene tree sets under the model.

KW - Bipartitions

KW - Coalescent

KW - Gene trees

KW - Species trees

UR - http://www.scopus.com/inward/record.url?scp=85002735939&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85002735939&partnerID=8YFLogxK

U2 - 10.1186/s12859-016-1266-4

DO - 10.1186/s12859-016-1266-4

M3 - Article

C2 - 28185570

AN - SCOPUS:85002735939

VL - 17

JO - BMC Bioinformatics

JF - BMC Bioinformatics

SN - 1471-2105

M1 - 417

ER -