Show simple item record

dc.contributor.author
Stadler, Tanja
dc.contributor.author
Degnan, James H.
dc.date.accessioned
2019-03-12T09:31:33Z
dc.date.available
2017-06-10T12:00:47Z
dc.date.available
2019-03-12T09:31:33Z
dc.date.issued
2012
dc.identifier.issn
1748-7188
dc.identifier.other
10.1186/1748-7188-7-7
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/60175
dc.identifier.doi
10.3929/ethz-b-000060175
dc.description.abstract
Background The ancestries of genes form gene trees which do not necessarily have the same topology as the species tree due to incomplete lineage sorting. Available algorithms determining the probability of a gene tree given a species tree require exponential computational runtime. Results In this paper, we provide a polynomial time algorithm to calculate the probability of a ranked gene tree topology for a given species tree, where a ranked tree topology is a tree topology with the internal vertices being ordered. The probability of a gene tree topology can thus be calculated in polynomial time if the number of orderings of the internal vertices is a polynomial number. However, the complexity of calculating the probability of a gene tree topology with an exponential number of rankings for a given species tree remains unknown. Conclusions Polynomial algorithms for calculating ranked gene tree probabilities may become useful in developing methodology to infer species trees based on a collection of gene trees, leading to a more accurate reconstruction of ancestral species relationships.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
BioMed Central
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/2.0/
dc.subject
Incomplete lineage sorting
en_US
dc.subject
Coalescent history
en_US
dc.subject
Anomalous gene trees
en_US
dc.subject
Dynamic programming
en_US
dc.title
A polynomial time algorithm for calculating the probability of a ranked gene tree given a species tree
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution 2.0 Generic
dc.date.published
2012-04-30
ethz.journal.title
Algorithms for Molecular Biology
ethz.journal.volume
7
en_US
ethz.journal.abbreviated
Algorithms Mol Biol
ethz.pages.start
7
en_US
ethz.size
9 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.identifier.scopus
ethz.publication.place
London
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02060 - Dep. Biosysteme / Dep. of Biosystems Science and Eng.::09490 - Stadler, Tanja / Stadler, Tanja
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02350 - Dep. Umweltsystemwissenschaften / Dep. of Environmental Systems Science::02720 - Institut für Integrative Biologie / Institute of Integrative Biology::03584 - Bonhoeffer, Sebastian / Bonhoeffer, Sebastian
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02060 - Dep. Biosysteme / Dep. of Biosystems Science and Eng.::09490 - Stadler, Tanja / Stadler, Tanja
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02350 - Dep. Umweltsystemwissenschaften / Dep. of Environmental Systems Science::02720 - Institut für Integrative Biologie / Institute of Integrative Biology::03584 - Bonhoeffer, Sebastian / Bonhoeffer, Sebastian
ethz.date.deposited
2017-06-10T12:01:23Z
ethz.source
ECIT
ethz.identifier.importid
imp5936501dc672425528
ethz.ecitpid
pub:96189
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-13T08:28:49Z
ethz.rosetta.lastUpdated
2020-02-15T17:41:35Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=A%20polynomial%20time%20algorithm%20for%20calculating%20the%20probability%20of%20a%20ranked%20gene%20tree%20given%20a%20species%20tree&rft.jtitle=Algorithms%20for%20Molecular%20Biology&rft.date=2012&rft.volume=7&rft.spage=7&rft.issn=1748-7188&rft.au=Stadler,%20Tanja&Degnan,%20James%20H.&rft.genre=article&rft_id=info:doi/10.1186/1748-7188-7-7&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record