Fast algorithms and heuristics for phylogenomics under ILS and hybridization
Identifieur interne : 000329 ( Pmc/Checkpoint ); précédent : 000328; suivant : 000330Fast algorithms and heuristics for phylogenomics under ILS and hybridization
Auteurs : Yun Yu [États-Unis] ; Nikola Ristic [États-Unis] ; Luay Nakhleh [États-Unis]Source :
- BMC Bioinformatics [ 1471-2105 ] ; 2013.
Abstract
Phylogenomic analyses involving whole-genome or multi-locus data often entail dealing with incongruent gene trees. In this paper, we consider two causes of such incongruence, namely, incomplete lineage sorting (ILS) and hybridization, and consider both parsimony and probabilistic criteria for dealing with them.
Under the assumption of ILS, computing the probability of a gene tree given a species tree is a very hard problem. We present a heuristic for speeding up the computation, and demonstrate how it scales up computations to data sizes that are not feasible to analyze using current techniques, while achieving very good accuracy. Further, under the assumption of both ILS and hybridization, computing the probability of a gene tree and parsimoniously reconciling it with a phylogenetic network are both very hard problems. We present two exact algorithms for these two problems that speed up existing techniques significantly and enable analyses of much larger data sets than is currently feasible.
Our heuristics and algorithms enable phylogenomic analyses of larger (in terms of numbers of taxa) data sets than is currently feasible. Further, our methods account for ILS and hybridization, thus allowing analyses of reticulate evolutionary histories.
Url:
DOI: 10.1186/1471-2105-14-S15-S6
PubMed: 24564257
PubMed Central: 3852049
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
PMC:3852049Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Fast algorithms and heuristics for phylogenomics under ILS and hybridization</title>
<author><name sortKey="Yu, Yun" sort="Yu, Yun" uniqKey="Yu Y" first="Yun" last="Yu">Yun Yu</name>
<affiliation wicri:level="2"><nlm:aff id="I1">Department of Computer Science, Rice University, Houston, TX, USA</nlm:aff>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science, Rice University, Houston, TX</wicri:regionArea>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Ristic, Nikola" sort="Ristic, Nikola" uniqKey="Ristic N" first="Nikola" last="Ristic">Nikola Ristic</name>
<affiliation wicri:level="2"><nlm:aff id="I1">Department of Computer Science, Rice University, Houston, TX, USA</nlm:aff>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science, Rice University, Houston, TX</wicri:regionArea>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Nakhleh, Luay" sort="Nakhleh, Luay" uniqKey="Nakhleh L" first="Luay" last="Nakhleh">Luay Nakhleh</name>
<affiliation wicri:level="2"><nlm:aff id="I1">Department of Computer Science, Rice University, Houston, TX, USA</nlm:aff>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science, Rice University, Houston, TX</wicri:regionArea>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">24564257</idno>
<idno type="pmc">3852049</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3852049</idno>
<idno type="RBID">PMC:3852049</idno>
<idno type="doi">10.1186/1471-2105-14-S15-S6</idno>
<date when="2013">2013</date>
<idno type="wicri:Area/Pmc/Corpus">000226</idno>
<idno type="wicri:Area/Pmc/Curation">000226</idno>
<idno type="wicri:Area/Pmc/Checkpoint">000329</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Fast algorithms and heuristics for phylogenomics under ILS and hybridization</title>
<author><name sortKey="Yu, Yun" sort="Yu, Yun" uniqKey="Yu Y" first="Yun" last="Yu">Yun Yu</name>
<affiliation wicri:level="2"><nlm:aff id="I1">Department of Computer Science, Rice University, Houston, TX, USA</nlm:aff>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science, Rice University, Houston, TX</wicri:regionArea>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Ristic, Nikola" sort="Ristic, Nikola" uniqKey="Ristic N" first="Nikola" last="Ristic">Nikola Ristic</name>
<affiliation wicri:level="2"><nlm:aff id="I1">Department of Computer Science, Rice University, Houston, TX, USA</nlm:aff>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science, Rice University, Houston, TX</wicri:regionArea>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Nakhleh, Luay" sort="Nakhleh, Luay" uniqKey="Nakhleh L" first="Luay" last="Nakhleh">Luay Nakhleh</name>
<affiliation wicri:level="2"><nlm:aff id="I1">Department of Computer Science, Rice University, Houston, TX, USA</nlm:aff>
<country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science, Rice University, Houston, TX</wicri:regionArea>
<placeName><region type="state">Texas</region>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2013">2013</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>Phylogenomic analyses involving whole-genome or multi-locus data often entail dealing with incongruent gene trees. In this paper, we consider two causes of such incongruence, namely, incomplete lineage sorting (ILS) and hybridization, and consider both parsimony and probabilistic criteria for dealing with them.</p>
</sec>
<sec><title>Results</title>
<p>Under the assumption of ILS, computing the probability of a gene tree given a species tree is a very hard problem. We present a heuristic for speeding up the computation, and demonstrate how it scales up computations to data sizes that are not feasible to analyze using current techniques, while achieving very good accuracy. Further, under the assumption of both ILS and hybridization, computing the probability of a gene tree and parsimoniously reconciling it with a phylogenetic network are both very hard problems. We present two exact algorithms for these two problems that speed up existing techniques significantly and enable analyses of much larger data sets than is currently feasible.</p>
</sec>
<sec><title>Conclusion</title>
<p>Our heuristics and algorithms enable phylogenomic analyses of larger (in terms of numbers of taxa) data sets than is currently feasible. Further, our methods account for ILS and hybridization, thus allowing analyses of reticulate evolutionary histories.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Maddison, Wp" uniqKey="Maddison W">WP Maddison</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Syring, J" uniqKey="Syring J">J Syring</name>
</author>
<author><name sortKey="Willyard, A" uniqKey="Willyard A">A Willyard</name>
</author>
<author><name sortKey="Cronn, R" uniqKey="Cronn R">R Cronn</name>
</author>
<author><name sortKey="Liston, A" uniqKey="Liston A">A Liston</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pollard, Da" uniqKey="Pollard D">DA Pollard</name>
</author>
<author><name sortKey="Iyer, Vn" uniqKey="Iyer V">VN Iyer</name>
</author>
<author><name sortKey="Moses, Am" uniqKey="Moses A">AM Moses</name>
</author>
<author><name sortKey="Eisen, Mb" uniqKey="Eisen M">MB Eisen</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Than, C" uniqKey="Than C">C Than</name>
</author>
<author><name sortKey="Sugino, R" uniqKey="Sugino R">R Sugino</name>
</author>
<author><name sortKey="Innan, H" uniqKey="Innan H">H Innan</name>
</author>
<author><name sortKey="Nakhleh, L" uniqKey="Nakhleh L">L Nakhleh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kuo, Ch" uniqKey="Kuo C">CH Kuo</name>
</author>
<author><name sortKey="Wares, Jp" uniqKey="Wares J">JP Wares</name>
</author>
<author><name sortKey="Kissinger, Jc" uniqKey="Kissinger J">JC Kissinger</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Cranston, Ka" uniqKey="Cranston K">KA Cranston</name>
</author>
<author><name sortKey="Hurwitz, B" uniqKey="Hurwitz B">B Hurwitz</name>
</author>
<author><name sortKey="Ware, D" uniqKey="Ware D">D Ware</name>
</author>
<author><name sortKey="Stein, L" uniqKey="Stein L">L Stein</name>
</author>
<author><name sortKey="Wing, Ra" uniqKey="Wing R">RA Wing</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="White, M" uniqKey="White M">M White</name>
</author>
<author><name sortKey="Ane, C" uniqKey="Ane C">C Ane</name>
</author>
<author><name sortKey="Dewey, C" uniqKey="Dewey C">C Dewey</name>
</author>
<author><name sortKey="Larget, B" uniqKey="Larget B">B Larget</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hobolth, A" uniqKey="Hobolth A">A Hobolth</name>
</author>
<author><name sortKey="Dutheil, J" uniqKey="Dutheil J">J Dutheil</name>
</author>
<author><name sortKey="Hawks, J" uniqKey="Hawks J">J Hawks</name>
</author>
<author><name sortKey="Schierup, M" uniqKey="Schierup M">M Schierup</name>
</author>
<author><name sortKey="Mailund, T" uniqKey="Mailund T">T Mailund</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Takuno, S" uniqKey="Takuno S">S Takuno</name>
</author>
<author><name sortKey="Kado, T" uniqKey="Kado T">T Kado</name>
</author>
<author><name sortKey="Sugino, Rp" uniqKey="Sugino R">RP Sugino</name>
</author>
<author><name sortKey="Nakhleh, L" uniqKey="Nakhleh L">L Nakhleh</name>
</author>
<author><name sortKey="Innan, H" uniqKey="Innan H">H Innan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Degnan, J" uniqKey="Degnan J">J Degnan</name>
</author>
<author><name sortKey="Salter, L" uniqKey="Salter L">L Salter</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Wu, Y" uniqKey="Wu Y">Y Wu</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Staubach, F" uniqKey="Staubach F">F Staubach</name>
</author>
<author><name sortKey="Lorenc, A" uniqKey="Lorenc A">A Lorenc</name>
</author>
<author><name sortKey="Messer, P" uniqKey="Messer P">P Messer</name>
</author>
<author><name sortKey="Tang, K" uniqKey="Tang K">K Tang</name>
</author>
<author><name sortKey="Petrov, D" uniqKey="Petrov D">D Petrov</name>
</author>
<author><name sortKey="Tautz, D" uniqKey="Tautz D">D Tautz</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Moody, M" uniqKey="Moody M">M Moody</name>
</author>
<author><name sortKey="Rieseberg, L" uniqKey="Rieseberg L">L Rieseberg</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Than, C" uniqKey="Than C">C Than</name>
</author>
<author><name sortKey="Ruths, D" uniqKey="Ruths D">D Ruths</name>
</author>
<author><name sortKey="Innan, H" uniqKey="Innan H">H Innan</name>
</author>
<author><name sortKey="Nakhleh, L" uniqKey="Nakhleh L">L Nakhleh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Meng, C" uniqKey="Meng C">C Meng</name>
</author>
<author><name sortKey="Kubatko, Ls" uniqKey="Kubatko L">LS Kubatko</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kubatko, Ls" uniqKey="Kubatko L">LS Kubatko</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Joly, S" uniqKey="Joly S">S Joly</name>
</author>
<author><name sortKey="Mclenachan, Pa" uniqKey="Mclenachan P">PA McLenachan</name>
</author>
<author><name sortKey="Lockhart, Pj" uniqKey="Lockhart P">PJ Lockhart</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Yu, Y" uniqKey="Yu Y">Y Yu</name>
</author>
<author><name sortKey="Than, C" uniqKey="Than C">C Than</name>
</author>
<author><name sortKey="Degnan, J" uniqKey="Degnan J">J Degnan</name>
</author>
<author><name sortKey="Nakhleh, L" uniqKey="Nakhleh L">L Nakhleh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Jones, G" uniqKey="Jones G">G Jones</name>
</author>
<author><name sortKey="Sagitov, S" uniqKey="Sagitov S">S Sagitov</name>
</author>
<author><name sortKey="Oxelman, B" uniqKey="Oxelman B">B Oxelman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Yu, Y" uniqKey="Yu Y">Y Yu</name>
</author>
<author><name sortKey="Barnett, R" uniqKey="Barnett R">R Barnett</name>
</author>
<author><name sortKey="Nakhleh, L" uniqKey="Nakhleh L">L Nakhleh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Yu, Y" uniqKey="Yu Y">Y Yu</name>
</author>
<author><name sortKey="Degnan, J" uniqKey="Degnan J">J Degnan</name>
</author>
<author><name sortKey="Nakhleh, L" uniqKey="Nakhleh L">L Nakhleh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Than, C" uniqKey="Than C">C Than</name>
</author>
<author><name sortKey="Ruths, D" uniqKey="Ruths D">D Ruths</name>
</author>
<author><name sortKey="Nakhleh, L" uniqKey="Nakhleh L">L Nakhleh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Nakhleh, L" uniqKey="Nakhleh L">L Nakhleh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Tavare, S" uniqKey="Tavare S">S Tavaré</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Than, C" uniqKey="Than C">C Than</name>
</author>
<author><name sortKey="Nakhleh, L" uniqKey="Nakhleh L">L Nakhleh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Doyon, Jp" uniqKey="Doyon J">JP Doyon</name>
</author>
<author><name sortKey="Hamel, S" uniqKey="Hamel S">S Hamel</name>
</author>
<author><name sortKey="Chauve, C" uniqKey="Chauve C">C Chauve</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Rambaut, A" uniqKey="Rambaut A">A Rambaut</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Robinson, D" uniqKey="Robinson D">D Robinson</name>
</author>
<author><name sortKey="Foulds, L" uniqKey="Foulds L">L Foulds</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hudson, Rr" uniqKey="Hudson R">RR Hudson</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<pmc article-type="abstract" xml:lang="en"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">BMC Bioinformatics</journal-id>
<journal-id journal-id-type="iso-abbrev">BMC Bioinformatics</journal-id>
<journal-title-group><journal-title>BMC Bioinformatics</journal-title>
</journal-title-group>
<issn pub-type="epub">1471-2105</issn>
<publisher><publisher-name>BioMed Central</publisher-name>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">24564257</article-id>
<article-id pub-id-type="pmc">3852049</article-id>
<article-id pub-id-type="publisher-id">1471-2105-14-S15-S6</article-id>
<article-id pub-id-type="doi">10.1186/1471-2105-14-S15-S6</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Proceedings</subject>
</subj-group>
</article-categories>
<title-group><article-title>Fast algorithms and heuristics for phylogenomics under ILS and hybridization</article-title>
</title-group>
<contrib-group><contrib contrib-type="author" corresp="yes" id="A1"><name><surname>Yu</surname>
<given-names>Yun</given-names>
</name>
<xref ref-type="aff" rid="I1">1</xref>
<email>yy9@rice.edu</email>
</contrib>
<contrib contrib-type="author" corresp="yes" id="A2"><name><surname>Ristic</surname>
<given-names>Nikola</given-names>
</name>
<xref ref-type="aff" rid="I1">1</xref>
<email>nr10@rice.edu</email>
</contrib>
<contrib contrib-type="author" corresp="yes" id="A3"><name><surname>Nakhleh</surname>
<given-names>Luay</given-names>
</name>
<xref ref-type="aff" rid="I1">1</xref>
<email>nakhleh@rice.edu</email>
</contrib>
</contrib-group>
<aff id="I1"><label>1</label>
Department of Computer Science, Rice University, Houston, TX, USA</aff>
<pub-date pub-type="collection"><year>2013</year>
</pub-date>
<pub-date pub-type="epub"><day>15</day>
<month>10</month>
<year>2013</year>
</pub-date>
<volume>14</volume>
<issue>Suppl 15</issue>
<supplement><named-content content-type="supplement-title">Proceedings of the Eleventh Annual Research in Computational Molecular Biology (RECOMB) Satellite Workshop on Comparative Genomics</named-content>
<named-content content-type="supplement-editor">Macha Nikolski and Yves Van de Peer</named-content>
<named-content content-type="supplement-sponsor">Publication of this supplement has not been supported by sponsorship. Information about the source of funding for publication charges can be found in the individual articles. Articles have undergone the journal's standard peer revire process for supplements. The Supplement Editors declare that they have no competing interests.</named-content>
</supplement>
<fpage>S6</fpage>
<lpage>S6</lpage>
<permissions><copyright-statement>Copyright © 2013 Yu et al.; licensee BioMed Central Ltd.</copyright-statement>
<copyright-year>2013</copyright-year>
<copyright-holder>Yu et al.; licensee BioMed Central Ltd.</copyright-holder>
<license license-type="open-access" xlink:href="http://creativecommons.org/licenses/by/2.0"><license-p>This is an open access article distributed under the terms of the Creative Commons Attribution License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/2.0">http://creativecommons.org/licenses/by/2.0</ext-link>
), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</license-p>
</license>
</permissions>
<self-uri xlink:href="http://www.biomedcentral.com/1471-2105/14/S15/S6"></self-uri>
<abstract><sec><title>Background</title>
<p>Phylogenomic analyses involving whole-genome or multi-locus data often entail dealing with incongruent gene trees. In this paper, we consider two causes of such incongruence, namely, incomplete lineage sorting (ILS) and hybridization, and consider both parsimony and probabilistic criteria for dealing with them.</p>
</sec>
<sec><title>Results</title>
<p>Under the assumption of ILS, computing the probability of a gene tree given a species tree is a very hard problem. We present a heuristic for speeding up the computation, and demonstrate how it scales up computations to data sizes that are not feasible to analyze using current techniques, while achieving very good accuracy. Further, under the assumption of both ILS and hybridization, computing the probability of a gene tree and parsimoniously reconciling it with a phylogenetic network are both very hard problems. We present two exact algorithms for these two problems that speed up existing techniques significantly and enable analyses of much larger data sets than is currently feasible.</p>
</sec>
<sec><title>Conclusion</title>
<p>Our heuristics and algorithms enable phylogenomic analyses of larger (in terms of numbers of taxa) data sets than is currently feasible. Further, our methods account for ILS and hybridization, thus allowing analyses of reticulate evolutionary histories.</p>
</sec>
</abstract>
<conference><conf-date>17-19 October 2013</conf-date>
<conf-name>Eleventh Annual Research in Computational Molecular Biology (RECOMB) Satellite Workshop on Comparative Genomics</conf-name>
<conf-loc>Lyon, France</conf-loc>
</conference>
</article-meta>
</front>
</pmc>
<affiliations><list><country><li>États-Unis</li>
</country>
<region><li>Texas</li>
</region>
</list>
<tree><country name="États-Unis"><region name="Texas"><name sortKey="Yu, Yun" sort="Yu, Yun" uniqKey="Yu Y" first="Yun" last="Yu">Yun Yu</name>
</region>
<name sortKey="Nakhleh, Luay" sort="Nakhleh, Luay" uniqKey="Nakhleh L" first="Luay" last="Nakhleh">Luay Nakhleh</name>
<name sortKey="Ristic, Nikola" sort="Ristic, Nikola" uniqKey="Ristic N" first="Nikola" last="Ristic">Nikola Ristic</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/CyberinfraV1/Data/Pmc/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000329 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Checkpoint/biblio.hfd -nk 000329 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Ticri/CIDE |area= CyberinfraV1 |flux= Pmc |étape= Checkpoint |type= RBID |clé= PMC:3852049 |texte= Fast algorithms and heuristics for phylogenomics under ILS and hybridization }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Checkpoint/RBID.i -Sk "pubmed:24564257" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Checkpoint/biblio.hfd \ | NlmPubMed2Wicri -a CyberinfraV1
![]() | This area was generated with Dilib version V0.6.25. | ![]() |